Теория алгоритмов 2MIT весна 2018 — различия между версиями
Материал из SEWiki
Bliznets (обсуждение | вклад) (→Лекции) |
Bliznets (обсуждение | вклад) (→Лекции) |
||
| Строка 12: | Строка 12: | ||
*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.]] | ||
Версия 14:23, 10 мая 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.
Литература
- 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)
