Просмотр исходного текста страницы NIS-TCS-23-24

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


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

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

О некоторых мероприятиях, которые можно засчитывать в НИС появляется информация в [https://t.me/joinchat/UzonA5kv5_wrhLwU канале специализации].

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

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

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

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

=== Экзамен 30.03.2024 ===

Экзамен для 4 курса бакалавриата и 2 года магистратуры пройдет 30.03, суббота, 11:00 - 19:00.
Экзамен онлайн, [https://us06web.zoom.us/j/85384378712?pwd=DjB4AYwsackAFloSrHGPBekFhJYjan.1 ссылка]
Формат экзамена: (очень) короткая беседа по посещенным мероприятиям и (чуть более длинный) рассказ об одном из посещенных мероприятий (10-15 минут). 
Я рассчитываю длительность беседы с одним сдающим на 20 минут. 
Запишитесь в таблицу участия, [https://docs.google.com/spreadsheets/d/1EENIuEGsMyKoBl2XK9T95pKexZTn2ko4bULQVWRUmAQ/edit?usp=sharing ссылка]


=== Экзамен 21.06.2024 ===

Экзамен онлайн, [https://us06web.zoom.us/j/81946785563?pwd=BlWOSPwkeVDavpy6RR1Awo6SQoCRLz.1 ссылка]
Формат экзамена: (очень) короткая беседа по посещенным мероприятиям и (чуть более длинный) рассказ об одном из посещенных мероприятий (15 минут). 
Я рассчитываю длительность беседы с одним сдающим на 20 минут. 
Запишитесь в таблицу участия, [https://docs.google.com/spreadsheets/d/13qbtu6eIpPQhIADy2xKcSFVHAFL3ns0YvtXKR4QdI9A/edit?usp=sharing ссылка]

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

'''1 модуль.''' Требуется прочитать статью A. Razborov, S. Rudich [https://www.sciencedirect.com/science/article/pii/S002200009791494X Natural proofs]  Необходимо понять все определения и формулировки из статьи, а также доказательство основной теоремы 4.1.
 
Занятие с разбором этой статьи планируется 21.10, начало 15:00. Ориентировочное время - 1 пара, в конце занятия будет тест на 25 минут. [https://us06web.zoom.us/j/88982455362?pwd=UgnFQjVbL1M356dXZjGpx8JJWNOIwA.1 Ссылка на zoom]. Просьба перед занятием зарегистрироваться в гугл классе НИС ТИ, [https://classroom.google.com/c/NTU2NjQ3NTExOTA1 ссылка], если почему-то не сработает, то код курса ocd43fw Это нужно, чтобы сдать тестовые задания. Кто регистрировался в прошлом году, повторно регистрироваться не нужно.

'''2 модуль.''' Требуется разобраться с содержанием статьи O. Goldreich [https://www.wisdom.weizmann.ac.il/~oded/COL/lnd.pdf Notes on Levin’s Theory of Average-Case Complexity]. 

Разбор этой статьи пройдет в два занятия (занятия аналогичны, достаточно участвовать в одном из них). Ссылки на zoom [https://us06web.zoom.us/j/87070865269?pwd=jdjx63uleGxXPfLuX67DCsWdvEAt4h.1 суббота, 09.12, 15:00], и [https://us06web.zoom.us/j/84610932904?pwd=gr7L0jKazQ240bmuybe1TOHxY4eRUV.1 понедельник, 11.12, 13:00].

'''3 модуль.'''
Разобрать статью Eric Allender, Harry Buhrman, Michal Koucký, Dieter van Melkebeek, and Detlef Ronneburger [https://people.cs.rutgers.edu/~allender/papers/KT.pdf Power from Random Strings]
Нужно понять определения основных видов колмогоровской сложности с ограничениями на ресурсы (и без),  соотношения между ними  и   основные результаты об алгоритмической сложности связанных с ними задач. Предлагается разобрать доказательства из раздела 2.2, уяснить основную идею доказательств  трудности (раздел 1.1) и технику ее применения на примере теоремы 31 и следствия 32 (раздел 3.2).


Занятие по разбору этой статьи пройдет 2 марта, суббота, начало 19:40. [https://us06web.zoom.us/j/86000033493?pwd=F1LAUDW8WGgEW07xml26HMjBnd7MVx.1 Ссылка на zoom]

'''4 модуль.''' Разобрать обзор по каталитическим вычислениям, Ian Mertz [https://eccc.weizmann.ac.il/report/2023/179/ Reusing Space: Techniques and Open Problems]

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

Разбор этой статьи пройдет  08.06 (суббота),  начало 10:00. [https://us06web.zoom.us/j/89039232572?pwd=iaPG9XCTmykR1ubsqvvxZWWYWhGhqo.1 Ссылка на zoom]

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

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

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