NIS-TCS-20-21

Материал из Wiki - Факультет компьютерных наук
Перейти к: навигация, поиск

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

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

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

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

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

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

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

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

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

3 модуль. Локальная лемма Ловаса. Требуется прочитать и разобрать статью Мозера, Тардоша, а также раздел 6 в тексте Румянцева, Шеня. Сделать это нужно к середине марта, после чего пройдет семинар с обсуждением статей.

Семинар с обсуждением статьи и тестом пройдет 17 марта с 11:10 до 12:30.

4 модуль. Доказательство гипотезы о чувствительности. Доказательство можно условно разбить на три части:

  1. нижняя оценка степени булевой функции через блочную чувствительность,
  2. связь чувствительности с максимальной степенью подграфа булева куба,
  3. нижняя оценка максимальной степени подграфа булева куба.

Первое — это довольно старый и известный результат Nisan, второе — также довольно старый результат Gotsman и Linial. Третье — это результат Huang 2019 года, который собственно и позволил доказать гипотезу.
В рамках НИС требуется разобраться с доказательством гипотезы. Для этого есть целый ряд возможных источников.

  • Есть оригинальные статьи Gotsman, Linial и Huang.
  • Есть полное изложение всего доказательства в блоге Tao.
  • Часть 2 хорошо описана в разделе 5.6 этого обзора.
  • Есть альтернативное доказательство части 3 by Knuth.
  • Еще одно альтернативное доказательство части 3 есть в блоге Федора Петрова.
  • Еще одно альтернативное доказательство части 3 есть в заметке Романа Карасева.
  • Еще одно полное изложение доказательства есть в этом (кажется, студенческом) обзоре.

Не обязательно разбирать доказательство следующих двух теорем: Markov’s inequality for polynomials и Cauchy interlacing theorem (доказательства этих теорем также вполне посильны, но их разбор выходит за рамки НИС).

Семинар с обсуждением статьи и тестом пройдет 14 июня с 16:20 до 17:40.

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

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

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