Теория алгоритмов 2MIT весна 2018

Преподаватель: Близнец Иван Анатольевич (iabliznets@gmail.com)

Лекции

13 февраля. Машина Тьюринга.
20 февраля. Универсальная машина Тьюринга. Класс NP.
27 февраля. NP-полнота SAT. Иерархия по времени. Теорема Ладнера.
06 марта. Машины с оракульным доступом. Построение языка B, такого что $P^B \neq NP^B$ . Сложность по памяти. pdf.
13 марта. TQBF является PSPACE-полным. Теорема Савича. Задача обощенной географии является PSPACE-полной. pdf.
20 марта. NL-полный язык. Определение класса NL помощью сертификата. NL=coNL. pdf.
27 марта. Полиномиальная иерархия. $Ntime[n] \not\subset TISP[n^{1.2},n^{0.2}]$ . pdf.
03 апреля. Вероятностный алгоритм для минимального разреза. Вероятностный $O^*(4^k)$ алгоритм для наибольшего леса. Теорема Адлемана об избыточности случайных бит в схемах. pdf.
10 апреля. Уменьшение ошибки в RP алгоритме(попарно независимые множества). Задача о стабильном паросочетании за $n\ln{n}+cn$ . pdf.
17 апреля. Оценки Чернова. Вероятностный приближенный алгоритм для Wiring problem. pdf.
24 апреля. Путь с логарифмической памятью. pdf.
25 апреля. Схемы. pdf.
08 мая. $BPP \subseteq P_{/poly}$ и $BPP \subseteq \Sigma^p_2$ . Теорема Вэлианта-Вазирани. pdf.
15 мая Котрольная работа. part I, part II

Вопросы к экзамену

Список вопросов

Литература

Sanjeev Arora and Boaz Barak, Computational Complexity: A Modern Approach. скачать

http://theory.cs.princeton.edu/complexity/

Rajeev Motwani and Prabhakar Raghavan, Randomized Algorithms.
Michael Sipser, Introduction to the Theory of Computation.

Различные видео материалы(материалы для полезной прокрастинации)

P vs. NP and the Computational Complexity Zoo смотреть
Crach course in Computer Science(в первых видео рассказывается история возникновения компьютеров, становится более понятно почему же машина Тьюринга или схема имеют что-то общее с компьютером) смотреть
Видеолекции похожего курса смотреть