Вторник, 14 сентября, 18:30. "Теория сложности вычислений" (Д.М. Ицыксон, С.И. Грязнов)

[Alexander V. Smal]

Добрый день!

На следующей неделе во вторник 14 сентября начинается первый курс
осеннего семестра Computer Science клуба "Теория сложности
вычислений".
https://compsciclub.ru/courses/computationalcomplexity/2021-autumn/
Лекции читает Д.М. Ицыксон (ПОМИ РАН), семинары - С.И. Грязнов (ПОМИ РАН)

Курс будет читаться еженедельно по вторникам в онлайн формате:
18:30 - лекция, 20:00 - семинар.

Все занятия будут проходить в Zoom. Ссылка для подключения будет
опубликована в новостях курса - её получат те, кто запишется на курс.
Участие в лекциях бесплатно и открыто для всех.

Аннотация:

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

Курс будет излагаться на математическом уровне строгости, однако не
требует специфических математических знаний, выходящих за рамки
программ первых двух курсов технических специальностей (алгебра,
математический анализ, основы дискретной математики, и основы теории
вероятностей).

Саша

--
Alexander V. Smal
St. Petersburg Department of Steklov Mathematical Institute
27 Fontanka, St. Petersburg, 191023, Russia