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