14.06.22 - 23.06.22
Факультет математики и комьютерных наук СПбГУ
Летняя школа МКН СПбГУ
Факультет математики и компьютерных наук СПбГУ в июне 2022 года проводит очную летнюю школу для учеников, окончивших десятый класс
Что будет на школе
Курсы по математике и программированию от преподавателей и студентов факультета
Новые знакомства
Приглашаем на школу заинтересованных школьников из Санкт-Петербурга и откуда угодно. Школа проходит только очно на Васильевском острове.
Интересные лекции и практические занятия
Короткие курсы сочетают изучение теории и решение задач. Для курсов по программированию вам понадобится ноутбук
Общение и игры
Студенты готовят для школьников экскурсии и сюрпризы. Вы интересно проведёте время и узнаете больше о факультете МКН СПбГУ
Участником школы можно стать, пройдя отбор на одно из двух направлений
– математика, до 40 участников, два трека
– информатика и программирование, до 30 участников, два трека
Планируемые в рамках школы курсы
Направление: математика
Геометрические неравенства
Преподаватели: Д. Н. Запорожец, Т. Д. Мосеева
На уроках алгебры все вы сталкивались с задачами, в которых требуется доказать какое-нибудь неравенство. В геометрии есть схожая область, которая изучает геометрические неравенства. Этот вид неравенств в школьной программе встречается значительно реже. Вместе с тем данный раздел является удивительно интересным и красивым. В нашем курсе мы разберем, либо попытаемся вместе решить различные задачи на данную тему, многие из которых на самом деле являются хорошо известными классическими теоремами. Также мы слегка коснемся задач, которые, несмотря на их простую формулировку, до сих пор ни кем не решены. Возможно это удастся сделать кому-то из вас.
На уроках алгебры все вы сталкивались с задачами, в которых требуется доказать какое-нибудь неравенство. В геометрии есть схожая область, которая изучает геометрические неравенства. Этот вид неравенств в школьной программе встречается значительно реже. Вместе с тем данный раздел является удивительно интересным и красивым. В нашем курсе мы разберем, либо попытаемся вместе решить различные задачи на данную тему, многие из которых на самом деле являются хорошо известными классическими теоремами. Также мы слегка коснемся задач, которые, несмотря на их простую формулировку, до сих пор ни кем не решены. Возможно это удастся сделать кому-то из вас.
Вычислительная геометрия
Преподаватели: Б. А. Золотов, М. И. Магин
В курсе вычислительной геометрии мы будем рассматривать различные геометрические объекты с алгоритмической точки зрения. Мы начнём с базовых задач поиска пересечения отрезков, определения направления поворота, построения касательных к многогранникам. После этого перейдём к более сложным задачам: перечисление развёрток и построение многогранников, которые из них склеиваются, поиск кратчайших путей на поверхностях, рисование графов. Затронем различные оптимизационные задачи, оригинальные и наглядные. Дадим обзор современных статей по вычислительной геометрии и посмотрим, какие вопросы актуальны прямо сейчас в этой науке. Посвятим часть занятия практическим навыкам иллюстрирования статей.
В курсе вычислительной геометрии мы будем рассматривать различные геометрические объекты с алгоритмической точки зрения. Мы начнём с базовых задач поиска пересечения отрезков, определения направления поворота, построения касательных к многогранникам. После этого перейдём к более сложным задачам: перечисление развёрток и построение многогранников, которые из них склеиваются, поиск кратчайших путей на поверхностях, рисование графов. Затронем различные оптимизационные задачи, оригинальные и наглядные. Дадим обзор современных статей по вычислительной геометрии и посмотрим, какие вопросы актуальны прямо сейчас в этой науке. Посвятим часть занятия практическим навыкам иллюстрирования статей.
Ориентированные графы
Преподаватели: Т. Ю. Шашков, Н. А. Кароль, К. В. Челпанов
Ориентированные графы (или орграфы) являются важным объектом в теории графов, они часто используются как в самых разных областях чистой математики, так и в разных задачах индустриальных компаний. Основной целью данного курса является знакомство с ориентированными графами и классическими результатами в этой области. Курс начнём с базовых определений и конструкций, а потом перейдём к обсуждению некоторых содержательных результатов. Обсудим, например, удаление вершин с сохранением сильной связности, количество гамильтоновых путей в турнирах, конструкцию ядра и её применения и многие другие интересные темы. Если в конце останется время, можем затронуть какую-нибудь другую интересующую аудиторию тему из теории графов или же погрузиться глубже в орграфы и обсудить чуть более сложную конструкцию слабых двойных циклов.
Ориентированные графы (или орграфы) являются важным объектом в теории графов, они часто используются как в самых разных областях чистой математики, так и в разных задачах индустриальных компаний. Основной целью данного курса является знакомство с ориентированными графами и классическими результатами в этой области. Курс начнём с базовых определений и конструкций, а потом перейдём к обсуждению некоторых содержательных результатов. Обсудим, например, удаление вершин с сохранением сильной связности, количество гамильтоновых путей в турнирах, конструкцию ядра и её применения и многие другие интересные темы. Если в конце останется время, можем затронуть какую-нибудь другую интересующую аудиторию тему из теории графов или же погрузиться глубже в орграфы и обсудить чуть более сложную конструкцию слабых двойных циклов.
Узлы и косы
Преподаватели: А. Ю. Миллер, И. С. Алексеев, Д. Д. Аксенова
С незапамятных времён узлы использовались как в практических, так и в декоративных целях. Математики впервые заинтересовались узлами лишь в XIX веке, и с этого времени теория узлов обрела статус самостоятельного раздела математики. Мы познакомимся с основными понятиями теории узлов и близкой к ней теории кос.
Наши занятия пройдут в формате практикума, на котором вам будет предложено продвинуться в решении наглядных задач, разбитых на две темы: про косы и про узлы. Сначала вы познакомитесь с косами, изучите их геометрические и алгебраические свойства, познаете комбинаторику раскрасок кос и наметите дорогу к теории узлов. Затем вам будет предложено продемонстрировать гибкость своего воображения, изучить с математической точки зрения преобразования ДНК, заданные некоторыми ферментами, применить раскраски узлов для анализа этих преобразований и, наконец, открыть для себя знаменитые полиномы узлов, позволяющие устанавливать их неразвязываемость.
Групповые решение задач будут сопровождаться теоретическими инструктажами, вводящими необходимые понятия.
С незапамятных времён узлы использовались как в практических, так и в декоративных целях. Математики впервые заинтересовались узлами лишь в XIX веке, и с этого времени теория узлов обрела статус самостоятельного раздела математики. Мы познакомимся с основными понятиями теории узлов и близкой к ней теории кос.
Наши занятия пройдут в формате практикума, на котором вам будет предложено продвинуться в решении наглядных задач, разбитых на две темы: про косы и про узлы. Сначала вы познакомитесь с косами, изучите их геометрические и алгебраические свойства, познаете комбинаторику раскрасок кос и наметите дорогу к теории узлов. Затем вам будет предложено продемонстрировать гибкость своего воображения, изучить с математической точки зрения преобразования ДНК, заданные некоторыми ферментами, применить раскраски узлов для анализа этих преобразований и, наконец, открыть для себя знаменитые полиномы узлов, позволяющие устанавливать их неразвязываемость.
Групповые решение задач будут сопровождаться теоретическими инструктажами, вводящими необходимые понятия.
Аналитическая теория чисел
Преподаватели: И. А. Ермошин, А. С. Калинин
В первой части курса мы обсудим неравенство большого решета и доказательство теоремы Бобмьери-Виноградова -- фундаментальной теоремы о распределении простых чисел в арифметических прогрессиях. Если останется время, мы поговорим о приложениях.
Вторая половина курса будет состоять в основном из определений, примеров и картинок, а не доказательств, поэтому будет понятна большинству школьников. Доказательства большинства теорем будут представлены как факты, т. к. требуют более серьёзного изучения аналитической теории чисел, чем позволяет время курса. Однако из них будут выведены некоторые интересные следствия. В самом начале будут мотивационные задачи: проблема конгруэнтных чисел, следствия из Великой теоремы Ферма. Ближе к концу (если успеем) мы поговорим о приложениях эллиптических кривых в криптографии и блокчейне.
В первой части курса мы обсудим неравенство большого решета и доказательство теоремы Бобмьери-Виноградова -- фундаментальной теоремы о распределении простых чисел в арифметических прогрессиях. Если останется время, мы поговорим о приложениях.
Вторая половина курса будет состоять в основном из определений, примеров и картинок, а не доказательств, поэтому будет понятна большинству школьников. Доказательства большинства теорем будут представлены как факты, т. к. требуют более серьёзного изучения аналитической теории чисел, чем позволяет время курса. Однако из них будут выведены некоторые интересные следствия. В самом начале будут мотивационные задачи: проблема конгруэнтных чисел, следствия из Великой теоремы Ферма. Ближе к концу (если успеем) мы поговорим о приложениях эллиптических кривых в криптографии и блокчейне.
Принцип максимума Понтрягина
Преподаватели: Р. В. Бессонов, П. В. Губкин
Мы познакомимся с одним из основных математических инструментов теории оптимального управления. Принцип максимума Понтрягина появился из попыток решения чисто прикладной задачи, связанной с аэродинамикой летательных аппаратов. В последствии оказалось, что он имеет разнообразные и подчас совершенно неожиданные применения.
Мы познакомимся с одним из основных математических инструментов теории оптимального управления. Принцип максимума Понтрягина появился из попыток решения чисто прикладной задачи, связанной с аэродинамикой летательных аппаратов. В последствии оказалось, что он имеет разнообразные и подчас совершенно неожиданные применения.
Геометрия Лобачевского
Преподаватели: С. В. Шамов, С. И. Архипов
Широко известный пятый постулат Евклида гласит, что через любую точку, не лежащую на прямой, можно провести ровно одну прямую, параллельную данной. Оказывается, можно отказаться от этого свойства, интерпретируя понятия «прямая», «расстояние», «угол» иначе, чем у Евклида. Мы построим несколько таких моделей, пользуясь техникой дробно-линейных преобразований (расширенной) комплексной плоскости.
Широко известный пятый постулат Евклида гласит, что через любую точку, не лежащую на прямой, можно провести ровно одну прямую, параллельную данной. Оказывается, можно отказаться от этого свойства, интерпретируя понятия «прямая», «расстояние», «угол» иначе, чем у Евклида. Мы построим несколько таких моделей, пользуясь техникой дробно-линейных преобразований (расширенной) комплексной плоскости.
Направление: информатика и программирование
Динамическое программирование
Преподаватели: И. С. Казменко, А. М. Исакова
Динамическое программирование — метод конструирования алгоритмов, при котором решение задачи сводится к решению меньших подзадач такого же типа. Этими общими словами можно описать как вычисление факториала или числа Фибоначчи, так и, например, алгоритм Дейкстры для поиска кратчайших путей в графе.
В курсе мы увидим, как идеи динамического программирования помогают придумывать и оптимизировать решения в самых разных задачах. Например, научимся быстро считать и нумеровать комбинаторные объекты, придумывать и коротко реализовывать динамику по подмножествам и динамику по профилю.
Теория будет понятна без предварительной подготовки. Для практической части — написания решений на компьютере и сдачи в автоматическую проверяющую систему — нужно владеть каким-нибудь современным языком программирования.
Динамическое программирование — метод конструирования алгоритмов, при котором решение задачи сводится к решению меньших подзадач такого же типа. Этими общими словами можно описать как вычисление факториала или числа Фибоначчи, так и, например, алгоритм Дейкстры для поиска кратчайших путей в графе.
В курсе мы увидим, как идеи динамического программирования помогают придумывать и оптимизировать решения в самых разных задачах. Например, научимся быстро считать и нумеровать комбинаторные объекты, придумывать и коротко реализовывать динамику по подмножествам и динамику по профилю.
Теория будет понятна без предварительной подготовки. Для практической части — написания решений на компьютере и сдачи в автоматическую проверяющую систему — нужно владеть каким-нибудь современным языком программирования.
Сравнение строк и алгоритмы на строках
Преподаватели: А. В. Тискин, А. И. Алёшин, Н. Е. Борозенец, Р. Т. Магдиев
Алгоритмы на данных, представленных в виде строк - классическая и бурно развивающаяся область исследований, имеющая как глубокие связи с различными разделами дискретной математики, так и многочисленные приложения в биоинформатике, программной инженерии, информационной безопасности, телекоммуникациях. В курсе будут рассмотрены ключевые понятия современной теории строковых алгоритмов и несколько алгоритмических и комбинаторных задач на строках.
Алгоритмы на данных, представленных в виде строк - классическая и бурно развивающаяся область исследований, имеющая как глубокие связи с различными разделами дискретной математики, так и многочисленные приложения в биоинформатике, программной инженерии, информационной безопасности, телекоммуникациях. В курсе будут рассмотрены ключевые понятия современной теории строковых алгоритмов и несколько алгоритмических и комбинаторных задач на строках.
Непоследовательное планирование
Преподаватели: А. А. Игнатьев, Ю. И. Дементьев
Дан граф задач — ориентированный ациклический граф с двумя выделенными вершинами s и t, и взвешенными ребрами. Вершины — состояния выполнения некоторого проекта/задания, ребра — возможные действия для достижения цели, стоимость ребра — затраты на выполнение конкретного действия. По этому графу ходит агент, который моделирует человеческое поведение: с одной стороны, старается минимизировать свои оценочные затраты для достижения цели, с другой — затраты в будущем оказывают меньшее влияние на принятие им решений о выборе пути, чем текущие. В базовой модели агент оценивает путь до вершины t так, что веса всех ребер, кроме первого, домножаются на коэффициент предвзятости \beta \in [0, 1]. Данная модель играет большую роль для разработчиков/дизайнеров задач и игр в оценке последствий человеческого поведения, связанных с несогласованным по времени планированием, включая прокрастинацию и отказ от долгосрочных перспектив. Мы предлагаем исследование различных задач, возникающих в такой постановке модели. В частности, включают в себя базовые алгоритмы, базовый дискретный теорвер, комбинаторика.
Дан граф задач — ориентированный ациклический граф с двумя выделенными вершинами s и t, и взвешенными ребрами. Вершины — состояния выполнения некоторого проекта/задания, ребра — возможные действия для достижения цели, стоимость ребра — затраты на выполнение конкретного действия. По этому графу ходит агент, который моделирует человеческое поведение: с одной стороны, старается минимизировать свои оценочные затраты для достижения цели, с другой — затраты в будущем оказывают меньшее влияние на принятие им решений о выборе пути, чем текущие. В базовой модели агент оценивает путь до вершины t так, что веса всех ребер, кроме первого, домножаются на коэффициент предвзятости \beta \in [0, 1]. Данная модель играет большую роль для разработчиков/дизайнеров задач и игр в оценке последствий человеческого поведения, связанных с несогласованным по времени планированием, включая прокрастинацию и отказ от долгосрочных перспектив. Мы предлагаем исследование различных задач, возникающих в такой постановке модели. В частности, включают в себя базовые алгоритмы, базовый дискретный теорвер, комбинаторика.
Древесная ширина, сепараторы, миноры
Преподаватели: Л. Б. Хазалия, А. К. Мозголина
Древесная ширина графа (tree-width), определяемая для декомпозиции графа в дерево (tree decomposition), -- структурный параметр, который часто можно встретить при анализе и построении алгоритмов для разных, хоть и в каком-то смысле специфических, задач. Мы посмотрим на несколько конкретных задач (предварительно: задача о вершинном покрытии, задача поиска максимального разреза, задача q-раскраски) как на задачи динамического программирования. После небольшого знакомства с параметризованными алгоритмами, попробуем проанализировать сложность разобранных ранее задач, взяв в качестве параметра древесную ширину.
Курс теоретический, как пререквизиты -- знание элементарных определений теории графов, а также даже поверхностное представление о динамическом программировании/методе математической индукции упростит понимание материала курса.
Древесная ширина графа (tree-width), определяемая для декомпозиции графа в дерево (tree decomposition), -- структурный параметр, который часто можно встретить при анализе и построении алгоритмов для разных, хоть и в каком-то смысле специфических, задач. Мы посмотрим на несколько конкретных задач (предварительно: задача о вершинном покрытии, задача поиска максимального разреза, задача q-раскраски) как на задачи динамического программирования. После небольшого знакомства с параметризованными алгоритмами, попробуем проанализировать сложность разобранных ранее задач, взяв в качестве параметра древесную ширину.
Курс теоретический, как пререквизиты -- знание элементарных определений теории графов, а также даже поверхностное представление о динамическом программировании/методе математической индукции упростит понимание материала курса.
Проектное программирование
Преподаватели: Л. С. Сорвин
Скорее всего, к текущему моменту вы в основном решали именно олимпиадные задачи на программирование, где цель - написать код, проходящий за ограниченное время тесты из проверяющей системы. Однако чаще в программировании встречаются другие задачи - в них необходимо создать проект, работающий самостоятельно или как часть некоторого механизма. В этом курсе мы в как раз попрактикуемся решать такие задачи - познакомимся с разными стилями программирования, будем писать свои проекты, а так же дополнять, исправлять и улучшать уже имеющиеся. В ходе курса мы изучим основы языка программирования Kotlin, напишем несложную игрушку и несколько базовых программ для компьютера. Для успешного прохождения курса достаточно владения любым языком программирования (например, Python, C++, Java, PascalABC.NET (http://pascalabc.net/)) на базовом уровне (ввод-вывод, обработка строк, работа с коллекциями, функции). Предварительное знакомство с языком Kotlin не требуется. Для выполнения заданий необходим ноутбук с установленной на него последней версией IntelliJ IDEA (https://www.jetbrains.com/idea/download (https://www.jetbrains.com/idea/download/)/, достаточно Community Edition), также необходимо заранее зарегистрироваться на сайте https://github.com (https://github.com/)/.
Скорее всего, к текущему моменту вы в основном решали именно олимпиадные задачи на программирование, где цель - написать код, проходящий за ограниченное время тесты из проверяющей системы. Однако чаще в программировании встречаются другие задачи - в них необходимо создать проект, работающий самостоятельно или как часть некоторого механизма. В этом курсе мы в как раз попрактикуемся решать такие задачи - познакомимся с разными стилями программирования, будем писать свои проекты, а так же дополнять, исправлять и улучшать уже имеющиеся. В ходе курса мы изучим основы языка программирования Kotlin, напишем несложную игрушку и несколько базовых программ для компьютера. Для успешного прохождения курса достаточно владения любым языком программирования (например, Python, C++, Java, PascalABC.NET (http://pascalabc.net/)) на базовом уровне (ввод-вывод, обработка строк, работа с коллекциями, функции). Предварительное знакомство с языком Kotlin не требуется. Для выполнения заданий необходим ноутбук с установленной на него последней версией IntelliJ IDEA (https://www.jetbrains.com/idea/download (https://www.jetbrains.com/idea/download/)/, достаточно Community Edition), также необходимо заранее зарегистрироваться на сайте https://github.com (https://github.com/)/.
14.06.22 - 23.06.22 | Факультет математики и комьютерных наук СПбГУ
Регистрация
Для того, чтобы принять участие в Летней школе, необходимо зарегистрироваться, и прислать решения отборочных заданий не позднее 12 мая. Присылайте столько задач, сколько получится решить
К участию в отборе приглашаются школьники, оканчивающие десятый класс и заинтересованные в посещении школы очно в Петербурге.
Внимание! Факультет организует и контролирует только занятия по расписанию. Свободное время, проезд, проживание, питание и т.п. организуется и оплачивается самостоятельно.
К участию в отборе приглашаются школьники, оканчивающие десятый класс и заинтересованные в посещении школы очно в Петербурге.
Внимание! Факультет организует и контролирует только занятия по расписанию. Свободное время, проезд, проживание, питание и т.п. организуется и оплачивается самостоятельно.
Факультет МКН СПбГУ
14 линия В.О., д. 29
10 минут от метро «Василеостровская»
10 минут от метро «Василеостровская»
summerschool2022@joinmkn.ru
