Сложность вычислений ФПМИ

Этот курс Верещагина может быть полезен студентам с потока ПМФ, которые не ходили на основной курс сложности. Также можно распространять информацию среди интересующихся знакомых с других потоков/факультетов.

===

16 февраля начнется полугодовой спецкурс Н.К. Верещагина "Сложность вычислений", который будет читаться онлайн по вторникам с 18:30 до 20:05.


Это - базовый спецкурс по теории сложности вычислений, включающий многие темы. В частности, доказательства трудности некоторых алгоритмических задач, теорию NP-полноты, классы BPP, #P, PSPACE. Предварительных знаний не требуется. Ссылка на сайт:

http://lpcs.math.msu.su/~ver/teaching/ComputationalComplexity/2020.html

https://drive.google.com/file/d/1-Rm-crZUx9jJyfPg_Ol_JgqQb3PqliPr/view?usp=sharing - видеозапись сегодня

Содержимое доски сегодня

Сегодня получилась большая задержка, давайте начнём в 10:30. Дальше постараюсь разрулить, чтобы вовремя начинать.

В этом семестре этот канал будет использоваться для курса "Сложность вычислений: дополнительные главы". Лекции будут по новой ссылке: https://meet.google.com/nae-ewmf-doz
Доска будет по ссылке https://idroo.com/board-QFFLqArpsx
Начало, видимо, будет немного позже 10, т.к. мне нужно успевать отвезти сына в школу. Завтра поймём, во сколько именно я успеваю.

Сегодня экзамен по той же ссылке, что вчера (см. в реплае).

Завтра, 19.01, будут заходы с 10 до 14 с интервалом в час. По 7 слотов каждый час. До 22 часов пишите личным сообщением, во сколько хотите прийти, потом назначу неопределившихся на оставшиеся места.

Сегодня экзамен по другой ссылке: 

Подключиться к конференции Zoom
https://us02web.zoom.us/j/88031076492?pwd=K0JXV2YwRC9leVhMTHkvZ0pGRnYvZz09

Идентификатор конференции: 880 3107 6492
Код доступа: 475829

Завтра будут заходы с 10 до 14 с интервалом в час. В 10 - шесть слотов, далее по семь. До 22 часов пишите личным сообщением, во сколько хотите прийти, потом назначу неопределившихся на оставшиеся места.

Список билетов, по которому будут выдаваться вопросы.

Основная ссылка на сегодняшний экзамен:
https://us02web.zoom.us/j/89538193206?pwd=TTVRbEV5U0NVNURNS3dBcUlWbk0vQT09

Идентификатор конференции: 895 3819 3206
Код доступа: 226092

Завтра сдающие будут приглашаться небольшими группами с 9:30 до 14:30 каждый час. Также есть 4 слота во второй половине дня. Если есть предпочтения по времени сдачи, пишите сегодня до 22 часов. Потом я поставлю тех, кто не написал, в оставшиеся слоты.

Правила сдачи экзамена.

В назначенное время выдаётся билет, форма которого определена в программе экзамена. До начала ответа студент может пользоваться любыми материалами для подготовки, при этом время на подготовку ограничено 60 минутами. Во время ответа отвечать нужно с чистого листа, делясь экраном компьютера. Во время сдачи должна быть включена камера. Пользоваться какими-либо материалами после начала ответа — запрещено. Преподаватель вправе задавать вопросы вне билета (без подробных доказательств).

Важно: время подготовки и ответа на билет ограничено 90 минутами. Так, выгоднее начинать отвечать раньше. Время на доп.вопросы и доп.задачи не регламентируется. В случае, если свободного принимающего нет, сроки сдвигаются на соответствующее время.

Завтра в 12:00 переписывание 1-й самостоятельной; в 12:45 — 2-й. Ссылка на зум: https://zoom.us/j/93972409063?pwd=c001Q1BIOG4xdFRIUDkxWUlLUGtrUT09.

При наличии справок — присылайте их в лс @irkstepanov

Уважаемые студенты!
В пятницу, 15-го января, мы проведём переписывание самостоятельных работ. Пропустившие по уважительной причине могут переписать без штрафа (но только при предоставлении справки или заблаговременном предупреждении семинариста). Остальные могут переписать с умножением результата на 0.5, при этом старый результат забывается, ДАЖЕ если он окажется лучше.

Исправлена программа экзамена (подсчёт числа изоморфизмов заменён на поиск одного).

Готов файл со второй дорешкой. Принимается до дня перед экзаменом. Также окончательно зафиксирован коэффициент для семестровой оценки - как есть.

Доделана программа экзамена. Она слегка уменьшена по сравнению с прошлым годом: список классов немного уменьшен, теорем и задач по 28 вместо 32. В четверг, 14 января, можно будет устроить консультацию.

Решения отправляйте своему семинаристу до 12:40.
Мусатов: телеграм
Гришутин: grishutin.ai@phystech.edu
Ишкуватов: ruslan.ishkuvatov@phystech.edu
Голованов: телеграм
Степанов: irkstepanov@gmail.com
Сапожников: телеграм