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

Информация по зачёту для студентов магистратуры блокчейн. Я получил одобрение на его выставление вплоть до конца экзаменов. Так что можно будет сдавать теоропрос либо на неделе 9-13 января, либо с основными экзаменами 21-24 января. Если оба варианта не подходят, пишите - попробуем согласовать другой вприант. Программу постараюсь сделать в начале следующей недели.

Рассадка в Б. Хим. на сегодня. Начинаем в 14:00, не опаздывайте. Левая часть: места 2-4 на рядах 1-12 и 1-4 на рядах 13-17 Средняя часть: места 5-6 на 1-м ряду и 5-8 на остальных Правая часть: места 9-11 на рядах 1-12 и 9-12 на рядах 13-17.

Контрольная пройдёт по той же схеме, что и первая. Примерно в 13 часов вывешу рассадку, не позже 14:00 постараюсь раздать работы. Будет выдан 1 лист с условием и 1 подписанный пустой лист, решения можно записывать на обоих, а также на своих пустых листах. Немного дополнительных листов тоже принесу. Пользоваться материалами и/или гаджетами нельзя. Если пропускаете по уважительной причине, пишите об этом до начала контрольной.

Прошёл срок выбора тем для проектов. В связи с этим прошу: * тех, кто ещё не выбрал тему проекта, но хочет его написать, определиться до завтрашнего вечера. Потом закрою редактирование листа с проектами. * тех, кто выбрал темы 0, 62, 67, 81, 93, указать конкретные спецификации, так чтобы каждая спецификация повторялась не более двух раз. Либо кому-то переключиться на другую тему, чтобы было не более 2 повторов. Проверяйте, кто ещё взял те же темы, и договаривайтесь друг с другом о разграничении спецификаций.

