.png)
В начале августа прошла студенческая смена МКН по теории сложности вычислений в Математическом центре “Сириус”. https://siriusmathcenter.ru/program/005s
Школу посетили 31 студент и студентка СПбГУ, МФТИ, ВШЭ, МГУ и ИТМО, прошедшие конкурсный отбор. Занятия проводили преподаватели МКН, ведущие также исследования в области теоретической информатики в Петербургском отделении математического института им. В. А. Стеклова РАН.
О том, что что изучали участники, рассказывает организатор программы профессор Александр Куликов:
“На смене мы рассказали классические результаты, а также некоторые последние достижения и открытые задачи в области теории сложности вычислений. Этот раздел компьютерных наук, грубо говоря, ищет ответ на такой вопрос: мы не можем быстро на компьютере решать многие интересные вычислительные задачи из-за того, что это просто невозможно, или же из-за того, что мы до сих пор не смогли придумать эффективный способ для этого? На этот вопрос мы смотрели с разных сторон на четырёх курсах: схемная сложность, формульная сложность и гипотеза KRW, сложность доказательств, высокоточные оценки сложности.
Интересно, что все эти четыре темы сильно переплетены между собой — и результатами, и методами, и гипотезами. Например, известно (и это, на первый взгляд, контринтуитивно), что, построив эффективный алгоритм, можно доказать нижнюю оценку на схемную сложность. И наоборот: некоторые методы, которые исходно разрабатывались для доказательства нижних оценок на схемы, могут быть использованы для того, чтобы разработать более быстрее алгоритмы. Гипотеза KRW связывает схемную сложность с коммуникационной сложностью, где игроки хотят найти что-то, обменявшись друг с другом как можно меньшим количеством информации. Эта область успешно применяется при анализе структур данных и алгоритмов обработки потоковых данных. Наконец, методы сложности доказательств используют и используются в методах схемной сложности.
В приложенном конспекте можно найти все базовые определения, формулировки разбиравшихся на школе результатов (без доказательств), упражнения и открытые задачи.”
Впечатления участника смены, студента четвёртого курса Современного программирования МКН СПбГУ, Григория Эмдина:
“Школа проходила в достаточно интенсивном темпе: по четыре пары в день, но, несмотря на это, все курсы хорошо усвоились. И даже оставалось время погулять по Сочи и покупаться в море!
На школе я приобрёл много новых знакомств. Большинство ребят были старше меня, и они делились своим опытом поступления в магистратуры/аспирантуры, рассказывали про свои дипломы и давали советы, как лучше его писать. Преподаватели помимо теории выдавали большое количество задач, в том числе и открытые проблемы, по которым можно будет написать статью или диплом.
Школа произвела на меня исключительно положительное впечатление, всем рекомендую ездить на подобные мероприятия. Хочется поблагодарить всех преподавателей и организаторов за столь чудесно проведенное время.”