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

Поздравляю с началом нового учебного года! Рад приветствовать третьекурсников на курсе по сложности вычислений. Тех, кто уже прошёл курс, приглашаю при желании оставаться в чате и помогать младшим товарищам. Лекции будут проходить на платформе Гугл-Мит по ссылке https://meet.google.com/ina-nwod-way. Распространите среди тех, кто не подписан на этот канал, а лучше подпишите их. Ссылка постоянная. Запись будет. Первая лекция сегодня в 13:55.

В итоге осенью будет спецкурс про рациональные доказательства. Кто заинтересован его слушать, присоединяйтесь к чату https://t.me/joinchat/DZlFTVfC3Wo-3aq4ym4YzA Программы пока нет, но к началу курса постараюсь сделать. Хотя что-то и по ходу можно будет варьировать.

В опросе про спецкурс пока что с отрывом лидируют рациональные доказательства. Новых голосов долго не поступало. Так что предлагаю утвердить. А про другие темы ещё успею прочесть в другие годы.

Проверка окончена. Определены пороги на оценки: 125 - 10 баллов 114 - 9 баллов 100 - 8 баллов 90 - 7 баллов 80 - 6 баллов 70 - 5 баллов 59 - 4 балла 47 - 3 балла Поскольку с меня оценки уже срочно просят, я их сейчас выставлю, а если вы захотите апеллировать и успешно это сделаете, заполню отдельный отрывной.

Пока домашки постепенно проверяются, предлагаю обсудить следующий семестр. Традиционно осенью я читаю продвинутый спецкурс по сложности вычислений для небольшой аудитории. Предлагаю по ссылке https://doodle.com/poll/duvk22hfs36e3xke записаться желающим ходить и выбрать тему. Можно выбирать несколько тем или отмечать вариант "наполовину", кликнув на него два раза. Варианты курсов (если нужны подробности, пишите в чате): 1) Вероятностно проверяемые доказательства. Полное доказательство PCP-теоремы (для этого нужно будет изучить теорию экспандеров), связь с аппроксимацией различных задач оптимизации, в том числе Unique Game Conjecture. 2) Псевдослучайность и дерандомизация. Различные псевдослучайные объекты (в том числе те же экспандеры), обоснование гипотезы BPP=P (генератор Нисана-Вигдерсона, Hardness vs Randomness). Этот курс я читал последние 2 года, так что он будет выбран только при большом перевесе. 3) Вычислительные задачи поиска. Подробно про классы задач поиска (PPAD и другие), связь с теорией игр и экономическими моделями. 4) Рациональные интерактивные доказательства. Подробно про системы доказательств с прувером или пруверами, максимизирующими награду. Доказательство теорем о равенстве соответствующих классов.

Немного о том, как выглядит сегодняшний экзамен: - Экзамен рассчитан на 3 часа, с 15 до 18 - Можно пользоваться любыми материалами, в т.ч. электронными и поиском в интернете, но нельзя общаться за исключением зум-конференции и телеграм-чата. - В итоговый вариант включены вопросы на 95 баллов, но скорее всего больше 60 будет трудно успеть набрать. Выбирайте вопросы по тем темам, которые больше нравятся. - 3 задачи общей стоимостью 23 балла требуют записи решения - Остальные требуют только ответа и бывают такого типа: — упорядочить сложностные классы по вложению. Оценивается пропорционально числу верно указанных мест для классов — классифицировать данную задачу (выбрать минимальный класс из предложенных, в который она входит) — выбрать из списка верные вариации определения того или иного класса или верные утверждения из предложенных. Тут за каждый верный ответ даются положительные баллы, за каждый неверный отрицательные. Если не отметить ничего, будет 0, если отметить всё, то тоже будет 0. В минус сумма не уходит. — задачи с числовым ответом. В условии сказано, с какой точностью нужно ввести ответ, за меньшую точность могут даваться частичные баллы. — несколько вопросов, не укладывающиеся в эту классификацию Экзамен будет происходить через видеоконференцию Zoom по ссылке https://us02web.zoom.us/j/84512195906?pwd=aVY2a0hkODlQWDdERVcrek1ma0JGZz09, выполнять задания надо в LMS. Идентификатор конференции: 845 1219 5906 Пароль: 500287 Конференция откроется с 14:45, экзамен в LMS автоматически откроется в 15.

Поскольку у меня 8-го утром будет ещё один экзамен и учитывая результаты опроса, я поставил начало контрольной 8 июня на 15 часов. Я сделал в LMS отдельную группу для написания контрольной и внёс туда всех, кто есть в ведомости, кроме Михаила Бочко, которого почему-то нет в системе. Если вы хотите писать к/р, но не попали в группу, пишите. Также я сделал возможность загрузить домашнее задание в LMS, и это предпочтительный вариант. Дедлайн - 23:59 9 июня, потом по 1 баллу штрафа за каждый час опоздания. Сама контрольная будет состоять из большого количества несложных вопросов, требующих выбора из вариантов ответа или короткого/числового ответа, а также из 2-3 задач, требующих записи решения. Максимально возможное число баллов будет порядка 80, время на выполнение - 3 часа.

Сегодня последняя лекция, всё как в прошлый раз. Продолжим говорить про классы задач поиска и связь с теорией игр. Начало в 10 часов.

Сегодня встреча по адресу https://meet.google.com/qem-ywws-ony. Доска использоваться не будет, продолжим идти по презентации. начнём через 5 минут

Напоминаю про ссылки на встречу https://meet.google.com/qem-ywws-ony и доску https://idroo.com/board-wXXr93o1cX. Начало сегодня в 10, будем доказывать связь рациональных доказательств с иерархией подсчёта. Другие темы я подробно не подготовил, так что если успеем пройти раньше, то начнём задачи поиска.