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

Материал из SEWiki
Перейти к: навигация, поиск

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

Лекции

  • 13 февраля. Машина Тьюринга.
  • 20 февраля. Универсальная машина Тьюринга. Класс NP.
  • 27 февраля. NP-полнота SAT. Иерархия по времени. Теорема Ладнера.
  • 06 марта. Машины с оракульным доступом. Построение языка B, такого что . Сложность по памяти.
  • 13 марта. TQBF является PSPACE-полным. Теорема Савича. Задача обощенной географии является PSPACE-полной.
  • 20 марта. NL-полный язык. Определение класса NL помощью сертификата. NL=coNL.
  • 27 марта. Полиномиальная иерархия. Невозможно разобрать выражение (MathML с переходом в SVG или PNG (рекомендуется для современных браузеров и инструментов повышения доступности): Недопустимый ответ («<p>Во время обработки HTTP-запроса обнаружена проблема: 400 Bad Request

</p>») от сервера «https://mathoid-beta.wmflabs.org»:): Ntime[n] \negsubseteq<TISP[n^{1.2},n^0.2]/math>. '''Литература''' * Sanjeev Arora and Boaz Barak, Computational Complexity: A Modern Approach. [http://theory.cs.princeton.edu/complexity/book.pdf скачать] http://theory.cs.princeton.edu/complexity/ == Практика Близнец == Преподаватель: Близнец Иван Анатольевич Результаты проверки ДЗ: [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 марта, "Полиномиальная иерархия."]] == Практика Глинских == Преподаватель: Глинских Людмила (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://mit.spbau.ru/sewiki/index.php?title=Теория_алгоритмов_2MIT_весна_2018&oldid=15272»