В январе этого года в «Сириусе» прошла смена для школьников. Организатор — факультет математики и компьютерных наук СПбГУ.

Программа состояла из трёх треков: «Математика», «Программирование» и «Computer Science». Курсы были разбавлены общеобразовательными лекциями и чаепитиями с преподавателями и организаторами. Среди преподавателей — учёные и преподаватели факультета МКН СПбГУ, БГУ, ВШЭ, МГУ, разработчики Яндекса и JetBrains, сотрудники ПОМИ РАН. О том, как была устроена смена, мы рассказали здесь, а сейчас выкладываем материалы части курсов.

image

Математика


1. Дискретная теория Морса


Преподаватели: Гаянэ Юрьевна Панина (СПбГУ, ПОМИ), Галина Пасс (Университет Тарту), Никита Калинин (СПбГУ, ВШЭ)

О курсе. Дискретная теория Морса — это рабочий инструмент во многих областях, симпатичная смесь комбинаторики и топологии. На курсе ребята переоткрыли этот метод в процессе решения задач. Началось всё с наглядных примеров: с теории Морса на двумерных поверхностях (сферах с ручками и плёнками), а затем перешли к более абстрактным конструкциям. Задачи были разбиты на проекты, которые можно было делать группами.

> Материалы

2. Почему теорему Ферма не доказали 300 лет назад?


Преподаватель: Иван Александрович Панин (ПОМИ)

О курсе. Великая теорема Ферма или последняя теорема Ферма — одна из самых популярных теорем математики. Её условие формулируется просто, на «школьном» арифметическом уровне, однако доказательство теоремы искали многие математики более трёхсот лет. Доказана в 1994 году Эндрю Уайлсом. Доказательство опубликовано в 1995 году, занимает порядка 100 страниц и использует сразу несколько разделов математики, созданных в 20 веке. На курсе было рассказано доказательство теоремы Ферма в случае, когда некоторое кольцо факториально. Доказательство доступно старшеклассникам и основано на классической теории чисел 19-го и начала 20-го века.

Почитать дополнительно: параграфы 1 и 7, раздел 3 из книги Боревич З.И., Шафаревич И. Р. «Теория чисел». Второе издание, издательство «Наука».

> Материалы

3. О методах подсчёта средних значений в аналитической теории чисел


Преподаватель: Алиса Седунова (СПбГУ)

image

image

> Материалы

4. Введение в теорию сумм произведений


Преподаватель: Илья Шкредов (МГУ, МИАН)

Пусть A — произвольное конечное множество целых чисел. Рассмотрим сумму и
произведение A с собой, а именно, множества

A+A := {c = a+b | a,b из A} и A·A := {c = a · b | a,b из A}.

Существуют множества с малой суммой, например, арифметические прогрессии:
если $P = 1, 2, . . . , n, то |P + P| = 2n ? 1$ (напомним, что |A| обозначает количество элементов множества A).

Аналогично, геометрическая прогрессия G = {2, 2?, ..., 2?} имеет малое произведение: |G · G| = 2n ? 1. Гипотеза сумм произведений утверждает, что не существует множеств, имеющих, одновременно, малую сумму и произведение, а именно, для произвольного для любого множества A выполнено, что либо A + A, либо A · A по размеру равно почти |A|? (точнее чуть меньше: |A|???). Неравенство выше до сих пор не доказано, но даже частичный прогресс в данной области уже привёл к существенному продвижению в задачах теории чисел, аддитивной комбинаторики, криптографии, теории динамических систем. Спецкурс представляет собой введение в эту замечательную часть математики.

Посмотреть дополнительно:

  • На странице лектора в файле Likbez содержится много вводных и не очень статей в аддитивную комбинаторику.
  • Видео на Постнауке
  • Обзоры «Суммы и произведения множеств и оценки рациональных тригонометрических сумм в полях простого порядка», «Теорема Семереди и задачи об арифметических прогрессиях».
  • Книга Тао-Ву «Additive combinatorics», Cambridge University Press 2006.

