NIS-TCS-20-21 — различия между версиями
| Строка 46: | Строка 46: | ||
Не обязательно разбирать доказательство следующих двух теорем: Markov’s inequality for polynomials и Cauchy interlacing theorem (доказательства этих теорем также вполне посильны, но их разбор выходит за рамки НИС). | Не обязательно разбирать доказательство следующих двух теорем: Markov’s inequality for polynomials и Cauchy interlacing theorem (доказательства этих теорем также вполне посильны, но их разбор выходит за рамки НИС). | ||
| − | Семинар с обсуждением статьи и тестом пройдет | + | Семинар с обсуждением статьи и тестом пройдет 14 июня с 16:20 до 17:40. |
== Правила оценивания == | == Правила оценивания == | ||
Текущая версия на 13:39, 6 июня 2022
Содержание
[убрать]Общая информация
Участие в НИС состоит из трех частей: посещение научных мероприятий, участие в разборе статей и экзамен.
В части посещения научных мероприятий студенты по своему выбору в течение года посещают научные мероприятия, интересные с точки зрения теоретической информатики. Это могут быть конференции, школы, семинары, мини-курсы и курсы, которые не засчитываются в оценку по другим курсам. В случае сомнений в том, будет ли мероприятие засчитано в НИС, стоит согласовать мероприятие с руководителями специализации.
О некоторых мероприятиях, которые можно засчитывать в НИС появляется информация в канале специализации.
Разбор статей организован следующим образом. Студентам предлагается одна тема на модуль, которую нужно самостоятельно изучить по 1-2 статьям. В конце модуля проводится семинар, на котором обсуждается содержание статей и возникшие вопросы, а также пишется небольшая письменная работа по статье.
Экзамен проводится в конце курса в формате собеседования. На экзамене обсуждается содержание посещенных студентом семинаров в целом, а также какая-то одна из прослушанных тем по выбору студента.
Продолжительность НИС
Курс проходит в следующих модулях
3 курс ПМИ: 1-4 модули
4 курс ПМИ: 1-3 модули
1 курс НОД: 1-4 модули
2 курс НОД: 1-2 модули
Статьи для разбора
3 модуль. Локальная лемма Ловаса. Требуется прочитать и разобрать статью Мозера, Тардоша, а также раздел 6 в тексте Румянцева, Шеня. Сделать это нужно к середине марта, после чего пройдет семинар с обсуждением статей.
Семинар с обсуждением статьи и тестом пройдет 17 марта с 11:10 до 12:30.
4 модуль. Доказательство гипотезы о чувствительности. Доказательство можно условно разбить на три части:
- нижняя оценка степени булевой функции через блочную чувствительность,
- связь чувствительности с максимальной степенью подграфа булева куба,
- нижняя оценка максимальной степени подграфа булева куба.
Первое — это довольно старый и известный результат 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%.
Оценка за разбор статей выставляется на основании письменных работ.
