NIS-TCS-20-21 — различия между версиями

Материал из Wiki - Факультет компьютерных наук
Перейти к: навигация, поиск
(Новая страница: «== Общая информация == == Правила оценивания ==»)
 
 
(не показано 9 промежуточных версии этого же участника)
Строка 1: Строка 1:
 
== Общая информация ==
 
== Общая информация ==
  
 +
 +
Участие в НИС состоит из трех частей: посещение научных мероприятий, участие в разборе статей и экзамен.
 +
 +
В части посещения научных мероприятий студенты по своему выбору в течение года посещают научные мероприятия, интересные с точки зрения теоретической информатики. Это могут быть конференции, школы, семинары, мини-курсы и курсы, которые не засчитываются в оценку по другим курсам. В случае сомнений в том, будет ли мероприятие засчитано в НИС, стоит согласовать мероприятие с руководителями специализации.
 +
 +
О некоторых мероприятиях, которые можно засчитывать в НИС появляется информация в [https://t.me/joinchat/UzonA5kv5_wrhLwU канале специализации].
 +
 +
Разбор статей организован следующим образом. Студентам предлагается одна тема на модуль, которую нужно самостоятельно изучить по 1-2 статьям. В конце модуля проводится семинар, на котором обсуждается содержание статей и возникшие вопросы, а также пишется небольшая письменная работа по статье.
 +
 +
Экзамен проводится в конце курса в формате собеседования. На экзамене обсуждается содержание посещенных студентом семинаров в целом, а также какая-то одна из прослушанных тем по выбору студента.
 +
 +
== Продолжительность НИС ==
 +
 +
Курс проходит в следующих модулях <br>
 +
3 курс ПМИ: 1-4 модули <br>
 +
4 курс ПМИ: 1-3 модули <br>
 +
1 курс НОД: 1-4 модули <br>
 +
2 курс НОД: 1-2 модули
 +
 +
== Статьи для разбора ==
 +
 +
<b>3 модуль.</b> Локальная лемма Ловаса. Требуется прочитать и разобрать [https://arxiv.org/abs/0903.0544 статью Мозера, Тардоша], а также раздел 6 в [https://arxiv.org/abs/1305.1535 тексте Румянцева, Шеня]. Сделать это нужно к середине марта, после чего пройдет семинар с обсуждением статей.
 +
 +
Семинар с обсуждением статьи и тестом пройдет 17 марта с 11:10 до 12:30.
 +
 +
<b>4 модуль.</b> Доказательство гипотезы о чувствительности. Доказательство можно условно разбить на три части: <br>
 +
<ol>
 +
<li>нижняя оценка степени булевой функции через блочную чувствительность, </li>
 +
<li>связь чувствительности с максимальной степенью подграфа булева куба, </li>
 +
<li>нижняя оценка максимальной степени  подграфа булева куба.</li>
 +
</ol>
 +
Первое — это довольно старый и известный результат Nisan, второе — также довольно старый результат Gotsman и Linial. Третье — это результат Huang 2019 года, который собственно и позволил доказать гипотезу. <br>
 +
В рамках НИС требуется разобраться с доказательством гипотезы. Для этого есть целый ряд возможных источников.
 +
<ul>
 +
<li>Есть оригинальные статьи [https://www.sciencedirect.com/science/article/pii/0097316592900608 Gotsman, Linial] и [https://arxiv.org/abs/1907.00847 Huang].</li>
 +
<li>Есть полное изложение всего доказательства в [https://terrytao.wordpress.com/2019/07/26/twisted-convolution-and-the-sensitivity-conjecture/ блоге Tao].</li>
 +
<li>Часть 2 хорошо описана в разделе 5.6 этого [https://theoryofcomputing.org/articles/gs004/ обзора].</li>
 +
<li>Есть альтернативное доказательство части 3 [https://www.cs.stanford.edu/~knuth/papers/huang.pdf by Knuth].</li>
 +
<li>Еще одно альтернативное доказательство части 3 есть в [https://fedyapetrov.wordpress.com/2019/07/03/low-level-variant-of-huangs-argument-for-sensitivity-conjecture/ блоге Федора Петрова].</li>
 +
<li>Еще одно альтернативное доказательство части 3 есть в [https://arxiv.org/abs/1907.11175 заметке Романа Карасева].</li>
 +
<li>Еще одно полное изложение доказательства есть в этом (кажется, студенческом) [https://www.ams.org/journals/bull/2020-57-04/S0273-0979-2020-01697-6/ обзоре]. </li>
 +
</ul>
 +
 +
Не обязательно разбирать доказательство следующих двух теорем: Markov’s inequality for polynomials и Cauchy interlacing theorem (доказательства этих теорем также вполне посильны, но их разбор выходит за рамки НИС).
 +
 +
Семинар с обсуждением статьи и тестом пройдет 14 июня с 16:20 до 17:40.
  
 
== Правила оценивания ==
 
== Правила оценивания ==
 +
 +
Вес посещения мероприятий в итоговой оценке составляет 30%, разбора статей — 40%, экзамена — 30%.
 +
 +
Оценка за разбор статей выставляется на основании письменных работ.

Текущая версия на 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 модуль. Доказательство гипотезы о чувствительности. Доказательство можно условно разбить на три части:

  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%.

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