Курс лекций «Сложность алгоритмов» (ИСПРАН, 3 курс МФТИ) — различия между версиями
StasFomin (обсуждение | вклад) |
StasFomin (обсуждение | вклад) (→Темы к следующему занятию) |
||
Строка 77: | Строка 77: | ||
И каждый день скачивать заново — ибо книга будет пересобираться и меняться постоянно. | И каждый день скачивать заново — ибо книга будет пересобираться и меняться постоянно. | ||
− | == | + | == Пройденные темы == |
− | + | ||
* [[Формально об алгоритмах. Вычислительные модели]] | * [[Формально об алгоритмах. Вычислительные модели]] | ||
* [[Временная и пространственная сложность алгоритмов]] | * [[Временная и пространственная сложность алгоритмов]] | ||
Строка 90: | Строка 89: | ||
* [[Полиномиальный в среднем алгоритм для задачи о рюкзаке]] | * [[Полиномиальный в среднем алгоритм для задачи о рюкзаке]] | ||
− | |||
* [[Вероятностная проверка тождеств]] | * [[Вероятностная проверка тождеств]] | ||
* [[MAX-SAT: вероятностное округление]] | * [[MAX-SAT: вероятностное округление]] | ||
* [[MAX-SAT: дерандомизация]] | * [[MAX-SAT: дерандомизация]] | ||
* [[Полиномиальный в среднем алгоритм для SAT]] | * [[Полиномиальный в среднем алгоритм для SAT]] | ||
− | |||
== Темы == | == Темы == |
Версия 15:45, 25 мая 2016
Содержание
Залогиньтесь, выбирайте удобное время (у вас три голоса), и записывайтесь.
Удобный вам день для зачета по нашему курсу:
|
Вы должны войти в систему, чтобы участвовать в этом голосовании.
- 2024-09-21: Выбираем удобное время созвонов ← Advanced Algorithms
- 2024-09-09: Презентация курса «на осень 2024» ← Advanced Algorithms
- 2024-05-02: Не портите страницы задач, оформляйте правильно ← Advanced Algorithms
Семестровый курс по выбору для студентов 3-го курса ФУПМ МФТИ.
- Лекторы
- д.ф.-м.н. Н.Н. Кузюрин, С.А. Фомин
Место чтения курса - ИСПРАН, Солженицына, можно найти в общем, 110 аудитория.
Формат проведения лекций: демонстрация с проектором с параллельным обсуждением, проверка тестами знаний по предыдущим темам. Подразумевается параллельное изучение студентами электронной версии курса.
Ведется список посещений.
Надо зарегистрироваться
- Зарегистрироваться здесь. Залогинится.
- Зайти на страницу настроек, указать свой email и подтвердить его.
- На своей личной странице, написать хотя бы ФИО и группу.
- На странице Blog:Advanced Algorithms найти вкладку «следить», и подписаться на этот блог. Но по опыту последних лет, народ разучился пользоватся RSS-подписками… с другой стороны — на ФУПМ МФТИ тотально используется VK — все студенты и администрации в этой сети. Поэтому заведена группа, https://vk.com/discopal, подписывайтесь и туда, туда тоже будут идти обьявления, плюс там же открытые обсуждения и все такое.
Книга
На растерзание отдается свежая сборка — можно искать в ней ошибки (они 100% есть — даже орфографические).
Специально искать опечатки смысла мало, проще действовать по принципу WIN-WIN, читать с помощью PDFXChange или другого ридера, позволяющего делать комментарии, делать пометки по ходу чтения и отсылать (каждый день) помеченный вариант на mailto:stas-fomin@yandex.ru. И каждый день скачивать заново — ибо книга будет пересобираться и меняться постоянно.
Пройденные темы
- Формально об алгоритмах. Вычислительные модели
- Временная и пространственная сложность алгоритмов
- Полиномиальные сводимости и NP-полные задачи. Классы NP, coNP, NPC
- Вероятностные вычисления. Классы RP, coRP, ZPP, BPP
- Жадный алгоритм в задачах о покрытии
- Жадный алгоритм в задаче о рюкзаке
- Динамическое программирование для задачи о рюкзаке
- Полностью полиномиальная аппроксимационная схема (FPTAS) для задачи о рюкзаке
- Полиномиальный в среднем алгоритм для задачи о рюкзаке
- Вероятностная проверка тождеств
- MAX-SAT: вероятностное округление
- MAX-SAT: дерандомизация
- Полиномиальный в среднем алгоритм для SAT
Темы
Рассмотренные в курсе темы.
В книге (и прошлых лекциях) всего сильно больше, но мы сфокусируемся именно на этих темах — на экзамене спрашивать будем только по ним. Но можно конечно читать и больше, найденные ошибки зачтутся, а знания скорее всего пригодятся на шестом курсе.
На этих страницах слайды презентаций, задачи, и т.п. Замечания по каждой презентации можно (и нужно) писать на вкладку «Обсуждение», для соотвествующего PDF-файла.
- Жадный алгоритм в задачах о покрытии
- Жадный алгоритм в задаче о рюкзаке
- Приближенный алгоритм для метрической задачи коммивояжера
- Динамическое программирование для задачи о рюкзаке
- Полностью полиномиальная аппроксимационная схема (FPTAS) для задачи о рюкзаке
- Полиномиальный в среднем алгоритм для SAT
- Вероятностная проверка тождеств
- MAX-SAT: вероятностное округление
- MAX-SAT: дерандомизация
- Вероятностный подсчет числа выполняемых наборов для ДНФ
- Формально об алгоритмах. Вычислительные модели
- Временная и пространственная сложность алгоритмов
- Полиномиальные сводимости и NP-полные задачи. Классы NP, coNP, NPC
- Вероятностные вычисления. Классы RP, coRP, ZPP, BPP
- Полиномиальная иерархия
Тренировка
Проверь себя, помнишь ли элементарные понятия и факты из курса. Тест возможно будет на экзамене, чтобы отсеять совсем невменяемых.
Задачи
Все статьи в этой категории — задачи, которые можно пытаться решать.
Любая активность, даже попытки решения — хорошо. После того, как задача решена, она перейдет в архив:
- Category:Решенные задачи — кстати, полезно смотреть чужие решения.
Cтатьи-решения задач помечать вставляя строку
[[Category:На проверку]]
и подписываться на изменения («watch this page»).
Проверенное решение перейдет в Category:Решения или, если возникнут вопросы-возражения в Category:Проблемы в решении.
Т.е. очередь решений на проверку → Category:На проверку, проверяйте, что ваши решения в правильной категории (а то их так и не проверят...).
Отдельно, пробуем новую инициативу — те, кто решил хоть несколько задач, и понял принцип оформления, предлагайте задачи с решениями по теме курса (можно взять из любых знакомых вам курсов и книг с алгоритмами). Этих задач на экзамене не будет, но возможно они пригодятся в следующем году, ну и за них будет выписано много премиальных баллов (2× … 3×… ) по сравнению с решением существующих задач.
Эти задачи заводим в Category:Предложенные студентами задачи
Книга
Специальная верстка для чтения с ноутбуков и КПК:
- альбомная ориентация
- крупные беззасечные шрифты
Кому не нравится — пишите обоснованные протесты (почему, конструктивные предложения).
Пишите замечания по содержимому — про проблемы с версткой и библиографией не писать, все там только в процессе.
File:book-advanced-algorithms.pdf
Видео
Записанное видео лекций Николая Николаевича Кузюрина и Стаса Фомина, за весенний семестр 2013 года.
- http://video-sky.0x1.tv/channels/ispras.ru/lectures/2013/2013-02-21-lectures.uncut.mkv1:23:15 — приближенные алгоритмы с гарантированной точностью, жадные алгоритмы в задаче о покрытии.
- http://video-sky.0x1.tv/channels/ispras.ru/lectures/2013/2013-02-21-lectures.uncut.mkv2:12:00 — временная и пространственная сложность алгоритмов.
- http://video-sky.0x1.tv/channels/ispras.ru/lectures/2013/2013-02-21-lectures.uncut.mkv2:36:30 — NP-полнота и сводимости.
- http://video-sky.0x1.tv/channels/ispras.ru/lectures/2013/2013-02-28-lectures.uncut.mkv0:00:22 — недетерминированные машины Тьюринга, NTIME, NP-полнота, NP-полнота сапера
- http://video-sky.0x1.tv/channels/ispras.ru/lectures/2013/2013-02-28-lectures.uncut.mkv1:19:30 — метрическая задача коммивояжера, алгоритм Кристофидеса.
- http://video-sky.0x1.tv/channels/ispras.ru/lectures/2013/2013-03-07-lectures.uncut.mkv0:03:31 — вероятностная проверка тождеств.
- http://video-sky.0x1.tv/channels/ispras.ru/lectures/2013/2013-03-07-lectures.uncut.mkv0:37:40 — вероятностное округление для MAX-SAT
- http://video-sky.0x1.tv/channels/ispras.ru/lectures/2013/2013-03-13-lectures.uncut.mkv0:03:59 — криптография, 4 курс
- http://video-sky.0x1.tv/channels/ispras.ru/lectures/2013/2013-03-14-lectures.uncut.mkv0:01:10 — Дерандомизация MAX-SAT
- http://video-sky.0x1.tv/channels/ispras.ru/lectures/2013/2013-03-14-lectures.uncut.mkv0:55:40 — Вероятностные классы сложности сложности RP/ZPP.
- http://video-sky.0x1.tv/channels/ispras.ru/lectures/2013/2013-03-20-lectures.uncut.mkv2:02:34 — Вероятностные классы сложности BPP
- http://video-sky.0x1.tv/channels/ispras.ru/lectures/2013/2013-03-21-lectures.uncut.mkv0:00:20 — Полиномиальность в среднем, полиномиальный в среднем алгоритм для SAT.
- http://video-sky.0x1.tv/channels/ispras.ru/lectures/2013/2013-03-28-lectures.uncut.mkv0:00:30 — Рюкзак. Жадный, квазиполиномиальный и PTAS-алгоритм
- http://video-sky.0x1.tv/channels/ispras.ru/lectures/2013/2013-04-04-lectures.uncut.mkv0:01:12 — BPP, полиномиальная иерархия, схемная сложность.
Примечания и ссылки
- Рекомендуем изучить Python. Ресурсов миллиарды, вот, например,
- Рекомендуется прочитать хотя бы лекции, а еще лучше — интерактивный учебник.
Полезная сопутствующая литература по курсу.
- Очень хорошие лекции по классической теории сложности, написанные одним из корифеев оной: Introduction to Complexity Theory by Oded Goldreich
- Более краткий курс по классической теории сложности, университет Technion.
- Еще один классический курс лекций по теории сложности от László Lovász.
- А. Китаев, А. Шень, М. Вялый, Классические и квантовые вычисления — замечательная книга. Содержит отличное введение в теорию сложности.