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

Традиционно в весеннем семестре этот канал используется для новостей по курсу "Сложность вычислений: дополнительные главы". Этот курс обязательный для кафедры ДМ, а также входит в пул курсов по выбору в магистратуре ИВТ. Но можно его взять и просто как факультатив. В этом году будут и лекции (читаю я), и семинары (ведёт Илья Степанов), по четвергам в 10:45 и 12:20, соответственно, всё в 202 НК. Сегодня будет две лекции, в следующий раз - 2 семинара. Начало сегодня, так что до скорой встречи!

В табличке появился столбец "Дата экзамена" и отдельный лист для запросов о переносе. Перенос гарантируется в таких случаях: - вы из группы блокчейн, тогда можете сдавать в любой день - вы перешли на семинары в другую группу, но хотите сдавать по графику своей - вы нашли, с кем поменяться В остальных случаях перенос не гарантируется, но можете написать свою причину на листе или мне лично.

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

Третья к/р пройдёт 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, Актовый зал. Если пропускаете по уважительной причине, сообщите до начала контрольной.

❗️В следующую среду, 29 ноября, в 13:55, вместо лекции будет вторая контрольная работа. Место - Актовый зал, как и у первой. Темы задач: * Классификация в полиномиальной иерархии * Полнота на втором уровне полиномиальной иерархии * Полнота в PSPACE * Доказательство принадлежности к L * Принадлежность и полнота в NL * Диагонализация * (только д/з) Случайные оракулы Формальный тренировочный вариант подготовим в ближайшее время. По третьей к/р, вероятнее всего, сделаем выбор: либо написать на зачётной неделе с оценкой в 10 баллов на к/р и 5 в дорешке, либо решать дома с оценкой в 8 баллов. (Т.е. любая причина пропуска будет уважительной).

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

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