Post #432
1.79K
compl-23-24-program.pdf236.1 KB
Готова программа курса этого года. Список тем написан с запасом, скорее всего будет меньше.
Channel Public Channel
СЛ Сложность вычислений ФПМИ
@diht_complexity
Новости курса "Сложность вычислений" для 3 курса ФИВТ МФТИ
- Subscribers
- 1.11K
- Photos
- 12
- Videos
- 0
- Links
- 160
Showing posts older than #433 · Back to latest
Older Posts 20 shown
Post #431
2.16K
Поздравляю с днём знаний! В этом семестре канал будет использоваться для очередного курса сложности вычислений у третьего курса ПМИ (кроме потока информатики). При желании можно остаться в канале и чате и помогать новым студентам.
А для тех, кто закончил курс и продолжит изучать различные сложностные курсы, вот ссылки на соответствующие чаты:
*️⃣ Криптография (обязательна в бакалавриате ДМ): канал https://t.me/fpmi_crypto (новый) и чат https://t.me/+RGQjj4R4Y4VcuJor Лекции по вторникам с 5 сентября в 12:25, семинары по понедельникам в 13:55 с 4 сентября
*️⃣ мой спецкурс "Псевдослучайность и дерандомизация" (описание см. выше) - чат https://t.me/+TFWCy-HlhfwGqZSe занятия по четвергам в 15:30 с 7 сентября
*️⃣ спецкурс Данилы Дёмина при моём участии "Изоморфизм графов" - чат https://t.me/+GiURflv_rt1lZGM6 На нём постараемся разобраться в алгоритме Бабаи, решающем задачу об изоморфизме графов за квазиполиномиальное время. Занятия по четвергам в 17:05, дата начала уточняется
*️⃣ спецсеминар под моим руководством "Игры и алгоритмы" - чат https://t.me/+VmejbREAJeE1YTRi Там в основном мои ученики рассказывают про свои исследования, иногда я тоже что-то рассказываю. Занятия по четвергам в 13:55, дата начала уточняется
Telegram Криптография ФПМИ Канал с новостями по курсу криптографии на ФПМИ МФТИ (параллельно для бакалавриата программы информатика, кафедры ДМ и магистратуры кафедры ТиПИ) А для тех, кто закончил курс и продолжит изучать различные сложностные курсы, вот ссылки на соответствующие чаты:
*️⃣ Криптография (обязательна в бакалавриате ДМ): канал https://t.me/fpmi_crypto (новый) и чат https://t.me/+RGQjj4R4Y4VcuJor Лекции по вторникам с 5 сентября в 12:25, семинары по понедельникам в 13:55 с 4 сентября
*️⃣ мой спецкурс "Псевдослучайность и дерандомизация" (описание см. выше) - чат https://t.me/+TFWCy-HlhfwGqZSe занятия по четвергам в 15:30 с 7 сентября
*️⃣ спецкурс Данилы Дёмина при моём участии "Изоморфизм графов" - чат https://t.me/+GiURflv_rt1lZGM6 На нём постараемся разобраться в алгоритме Бабаи, решающем задачу об изоморфизме графов за квазиполиномиальное время. Занятия по четвергам в 17:05, дата начала уточняется
*️⃣ спецсеминар под моим руководством "Игры и алгоритмы" - чат https://t.me/+VmejbREAJeE1YTRi Там в основном мои ученики рассказывают про свои исследования, иногда я тоже что-то рассказываю. Занятия по четвергам в 13:55, дата начала уточняется
Post #430
2.06K
Пока все ещё следят за каналом, давайте обсудим следующий семестр. Традиционно осенью я читаю продвинутый спецкурс по сложности вычислений для тех, кто хочет разобраться ещё глубже. Есть несколько возможных тем. В комментариях в чате я сейчас выложу примерные программы и сделаю неанонимный опрос (с выбором нескольких вариантов) о предпочтениях, а тут кратко напишу о содержании в разных вариантах.
* Вероятностно проверяемые доказательства - основы теории экспандеров, полное доказательство PCP-теоремы и рассмотрение сложности приближения в конкретных задачах, роль Unique Game Conjecture. Предыдущий раз читался в 2017 году, так что можно обновить.
* Псевдослучайность и дерандомизация - тоже основы теории экспандеров, генераторы псевдослучайных чисел, методы дерандомизации, теорема Рейнгольда (детерминированная проверка достижимости в графе на лог. памяти), почему мы верим, что P=BPP, и почему пока что не получилось этого доказать. Читался в 2018, 2019 и 2021 годах, но если будет интерес, то прочитаю снова.
* Сложность задач поиска - подробное рассмотрение классов PPA, PPAD и других подклассов TFNP, доказательство полноты задач о неподвижных точках в PPAD, классификация некоторых других задач. Эту тему мы в этом году пропустили, такой курс я читал в предыдущем (2022) году, при этом он вызвал такой интерес, что был продолжен и весной (правда, получилось провести не очень много занятий). Так что можно и повторить.
* Рациональные интерактивные доказательства - доказательство теорем о классификации разных классов рациональных интерактивных доказательств. Мы эту тему сейчас тоже не прошли, суть в том, что верификатор платит пруверу деньги по какой-то просто вычисляемой формуле, а прувер максимизирует эту выплату и так выявляет нужную информацию. Курс читался один раз, в 2020 году.
* Вероятностно проверяемые доказательства - основы теории экспандеров, полное доказательство PCP-теоремы и рассмотрение сложности приближения в конкретных задачах, роль Unique Game Conjecture. Предыдущий раз читался в 2017 году, так что можно обновить.
* Псевдослучайность и дерандомизация - тоже основы теории экспандеров, генераторы псевдослучайных чисел, методы дерандомизации, теорема Рейнгольда (детерминированная проверка достижимости в графе на лог. памяти), почему мы верим, что P=BPP, и почему пока что не получилось этого доказать. Читался в 2018, 2019 и 2021 годах, но если будет интерес, то прочитаю снова.
* Сложность задач поиска - подробное рассмотрение классов PPA, PPAD и других подклассов TFNP, доказательство полноты задач о неподвижных точках в PPAD, классификация некоторых других задач. Эту тему мы в этом году пропустили, такой курс я читал в предыдущем (2022) году, при этом он вызвал такой интерес, что был продолжен и весной (правда, получилось провести не очень много занятий). Так что можно и повторить.
* Рациональные интерактивные доказательства - доказательство теорем о классификации разных классов рациональных интерактивных доказательств. Мы эту тему сейчас тоже не прошли, суть в том, что верификатор платит пруверу деньги по какой-то просто вычисляемой формуле, а прувер максимизирует эту выплату и так выявляет нужную информацию. Курс читался один раз, в 2020 году.
Post #429
1.63K
Сложность вычислений ФПМИ К/р для тех, кто не писал 14-го, будет 22 июня в 15:00, аудитория 123 ГК. Возможно начало с опозданием, если затянется экзамен по логике, но вроде бы должны уложиться.
Давайте начало на 15:30 перенесём, предыдущий экзамен затягивается - не будет свободных мест в аудитории.
Post #428
1.64K
К/р для тех, кто не писал 14-го, будет 22 июня в 15:00, аудитория 123 ГК. Возможно начало с опозданием, если затянется экзамен по логике, но вроде бы должны уложиться.
Post #427
2.12K
compl-topics-hw-2-2023.pdf736.4 KB
Готово второе домашнее задание. В нём нет разницы по максимальному числу зачтённых задач со сделанным проектом и без него. Рекомендую посмотреть на задачи и решить, не хотите ли вы всё-таки написать проект. Запись ещё открыта. Срок сдачи задания пока не ставлю, принимаются предложения по нему.
Post #426
2.03K
compl-topics-projects-2023.pdf248.9 KB
Также я всё-таки сделал список проектов, приглашаю желающих выбрать себе тему на втором листе таблички: https://docs.google.com/spreadsheets/d/12ApZWYJQSgR4HAWgosn4kFy8u7V0wZqHZbNNYZ52b9M/edit?usp=sharing
Список составлен так: взяты осенние темы, которые никто на курсе не взял, также добавлен ряд новых, как по темам весеннего курса, так и других. Алгоритмических тем в списке в этот раз нет, но если придумаете что-нибудь отличное от осеннего списка, то можно сделать.
Проект ничего не блокирует, но позволяет заменить часть задач из домашки.
Список составлен так: взяты осенние темы, которые никто на курсе не взял, также добавлен ряд новых, как по темам весеннего курса, так и других. Алгоритмических тем в списке в этот раз нет, но если придумаете что-нибудь отличное от осеннего списка, то можно сделать.
Проект ничего не блокирует, но позволяет заменить часть задач из домашки.
Post #425
1.59K
compl-book.pdf9.1 MB
Выкладываю текущую версию книги. Что нового:
- почти написана первая обзорная глава, там много интересного материала
- почти написано доказательство экспоненциальной PCP-теоремы
- отдельные исправления ошибок и дополнения в других главах.
- почти написана первая обзорная глава, там много интересного материала
- почти написано доказательство экспоненциальной PCP-теоремы
- отдельные исправления ошибок и дополнения в других главах.
Post #424
1.61K
Сегодня, 4 мая, лекции тоже не будет - я в отъезде, провести онлайн нет возможности. 11 мая сделаем последнюю лекцию - думаю, доразберёмся с MIP=NEXP. Про рациональные доказательства можно сделать дополнительную лекцию 18-го, если будет запрос. В к/р этой темы не будет, но в домашку одну задачу включу.
Post #423
1.66K
Завтра, 27 апреля, лекции не будет - я уеду на конференцию в Сочи
Post #422
1.89K
compl-topics-hw-1-2023.pdf696.2 KB
Как и обещал, выкладываю первую домашку. В файле индивидуальные варианты. Если вас нет в списке, берите один из запасных в конце файла и сообщите мне. Там сказано про проекты, постараюсь их список тоже выложить сегодня-завтра. Проект можно сделать вместо решения части задач (примерно четырёх), итоговую оценку он не ограничивает. Срок сдачи в файле не написан, предлагаю 12 мая (это для задач, для проектов позже).
Post #421
1.57K
Сегодня постараюсь выложить первую домашку. Пока что сделал табличку для оценок, оттуда же буду брать данные для индивидуальных вариантов. Там сейчас только бакалавриат кафедры ДМ. Если вы из магистратуры или с другой кафедры и сдаёте курс, напишите мне имя и номер группы, чтобы я добавил.
Ссылка: https://docs.google.com/spreadsheets/d/12ApZWYJQSgR4HAWgosn4kFy8u7V0wZqHZbNNYZ52b9M/edit?usp=sharing
Google Docs ДМ: Сложность вычислений: дополнительные главы, весна 2023 Ссылка: https://docs.google.com/spreadsheets/d/12ApZWYJQSgR4HAWgosn4kFy8u7V0wZqHZbNNYZ52b9M/edit?usp=sharing
Post #420
1.78K
Завтра, 23 марта, занятия не будет - я уеду на всерос по экономике
Post #419
2.02K
Приглашаю поучаствовать в математическом квесте "Интеграл по городу", который пройдёт в Майкопе (Адыгея) и онлайн 11-12 марта. Суть квеста - поиск различных объектов в городе или в интернет-источниках (панорамах, фотосайтах и т.д.) и решение математических задач, данные для которых нужно найти на этих объектах. Задачи не используют высшую математику, так что доступны старшим школьникам - зовите друзей-нематематиков или младших братьев и сестёр (а половина заданий не требуют математики вообще).
11 марта будут короткие категории "Тьюринг" онлайн и "Евклид" в городе, начало в 15:30, окончание в 18:00. 12 марта - длинные категории "Колмогоров" онлайн и "Лобачевский" в городе, начало в 10:00, окончание в 18:30. Можно участвовать командами от 1 до 6 человек.
Подробности и регистрация по ссылке https://www.runcity.org/ru/events/maykop2023/
Участие стоит 961 рубль с команды или бесплатно по промокоду mipt. Если кто-то захочет добраться до Майкопа и понадобится помощь, пишите в личку.
11 марта будут короткие категории "Тьюринг" онлайн и "Евклид" в городе, начало в 15:30, окончание в 18:00. 12 марта - длинные категории "Колмогоров" онлайн и "Лобачевский" в городе, начало в 10:00, окончание в 18:30. Можно участвовать командами от 1 до 6 человек.
Подробности и регистрация по ссылке https://www.runcity.org/ru/events/maykop2023/
Участие стоит 961 рубль с команды или бесплатно по промокоду mipt. Если кто-то захочет добраться до Майкопа и понадобится помощь, пишите в личку.
Сложность вычислений ФПМИ pinned «Закреплённый пост со служебной информацией, весна 2023 Расписание: Лекции - четверг, 10:45-13:00, 113 ГК. Ресурсы для студентов: https://t.me/diht_complexity - этот канал https://t.me/+_zvpm0_mwVwwZThi - чат к каналу https://www.dropbox.com/sh/r46j99n2u…»
Post #417
1.86K
Закреплённый пост со служебной информацией, весна 2023
Расписание:
Лекции - четверг, 10:45-13:00, 113 ГК.
Ресурсы для студентов:
https://t.me/diht_complexity - этот канал
https://t.me/+_zvpm0_mwVwwZThi - чат к каналу
https://www.dropbox.com/sh/r46j99n2ujdfjhm/AADMtzp7AVXyX9oZWnZOGoNja?dl=0 - папка с материалами
Telegram Сложность вычислений ФПМИ Новости курса "Сложность вычислений" для 3 курса ФИВТ МФТИ Расписание:
Лекции - четверг, 10:45-13:00, 113 ГК.
Ресурсы для студентов:
https://t.me/diht_complexity - этот канал
https://t.me/+_zvpm0_mwVwwZThi - чат к каналу
https://www.dropbox.com/sh/r46j99n2ujdfjhm/AADMtzp7AVXyX9oZWnZOGoNja?dl=0 - папка с материалами
Post #416
1.54K
ZKP-for-children.pdf226.8 KB
Статья про нулевое разглашение для детей, про которую я говорил сегодня на лекции.
Post #415
1.29K
Сегодня будет вводная лекция, по крайней мере первую пару из полутора. На ней я неформально расскажу про основные темы курса, в том числе опишу решения таких задач:
1) Как убедить недоверчивого дальтоника, что в остальном одинаковые предметы имеют разный цвет.
2) Как гениальному археологу доказать назойливой прессе открытие древнего заклинания, не разгласив его.
3) Как записать математическое доказательство, чтобы для его проверки было достаточно прочесть лишь несколько битов, и при чём здесь задачи аппроксимации.
4) Как заставить жадного владельца облачного сервера проводить именно те вычисления, которые нужны клиенту.
Приходите, лекция уже скоро!
1) Как убедить недоверчивого дальтоника, что в остальном одинаковые предметы имеют разный цвет.
2) Как гениальному археологу доказать назойливой прессе открытие древнего заклинания, не разгласив его.
3) Как записать математическое доказательство, чтобы для его проверки было достаточно прочесть лишь несколько битов, и при чём здесь задачи аппроксимации.
4) Как заставить жадного владельца облачного сервера проводить именно те вычисления, которые нужны клиенту.
Приходите, лекция уже скоро!
Post #414
1.16K
Кто не сдавал экзамен, но хочет сдать, напишите мне в личку, выберем дату. Особенно если хотите сдавать в первой половине февраля.
Channel name was changed to «Сложность вычислений ФПМИ»