Курс по книге «Эффективные алгоритмы и сложность вычислений»
Содержание
Книга
На растерзание отдается свежая сборка — можно искать в ней ошибки (они 100% есть — даже орфографические).
Специально искать опечатки смысла мало, проще действовать по принципу WIN-WIN, читать с помощью PDFXChange или другого ридера, позволяющего делать комментарии, делать пометки по ходу чтения и отсылать (каждый день) помеченный вариант на mailto:stas-fomin@yandex.ru. И каждый день скачивать заново — ибо книга будет пересобираться и меняться постоянно.
?
- [zoo]
Темы
- Формально об алгоритмах. Вычислительные модели
- Временная и пространственная сложность алгоритмов
- Полиномиальные сводимости и NP-полные задачи. Классы NP, coNP, NPC
- Вероятностные вычисления. Классы RP, coRP, ZPP, BPP
- Жадный алгоритм в задачах о покрытии
- Жадный алгоритм в задаче о рюкзаке
- Динамическое программирование для задачи о рюкзаке
- Полностью полиномиальная аппроксимационная схема (FPTAS) для задачи о рюкзаке
- Полиномиальный в среднем алгоритм для задачи о рюкзаке
- Полиномиальный в среднем алгоритм для SAT
- Полиномиальный в среднем алгоритм для задачи упаковки
- Приближенный алгоритм для метрической задачи коммивояжера
- Вероятностная проверка тождеств
- MAX-SAT: вероятностное округление
- MAX-CUT: вероятностное округление
- MAX-SAT: дерандомизация
- Вероятностный подсчет числа выполняемых наборов для ДНФ
- Вероятностно проверяемые доказательства. PCP-системы. PCP-теорема
- PCP и аппроксимируемость
- Полиномиальная иерархия
- Схемная сложность
На этих страницах слайды презентаций, задачи, и т.п. Замечания по каждой презентации можно (и нужно) писать на вкладку «Обсуждение», для соотвествующего PDF-файла.
В книге (и прошлых лекциях) всего сильно больше, но мы сфокусируемся именно на этих темах — на экзамене спрашивать будем только по ним. Но можно конечно читать и больше, найденные ошибки зачтутся, а знания скорее всего пригодятся на шестом курсе.
Тренировка
Проверь себя, помнишь ли элементарные понятия и факты из курса.
Теоретические упражнения
- Нужно быть залогиненным
- Скрыто из интернета
- Надо решить N задач из M разных разделов.
- Либо одну бонусную задачу — считаем, что ее решение закрывает квест.
- Выбирайте задачи из Open Exercises, переходите к редактированию по «Беру…»
- помечайте их как {{reserve-task|~~~~~}}
- Решение на подстранице вашей личной страницы
- Вики-ссылка на задачу
- Решение — можно использовать текст, латех целиком внутри тега «latex», или просто вставки математики внутри тега «m»
- На худой конец — очень аккуратно оформить на листочке, сфотографировать, загрузить файлы (разберетесь).
- Метка «{{checkme}}», когда решите.
- Внизу вставка всего этого по клику →
- Они попадут в Категория:На проверку
- Все как обычно в наших квестах.
- Изучайте чужие решения
- Категория:Решенные задачи
- Смотрите «Ссылки сюда» → решения студентов.
Книга
Специальная верстка для чтения с ноутбуков и КПК:
- альбомная ориентация
- крупные беззасечные шрифты
Кому не нравится — пишите обоснованные протесты (почему, конструктивные предложения).
Пишите замечания по содержимому — про проблемы с версткой и библиографией не писать, все там только в процессе.
File:book-advanced-algorithms.pdf
Смешное — реакция «обычных программистов»
Полезная сопутствующая литература по курсу.
- Очень хорошие лекции по классической теории сложности, написанные одним из корифеев оной: Introduction to Complexity Theory by Oded Goldreich
- Более краткий курс по классической теории сложности, университет Technion.
- Еще один классический курс лекций по теории сложности от László Lovász.
- А. Китаев, А. Шень, М. Вялый, «Классические и квантовые вычисления» — замечательная книга. Содержит отличное введение в теорию сложности.
- Лекции Сложность вычислений (3 курс, осень 2019) - лектор -- Мусатов Д.В., трейлер
Нужно знать!
[ Хронологический вид ]Комментарии
Войдите, чтобы комментировать.