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

Готова дорешка по второй контрольной, решать можно до экзамена, но лучше присылать хотя бы за день.

Досрочный экзамен пройдёт завтра в Долгопрудном, сбор в 10 у 123 ГК.

Программа экзамена

По поводу лекции 15 декабря общественное настроение понятно: будет философская беседа. Но приходите, раз уж проголосовали.

Тренировочный вариант второй контрольной наконец подготовлен. Контрольная пройдёт в семинарское время 15 и 19 декабря.

Чем занять лекционное время в пятницу, 15 декабря? (Это пока замер мнений, результат не будет обязывающим). anonymous poll Беседа про философские аспекты сложности вычислений – 20 👍👍👍👍👍👍👍 67% Контрольная для 599 группы и желающих из других групп – 4 👍 13% Обычная лекция (материал НЕ будет на экзамене) – 3 👍 10% Презентация проектов для желающих – 3 👍 10% 👥 30 people voted so far.

Дорешка изготовлена. По вашим заявкам задачи распределены случайно. Задачи упорядочены по студентам так же, как в табличке. Работает поичск по файлу. Некоторые сложные задачи повторяются с контрольной, кому-то может даже та же самая попасться, это нормально. Некоторые могут оказаться сильно сложнее, чем на контрольной, но случайное распределение должно всё сгладить. Срок сдачи я поставил перед 2-й контрольной (15/19 декабря). Конечно, группе 599 тоже можно сдавать до 19-го, но лучше всё-таки 15-го.

Каким методом выдавать дорешку? (Решится простым большинством по этому опросу). Распределить задачи случайно – 49 👍👍👍👍👍👍👍 92% Сделать список со свободным выбором (1 задача на группу) – 4 👍 8% 👥 53 people voted so far.

Результаты первой к/р. Дорешка скоро появится. https://docs.google.com/spreadsheets/d/1j3-DtAPnmXNbtRVOQOmyiknIJlNcL517B3Q37BdF95E/edit?usp=drivesdk

Во вторник, 28 ноября, в 18:30 в Актовом зале ЛК будет доклад Владимира Колмогорова "Complexity classifications of Valued Constraint Satisfaction Problems". Аннотация по ссылке https://mipt.ru/education/departments/fpmi/events/vladimir_kolmogorov Доклад будет про исследования последних 5 лет в theoretical computer science, имеющие важные приложения в компьютерном зрении. Так что если какая-то из этих тем вас интересует, то очень рекомендуется сходить и приобщиться.

Обновлённая информация: семинар и лекция в пятницу всё-таки отменятся, в связи с семейными обстоятельствами преподавателя. Рекомендуется потратить освободившееся время на работу над проектами. Или сходить на конференцию.

(Информация устарела, см. обновление ниже) Многие интересуются, состоятся ли занятия в пятницу. Формально они отменены, чтобы можно было сходить на пленарные доклады на конференции. Однако энтузиазма в студенческих массах (и среди лектора) по поводу конференции не наблюдается, поэтому занятия пройдут по расписанию. И семинар в 599 группе, и лекция. Будем изучать сложность задач подсчёта и класс #P. Посещение, разумеется, свободное, как и всегда.

Юмор пятничным вечером по теме сегодняшней лекции: почитайте отзывы на Амазоне о книге "Миллион случайных цифр": https://www.amazon.com/Million-Random-Digits-Normal-Deviates/product-reviews/0833030477/

Комментарий к опросу: в прошлые годы были задачи подсчёта и сложность в среднем, интерактивные доказательства и PCP будут в курсе допглав (в любом случае подробнее, чем за пару лекций), задачи поиска - на алгоритмической теории игр в магистратуре нашей кафедры, про дерандомизацию я раньше только на спецкурсе рассказывал.

Тем от обязательной части программы осталось примерно на 1-2 лекции, а самих лекций осталось 4. Какие темы было бы более интересно изучить на последних двух лекциях 1 и 8 декабря? anonymous poll Псевдослучайные конструкции и дерандомизация – 9 👍👍👍👍👍👍👍 35% Подсчёт сложности в среднем – 6 👍👍👍👍👍 23% Трудность задач аппроксимации и вероятностно проверяемые доказательства. – 5 👍👍👍👍 19% Задачи подсчёта подробно (теорема Тоды с доказательством и иерархия подсчёта) – 3 👍👍 12% Интерактивные доказательства – 3 👍👍 12% Задачи поиска (PPAD и др. классы) ▫️ 0% 👥 26 people voted so far.

Тренировочный вариант контрольной. Если от какой-либо группы будет консолидированное желание заменить на L и NL, сообщите.