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

Третья к/р оказалась проверена быстрее второй, так что готова дорешка к ней. Срок - 2 суток до вашего экзамена (но лучше раньше).

Программа устного экзамена (а также теоропроса к зачёту для группы магистров). Подробные правила внутри.

Листочки последних семинаров

Формальный тренировочный вариант к завтрашней контрольной и будущей домашке. Напоминаю, до начала к/р нужно отметиться, будете ли вы её писать очно (задачи по 10 баллов) или сдавать домашние задачи по 8 баллов.

Третья к/р пройдёт 20.12 в 13:55 в Б.Хим. На ней будут даны 4 задачи по 10 баллов. Можно пропустить по любой причине, тогда задачи перейдут в дорешку по 8 баллов. Если же вы пишете к/р, то дорешка будет по 5 баллов, как обычно. Прошу выбрать, придёте ли вы на к/р, на третьем листе в табличке: https://docs.google.com/spreadsheets/d/1v4gljniA57DAP2trZHRCF6TrG1VPk5OuxpdSulOfhBw/edit?usp=sharing Если будет много желающих писать, которые не могут прийти, что-нибудь придумаем. Варианты сделаю на тех, кто придёт, плюс немного запасных

Темы задач (формальный тренировочный вариант постараюсь выложить завтра утром):
* Вариации P/poly (конкретные полиномы и т.д.)
* Классификация в NC-иерархии
* Несложная задача про вероятностные классы (модификация языка из одного класса лежит в том же ли другом заданном классе)
* Дерандомизация (методом УМО или k-независимости на выбор)
Будет ещё 2 задачи только на дом:
* Вероятностные классы с неравномерной монеткой
* NP-трудные задачи подсчёта (не было в курсе, нужно разобраться самостоятельно)

Рассадка на сегодня. Актовый зал в ЛК, по 7 мест с каждой стороны от прохода. Приходите к 13:55, до того же времени принимаются сообщения об уважительном пропуске.

https://docs.google.com/spreadsheets/d/1v4gljniA57DAP2trZHRCF6TrG1VPk5OuxpdSulOfhBw/edit#gid=0 - в табличке открыты поля до конца семестра. В том числе в столбце CM есть предварительная оценка за семестр. Формула может немного поменяться в любую сторону, но вряд ли сильно. Сейчас она такая (нелинейная): 1 балл итоговой оценки ставится за 36 баллов за к/р+д/з, 2 балла за 80, 3 балла за 132, 4 балла за 192, в промежутках линейная интерполяция. К этому будет добавлено число баллов за проект (0-12), поделённое на 5, и число баллов за экзамен (0-10), поделённое на 2. Потом всё это округлится вниз до целого и это будет итоговая оценка (при условии, что экзамен хотя бы на 3).

Напоминаю, что завтра будет контрольная - 13:55, Актовый зал. Если пропускаете по уважительной причине, сообщите до начала контрольной.

Задачи к 13-му семинару

Вот тренировочный вариант к к/р на следующей неделе.

❗️В следующую среду, 29 ноября, в 13:55, вместо лекции будет вторая контрольная работа. Место - Актовый зал, как и у первой.

Темы задач:
* Классификация в полиномиальной иерархии
* Полнота на втором уровне полиномиальной иерархии
* Полнота в PSPACE
* Доказательство принадлежности к L
* Принадлежность и полнота в NL
* Диагонализация
* (только д/з) Случайные оракулы

Формальный тренировочный вариант подготовим в ближайшее время.

По третьей к/р, вероятнее всего, сделаем выбор: либо написать на зачётной неделе с оценкой в 10 баллов на к/р и 5 в дорешке, либо решать дома с оценкой в 8 баллов. (Т.е. любая причина пропуска будет уважительной).

Задачи к 10—12 семинарам

По поводу проектов: ряд номеров (в настоящий момент 66, 68, 72, 82, 86) выбраны с превышением квоты на число студентов на проект, при этом нет никаких явно указанных спецификаций. Если у вас один из этих номеров, то нужно сделать одно из двух: либо договориться, кто из троих выберет другой номер, либо написать явно спецификации, так чтобы подтемы были разными. Лист выбора проектов пока что открыт на редактирование, так что можно ещё выбрать проект, но тоже без превышения квоты, либо с соблюдением правил такого превышения. В конце недели выбор проектов закроется, если останутся превышения квот без комментариев, то будут проанализированы по истории изменений, и последняя по времени запись аннулирована.

Готова дорешка по первой к/р. В нй задачи по 8 темам - всем, что были в к/р хотя бы у одной группы. Число баллов за задачу написано в файле и в табличке. Срок сдачи поставлен на 22 ноября - через 2 недели с небольшим.

Задачи к 9-му семинару

Я тут ещё немного дописал и перекомпилировал compl-book, сделал 3 варианта по размеру шрифта: 10pt, 11pt и 12pt. Давайте я их сейчас выложу в комментариях, а вы посмотрите, как вам лучше читается. Я тогда дальнейшие версии буду в выбранном формате выкладывать.