|
Введение в теорию сложности
(6 сентября–6 декабря 2021 г., МИАН, комн. 430 (ул. Губкина, 8) + Zoom, г. Москва)
|
Курс посвящен теоретическим основам компьютерных наук. Будут рассмотрены основные сложностные классы, такие как P, NP, coNP, PSPACE, BPP, P/poly, будут разобраны понятия сводимости и полноты, будут показаны примеры полных задач для части из перечисленных классов. Ближе к концу курса будут рассмотрены дополнительные темы из теории сложности вычислений, такие как коммуникационная сложность и ее приложения к потоковым алгоритмам.
Расписание на осенний семестр 2021/2022 учебного года:
Время занятий: понедельник 10:00 – 11:25
Первое занятие: 6 сентября
 Руководитель семинара
Подольский Владимир Владимирович
Организации
Московский физико-технический институт (государственный университет), г. Долгопрудный, Московская обл.
Математический институт им. В.А. Стеклова Российской академии наук, г. Москва
Математический центр мирового уровня «Математический институт им. В.А. Стеклова Российской академии наук» (МЦМУ МИАН) |
|
| Введение в теорию сложности, г. Москва, 6 сентября–6 декабря 2021 г. |
|
|
6 декабря 2021 г. (пн) |
 |
| 1. |
Лекция 13. Введение в теорию сложности
В. В. Подольский
6 декабря 2021 г. 10:00, г. Москва, МИАН, комн. 430 (ул. Губкина, 8) + Zoom
|
|
|
|
|
|
29 ноября 2021 г. (пн) |
|
| 2. |
Лекция 12. Введение в теорию сложности
В. В. Подольский
29 ноября 2021 г. 10:00, г. Москва, МИАН, комн. 430 (ул. Губкина, 8) + Zoom
|
|
|
|
|
|
|
22 ноября 2021 г. (пн) |
|
| 3. |
Лекция 11. Введение в теорию сложности
В. В. Подольский
22 ноября 2021 г. 10:00, г. Москва, МИАН, комн. 430 (ул. Губкина, 8) + Zoom
|
|
|
|
|
|
|
15 ноября 2021 г. (пн) |
|
| 4. |
Лекция 10. Введение в теорию сложности
В. В. Подольский
15 ноября 2021 г. 10:00, г. Москва, МИАН, комн. 430 (ул. Губкина, 8) + Zoom
|
|
|
|
|
|
|
8 ноября 2021 г. (пн) |
|
| 5. |
Лекция 9. Введение в теорию сложности
В. В. Подольский
8 ноября 2021 г. 10:00, г. Москва, МИАН, комн. 430 (ул. Губкина, 8) + Zoom
|
|
|
|
|
|
|
25 октября 2021 г. (пн) |
|
| 6. |
Лекция 8. Введение в теорию сложности
В. В. Подольский
25 октября 2021 г. 10:00, г. Москва, МИАН, комн. 430 (ул. Губкина, 8) + Zoom
|
|
|
|
|
|
|
18 октября 2021 г. (пн) |
|
| 7. |
Лекция 7. Введение в теорию сложности
В. В. Подольский
18 октября 2021 г. 10:00, г. Москва, МИАН, комн. 430 (ул. Губкина, 8) + Zoom
|
|
|
|
|
|
|
11 октября 2021 г. (пн) |
|
| 8. |
Лекция 6. Введение в теорию сложности
В. В. Подольский
11 октября 2021 г. 10:00, г. Москва, МИАН, комн. 430 (ул. Губкина, 8) + Zoom
|
|
|
|
|
|
|
4 октября 2021 г. (пн) |
|
| 9. |
Лекция 5. Введение в теорию сложности
В. В. Подольский
4 октября 2021 г. 10:00, г. Москва, МИАН, комн. 430 (ул. Губкина, 8) + Zoom
|
|
|
|
|
|
|
27 сентября 2021 г. (пн) |
|
| 10. |
Лекция 4. Введение в теорию сложности
В. В. Подольский
27 сентября 2021 г. 10:00, г. Москва, МИАН, комн. 430 (ул. Губкина, 8) + Zoom
|
|
|
|
|
|
|
20 сентября 2021 г. (пн) |
|
| 11. |
Лекция 3. Введение в теорию сложности
В. В. Подольский
20 сентября 2021 г. 10:00, г. Москва, МИАН, комн. 430 (ул. Губкина, 8) + Zoom
|
|
|
|
|
|
|
13 сентября 2021 г. (пн) |
|
| 12. |
Лекция 2. Введение в теорию сложности
В. В. Подольский
13 сентября 2021 г. 10:00, г. Москва, МИАН, комн. 430 (ул. Губкина, 8) + Zoom
|
|
|
|
|
|
|
6 сентября 2021 г. (пн) |
|
| 13. |
Лекция 1. Введение в теорию сложности
В. В. Подольский
6 сентября 2021 г. 10:00, г. Москва, МИАН, комн. 430 (ул. Губкина, 8) + Zoom
|
|
|
|
|
|
|
Обратная связь: