|
Введение в теорию сложности
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, г. Москва, МФТИ - МИАН
|
|
|
|
|
|
|
Пользовательское соглашение