Get best of the week

Materials from the shift for students in mathematics and programming in "Sirius"

In January of this year, a shift for schoolchildren took place at Sirius . Organizer - Faculty of Mathematics and Computer Science, St. Petersburg State University .

The program consisted of three tracks: "Mathematics", "Programming" and "Computer Science". The courses were diluted with general education lectures and tea parties with teachers and organizers. Among the teachers are scientists and teachers of the Faculty of Mathematics and Mathematics of St. Petersburg State University, BSU, Higher School of Economics, Moscow State University, Yandex and JetBrains developers, employees of POMI RAS. We talked about how the shift was arranged here , and now we are posting materials for part of the courses.

image

Mathematics


1. Discrete Morse Theory


Teachers: Gayane Panieva (St. Petersburg State University, POMI), Galina Pass (University of Tartu), Nikita Kalinin (St. Petersburg State University, Higher School of Economics)

About the course. The discrete Morse theory is a working tool in many areas, a nice mix of combinatorics and topology. On the course, the guys rediscovered this method in the process of solving problems. It all started with illustrative examples: with Morse theory on two-dimensional surfaces (spheres with handles and films), and then moved on to more abstract constructions. The tasks were divided into projects that could be done in groups.

→ Materials

2. Why was Fermat's theorem not proven 300 years ago?


Teacher: Ivan A. Panin (POMI)

About the course. The great Fermat's theorem or the last Fermat's theorem is one of the most popular theorems in mathematics. Its condition is formulated simply, at the "school" arithmetic level, however, many mathematicians have searched for the proof of the theorem for more than three hundred years. Proved in 1994 by Andrew Wiles. The proof was published in 1995, takes about 100 pages and uses several sections of mathematics created in the 20th century. On the course, a proof was given of Fermat's theorem in the case when some ring is factorial. The proof is accessible to high school students and is based on the classical number theory of the 19th and early 20th centuries.

Read more:paragraphs 1 and 7, section 3 of the book Borevich Z. I., Shafarevich I. R. "Theory of numbers." Second Edition, Nauka Publishing House.

→ Materials

3. On methods for calculating averages in analytical number theory


Lecturer: Alisa Sedunova (St. Petersburg State University)

image

image

→ Materials

4. Introduction to the theory of sums of products


Lecturer: Ilya Shkredov (Moscow State University, Steklov Mathematical Institute)

Let A be an arbitrary finite set of integers. Consider the sum and the
product of A with us, namely, the set

A + A: = {c = a + b | a, b from A} and A · A: = {c = a · b | a, b from A}.

There are sets with a small sum, for example, arithmetic progressions:
ifP=1,2,...,n,|P+P|=2n−1(recall that | A | denotes the number of elements of the set A).

Similarly, the geometric progression G = {2, 2², ..., 2ⁿ} has a small product: | G · G | = 2n - 1. The product sum hypothesis states that there are no sets that simultaneously have a small sum and a product, namely, for an arbitrary set A that either A + A or A · A is almost equal in size | A | ² (more precisely a little less: | A | ²⁻ᵋ). The inequality above has not yet been proved, but even partial progress in this area has already led to significant progress in problems of number theory, additive combinatorics, cryptography, and the theory of dynamical systems. The special course is an introduction to this wonderful part of mathematics.

View more:

  • The lecturer's page in the Likbez file contains many introductory and not very articles on additive combinatorics.
  • Post-Science Video
  • Surveys “Sums and products of sets and estimates of rational trigonometric sums in fields of simple order”, “Semeredi theorem and problems on arithmetic progressions”.
  • Tao Wu's book Additive combinatorics, Cambridge University Press 2006.

→ Materials

Programming


1. The principles of programming


Teacher: Vitaliy Bragilevsky (JetBrains)

About the course. This course is devoted to the study and practice of the basic principles that underlie modern industrial programming. As part of the course, the lecturer tried to formulate an attitude towards programming as a type of professional activity aimed at creating high-quality, supported and productive software. To do this, students studied the concept and ways to achieve software quality, discussed methods of testing programs, talked about different styles of programming and how to work with data that should live between program launches.

The main programming language of the course is Python, students also got acquainted with several others (for example, Rust). This allows you to expand your programmer's horizons, and also to understand that the capabilities of a programming language substantially determine what a programmer can express with his help, what tasks he will be comfortable with, and with which he may have some difficulties.

Read more: S. McConnell. Perfect code. Master Class. Russian edition, 2019.

→ Materials

2. Functional programming


Lecturer: Denis Nikolaevich Moskvin (St. Petersburg State University, Higher School of Economics)

About the course. The course began with a discussion of different computational models, students tried to figure out how a substitution model of calculations allows you to program without instructions, using only expressions and declarations. They discussed an energetic and lazy approach to computing, the role of recursion in functional languages ​​and ways to ensure the effective implementation of recursive functions. We got acquainted with the principles of constructing systems of types of functional languages, let's talk about why their types are called algebraic.

