Введение в теорию сложности 15 сентября–29 декабря 2020 г., МФТИ - МИАН, г. Москва
Курс посвящен теоретическим основам компьютерных наук. Будут рассмотрены основные сложностные классы, такие как P, NP, coNP, PSPACE, BPP, P/poly, будут разобраны понятия сводимости и полноты, будут показаны примеры полных задач для части из перечисленных классов. Ближе к концу курса будут рассмотрены дополнительные темы из теории сложности вычислений, такие как коммуникационная сложность и ее приложения к потоковым алгоритмам.
RSS: Ближайшие семинары
Руководитель семинара
Подольский Владимир Владимирович
Организации
Московский физико-технический институт (государственный университет), г. Долгопрудный, Московская обл. Математический институт им. В.А. Стеклова Российской академии наук, г. Москва |
|
Введение в теорию сложности, г. Москва, 15 сентября–29 декабря 2020 г. |
|
|
3 ноября 2020 г. (вт) |
 |
1. |
Занятие 7. NP-полнота следующих задач: NAE-3-SAT, 3-COL, SUBSET-SUM, CLIQUE, VERTEX-COVER В. В. Подольский 3 ноября 2020 г. 16:15, г. Москва, МФТИ - МИАН
|
|
|
|
|
|
27 октября 2020 г. (вт) |
 |
2. |
Занятие 6. Соотношение между классами P и P/poly. Задача CIRCUIT-SAT, ее NP-полнота. Задача 3-SAT, ее NP-полнота. Задача IND-SET, ее NP-полнота В. В. Подольский 27 октября 2020 г. 16:15, г. Москва, МФТИ - МИАН
|
|
|
|
|
|
20 октября 2020 г. (вт) |
 |
3. |
Занятие 5. Булевых схемы. Примеры: сложение, умножение, связность. Верхняя и нижняя оценки сложности вычисления булевых функций булевыми схемами В. В. Подольский 20 октября 2020 г. 16:15, г. Москва, МФТИ - МИАН
|
|
|
|
|
|
13 октября 2020 г. (вт) |
 |
4. |
Занятие 4. Класс NP, примеры. Соотношение с классами P и PSPACE. Недетерминированные машины Тьюринга, второе определение класса NP, эквивалентность определений. Полиномиальные сводимости, их основные свойства. NP-трудность и NP-полнота, их основные свойства В. В. Подольский 13 октября 2020 г. 16:15, г. Москва, МФТИ - МИАН
|
|
|
|
|
|
6 октября 2020 г. (вт) |
 |
5. |
Занятие 3. Теоремы об иерархии по времени и по памяти В. В. Подольский 6 октября 2020 г. 16:15, г. Москва, МФТИ - МИАН
|
|
|
|
|
|
29 сентября 2020 г. (вт) |
 |
6. |
Занятие 2. Связь одноленточных и многоленточных машин Тьюринга. Универсальная машина Тьюринга. Вычисления с ограничением на время и память. Классы P, PSPACE, EXP. Примеры полиномиально вычислимых функций и полиномиально разрешимых языков В. В. Подольский 29 сентября 2020 г. 16:15, г. Москва, МФТИ - МИАН
|
|
|
|
|
|
22 сентября 2020 г. (вт) |
 |
7. |
Занятие 1. Машины Тьюринга, вычисление функций на машинах Тьюринга, лемма об очистке мусора, многоленточные машины Тьюринга В. В. Подольский 22 сентября 2020 г. 16:15, г. Москва, МФТИ - МИАН
|
|
|
|
|
|
15 сентября 2020 г. (вт) |
 |
8. |
Занятие 0. Устройство курса правила оценивания. Краткий обзор основ сложности вычислений. Классы с ограничением на память. Класс PSPACE, его свойства. Задача TQBF является PSPACE-полной. PSPACE=NPSPACE В. В. Подольский 15 сентября 2020 г. 16:15, г. Москва, МФТИ - МИАН
|
|
|
|
 |
|