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

Материал из SEWiki
Перейти к: навигация, поиск
(Практика Близнец)
(Лекции)
Строка 11: Строка 11:
 
*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>.  
 
*03 апреля. Вероятностный алгоритм для минимального разреза. Вероятностный <math>O^*(4^k)</math> алгоритм для наибольшего леса. Теорема Адлемана об избыточности случайных бит в схемах.
 
*03 апреля. Вероятностный алгоритм для минимального разреза. Вероятностный <math>O^*(4^k)</math> алгоритм для наибольшего леса. Теорема Адлемана об избыточности случайных бит в схемах.
*10 апреля.  
+
*10 апреля. Уменьшение ошибки в RP алгоритме(попарно независимые множества). Задача о стабильном паросочетании за <math>n\ln{n}+cn</math>.
  
  

Версия 17:10, 13 апреля 2018

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

Лекции

  • 13 февраля. Машина Тьюринга.
  • 20 февраля. Универсальная машина Тьюринга. Класс NP.
  • 27 февраля. NP-полнота SAT. Иерархия по времени. Теорема Ладнера.
  • 06 марта. Машины с оракульным доступом. Построение языка B, такого что . Сложность по памяти.
  • 13 марта. TQBF является PSPACE-полным. Теорема Савича. Задача обощенной географии является PSPACE-полной.
  • 20 марта. NL-полный язык. Определение класса NL помощью сертификата. NL=coNL.
  • 27 марта. Полиномиальная иерархия. .
  • 03 апреля. Вероятностный алгоритм для минимального разреза. Вероятностный алгоритм для наибольшего леса. Теорема Адлемана об избыточности случайных бит в схемах.
  • 10 апреля. Уменьшение ошибки в RP алгоритме(попарно независимые множества). Задача о стабильном паросочетании за .


Литература

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

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

  • Rajeev Motwani and Prabhakar Raghavan, Randomized Algorithms.

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

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

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

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

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

Табличка

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

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

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

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

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

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

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

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