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

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

Лекции

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

Литература

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

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

• Rajeev Motwani and Prabhakar Raghavan, Randomized Algorithms.

Практика Близнец

Преподаватель: Близнец Иван Анатольевич

Результаты проверки ДЗ: смотреть

• 15 февраля, "Машина Тьюринга."
• 15 февраля, "Машина Тьюринга(ДЗ)."
• 20 февраля, "Класс NP."
• 20 февраля, "Класс NP(ДЗ)."
• 27 февраля, "Классы NP, coNP, иерархия по времени."
• 27 февраля, "Классы NP, coNP, иерархия по времени(ДЗ)."
• 06 марта, "Оракульные машины и PSPACE(ДЗ)."
• 13 марта, "PSPACE."
• 13 марта, "PSPACE(ДЗ)."
• 20 марта, "Класс NL."
• 20 марта, "Класс NL(ДЗ)."
• 20 марта, "Класс NL(ДЗ+подсказки)."
• 27 марта, "Полиномиальная иерархия."
• 27 марта, "Полиномиальная иерархия (ДЗ)."
• 27 марта, "Полиномиальная иерархия (ДЗ+подсказки)."
• 3 апреля, "Вероятностные алгоритмы. Вероятностные классы."
• 3 апреля, "Вероятностные алгоритмы. Вероятностные классы(ДЗ)."
• 10 апреля, "Предыдущие задачи(ДЗ)."
• 10 апреля, "Предыдущие задачи+подсказки(ДЗ)."
• 17 апреля, "Оценки Чернова."
• 17 апреля, "Оценки Чернова. Элементы линейного программирования(ДЗ)."
• 24 апреля, "Путь. Увеличение вероятности."
• 26 апреля, "Схемы."
• 26 апреля, "Схемы(ДЗ)."

Практика Глинских

Преподаватель: Глинских Людмила (email: lglinskih at gmail dot com)

Табличка

Домашнее задание к практике 1

Домашнее задание к практике 2

Домашнее задание к практике 3

Домашнее задание к практике 4

Домашнее задание к практике 5

Домашнее задание к практике 6

Домашнее задание к практике 7

Домашнее задание к практике 8

Домашнее задание к практике 9 и 10

Домашнее задание к практике 11 и 12