> Материалы

Программирование


1. Принципы программирования


Преподаватель: Виталий Брагилевский (JetBrains)

О курсе. Этот курс посвящён изучению и практике базовых принципов, которые лежат в основе современного промышленного программирования. В рамках курса лектор постарался сформировать отношение к программированию как виду профессиональной деятельности, направленному на создание качественного, поддерживаемого и производительного ПО. Для этого студенты изучили понятие и способы достижения качества ПО, обсудили приёмы тестирования программ, поговорили о различных стилях программирования и о том, как можно работать с данными, которые должны жить между запусками программы.

Основной язык программирования на курсе — Python, студенты также познакомились с несколькими другими (например, Rust). Это позволяет расширить программистский кругозор, а также понять, что возможности языка программирования существенно определяют то, что вообще может выразить программист с его помощью, какие задачи ему будет удобно решать, а с какими у него могут возникнуть некоторые сложности.

Почитать дополнительно: С. Макконнелл. Совершенный код. Мастер-класс. Русская редакция, 2019.

> Материалы

2. Функциональное программирование


Преподаватель: Денис Николаевич Москвин (СПбГУ, ВШЭ)

О курсе. Курс начался с обсуждения разных вычислительных моделей, студенты попробовали разобраться в том, как подстановочная модель вычислений позволяет программировать без инструкций, используя только выражения и объявления. Обсудили энергичный и ленивый подход к вычислениям, роль рекурсии в функциональных языках и способы обеспечения эффективной реализации рекурсивных функций. Познакомились с принципами построения систем типов функциональных языков, поговорим о том, почему их типы называют алгебраическими.

Увидели, как типы позволяют осуществлять контроль за тем, что делает программист, и удивились тому, насколько этот контроль ненавязчив и тотален одновременно. Язык программирования этого курса — Haskell. Студенты кратко обсудили его историю и сложившуюся к настоящему моменту инфраструктуру, познакомились с синтаксисом, не забывая о семантике, и написали некоторое количество программ: сначала совместно, а затем индивидуально.

Посмотреть дополнительно:


> Материалы

3. Работа в командной строке Unix


Преподаватель: Виталий Брагилевский (JetBrains)

О курсе. Эффективность использования компьютера при решении разнообразных задач существенно зависит от того, какой инструментарий используется. Многие предпочитают графические приложения и работают преимущественно мышкой (или трекпадом!). Программисты же чаще предпочитают клавиатуру и иногда вообще отказываются от графического интерфейса в пользу утилит командной строки и консольных текстовых редакторов.

В этом курсе студенты научились использовать командную строку в стиле UNIX, научились программировать в bash, а также применять десятки различных утилит, которые традиционно используются в UNIX-системах, таких как Linux и Mac OS X. Пользователи Windows 10 для тех же целей использовали WSL и Windows Terminal. И самое главное: мы научились выходить из редактора vi и узнали, чем редактор Emacs всё-таки лучше (или наоборот!).

> Материалы

4. Читаем и пишем на языке Kotlin


Преподаватель: Михаил Сенин (JetBrains)

image

О курсе. Kotlin — это современный язык программирования общего назначения, ? который разрабатывает компания JetBrains. Kotlin обладает свойствами, важными при промышленном программировании. Язык отличает лаконичность и хорошая поддержка IDE. В 2017 году Kotlin был выбран компанией Google в качестве языка для разработки мобильных приложений под Android. Язык удобен для разработки серверных, нативных и web-приложений.

В рамках курса мы изучили синтаксис языка и реализовали проект собственного мессенджера, включающий серверное приложение, web-клиент и приложение под Android. Работали в Intellij IDEA (Community Edition) и Android Studio.

Посмотреть дополнительно:

  • Книга «Kotlin в действии» Д. Жемерова
  • Документация и упражнения на kotlinlang.ru и kotlinlang.org
  • Курсы по Kotlin на Stepik и Coursera

> Материалы

Компьютерные науки


1. Поиск комбинаторных объектов при помощи ILP и SAT-солверов


Преподаватель: Александр Куликов (СПбГУ, CS центр, JetBrains)

О курсе. Студенты потренировались находить сложные комбинаторные объекты с помощью SAT-солверов, программ для решения задачи булевой выполнимости и ILP-солверов, программ для решения задачи целочисленного линейного программирования. Узнали, как формулируются эти две задачи и как многие практически важные задачи к ним сводятся. В частности, вместе реализовали программы для решения судоку, японских кроссвордов, нахождения латинских и греко-латинских квадратов. После этого перешли от головоломок к задачам, важным в индустрии: поиску эффективных булевых схем (познакомились с программой Кнута поиска схем и его гипотезой о сложности одной функции) и больших независимых множеств в графах.

Для практики понадобилось базовое знание языка программирования Pyhton3 (циклы, функции, ввод/вывод) и библиотеки pycosat и mip.

> Материалы

2. Анализ изображений и свёрточные сети


Преподаватели: Алексей Артамонов (Яндекс), Александр Авдюшенко (СПбГУ, CS центр, Яндекс)

О курсе. В современном мире регулярно происходят прорывы в области компьютерного зрения: выявление брака на производстве по изображению, распознавание и даже изменение лица человека, диагностика заболеваний на ранних стадиях по снимкам — каждый легко вспомнит очередную свежую новость из этой области. Cвёрточные нейросети на данный момент в компьютерном зрении — один из самых громких успехов машинного обучения. В этом курсе студенты учились:

  • Работать с изображениями с помощью Python.
  • Извлекать простые и сложные семантические признаки.
  • Конструировать свёрточные нейронные сети.
  • Запускать и тренировать их.

Посмотреть дополнительно:


> Материалы

3. Обучение с подкреплением


Преподаватели: Алексей Толстиков, Виктор Отлига (Яндекс, БГУ)

О курсе. Каждый день вы ищете что-нибудь в интернете с помощью одной из крупных поисковых систем, таких, например, как Яндекс или Google. Или смотрите сериалы через Кинопоиск, а он советует, какие ещё сериалы вам могут понравиться. А, может быть, вы слышали о том, что компьютер превзошёл человека в таких играх как го, Dota 2 и даже Starcraft 2? В основе всего этого лежит машинное обучение, с которым предлагается познакомиться в нашем курсе. Мы поговорим про классические алгоритмы и про более продвинутые — такие как нейронные сети и обучение с подкреплением.

На практических занятиях мы реализуем собственного бота для классической игры «Пакман». В основе принятия решений нашим игроком с искусственным интеллектом будет один из интереснейших разделов машинного обучения – обучение с подкреплением. В конце курса наши боты сразятся в турнире.

Посмотреть дополнительно:

  • Можно попрактиковаться в Open AI Gym.
  • Курс лекций по «Deep Reinforcement Learning» от компании Deep Mind, дочерней компании Google, занимающейся искусственным интеллектом.
  • Курс лекций «Reinforcement Learning» от David Silver.
  • Книга «Reinforcement Learning: An Introduction».

> Материалы

4. Рекомендательные системы


Преподаватель: Андрей Данильченко (Яндекс)

image

О курсе. Мы ежедневно сталкиваемся с огромным количеством информации: идут учебные проекты, друзья пишут в соцсетях, на Хабре выходят интересные статьи, появляются новые треки любимых музыкантов и новые фильмы, которые хочется посмотреть. Чтобы не утонуть в этом многообразии контента используются рекомендательные системы. Радио подбирает вам персональные треки, Дзен и соцсети ранжируют контент персонально. В этом курсе мы поговорили о том, как подобные системы работают «под капотом»: откуда берут данные, какие алгоритмы используют для отбора и ранжирования контента.

> Материалы

Список всех курсов смены с презентациями