They saw how types allow you to exercise control over what the programmer does, and were surprised how this control is unobtrusive and total at the same time. The programming language for this course is Haskell. Students briefly discussed its history and the infrastructure that has been developed to date, got acquainted with the syntax, not forgetting the semantics, and wrote a number of programs: first together, and then individually.

View more:


→ Materials

3. Work on the Unix command line


Teacher: Vitaliy Bragilevsky (JetBrains)

About the course. The effectiveness of using a computer to solve a variety of tasks significantly depends on what tools are used. Many people prefer graphical applications and work mainly with the mouse (or trackpad!). Programmers, on the other hand, prefer the keyboard more often and sometimes refuse the graphical interface in favor of command-line utilities and console text editors.

In this course, students learned how to use the UNIX-style command line, learned how to program in bash, and also used dozens of different utilities that are traditionally used on UNIX systems such as Linux and Mac OS X. Windows 10 users used WSL and Windows Terminal And most importantly: we learned to exit the vi editor and found out why the Emacs editor is still better (or vice versa!).

→ Materials

4. Read and write in the Kotlin language


Teacher : Mikhail Senin (JetBrains)

image

About the course. Kotlin is a modern, general-purpose programming language developed by JetBrains. Kotlin has features that are important in industrial programming. The language is concise and has good IDE support. In 2017, Kotlin was chosen by Google as the language for developing mobile applications for Android. The language is convenient for developing server, native and web applications.

As part of the course, we studied the syntax of the language and implemented a project of our own messenger, including a server application, a web client and an Android application. Worked at Intellij IDEA (Community Edition) and Android Studio.

View more:

  • The book "Kotlin in action" D. Zhemerova
  • Documentation and exercises at kotlinlang.ru and kotlinlang.org
  • Kotlin courses at Stepik and Coursera

→ Materials

Computer science


1. Search for combinatorial objects using ILP and SAT solvers


Lecturer: Alexander Kulikov (St. Petersburg State University, CS Center, JetBrains)

About the course. Students trained to find complex combinatorial objects using SAT solvers, programs for solving the Boolean satisfiability problem and ILP solvers, programs for solving the integer linear programming problem. We learned how these two tasks are formulated and how many practically important tasks are reduced to them. In particular, they jointly implemented programs for solving Sudoku, Japanese crosswords, and finding Latin and Greek-Latin squares. After that, we switched from puzzles to tasks important in the industry: to search for effective Boolean circuits (we got acquainted with Knuth's program for searching circuits and his hypothesis about the complexity of one function) and large independent sets in graphs.

For practice, I needed basic knowledge of the Pyhton3 programming language (loops, functions, I / O) and the pycosat and mip libraries.

→ Materials

2. Image analysis and convolutional networks


Teachers: Alexey Artamonov (Yandex), Alexander Avdyushenko (St. Petersburg State University, CS Center, Yandex)

About the course. Breakthroughs in the field of computer vision regularly occur in the modern world: detecting marriage in production by image, recognizing and even changing a person’s face, diagnosing diseases in the early stages from photographs - everyone will easily remember the latest fresh news from this area. Convolutional neural networks at the moment in computer vision are one of the biggest successes in machine learning. In this course, students studied:

  • Work with images using Python.
  • Extract simple and complex semantic attributes.
  • Design convolutional neural networks.
  • Run and train them.

View more:


→ Materials

3. Reinforcement training


Teachers: Alexey Tolstikov, Victor Otliga (Yandex, BSU)

About the course. Every day you are looking for something on the Internet using one of the major search engines, such as, for example, Yandex or Google. Or watch the series through Kinopoisk, and he advises what other series you might like. Or maybe you've heard that the computer has surpassed humans in games like go, Dota 2, and even Starcraft 2? The basis of all this is machine learning, which is proposed to meet in our course. We’ll talk about classic algorithms and more advanced ones such as neural networks and reinforcement learning.

In practical classes, we implement our own bot for the classic Pakman game. Our decision-maker with artificial intelligence will be based on one of the most interesting sections of machine learning - reinforcement learning. At the end of the course, our bots will fight in the tournament.

View more:

  • You can practice with Open AI Gym.
  • Lecture course on Deep Reinforcement Learning from Deep Mind, a Google-based subsidiary of artificial intelligence.
  • Lecture Course “Reinforcement Learning” by David Silver.
  • The book "Reinforcement Learning: An Introduction".

→ Materials

4. Recommender systems


Lecturer: Andrey Danilchenko (Yandex)

image

About the course. Every day we are faced with a huge amount of information: educational projects are underway, friends write on social networks, interesting articles are published on Habré, new tracks of favorite musicians and new films that you want to watch appear. In order not to drown in this variety of content, recommendation systems are used. Radio picks up your personal tracks, Zen and social networks rank the content personally. In this course, we talked about how such systems work “under the hood”: where does the data come from, what algorithms are used to select and rank content.

→ Materials

List of all shift courses with presentations

More articles:


All Articles