Рассадка на сегодня. Приходите к 13:55 в Актовый зал.

Подготовлена дорешка с индивидуальными вариантами по первой контрольной. Время на сдачу - 2 недели, до 16 декабря. Задачи, не бывшие на контрольной, оцениваются в 10 баллов, а бывшие - в 5, либо в 8 для пропустивших по уважительной причине. Эти баллы добавляются к оценке за к/р, однако сумма не может превысить 8.

А это вариант 2-й контрольной, который выдавался в среду.

Итоговое решение по третьей контрольной: для желающих она будет проводиться очно с задачами по 10 баллов, остальные получат задачи на дом по 8 баллов. Но нужно будет заявить о своём желании получить задачи на дом, для молчунов они будут по 5 баллов. Выбор скоро сделаем в табличке.

В табличке с оценками (https://docs.google.com/spreadsheets/d/1pOIEwQIhLC8v8JTX5Rk_By83tPb8cN-r75E02vVDr3Q/edit?usp=sharing) появился лист для выбора, как вы хотите написать 3-ю контрольную. Он доступен для редактирования, там выпадающее меню.
Если вы выбираете написать очно, то можно будет набрать 10 баллов за задачу на к/р и 5 баллов на дорешке. Если выбираете решить дома, то 8 баллов на дорешке. Если молчите, то просто 5 баллов на дорешке. Срок выбора до 11:00 18.12.
Сегодня постараемся также выложить вторую дорешку, тренировочный вариант 3-й к/р, зафиксировать шкалу перевода оценок за к/р в итоговую и составить программу экзамена.

Подготовлена дорешка по второй к/р. Можно сдавать до срока экзамена в вашей группе за вычетом двух дней.

Подготовлен тренировочный вариант 3-й к/р. Время и место пока уточняются, зависят от итогового числа записавшихся.

Напоминаю, что до 11:00 завтра нужно выбрать, хотите ли вы решать задачи из 3-й к/р в аудитории или дома. Можно менять свой выбор, если передумали. Сама контрольная будет в 13:55 в 202 НК. Параллельно будет устный приём задач по логике, надеюсь, он не помешает.

Это программа экзамена этого года (а также зачёта у магистров с потока блокчейн). Подробные правила приёма экзамена и выставления оценки за него внутри файла.
(Обновлено 18.12 в 11:12 - добавлена и затем исправлена точная формула расчёта итоговой оценки).

Также выкладываю последнюю версию своей книги. Для нашего курса релевантны первые 10 глав и немножко 11-я. Местами текст не дописан, но для подготовки к экзамену должно хватить. Если найдёте вопрос из программы, который совсем не освещён, напишите, постараюсь быстро добавить.

Третья контрольная проверена, дорешка тоже составлена, прикладываю. Экзамены будут уже на следующей неделе, так что я поставил срок сдачи 15:00 накануне экзамена, чтобы успеть проверить. Но в крайнем случае допринимаем устно перед выдачей билета.

Расписание экзаменов:
Вторник, 24.12, поточная Арктики - группы 220, 221, 222
Среда, 25.12, 113 ГК - группы 224, 226, 227
Магистры из 411 могут приходить в удобный день из этих двух.
Расписание захода сделаем позже, наверное, завтра.

Расписание захода задержалось, пока что поставил даты из академических групп. На листе "Дата экзамена" можно:
- выбрать дату, если вы из группы 411 (магистратура блокчейн)
- попросить о переносе даты (удовлетворение просьб не гарантируется, посмотрим по ситуации с количеством просьб и принимающих. Если причина уважительная, постараемся удовлетворить, но пишите мне в личку, в чём эта причина заключается)
- заявить, что на эту сдачу вы по какой-либо причине не придёте

Через пару часов я хотел бы составить время захода на завтра. Как обычно, чем выше текущая оценка за семестр, тем раньше будем звать. Начнём в 10 часов.

Про пересдачу осеннего курса: будет 2 возможности, в эту пятницу 14.02 и в понедельник 24.02. Оба раза утром, ориентировочно в 10. При необходимости сделаем ещё один день в марте. В табличке (https://docs.google.com/spreadsheets/d/1pOIEwQIhLC8v8JTX5Rk_By83tPb8cN-r75E02vVDr3Q/edit?usp=sharing) я пометил цветом, кто есть в списках на пересдачу. Пока что напишите мне в личку (@musatych), в какой из дней хотите прийти, в т.ч. если вас в списках по какой-то причине нет. Формальная запись для формирования ведомости тоже скоро будет. До пересдачи можно досдавать задачи из 2-й и 3-й домашки, которые не сдавались (в домашке) ранее, но в любом случае из расчёта 5 баллов за задачу.

В этом семестре канал и чат традиционно будут использоваться для курса дополнительных глав сложности вычислений. Это одновременно кафедральный курс для кафедры ДМ и курс по выбору в магистратуре. Но при желании можно и просто так ходить/сдавать. В этом файле приведена примерная программа курса, возможны изменения.

#дневниклекций
В этом семестре буду стараться записывать, что успели изучить на лекциях. Первая лекция 6 февраля была вводная. Мы прошли:
- неформальное объяснение, что такое интерактивное доказательство, на примере Боба-дальтоника и разноцветных носков
- неформальное объяснение, что такое доказательство с нулевым разглашением, на примере игры "Where's Waldo?" и судоку
- продолжение рассказа про нулевое разглашение: история про Али-Бабу, разбойника и Мика Али по мотивам статьи Кискатера и Гийю
- неформальное объяснение, что такое вероятностное проверяемое доказательство и его связь с задачами аппроксимации
- пара слов про доказательства с несколькими пруверами
- неформальный рассказ про игры Артура-Мерлина (интерактивные доказательства с общей случайностью), а также Артура и рационального Мерлина и их связь с облачными вычислениями
- несколько более формальный рассказ про интерактивный протокол для задачи о неизоморфизме графов

Выяснилось, что в программе была неправильная ссылка на чат. Вот правильная: https://yangx.top/+d7Y5C4MxnaRmZmM6

#дневниклекций
В прошлый раз, 13 февраля, на лекции прошли вот что (если что важное забыл перечислить, дополняйте):
- максимально общее определение интерактивной системы доказательств
- определение классов MA и AM
- амплификация в MA, вложение MA в AM.
- теорема о коллапсе AM-иерархии и теорема об ускорении: формулировки и идеи доказательства
- вложение MA и AM в полиномиальную иерархию: идея доказательства, формально наличие нужных сдвигов не доказывали
- протокол Голдвассер-Сипсера с общими случайными битами для задачи о неизоморфизме графов: идея сводимости к проверке размера множества и идея хеширования

Сегодня будем подробнее разбираться с этим протоколом, потом перейдём к IP=PSPACE

#дневниклекций
20 февраля подробно обсуждали протокол Голвассер-Сипсера:
- Повтор общей идеи
- Определение семейства попарно независимых хеш-функций. 2 эквивалентных формулировки.
- Обсуждение арифметики конечных полей. Построение поля размера 2^n: сложение и умножение по модулю неприводимого многочлена. О сложности поиска неприводимого многочлена.
- Построение семейства попарно независимых хеш-функций как аффинных функций в конечном поле
- Лемма о том, что ожидаемый размер образа под действием случайной хеш-функции не меньше 3/4 от размера исходного множества
- Построение протокола Голдвассер-Сипсера и доказательство его корректности

IP=PSPACE не успели, будет в следующий раз

Информация для пересдающих завтра осенний курс. Аудитория 520 ГК, начало в 10:00, рекомендуемое время захода есть в табличке. Если время не подходит или не отмечено, пишите в личку.