NIS-TCS-23-24 — различия между версиями
Vyalyi (обсуждение | вклад) |
Vyalyi (обсуждение | вклад) |
||
| (не показано 11 промежуточных версии этого же участника) | |||
| Строка 19: | Строка 19: | ||
4 курс ПМИ: 1-3 модули <br> | 4 курс ПМИ: 1-3 модули <br> | ||
1 курс СКН: 1-4 модули <br> | 1 курс СКН: 1-4 модули <br> | ||
| − | 2 курс СКН: 1-2 модули | + | 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 ссылка] | ||
== Статьи для разбора == | == Статьи для разбора == | ||
| Строка 25: | Строка 41: | ||
'''1 модуль.''' Требуется прочитать статью A. Razborov, S. Rudich [https://www.sciencedirect.com/science/article/pii/S002200009791494X Natural proofs] Необходимо понять все определения и формулировки из статьи, а также доказательство основной теоремы 4.1. | '''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] | ||
== Правила оценивания == | == Правила оценивания == | ||
Текущая версия на 17:37, 14 июня 2024
Содержание
Общая информация
Участие в НИС состоит из трех частей: посещение научных мероприятий, участие в разборе статей и экзамен.
В части посещения научных мероприятий студенты по своему выбору в течение года посещают научные мероприятия, интересные с точки зрения теоретической информатики. Это могут быть конференции, школы, семинары, мини-курсы и курсы, которые не засчитываются в оценку по другим курсам. В случае сомнений в том, будет ли мероприятие засчитано в НИС, стоит согласовать мероприятие с руководителями специализации.
О некоторых мероприятиях, которые можно засчитывать в НИС появляется информация в канале специализации.
Разбор статей организован следующим образом. Студентам предлагается одна тема на модуль, которую нужно самостоятельно изучить по 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%.
Оценка за разбор статей выставляется на основании письменных работ.
