NIS-TCS-23-24

Общая информация

Участие в НИС состоит из трех частей: посещение научных мероприятий, участие в разборе статей и экзамен.

В части посещения научных мероприятий студенты по своему выбору в течение года посещают научные мероприятия, интересные с точки зрения теоретической информатики. Это могут быть конференции, школы, семинары, мини-курсы и курсы, которые не засчитываются в оценку по другим курсам. В случае сомнений в том, будет ли мероприятие засчитано в НИС, стоит согласовать мероприятие с руководителями специализации.

О некоторых мероприятиях, которые можно засчитывать в НИС появляется информация в канале специализации.

Разбор статей организован следующим образом. Студентам предлагается одна тема на модуль, которую нужно самостоятельно изучить по 1-2 статьям. В конце модуля проводится семинар, на котором обсуждается содержание статей и возникшие вопросы, а также пишется небольшая письменная работа по статье. Информация о статьях для разбора и сроках семинара по разбору статьи публикуется в телеграмм канале Курсы по выбору и НИС ТИ, на который нужно обязательно подписаться. Для этого свяжитесь с М.Н. Вялым.

Экзамен проводится в конце курса в формате собеседования. На экзамене обсуждается содержание посещенных студентом семинаров в целом, а также какая-то одна из прослушанных тем по выбору студента.

Продолжительность НИС

Курс проходит в следующих модулях
3 курс ПМИ: 1-4 модули
4 курс ПМИ: 1-3 модули
1 курс СКН: 1-4 модули
2 курс СКН: 1-2(3) модули

Экзамен 30.03.2024

Экзамен для 4 курса бакалавриата и 2 года магистратуры пройдет 30.03, суббота, 11:00 - 19:00. Экзамен онлайн, ссылка Формат экзамена: (очень) короткая беседа по посещенным мероприятиям и (чуть более длинный) рассказ об одном из посещенных мероприятий (10-15 минут). Я рассчитываю длительность беседы с одним сдающим на 20 минут. Запишитесь в таблицу участия, ссылка

Экзамен 21.06.2024

Экзамен онлайн, ссылка Формат экзамена: (очень) короткая беседа по посещенным мероприятиям и (чуть более длинный) рассказ об одном из посещенных мероприятий (15 минут). Я рассчитываю длительность беседы с одним сдающим на 20 минут. Запишитесь в таблицу участия, ссылка

Статьи для разбора

1 модуль. Требуется прочитать статью A. Razborov, S. Rudich Natural proofs Необходимо понять все определения и формулировки из статьи, а также доказательство основной теоремы 4.1.

Занятие с разбором этой статьи планируется 21.10, начало 15:00. Ориентировочное время - 1 пара, в конце занятия будет тест на 25 минут. Ссылка на zoom. Просьба перед занятием зарегистрироваться в гугл классе НИС ТИ, ссылка, если почему-то не сработает, то код курса ocd43fw Это нужно, чтобы сдать тестовые задания. Кто регистрировался в прошлом году, повторно регистрироваться не нужно.

2 модуль. Требуется разобраться с содержанием статьи O. Goldreich Notes on Levin’s Theory of Average-Case Complexity.

Разбор этой статьи пройдет в два занятия (занятия аналогичны, достаточно участвовать в одном из них). Ссылки на zoom суббота, 09.12, 15:00, и понедельник, 11.12, 13:00.

3 модуль. Разобрать статью Eric Allender, Harry Buhrman, Michal Koucký, Dieter van Melkebeek, and Detlef Ronneburger Power from Random Strings Нужно понять определения основных видов колмогоровской сложности с ограничениями на ресурсы (и без), соотношения между ними и основные результаты об алгоритмической сложности связанных с ними задач. Предлагается разобрать доказательства из раздела 2.2, уяснить основную идею доказательств трудности (раздел 1.1) и технику ее применения на примере теоремы 31 и следствия 32 (раздел 3.2).

Занятие по разбору этой статьи пройдет 2 марта, суббота, начало 19:40. Ссылка на zoom

4 модуль. Разобрать обзор по каталитическим вычислениям, Ian Mertz Reusing Space: Techniques and Open Problems

Обязательны к прочтению введение и часть I. В части II (список задач) можно посмотреть те разделы, которые вызывают интерес. Обзор очень задорно написан и хорошо демонстрирует, как от простого программистского трюка можно перейти к глубоким вопросам теории сложности. Крайне рекомендуется прочесть введение, оно написано очень легко и мотивирующе. Для понимания происходящего полезно знать о классах малой памяти (L, NL), но чего-то сложного о них не требуется. Главное - понимать, как устроено вычисление на памяти, существенно меньшей, чем длина входа.

Разбор этой статьи пройдет 08.06 (суббота), начало 10:00. Ссылка на zoom

Правила оценивания

Вес посещения мероприятий в итоговой оценке составляет 30%, разбора статей — 40%, экзамена — 30%.

Оценка за разбор статей выставляется на основании письменных работ.