Теория алгоритмов 2MIT весна 2018 — различия между версиями

Материал из SEWiki
Перейти к: навигация, поиск
(Лекции)
(Практика Глинских)
 
(не показано 11 промежуточных версий 2 участников)
Строка 6: Строка 6:
 
*20 февраля. Универсальная машина Тьюринга. Класс NP.  
 
*20 февраля. Универсальная машина Тьюринга. Класс NP.  
 
*27 февраля. NP-полнота SAT. Иерархия по времени. Теорема Ладнера.   
 
*27 февраля. NP-полнота SAT. Иерархия по времени. Теорема Ладнера.   
*06 марта. Машины с оракульным доступом. Построение языка B, такого что <math>P^B \neq NP^B</math>. Сложность по памяти.
+
*06 марта. Машины с оракульным доступом. Построение языка B, такого что <math>P^B \neq NP^B</math>. Сложность по памяти. [[Медиа:AlgTh-lec-4.pdf|pdf.]]
*13 марта. TQBF  является PSPACE-полным. Теорема Савича. Задача обощенной географии является PSPACE-полной.   
+
*13 марта. TQBF  является PSPACE-полным. Теорема Савича. Задача обощенной географии является PSPACE-полной.  [[Медиа:AlgTh-lec-5.pdf|pdf.]]
*20 марта. NL-полный язык. Определение класса NL помощью сертификата. NL=coNL.  
+
*20 марта. NL-полный язык. Определение класса NL помощью сертификата. NL=coNL. [[Медиа:AlgTh-lec-6.pdf|pdf.]]
*27 марта. Полиномиальная иерархия. <math>Ntime[n] \not\subset TISP[n^{1.2},n^{0.2}]</math>.  
+
*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.]]  
 
*03 апреля. Вероятностный алгоритм для минимального разреза. Вероятностный <math>O^*(4^k)</math> алгоритм для наибольшего леса. Теорема Адлемана об избыточности случайных бит в схемах. [[Медиа:AlgTh-lec-8.pdf|pdf.]]  
 
*10 апреля. Уменьшение ошибки в RP алгоритме(попарно независимые множества). Задача о стабильном паросочетании за <math>n\ln{n}+cn</math>.  [[Медиа:AlgTh-lec-9.pdf|pdf.]]  
 
*10 апреля. Уменьшение ошибки в RP алгоритме(попарно независимые множества). Задача о стабильном паросочетании за <math>n\ln{n}+cn</math>.  [[Медиа:AlgTh-lec-9.pdf|pdf.]]  
*17 апреля. Оценки Чернова. Вероятностный приближенный алгоритм для Wiring problem.
+
*17 апреля. Оценки Чернова. Вероятностный приближенный алгоритм для Wiring problem. [[Медиа:AlgTh-lec-10.pdf|pdf.]]
*24 апреля. Путь с логарифмической памятью.
+
*24 апреля. Путь с логарифмической памятью. [[Медиа:AlgTh-lec-11.pdf|pdf.]]
*25 апреля. Схемы.   
+
*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.]]
 
*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|Список вопросов]]
  
 
'''Литература'''
 
'''Литература'''
Строка 24: Строка 28:
 
http://theory.cs.princeton.edu/complexity/
 
http://theory.cs.princeton.edu/complexity/
 
* Rajeev Motwani and Prabhakar Raghavan, Randomized Algorithms.
 
* 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 смотреть]
  
 
== Практика Близнец ==
 
== Практика Близнец ==
Строка 79: Строка 89:
  
 
[http://lglinskih.com/HW12.pdf Домашнее задание к практике 11 и 12]
 
[http://lglinskih.com/HW12.pdf Домашнее задание к практике 11 и 12]
 +
 +
[http://lglinskih.com/HW13.pdf Домашнее задание к практике 13 (последнее/дополнительное домашнее задание)]
 +
 +
Переписка контрольной работы: [[Медиа:KR.pdf|теория]], [[Медиа:KR2.pdf|практика]]

Текущая версия на 12:58, 12 июня 2018

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

Лекции

  • 13 февраля. Машина Тьюринга.
  • 20 февраля. Универсальная машина Тьюринга. Класс NP.
  • 27 февраля. NP-полнота SAT. Иерархия по времени. Теорема Ладнера.
  • 06 марта. Машины с оракульным доступом. Построение языка B, такого что . Сложность по памяти. pdf.
  • 13 марта. TQBF является PSPACE-полным. Теорема Савича. Задача обощенной географии является PSPACE-полной. pdf.
  • 20 марта. NL-полный язык. Определение класса NL помощью сертификата. NL=coNL. pdf.
  • 27 марта. Полиномиальная иерархия. . pdf.
  • 03 апреля. Вероятностный алгоритм для минимального разреза. Вероятностный алгоритм для наибольшего леса. Теорема Адлемана об избыточности случайных бит в схемах. pdf.
  • 10 апреля. Уменьшение ошибки в RP алгоритме(попарно независимые множества). Задача о стабильном паросочетании за . pdf.
  • 17 апреля. Оценки Чернова. Вероятностный приближенный алгоритм для Wiring problem. pdf.
  • 24 апреля. Путь с логарифмической памятью. pdf.
  • 25 апреля. Схемы. pdf.
  • 08 мая. и . Теорема Вэлианта-Вазирани. 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(в первых видео рассказывается история возникновения компьютеров, становится более понятно почему же машина Тьюринга или схема имеют что-то общее с компьютером) смотреть
  • Видеолекции похожего курса смотреть

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

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

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

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

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

Табличка

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

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

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

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

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

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

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

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

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

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

Домашнее задание к практике 13 (последнее/дополнительное домашнее задание)

Переписка контрольной работы: теория, практика