Просмотр исходного текста страницы Теория алгоритмов 2MIT весна 2018

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

== Лекции ==

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


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

[[Медиа:AlgTh-Questions.pdf|Список вопросов]]

'''Литература'''

* Sanjeev Arora and Boaz Barak, Computational Complexity: A Modern Approach. [http://theory.cs.princeton.edu/complexity/book.pdf скачать]
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  [https://www.youtube.com/watch?v=YX40hbAHx3s смотреть]
* Crach course in Computer Science(в первых видео рассказывается история возникновения компьютеров, становится более понятно почему же машина Тьюринга или схема имеют что-то общее с компьютером) [https://www.youtube.com/watch?v=tpIctyqH29Q&list=PL8dPuuaLjXtNlUrzyH5r6jN9ulIgZBpdo смотреть]
* Видеолекции похожего курса [http://lectoriy.mipt.ru/course/Maths-ComputationalComplexity-14L#lectures смотреть]

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

Результаты проверки ДЗ: [https://docs.google.com/spreadsheets/d/1Jf40tlFPqN0pkEq7TnD651xIob_ly79RJ7HjayYbhqk/edit?usp=sharing смотреть]

*[[Медиа:AlgTh-class-1.pdf|15 февраля, "Машина Тьюринга."]]
*[[Медиа:AlgTh-home-1-fixed.pdf|15 февраля, "Машина Тьюринга(ДЗ)."]]
*[[Медиа:AlgTh-class-2.pdf|20 февраля, "Класс NP."]]
*[[Медиа:AlgTh-home-2.pdf|20 февраля, "Класс NP(ДЗ)."]]
*[[Медиа:AlgTh-class-3.pdf|27 февраля, "Классы NP, coNP, иерархия по времени."]]
*[[Медиа:AlgTh-home-3-fix.pdf|27 февраля, "Классы NP, coNP, иерархия по времени(ДЗ)."]]
*[[Медиа:AlgTh-home-4.pdf|06 марта, "Оракульные машины и PSPACE(ДЗ)."]]
*[[Медиа:AlgTh-class-5-fixed.pdf|13 марта, "PSPACE."]]
*[[Медиа:AlgTh-home-5-fixed.pdf|13 марта, "PSPACE(ДЗ)."]]
*[[Медиа:AlgTh-class-6.pdf|20 марта, "Класс NL."]]
*[[Медиа:AlgTh-home-6-fixed.pdf|20 марта, "Класс NL(ДЗ)."]]
*[[Медиа:AlgTh-home-6-hints-fixed.pdf|20 марта, "Класс NL(ДЗ+подсказки)."]]
*[[Медиа:AlgTh-class-7.pdf|27 марта, "Полиномиальная иерархия."]]
*[[Медиа:AlgTh-home-7.pdf|27 марта, "Полиномиальная иерархия (ДЗ)."]]
*[[Медиа:AlgTh-home-7-hints.pdf|27 марта, "Полиномиальная иерархия (ДЗ+подсказки)."]]
*[[Медиа:AlgTh-class-8.pdf|3 апреля, "Вероятностные алгоритмы. Вероятностные классы."]]
*[[Медиа:AlgTh-home-8-added.pdf|3 апреля, "Вероятностные алгоритмы. Вероятностные классы(ДЗ)."]]
*[[Медиа:AlgTh-home-9.pdf|10 апреля, "Предыдущие задачи(ДЗ)."]]
*[[Медиа:AlgTh-home-9-hints.pdf|10 апреля, "Предыдущие задачи+подсказки(ДЗ)."]]
*[[Медиа:AlgTh-class-10-fixed.pdf|17 апреля, "Оценки Чернова."]]
*[[Медиа:AlgTh-home-10-fixed.pdf|17 апреля, "Оценки Чернова. Элементы линейного программирования(ДЗ)."]]
*[[Медиа:AlgTh-class-11.pdf|24 апреля, "Путь. Увеличение вероятности."]]
*[[Медиа:AlgTh-class-12.pdf|26 апреля, "Схемы."]]
*[[Медиа:AlgTh-home-12.pdf|26 апреля, "Схемы(ДЗ)."]]

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

[https://docs.google.com/spreadsheets/d/1oKyKA2hr9u7w_RWiqdbg4-5NodDbc7MHd0L5qA6cFTM/edit?usp=sharing Табличка]

[http://lglinskih.com/HW1.pdf Домашнее задание к практике 1]   

[http://lglinskih.com/HW2.pdf Домашнее задание к практике 2]

[http://lglinskih.com/HW3.pdf Домашнее задание к практике 3]

[http://lglinskih.com/HW4.pdf Домашнее задание к практике 4]

[http://lglinskih.com/HW5.pdf Домашнее задание к практике 5]

[http://lglinskih.com/HW6.pdf Домашнее задание к практике 6]

[http://lglinskih.com/HW7.pdf Домашнее задание к практике 7]

[http://lglinskih.com/HW8.pdf Домашнее задание к практике 8]

[http://lglinskih.com/HW910.pdf Домашнее задание к практике 9 и 10]

[http://lglinskih.com/HW12.pdf Домашнее задание к практике 11 и 12]

[http://lglinskih.com/HW13.pdf Домашнее задание к практике 13 (последнее/дополнительное домашнее задание)]

Переписка контрольной работы: [[Медиа:KR.pdf|теория]], [[Медиа:KR2.pdf|практика]]