В табличке (https://docs.google.com/spreadsheets/d/1tU8AaboXrUVQmrWKz92vsEah1xvQ8dSC_fy4aNkSb0A/edit?usp=sharing) появилась вкладка "Проекты". Она должна быть доступна для редактирования по ссылке. Список тем будет выложен сегодня вечером. Но если у вас есть своя тема, можете уже записаться: отметьте 0 напротив своего имени в столбце C и впишите тему проекта в столбец D.

В рассадке была ошибка, теперь правильно.

Рассадка на сегодня (напоминаю, это Б.Хим.) Вам будет выдано по 2 подписанных листа: один чистый, другой с условием. Записывать решение можно и там, и там, условие сдавать не обязательно, если там ничего не писали. Дополнительные листы подготовьте при необходимости.

Ещё некоторые соображения по завтрашней контрольной: - Вариант будет сложнее тренировочного (т.к. некоторые задачи тренировочного взяты из самостоятельных, где было 4 задачи на полчаса) - Все задачи оригинальные - Предполагается, что отличный результат - это 4 задачи из 6, хороший - 2.5 - В нескольких задачах есть пункты, по которым явно прописаны баллы. Частичные решения оцениваются и приветствуются (в отличие от того, как было на логике) - Правила дорешки: если вы решаете задачу менее чем на 8 баллов, то получаете на дом похожую задачу и можете её решить не более чем на 5 баллов (или на 8, если пропустили по уважительной причине).

Готова табличка для будущих оценок: https://docs.google.com/spreadsheets/d/1tU8AaboXrUVQmrWKz92vsEah1xvQ8dSC_fy4aNkSb0A/edit?usp=sharing Пожалуйста, проверьте, что вы там есть, и напишите мне, если: - Вас там нет (особенно если вы из магистратуры блокчейн, тогда вас точно нет) - Вы не в той группе, с которой реально ходите на семинары - Есть какая-либо другая ошибка, например, в написании имени - Вы не придёте завтра по уважительной причине, но в графе "участие" (столбец U) стоит 1, в том числе если уже писали, а я не отметил Я примерно в 9 утра заберу данные, какие будут, для генерации вариантов, постарайтесь исправить до этого времени

Контрольная пройдёт завтра, с 14:00 до 15:20, в аудитории ❗Б.Хим. ❗Будет рассадка по местам, вывешу завтра. Постарайтесь прийти к 13:55, чтобы начать вовремя. Если пропускаете по уважительной причине, пишите мне до начала контрольной, можно будет делать дорешку из расчёта 8 баллов за задачу. Табличку с участниками вывешу позже, но если меняли группу или сдаёте как курс по выбору, тоже напишите мне об этом. Студентов с программы блокчейн прошу прислать список, кто курс сдаёт, а кто перезасчитывает.

Закреплённый пост со служебной информацией: Расписание: Лекции - среда, 13:55, 202 НК. Семинары и семинаристы: 020 - Голованов, чт, 10:45, 424 ГК 021 - Якунин, чт, 12:20, 204 УПМ 022 - Александров, вт, 10:45, 530 ГК 023 - Васильчишин, вт, 09:00, 409 ГК 024 - Степанов, чт, 15:30, 528 ГК 025 - Мусатов, чт, 15:30, 302 КПМ 026 - Якунин, чт, 13:35, 204 УПМ 027 - Александров, вт, 12:20, 530 ГК 028 - Смирнов, вт, 13:55, 418 ГК 029 - Букреев, чт, 10:45, 411 ГК Ресурсы для студентов: https://t.me/diht_complexity - этот канал https://t.me/+_zvpm0_mwVwwZThi - чат к каналу https://www.dropbox.com/sh/78k1vny4gy9bs9y/AADvsSaKxRWTtrrFIeCXgh7na?dl=0 - папка с материалами <Будет дополнено> - табличка для записи на проекты <Будет дополнено> - табличка с оценками за контрольные

А студентов кафедры ДМ, перешедших на 4-й курс, приглашаю в чат курса по криптографии: https://t.me/+RGQjj4R4Y4VcuJor

По итогам голосования и сопутствующих соображений решил попробовать прочесть спецкурс по задачам поиска. Кто хочет ходить, присоединяйтесь к чату https://t.me/+BsCLVBEcojw1NmYy, там и время обсудим.

В конце семестра не успели обсудить один вопрос, давайте обсудим сейчас, по крайней мере среди тех, кто на связи. Традиционно осенью я читаю продвинутый спецкурс по сложности вычислений для тех, кто хочет разобраться ещё глубже. Есть несколько возможных тем. В комментариях в чате я сейчас выложу примерные программы и сделаю неанонимный опрос (с выбором нескольких вариантов) о предпочтениях, а тут кратко напишу о содержании в разных вариантах. * Вероятностно проверяемые доказательства - основы теории экспандеров, полное доказательство PCP-теоремы и рассмотрение сложности приближения в конкретных задачах, роль Unique Game Conjecture. Предыдущий раз читался в 2017 году, так что можно обновить. * Псевдослучайность и дерандомизация - тоже основы теории экспандеров, генераторы псевдослучайных чисел, методы дерандомизации, теорема Рейнгольда (детерминированная проверка достижимости в графе на лог. памяти), почему мы верим, что P=BPP, и почему пока что не получилось этого доказать. Читался в 2018, 2019 и 2021 годах, но если будет интерес, то прочитаю снова. * Сложность задач поиска - подробное рассмотрение классов PPA, PPAD и других подклассов TFNP, доказательство полноты задач о неподвижных точках в PPAD, классификация некоторых других задач. Эту тему мы в этом году пропустили, такой курс я не читал никогда, но в последние годы многое изучил по этой теме, так что было бы интересно. * Рациональные интерактивные доказательства - доказательство теорем о классификации разных классов рациональных интерактивных доказательств. Мы эту тему сейчас тоже не прошли, суть в том, что верификатор платит пруверу деньги по какой-то просто вычисляемой формуле, а прувер максимизирует эту выплату и так выявляет нужную информацию. Курс читался один раз, в 2020 году.