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

В силу ряда причин мы немного поменяли местами части курса (возможно, это скажется и на итоговом наборе тем). В первой половине будут только темы, связанные с практически реализуемыми алгоритмами. А именно, мы поговорим про алгоритмы на логарифмической памяти (детерминированные и недетерминированные) и про вероятностные алгоритмы. Во второй половине мы будет рассказ о классах шире, чем NP: полиномиальной иерархии, полиномиальной памяти и др. Также в какой-то момент будет рассказ про схемы из функциональных элементов (там есть и реализуемые, и недостижимые классы).

В осеннем семестре 2020 года Константин Макарычев устраивает курс лекций Advanced Algorithms (примерно по программе своего аспирантского курса в Northwestern University - но на русском языке). Будут регулярно выкладываться видеолекции. Кроме того, Илья Разенштейн и Александр Шень (если будет хотя бы несколько желающих) будут проводить занятия по материалам этих лекций регулярно, начиная со следующей недели. Ссылка на очередную порцию видеолекций и задачи для обсуждения на семинарах будут выкладываться на сайте CSC по понедельникам (окончательный день для обсуждений будет согласован со слушателями) https://www.advancedalgorithms.com/ru_prelim - ссылки на видеолекции как таковые. https://compsciclub.ru/courses/advancedalgorithms/2020-autumn/ страница курса в Computer Science Center (которые согласились поддерживать присылку заданий, коммуникацию и т.п.) До конца года будет 10 недель (и соответственно 10 занятий). В конце для желающих будет устроен экзамен.

И видеозапись: https://drive.google.com/file/d/1VGzgRsd9QA7hzyc0KIfoeLlFo3V0Kf26/view?usp=sharing

Курс по доказуемости в итоге будет по вторникам с 14:30 до 16:00. Первая лекция завтра онлайн, потом планируется офлайн с трансляцией. Регистрация на курс вот тут: http://www.mathnet.ru/php/conference.phtml?option_lang=rus&eventID=28&confid=1834

Семинар в группе 823 сегодня будет онлайн. Если вы хотите его посетить, присоединяйтесь в 15:30 к https://meet.google.com/sum-ypuc-yyd?hs=122&authuser=1 Запись тоже планируется.

https://drive.google.com/file/d/1KoCQGzI7UB2R8DCe2BbAc4-vlJdBypbt/view?usp=sharing - запись сегодняшней лекции

Напоминаю ссылку, по которой будет лекция: https://meet.google.com/ina-nwod-way Традиционная просьба для тех, кто не с физтеховского аккаунта, не опаздывать

Обратите внимание на перестановку семинаров (и преподавателей) в 823 и 824 группах. Не запутайтесь! При желании можно остаться у прежнего преподавателя, конечно.

https://drive.google.com/file/d/1Igi8sjB_vSHReLGTt2s0Y6iN3CQ0MNhs/view?usp=sharing - запись сегодняшней лекции

Напоминаю, что сегодня будет лекция про проблему "P=NP?" Начало в 13:55 по ссылке https://meet.google.com/ina-nwod-way Если будете слушать не с аккаунта phystech.edu, пожалуйста, не опаздывайте, подключайтесь с 13:50.

Институт математики им. Стеклова и МФТИ открывают базовую кафедру, в рамках которой будет читаться линейка алгоритмических курсов. Вот список курсов и расписание: пн 10:00 — 11:25: «Теория чисел» (лектор М.Р. Габдуллин) пн 11:30 — 12:55: «Доказуемость и формальная арифметика» (лекторы Л.Д. Беклемишев и Т.Л. Яворская) вт 13:35 — 15:00: «Сложность вычислений» (лектор В.В. Подольский, курс общий с «квантовой» линейкой) вт 15:00 — 16:25: «Геометрическая теория групп» (лектор И.Г. Лысёнок) вт 17:45 — 19:15: «Сходимость случайных процессов» (лектор В.И. Афанасьев) Курсы планируются онлайн, некоторые могут быть офлайн в здании МИАН (м. Академическая). Курсы Беклемишева/Яворской и Подольского точно должны быть очень интересными. Подробности можно узнать у куратора программы Степана Кузнецова по адресу sk(собака)mi-ras.ru. О возможностях перезачёта в физтехе можно договориться в индивидуальном порядке. Про зачёт курса Подольского вместо какой-то части моего будет централизованное решение в течение недели.