Теория алгоритмов 2MIT весна 2018 — различия между версиями
Материал из SEWiki
Lglinskih (обсуждение | вклад) (→Практика Глинских) |
Bliznets (обсуждение | вклад) (→Лекции) |
||
| Строка 6: | Строка 6: | ||
*20 февраля. Универсальная машина Тьюринга. Класс NP. | *20 февраля. Универсальная машина Тьюринга. Класс NP. | ||
*27 февраля. NP-полнота SAT. Иерархия по времени. Теорема Ладнера. | *27 февраля. NP-полнота SAT. Иерархия по времени. Теорема Ладнера. | ||
| + | *06 марта. Машины с оракульным доступом. Построение языка B, такого что <math>P^B \neq NP^B</math>. Сложность по памяти. | ||
| + | *13 марта. TQBF является PSPACE-полным. Теорема Савича. Задача обощенной географии является PSPACE-полной. | ||
| + | *20 марта. Классы NL, coNL. NL=coNL. NL-полный язык. | ||
| + | |||
'''Литература''' | '''Литература''' | ||
Версия 20:15, 19 марта 2018
Преподаватель: Близнец Иван Анатольевич (iabliznets@gmail.com)
Лекции
- 13 февраля. Машина Тьюринга.
- 20 февраля. Универсальная машина Тьюринга. Класс NP.
- 27 февраля. NP-полнота SAT. Иерархия по времени. Теорема Ладнера.
- 06 марта. Машины с оракульным доступом. Построение языка B, такого что . Сложность по памяти.
- 13 марта. TQBF является PSPACE-полным. Теорема Савича. Задача обощенной географии является PSPACE-полной.
- 20 марта. Классы NL, coNL. NL=coNL. NL-полный язык.
Литература
- Sanjeev Arora and Boaz Barak, Computational Complexity: A Modern Approach. скачать
http://theory.cs.princeton.edu/complexity/
Практика Близнец
Преподаватель: Близнец Иван Анатольевич
Результаты проверки ДЗ: смотреть
- 15 февраля, "Машина Тьюринга."
- 15 февраля, "Машина Тьюринга(ДЗ)."
- 20 февраля, "Класс NP."
- 20 февраля, "Класс NP(ДЗ)."
- 27 февраля, "Классы NP, coNP, иерархия по времени."
- 27 февраля, "Классы NP, coNP, иерархия по времени(ДЗ)."
- 06 марта, "Оракульные машины и PSPACE(ДЗ)."
- 13 марта, "PSPACE."
- 13 марта, "PSPACE(ДЗ)."
Практика Глинских
Преподаватель: Глинских Людмила (email: lglinskih at gmail dot com)
