Материалы со смены для школьников по математике и программированию в «Сириусе»
В январе этого года в «Сириусе» прошла смена для школьников. Организатор — факультет математики и компьютерных наук СПбГУ.
Программа состояла из трёх треков: «Математика», «Программирование» и «Computer Science». Курсы были разбавлены общеобразовательными лекциями и чаепитиями с преподавателями и организаторами. Среди преподавателей — учёные и преподаватели факультета МКН СПбГУ, БГУ, ВШЭ, МГУ, разработчики Яндекса и JetBrains, сотрудники ПОМИ РАН. О том, как была устроена смена, мы рассказали здесь, а сейчас выкладываем материалы части курсов.
Математика
1. Дискретная теория Морса
Преподаватели: Гаянэ Юрьевна Панина (СПбГУ, ПОМИ), Галина Пасс (Университет Тарту), Никита Калинин (СПбГУ, ВШЭ)
О курсе. Дискретная теория Морса — это рабочий инструмент во многих областях, симпатичная смесь комбинаторики и топологии. На курсе ребята переоткрыли этот метод в процессе решения задач. Началось всё с наглядных примеров: с теории Морса на двумерных поверхностях (сферах с ручками и плёнками), а затем перешли к более абстрактным конструкциям. Задачи были разбиты на проекты, которые можно было делать группами.
Материалы
2. Почему теорему Ферма не доказали 300 лет назад?
Преподаватель: Иван Александрович Панин (ПОМИ)
О курсе. Великая теорема Ферма или последняя теорема Ферма — одна из самых популярных теорем математики. Её условие формулируется просто, на «школьном» арифметическом уровне, однако доказательство теоремы искали многие математики более трёхсот лет. Доказана в 1994 году Эндрю Уайлсом. Доказательство опубликовано в 1995 году, занимает порядка 100 страниц и использует сразу несколько разделов математики, созданных в 20 веке. На курсе было рассказано доказательство теоремы Ферма в случае, когда некоторое кольцо факториально. Доказательство доступно старшеклассникам и основано на классической теории чисел 19-го и начала 20-го века.
Почитать дополнительно: параграфы 1 и 7, раздел 3 из книги Боревич З.И., Шафаревич И. Р. «Теория чисел». Второе издание, издательство «Наука».
Материалы
3. О методах подсчёта средних значений в аналитической теории чисел
Преподаватель: Алиса Седунова (СПбГУ)
Материалы
4. Введение в теорию сумм произведений
Преподаватель: Илья Шкредов (МГУ, МИАН)
Пусть A — произвольное конечное множество целых чисел. Рассмотрим сумму и
произведение A с собой, а именно, множества
A+A:= {c = a+b | a, b из A} и A·A:= {c = a · b | a, b из A}.
Существуют множества с малой суммой, например, арифметические прогрессии:
если 
(напомним, что |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. Студенты кратко обсудили его историю и сложившуюся к настоящему моменту инфраструктуру, познакомились с синтаксисом, не забывая о семантике, и написали некоторое количество программ: сначала совместно, а затем индивидуально.
Посмотреть дополнительно:
— Онлайн-курс на stepik.org. Функциональное программирование на языке Haskell.
— Онлайн-курс на stepik.org. Функциональное программирование на языке Haskell, часть 2.
— Запись курса лекций «Функциональное программирование» в Computer Science Center.
Материалы
3. Работа в командной строке Unix
Преподаватель: Виталий Брагилевский (JetBrains)
О курсе. Эффективность использования компьютера при решении разнообразных задач существенно зависит от того, какой инструментарий используется. Многие предпочитают графические приложения и работают преимущественно мышкой (или трекпадом!). Программисты же чаще предпочитают клавиатуру и иногда вообще отказываются от графического интерфейса в пользу утилит командной строки и консольных текстовых редакторов.
В этом курсе студенты научились использовать командную строку в стиле UNIX, научились программировать в bash, а также применять десятки различных утилит, которые традиционно используются в UNIX-системах, таких как Linux и Mac OS X. Пользователи Windows 10 для тех же целей использовали WSL и Windows Terminal. И самое главное: мы научились выходить из редактора vi и узнали, чем редактор Emacs всё-таки лучше (или наоборот!).
Материалы
4. Читаем и пишем на языке Kotlin
Преподаватель: Михаил Сенин (JetBrains)
О курсе. 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.
— Извлекать простые и сложные семантические признаки.
— Конструировать свёрточные нейронные сети.
— Запускать и тренировать их.
Посмотреть дополнительно:
— Познакомиться с языком программирования Python. Для этого можно пройти один из списка ниже или аналогичный на ваш вкус.
— Хорошее «Введение в Python» и IDE PyCharm. Ещё одно. И третье.
— Посмотреть библиотеку numpy, например, тут.
— Знакомство с обработкой изображений: видеозаписи курса Леши Артамонова в CS центре, курс по анализу изображений от University of Washington.
Материалы
3. Обучение с подкреплением
Преподаватели: Алексей Толстиков, Виктор Отлига (Яндекс, БГУ)
О курсе. Каждый день вы ищете что-нибудь в интернете с помощью одной из крупных поисковых систем, таких, например, как Яндекс или Google. Или смотрите сериалы через Кинопоиск, а он советует, какие ещё сериалы вам могут понравиться. А, может быть, вы слышали о том, что компьютер превзошёл человека в таких играх как го, Dota 2 и даже Starcraft 2? В основе всего этого лежит машинное обучение, с которым предлагается познакомиться в нашем курсе. Мы поговорим про классические алгоритмы и про более продвинутые — такие как нейронные сети и обучение с подкреплением.
На практических занятиях мы реализуем собственного бота для классической игры «Пакман». В основе принятия решений нашим игроком с искусственным интеллектом будет один из интереснейших разделов машинного обучения — обучение с подкреплением. В конце курса наши боты сразятся в турнире.
Посмотреть дополнительно:
— Можно попрактиковаться в Open AI Gym.
— Курс лекций по «Deep Reinforcement Learning» от компании Deep Mind, дочерней компании Google, занимающейся искусственным интеллектом.
— Курс лекций «Reinforcement Learning» от David Silver.
— Книга «Reinforcement Learning: An Introduction».
Материалы
4. Рекомендательные системы
Преподаватель: Андрей Данильченко (Яндекс)
О курсе. Мы ежедневно сталкиваемся с огромным количеством информации: идут учебные проекты, друзья пишут в соцсетях, на Хабре выходят интересные статьи, появляются новые треки любимых музыкантов и новые фильмы, которые хочется посмотреть. Чтобы не утонуть в этом многообразии контента используются рекомендательные системы. Радио подбирает вам персональные треки, Дзен и соцсети ранжируют контент персонально. В этом курсе мы поговорили о том, как подобные системы работают «под капотом»: откуда берут данные, какие алгоритмы используют для отбора и ранжирования контента.
Материалы
Список всех курсов смены с презентациями
