Курс лекций «Сложность алгоритмов» (ИСПРАН, 3 курс МФТИ) — различия между версиями
StasFomin (обсуждение | вклад) |
StasFomin (обсуждение | вклад) |
||
(не показано 27 промежуточных версий этого же участника) | |||
Строка 1: | Строка 1: | ||
− | <!-- [[Special:MediawikiQuizzer/Algs-3-course-ispras-weekly| | + | <!-- * [[Special:MediawikiQuizzer/Algs-3-course-ispras-weekly|Обещанный тест на повышение оценки с 22:00-23:00]] --> |
− | + | <!-- * [[Special:MediawikiQuizzer/Algs-3-course-ispras-exam|Тест перед экзаменом]] --> | |
− | <!-- [[Special:MediawikiQuizzer/GRE-CS-v01| | + | <!-- |
+ | [[Special:MediawikiQuizzer/GRE-CS-v01|Обещанный тест на повышение оценки с 15:00-15:30]] | ||
+ | --> | ||
__TOC__ | __TOC__ | ||
Строка 8: | Строка 10: | ||
--> | --> | ||
+ | <!-- | ||
<poll> | <poll> | ||
AUTHORIZED | AUTHORIZED | ||
Строка 24: | Строка 27: | ||
<s>Хорошо, по результатам голосования встречаемся в четверг, в 11:00, 2019-05-30</s> | <s>Хорошо, по результатам голосования встречаемся в четверг, в 11:00, 2019-05-30</s> | ||
Хорошо, по результатам переголосования встречаемся в среду, в 10:00, 2019-05-29 | Хорошо, по результатам переголосования встречаемся в среду, в 10:00, 2019-05-29 | ||
+ | |||
+ | [[Участник:StasFomin|StasFomin]] 11:25, 29 мая 2019 (MSK): Никто не пришел, ведомости заполнены, пытайтесь поймать меня или НН с отрывным. Всем успехов. | ||
+ | --> | ||
<!-- | <!-- | ||
Строка 54: | Строка 60: | ||
Семестровый курс по выбору для студентов 3-го курса ФУПМ МФТИ. | Семестровый курс по выбору для студентов 3-го курса ФУПМ МФТИ. | ||
− | ; | + | ;Лектор: [mailto:stas-fomin@yandex.ru Стас Фомин] |
− | Место чтения курса - ИСПРАН, | + | |
− | Солженицына, можно найти в общем, 110 аудитория. | + | Место чтения курса - ИСПРАН, Станиславского 19. |
+ | <!-- Солженицына, можно найти в общем, 110 аудитория. --> | ||
<!-- | <!-- | ||
Строка 71: | Строка 78: | ||
---- | ---- | ||
+ | Формат проведения лекций: демонстрация с проектором с параллельным обсуждением, проверка тестами знаний по предыдущим темам. Подразумевается параллельное изучение студентами электронной версии курса, просмотра видео лекций, решение задач. | ||
+ | Ведется [https://docs.google.com/spreadsheet/pub?key=0Ao6tsK_6FZEldFhKM3F6TzlQWmtXY3owalpvT3BRS2c&single=true&gid=11&output=html список посещений]. | ||
+ | <blockquote> | ||
+ | В карантинное время — занимаемся самостоятельно по темам из раздела «Фокус», | ||
+ | читаем книгу, смотрим видео и слайды, решаем задачи, см. ниже. | ||
+ | |||
+ | Если будут дополнительные новые лекции или удаленные собрания — об этом будут аннонсы | ||
+ | в [http://vk.com/discopal группе VK]. | ||
+ | </blockquote> | ||
− | |||
− | |||
<html><center> | <html><center> | ||
Строка 83: | Строка 97: | ||
== Надо зарегистрироваться == | == Надо зарегистрироваться == | ||
− | * Зарегистрироваться здесь. Залогиниться. | + | * Зарегистрироваться здесь. Залогиниться. |
− | * Зайти на страницу [http://discopal.ispras.ru/%D0%A1%D0%BB%D1%83%D0%B6%D0%B5%D0%B1%D0%BD%D0%B0%D1%8F:Preferences настроек], указать свой email и подтвердить его. | + | * Зайти на страницу [http://discopal.ispras.ru/%D0%A1%D0%BB%D1%83%D0%B6%D0%B5%D0%B1%D0%BD%D0%B0%D1%8F:Preferences настроек], указать свой email и подтвердить его. Почту от mail.ru не используйте. Она ужасно проблемная (все нотификации уйдут в спам или отразятся сервисом). |
* На своей личной странице, написать хотя бы ФИО и группу. | * На своей личной странице, написать хотя бы ФИО и группу. | ||
* На странице [[Blog:Advanced Algorithms]] найти вкладку «следить», и подписаться на этот блог. Но по опыту последних лет, народ разучился пользоватся RSS-подписками… с другой стороны — на ФУПМ МФТИ тотально используется VK — все студенты и администрации в этой сети. Поэтому заведена группа, https://vk.com/discopal, подписывайтесь и туда, туда тоже будут идти обьявления, плюс там же открытые обсуждения и все такое. | * На странице [[Blog:Advanced Algorithms]] найти вкладку «следить», и подписаться на этот блог. Но по опыту последних лет, народ разучился пользоватся RSS-подписками… с другой стороны — на ФУПМ МФТИ тотально используется VK — все студенты и администрации в этой сети. Поэтому заведена группа, https://vk.com/discopal, подписывайтесь и туда, туда тоже будут идти обьявления, плюс там же открытые обсуждения и все такое. | ||
Строка 95: | Строка 109: | ||
Специально искать опечатки смысла мало, проще действовать по принципу WIN-WIN, читать с помощью PDFXChange или другого ридера, позволяющего делать комментарии, делать пометки по ходу чтения и отсылать (каждый день) помеченный вариант на mailto:stas-fomin@yandex.ru. | Специально искать опечатки смысла мало, проще действовать по принципу WIN-WIN, читать с помощью PDFXChange или другого ридера, позволяющего делать комментарии, делать пометки по ходу чтения и отсылать (каждый день) помеченный вариант на mailto:stas-fomin@yandex.ru. | ||
И каждый день скачивать заново — ибо книга будет пересобираться и меняться постоянно. | И каждый день скачивать заново — ибо книга будет пересобираться и меняться постоянно. | ||
− | |||
− | |||
− | |||
=== ? === | === ? === | ||
Строка 107: | Строка 118: | ||
* [[Полиномиальные сводимости и NP-полные задачи. Классы NP, coNP, NPC]] | * [[Полиномиальные сводимости и NP-полные задачи. Классы NP, coNP, NPC]] | ||
* [[Вероятностные вычисления. Классы RP, coRP, ZPP, BPP]] | * [[Вероятностные вычисления. Классы RP, coRP, ZPP, BPP]] | ||
− | + | ||
− | + | == Фокус == | |
+ | |||
* [[Жадный алгоритм в задачах о покрытии]] | * [[Жадный алгоритм в задачах о покрытии]] | ||
* [[Жадный алгоритм в задаче о рюкзаке]] | * [[Жадный алгоритм в задаче о рюкзаке]] | ||
Строка 114: | Строка 126: | ||
* [[Полностью полиномиальная аппроксимационная схема (FPTAS) для задачи о рюкзаке]] | * [[Полностью полиномиальная аппроксимационная схема (FPTAS) для задачи о рюкзаке]] | ||
* [[Полиномиальный в среднем алгоритм для задачи о рюкзаке]] | * [[Полиномиальный в среднем алгоритм для задачи о рюкзаке]] | ||
− | |||
− | |||
− | |||
* [[Полиномиальный в среднем алгоритм для SAT]] | * [[Полиномиальный в среднем алгоритм для SAT]] | ||
* [[Полиномиальный в среднем алгоритм для задачи упаковки]] | * [[Полиномиальный в среднем алгоритм для задачи упаковки]] | ||
Строка 122: | Строка 131: | ||
* [[MAX-SAT: вероятностное округление]] | * [[MAX-SAT: вероятностное округление]] | ||
* [[MAX-SAT: дерандомизация]] | * [[MAX-SAT: дерандомизация]] | ||
− | |||
* [[MAX-CUT: вероятностное округление]] | * [[MAX-CUT: вероятностное округление]] | ||
== Темы == | == Темы == | ||
− | + | * [[Вероятностно проверяемые доказательства. PCP-системы. PCP-теорема]] | |
− | + | * [[PCP и аппроксимируемость]] | |
На этих страницах слайды презентаций, задачи, и т.п. | На этих страницах слайды презентаций, задачи, и т.п. | ||
Строка 134: | Строка 142: | ||
В книге (и прошлых лекциях) всего сильно больше, но мы сфокусируемся именно на этих темах — на экзамене спрашивать будем только по ним. | В книге (и прошлых лекциях) всего сильно больше, но мы сфокусируемся именно на этих темах — на экзамене спрашивать будем только по ним. | ||
Но можно конечно читать и больше, найденные ошибки зачтутся, а знания скорее всего пригодятся на шестом курсе. | Но можно конечно читать и больше, найденные ошибки зачтутся, а знания скорее всего пригодятся на шестом курсе. | ||
− | |||
− | |||
* [[Полиномиальная иерархия]] | * [[Полиномиальная иерархия]] | ||
* [[Схемная сложность]] | * [[Схемная сложность]] | ||
---- | ---- | ||
− | |||
<!-- | <!-- | ||
Строка 161: | Строка 166: | ||
<pre><nowiki>[[Category:На проверку]]</nowiki></pre> | <pre><nowiki>[[Category:На проверку]]</nowiki></pre> | ||
и подписываться на изменения («watch this page»). | и подписываться на изменения («watch this page»). | ||
− | |||
Любая активность, даже попытки решения — хорошо. | Любая активность, даже попытки решения — хорошо. | ||
Строка 177: | Строка 181: | ||
Эти задачи заводим в | Эти задачи заводим в | ||
[[:Category:Предложенные студентами задачи]] | [[:Category:Предложенные студентами задачи]] | ||
− | |||
− | |||
− | |||
Все статьи в этой категории — задачи, которые можно пытаться решать. | Все статьи в этой категории — задачи, которые можно пытаться решать. | ||
Строка 202: | Строка 203: | ||
Эти задачи заводим в | Эти задачи заводим в | ||
[[:Category:Предложенные студентами задачи]] | [[:Category:Предложенные студентами задачи]] | ||
− | |||
---- | ---- | ||
+ | А еще есть квест | ||
+ | * [[LeetCoding]] | ||
<!-- | <!-- | ||
Строка 224: | Строка 226: | ||
[[:File:book-advanced-algorithms.pdf]] | [[:File:book-advanced-algorithms.pdf]] | ||
+ | |||
+ | Смешное — [https://vk.com/im?sel=1712504&w=wall-54530371_213451%2F1a6855f382934ad3ee реакция «обычных программистов»] | ||
==== Видео ==== | ==== Видео ==== | ||
Строка 232: | Строка 236: | ||
* Рекомендуем изучить Python. Ресурсов миллиарды, вот, например, | * Рекомендуем изучить Python. Ресурсов миллиарды, вот, например, | ||
* Рекомендуется прочитать хотя бы [http://ru.wikiversity.org/wiki/%D0%9F%D1%80%D0%BE%D0%B3%D1%80%D0%B0%D0%BC%D0%BC%D0%B8%D1%80%D0%BE%D0%B2%D0%B0%D0%BD%D0%B8%D0%B5_%D0%B8_%D0%BD%D0%B0%D1%83%D1%87%D0%BD%D1%8B%D0%B5_%D0%B2%D1%8B%D1%87%D0%B8%D1%81%D0%BB%D0%B5%D0%BD%D0%B8%D1%8F_%D0%BD%D0%B0_%D1%8F%D0%B7%D1%8B%D0%BA%D0%B5_Python лекции], а еще лучше — [http://pythontutor.ru интерактивный учебник]. | * Рекомендуется прочитать хотя бы [http://ru.wikiversity.org/wiki/%D0%9F%D1%80%D0%BE%D0%B3%D1%80%D0%B0%D0%BC%D0%BC%D0%B8%D1%80%D0%BE%D0%B2%D0%B0%D0%BD%D0%B8%D0%B5_%D0%B8_%D0%BD%D0%B0%D1%83%D1%87%D0%BD%D1%8B%D0%B5_%D0%B2%D1%8B%D1%87%D0%B8%D1%81%D0%BB%D0%B5%D0%BD%D0%B8%D1%8F_%D0%BD%D0%B0_%D1%8F%D0%B7%D1%8B%D0%BA%D0%B5_Python лекции], а еще лучше — [http://pythontutor.ru интерактивный учебник]. | ||
− | |||
== Полезная сопутствующая литература по курсу. == | == Полезная сопутствующая литература по курсу. == | ||
Строка 240: | Строка 243: | ||
* Еще один классический [http://www.cs.yale.edu/HTML/YALE/CS/HyPlans/lovasz/complex.ps курс лекций по теории сложности от László Lovász.] | * Еще один классический [http://www.cs.yale.edu/HTML/YALE/CS/HyPlans/lovasz/complex.ps курс лекций по теории сложности от László Lovász.] | ||
* ''А. Китаев, А. Шень, М. Вялый'', [http://discopal.ispras.ru/img_auth.php/9/96/Qbook_.pdf Классические и квантовые вычисления] — замечательная книга. Содержит отличное введение в теорию сложности. | * ''А. Китаев, А. Шень, М. Вялый'', [http://discopal.ispras.ru/img_auth.php/9/96/Qbook_.pdf Классические и квантовые вычисления] — замечательная книга. Содержит отличное введение в теорию сложности. | ||
+ | * Лекции [https://www.youtube.com/watch?v=NzeS8XoGCLI&list=PL4_hYwCyhAvbXd4YjOILzI5nPZMIzotMG Сложность вычислений (3 курс, осень 2019) - лектор -- Мусатов Д.В.] | ||
+ | ---- | ||
+ | {{:Библиотека}} | ||
+ | |||
+ | <!-- | ||
== Нужно знать! == | == Нужно знать! == | ||
[[File:Что ждут на курсе по криптографии от вас.jpg|800px|center]] | [[File:Что ждут на курсе по криптографии от вас.jpg|800px|center]] | ||
− | + | --> | |
<references/> | <references/> |
Версия 19:52, 26 мая 2020
Содержание
- 2024-04-18: Обзор квестов курса ← Advanced Algorithms
- 2024-03-28: Эксперимент — улучшаем старые решения ← Advanced Algorithms
- 2024-03-28: Python-решения — давайте потренируемся их сделать питонистей ← Advanced Algorithms
Семестровый курс по выбору для студентов 3-го курса ФУПМ МФТИ.
- Лектор
- Стас Фомин
Место чтения курса - ИСПРАН, Станиславского 19.
Формат проведения лекций: демонстрация с проектором с параллельным обсуждением, проверка тестами знаний по предыдущим темам. Подразумевается параллельное изучение студентами электронной версии курса, просмотра видео лекций, решение задач.
Ведется список посещений.
В карантинное время — занимаемся самостоятельно по темам из раздела «Фокус», читаем книгу, смотрим видео и слайды, решаем задачи, см. ниже.
Если будут дополнительные новые лекции или удаленные собрания — об этом будут аннонсы в группе VK.
Надо зарегистрироваться
- Зарегистрироваться здесь. Залогиниться.
- Зайти на страницу настроек, указать свой email и подтвердить его. Почту от mail.ru не используйте. Она ужасно проблемная (все нотификации уйдут в спам или отразятся сервисом).
- На своей личной странице, написать хотя бы ФИО и группу.
- На странице Blog:Advanced Algorithms найти вкладку «следить», и подписаться на этот блог. Но по опыту последних лет, народ разучился пользоватся RSS-подписками… с другой стороны — на ФУПМ МФТИ тотально используется VK — все студенты и администрации в этой сети. Поэтому заведена группа, https://vk.com/discopal, подписывайтесь и туда, туда тоже будут идти обьявления, плюс там же открытые обсуждения и все такое.
Книга
На растерзание отдается свежая сборка — можно искать в ней ошибки (они 100% есть — даже орфографические).
Специально искать опечатки смысла мало, проще действовать по принципу WIN-WIN, читать с помощью PDFXChange или другого ридера, позволяющего делать комментарии, делать пометки по ходу чтения и отсылать (каждый день) помеченный вариант на mailto:stas-fomin@yandex.ru. И каждый день скачивать заново — ибо книга будет пересобираться и меняться постоянно.
?
- [zoo]
Пройдено
- Формально об алгоритмах. Вычислительные модели
- Временная и пространственная сложность алгоритмов
- Полиномиальные сводимости и NP-полные задачи. Классы NP, coNP, NPC
- Вероятностные вычисления. Классы RP, coRP, ZPP, BPP
Фокус
- Жадный алгоритм в задачах о покрытии
- Жадный алгоритм в задаче о рюкзаке
- Динамическое программирование для задачи о рюкзаке
- Полностью полиномиальная аппроксимационная схема (FPTAS) для задачи о рюкзаке
- Полиномиальный в среднем алгоритм для задачи о рюкзаке
- Полиномиальный в среднем алгоритм для SAT
- Полиномиальный в среднем алгоритм для задачи упаковки
- Вероятностная проверка тождеств
- MAX-SAT: вероятностное округление
- MAX-SAT: дерандомизация
- MAX-CUT: вероятностное округление
Темы
На этих страницах слайды презентаций, задачи, и т.п. Замечания по каждой презентации можно (и нужно) писать на вкладку «Обсуждение», для соотвествующего PDF-файла.
В книге (и прошлых лекциях) всего сильно больше, но мы сфокусируемся именно на этих темах — на экзамене спрашивать будем только по ним. Но можно конечно читать и больше, найденные ошибки зачтутся, а знания скорее всего пригодятся на шестом курсе.
Тренировка
Проверь себя, помнишь ли элементарные понятия и факты из курса.
Задачи
Все статьи в этой категории — задачи, которые можно пытаться решать.
- Category:Нерешенные задачи. Осталось 22 нерешенных задач.
Решать надо создавая для решения подстраницу личной страницы, и ссылаясь в решении на задачу.
- Пример
- Задача Вероятностная_проверка_тождеств/Задачи/determinant → Решение Участник:StasFomin/Задача determinant.
Cтатьи-решения задач помечать вставляя строку
[[Category:На проверку]]
и подписываться на изменения («watch this page»).
Любая активность, даже попытки решения — хорошо. После того, как задача решена, она перейдет в архив:
Проверенное решение перейдет в Category:Решения или, если возникнут вопросы-возражения в Category:Проблемы в решении.
Т.е. очередь решений на проверку → Category:На проверку (там сейчас 10 задач), проверяйте, что ваши решения в правильной категории (а то их так и не проверят...).
Отдельно, пробуем новую инициативу — те, кто решил хоть несколько задач, и понял принцип оформления, предлагайте задачи с решениями по теме курса (можно взять из любых знакомых вам курсов и книг с алгоритмами). Этих задач на экзамене не будет, но возможно они пригодятся в следующем году, ну и за них будет выписано много премиальных баллов (2× … 3×… ) по сравнению с решением существующих задач.
Эти задачи заводим в Category:Предложенные студентами задачи
Все статьи в этой категории — задачи, которые можно пытаться решать.
Любая активность, даже попытки решения — хорошо. После того, как задача решена, она перейдет в архив:
- 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.
- А. Китаев, А. Шень, М. Вялый, Классические и квантовые вычисления — замечательная книга. Содержит отличное введение в теорию сложности.
- Лекции Сложность вычислений (3 курс, осень 2019) - лектор -- Мусатов Д.В.