Курс лекций «Сложность алгоритмов» (ИСПРАН, 3 курс МФТИ) — различия между версиями

Материал из DISCOPAL
Перейти к: навигация, поиск
 
(не показано 25 промежуточных версий этого же участника)
Строка 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/Algs-3-course-ispras-exam|Тест перед экзаменом]] -->
 
+
<!--
<!-- [[Special:MediawikiQuizzer/GRE-CS-v01|Еженедельная проверка — сегодня экспериментальная]] -->
+
[[Special:MediawikiQuizzer/GRE-CS-v01|Обещанный тест на повышение оценки с 15:00-15:30]]
 +
-->
  
 
__TOC__
 
__TOC__
Строка 9: Строка 10:
 
-->
 
-->
  
 +
<!--
 
<poll>
 
<poll>
 
AUTHORIZED
 
AUTHORIZED
Строка 27: Строка 29:
  
 
[[Участник:StasFomin|StasFomin]] 11:25, 29 мая 2019 (MSK): Никто не пришел, ведомости заполнены, пытайтесь поймать меня или НН с отрывным. Всем успехов.
 
[[Участник:StasFomin|StasFomin]] 11:25, 29 мая 2019 (MSK): Никто не пришел, ведомости заполнены, пытайтесь поймать меня или НН с отрывным. Всем успехов.
 +
-->
 +
 
<!--
 
<!--
 
<poll>
 
<poll>
Строка 56: Строка 60:
 
Семестровый курс по выбору для студентов 3-го курса ФУПМ МФТИ.
 
Семестровый курс по выбору для студентов 3-го курса ФУПМ МФТИ.
  
;Лекторы: д.ф.-м.н. [mailto:nnkuz@ispras.ru Н.Н. Кузюрин], [mailto:stas-fomin@yandex.ru Стас Фомин]
+
;Лектор: [mailto:stas-fomin@yandex.ru Стас Фомин]
  
Место чтения курса - ИСПРАН,
+
 
Солженицына, можно найти в общем, 110 аудитория.
+
Место чтения курса - ИСПРАН, Станиславского 19.
 +
<!-- Солженицына, можно найти в общем, 110 аудитория. -->
  
 
<!--
 
<!--
Строка 73: Строка 78:
 
----
 
----
  
 +
Формат проведения лекций: демонстрация с проектором с параллельным обсуждением, проверка тестами знаний по предыдущим темам. Подразумевается параллельное изучение студентами электронной версии курса, просмотра видео лекций, решение задач.
  
 +
Ведется [https://docs.google.com/spreadsheet/pub?key=0Ao6tsK_6FZEldFhKM3F6TzlQWmtXY3owalpvT3BRS2c&single=true&gid=11&output=html список посещений].
  
 +
<blockquote>
 +
В карантинное время — занимаемся самостоятельно по темам из раздела «Фокус»,
 +
читаем книгу, смотрим видео и слайды, решаем задачи, см. ниже.
 +
 +
Если будут дополнительные новые лекции или удаленные собрания — об этом будут аннонсы
 +
в [http://vk.com/discopal группе VK].
 +
</blockquote>
  
Формат проведения лекций: демонстрация с проектором с параллельным обсуждением, проверка тестами знаний по предыдущим темам. Подразумевается параллельное изучение студентами электронной версии курса, просмотра видео лекций, решение задач.
 
  
Ведется [https://docs.google.com/spreadsheet/pub?key=0Ao6tsK_6FZEldFhKM3F6TzlQWmtXY3owalpvT3BRS2c&single=true&gid=11&output=html список посещений].
 
  
 
<html><center>
 
<html><center>
Строка 85: Строка 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, подписывайтесь и туда, туда тоже будут идти обьявления, плюс там же открытые обсуждения и все такое.
Строка 97: Строка 109:
 
Специально искать опечатки смысла мало, проще действовать по принципу WIN-WIN, читать с помощью PDFXChange или другого ридера, позволяющего делать комментарии, делать пометки по ходу чтения и отсылать (каждый день) помеченный вариант на mailto:stas-fomin@yandex.ru.
 
Специально искать опечатки смысла мало, проще действовать по принципу WIN-WIN, читать с помощью PDFXChange или другого ридера, позволяющего делать комментарии, делать пометки по ходу чтения и отсылать (каждый день) помеченный вариант на mailto:stas-fomin@yandex.ru.
 
И каждый день скачивать заново — ибо книга будет пересобираться и меняться постоянно.
 
И каждый день скачивать заново — ибо книга будет пересобираться и меняться постоянно.
 
 
 
  
 
=== ? ===
 
=== ? ===
Строка 109: Строка 118:
 
* [[Полиномиальные сводимости и NP-полные задачи. Классы NP, coNP, NPC]]
 
* [[Полиномиальные сводимости и NP-полные задачи. Классы NP, coNP, NPC]]
 
* [[Вероятностные вычисления. Классы RP, coRP, ZPP, BPP]]
 
* [[Вероятностные вычисления. Классы RP, coRP, ZPP, BPP]]
* [[Вероятностно проверяемые доказательства. PCP-системы. PCP-теорема]]
+
 
* [[PCP и аппроксимируемость]]
+
== Фокус ==
 +
 
 
* [[Жадный алгоритм в задачах о покрытии]]
 
* [[Жадный алгоритм в задачах о покрытии]]
 
* [[Жадный алгоритм в задаче о рюкзаке]]
 
* [[Жадный алгоритм в задаче о рюкзаке]]
Строка 116: Строка 126:
 
* [[Полностью полиномиальная аппроксимационная схема (FPTAS) для задачи о рюкзаке]]
 
* [[Полностью полиномиальная аппроксимационная схема (FPTAS) для задачи о рюкзаке]]
 
* [[Полиномиальный в среднем алгоритм для задачи о рюкзаке]]
 
* [[Полиномиальный в среднем алгоритм для задачи о рюкзаке]]
 
== Фокус ==
 
 
 
* [[Полиномиальный в среднем алгоритм для SAT]]
 
* [[Полиномиальный в среднем алгоритм для SAT]]
 
* [[Полиномиальный в среднем алгоритм для задачи упаковки]]
 
* [[Полиномиальный в среднем алгоритм для задачи упаковки]]
Строка 124: Строка 131:
 
* [[MAX-SAT: вероятностное округление]]
 
* [[MAX-SAT: вероятностное округление]]
 
* [[MAX-SAT: дерандомизация]]
 
* [[MAX-SAT: дерандомизация]]
 
 
* [[MAX-CUT: вероятностное округление]]
 
* [[MAX-CUT: вероятностное округление]]
  
 
== Темы ==
 
== Темы ==
 
+
* [[Вероятностно проверяемые доказательства. PCP-системы. PCP-теорема]]
 
+
* [[PCP и аппроксимируемость]]
  
 
На этих страницах слайды презентаций, задачи, и т.п.
 
На этих страницах слайды презентаций, задачи, и т.п.
Строка 136: Строка 142:
 
В книге (и прошлых лекциях) всего сильно больше, но мы сфокусируемся именно на этих темах — на экзамене спрашивать будем только по ним.
 
В книге (и прошлых лекциях) всего сильно больше, но мы сфокусируемся именно на этих темах — на экзамене спрашивать будем только по ним.
 
Но можно конечно читать и больше, найденные ошибки зачтутся, а знания скорее всего пригодятся на шестом курсе.  
 
Но можно конечно читать и больше, найденные ошибки зачтутся, а знания скорее всего пригодятся на шестом курсе.  
 
 
  
 
* [[Полиномиальная иерархия]]
 
* [[Полиномиальная иерархия]]
 
* [[Схемная сложность]]
 
* [[Схемная сложность]]
 
----
 
----
 
  
 
<!--
 
<!--
Строка 163: Строка 166:
 
<pre><nowiki>[[Category:На проверку]]</nowiki></pre>
 
<pre><nowiki>[[Category:На проверку]]</nowiki></pre>
 
и подписываться на изменения («watch this page»).
 
и подписываться на изменения («watch this page»).
 
  
 
Любая активность, даже попытки решения  — хорошо.
 
Любая активность, даже попытки решения  — хорошо.
Строка 179: Строка 181:
 
Эти задачи заводим в
 
Эти задачи заводим в
 
[[:Category:Предложенные студентами задачи]]
 
[[:Category:Предложенные студентами задачи]]
 
 
 
  
 
Все статьи в этой категории — задачи, которые можно пытаться решать.
 
Все статьи в этой категории — задачи, которые можно пытаться решать.
Строка 204: Строка 203:
 
Эти задачи заводим в
 
Эти задачи заводим в
 
[[:Category:Предложенные студентами задачи]]
 
[[:Category:Предложенные студентами задачи]]
 
  
 
----
 
----
  
 +
А еще есть квест
 +
* [[LeetCoding]]
  
 
<!--
 
<!--
Строка 226: Строка 226:
  
 
[[:File:book-advanced-algorithms.pdf]]
 
[[:File:book-advanced-algorithms.pdf]]
 +
 +
Смешное — [https://vk.com/im?sel=1712504&w=wall-54530371_213451%2F1a6855f382934ad3ee реакция «обычных программистов»]
  
 
==== Видео ====
 
==== Видео ====
Строка 234: Строка 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 интерактивный учебник].
 
  
 
==  Полезная сопутствующая литература по курсу.  ==
 
==  Полезная сопутствующая литература по курсу.  ==
Строка 242: Строка 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/>

Текущая версия на 22:52, 26 мая 2020





Семестровый курс по выбору для студентов 3-го курса ФУПМ МФТИ.

Лектор
Стас Фомин


Место чтения курса - ИСПРАН, Станиславского 19.



Формат проведения лекций: демонстрация с проектором с параллельным обсуждением, проверка тестами знаний по предыдущим темам. Подразумевается параллельное изучение студентами электронной версии курса, просмотра видео лекций, решение задач.

Ведется список посещений.

В карантинное время — занимаемся самостоятельно по темам из раздела «Фокус», читаем книгу, смотрим видео и слайды, решаем задачи, см. ниже.

Если будут дополнительные новые лекции или удаленные собрания — об этом будут аннонсы в группе VK.


Успеваемость зарегистрированных студентов

Надо зарегистрироваться

  • Зарегистрироваться здесь. Залогиниться.
  • Зайти на страницу настроек, указать свой email и подтвердить его. Почту от mail.ru не используйте. Она ужасно проблемная (все нотификации уйдут в спам или отразятся сервисом).
  • На своей личной странице, написать хотя бы ФИО и группу.
  • На странице Blog:Advanced Algorithms найти вкладку «следить», и подписаться на этот блог. Но по опыту последних лет, народ разучился пользоватся RSS-подписками… с другой стороны — на ФУПМ МФТИ тотально используется VK — все студенты и администрации в этой сети. Поэтому заведена группа, https://vk.com/discopal, подписывайтесь и туда, туда тоже будут идти обьявления, плюс там же открытые обсуждения и все такое.

Книга

На растерзание отдается свежая сборка — можно искать в ней ошибки (они 100% есть — даже орфографические).

Специально искать опечатки смысла мало, проще действовать по принципу WIN-WIN, читать с помощью PDFXChange или другого ридера, позволяющего делать комментарии, делать пометки по ходу чтения и отсылать (каждый день) помеченный вариант на mailto:stas-fomin@yandex.ru. И каждый день скачивать заново — ибо книга будет пересобираться и меняться постоянно.

?

Пройдено

Фокус

Темы

На этих страницах слайды презентаций, задачи, и т.п. Замечания по каждой презентации можно (и нужно) писать на вкладку «Обсуждение», для соотвествующего PDF-файла.

В книге (и прошлых лекциях) всего сильно больше, но мы сфокусируемся именно на этих темах — на экзамене спрашивать будем только по ним. Но можно конечно читать и больше, найденные ошибки зачтутся, а знания скорее всего пригодятся на шестом курсе.



Тренировка

Проверь себя, помнишь ли элементарные понятия и факты из курса.

Задачи

Все статьи в этой категории — задачи, которые можно пытаться решать.

Решать надо создавая для решения подстраницу личной страницы, и ссылаясь в решении на задачу.

Пример
Задача Вероятностная_проверка_тождеств/Задачи/determinant → Решение Участник:StasFomin/Задача determinant.

Cтатьи-решения задач помечать вставляя строку

[[Category:На проверку]]

и подписываться на изменения («watch this page»).

Любая активность, даже попытки решения — хорошо. После того, как задача решена, она перейдет в архив:

Проверенное решение перейдет в Category:Решения или, если возникнут вопросы-возражения в Category:Проблемы в решении.

Т.е. очередь решений на проверку → Category:На проверку (там сейчас 2 задач), проверяйте, что ваши решения в правильной категории (а то их так и не проверят...).

Отдельно, пробуем новую инициативу — те, кто решил хоть несколько задач, и понял принцип оформления, предлагайте задачи с решениями по теме курса (можно взять из любых знакомых вам курсов и книг с алгоритмами). Этих задач на экзамене не будет, но возможно они пригодятся в следующем году, ну и за них будет выписано много премиальных баллов (2× … 3×… ) по сравнению с решением существующих задач.

Эти задачи заводим в Category:Предложенные студентами задачи

Все статьи в этой категории — задачи, которые можно пытаться решать.

Любая активность, даже попытки решения — хорошо. После того, как задача решена, она перейдет в архив:

Cтатьи-решения задач помечать вставляя строку

[[Category:На проверку]]

и подписываться на изменения («watch this page»).

Проверенное решение перейдет в Category:Решения или, если возникнут вопросы-возражения в Category:Проблемы в решении.

Т.е. очередь решений на проверку → Category:На проверку, проверяйте, что ваши решения в правильной категории (а то их так и не проверят...).

Отдельно, пробуем новую инициативу — те, кто решил хоть несколько задач, и понял принцип оформления, предлагайте задачи с решениями по теме курса (можно взять из любых знакомых вам курсов и книг с алгоритмами). Этих задач на экзамене не будет, но возможно они пригодятся в следующем году, ну и за них будет выписано много премиальных баллов (2× … 3×… ) по сравнению с решением существующих задач.

Эти задачи заводим в Category:Предложенные студентами задачи


А еще есть квест


Книга

Специальная верстка для чтения с ноутбуков и КПК:

  • альбомная ориентация
  • крупные беззасечные шрифты

Кому не нравится — пишите обоснованные протесты (почему, конструктивные предложения).

Пишите замечания по содержимому — про проблемы с версткой и библиографией не писать, все там только в процессе.

File:book-advanced-algorithms.pdf

Смешное — реакция «обычных программистов»

Видео

Записанное видео лекций Николая Николаевича Кузюрина и Стаса Фомина, за весенний семестр 2013 года.

  • http://video.ispras.ru/channels/ispras.ru/lectures/2013/2013-02-21-lectures.uncut.mkv1:23:15 — приближенные алгоритмы с гарантированной точностью, жадные алгоритмы в задаче о покрытии.
  • http://video.ispras.ru/channels/ispras.ru/lectures/2013/2013-02-21-lectures.uncut.mkv2:12:00 — временная и пространственная сложность алгоритмов.
  • http://video.ispras.ru/channels/ispras.ru/lectures/2013/2013-02-21-lectures.uncut.mkv2:36:30 — NP-полнота и сводимости.
  • http://video.ispras.ru/channels/ispras.ru/lectures/2013/2013-02-28-lectures.uncut.mkv0:00:22 — недетерминированные машины Тьюринга, NTIME, NP-полнота, NP-полнота сапера
  • http://video.ispras.ru/channels/ispras.ru/lectures/2013/2013-02-28-lectures.uncut.mkv1:19:30 — метрическая задача коммивояжера, алгоритм Кристофидеса.
  • http://video.ispras.ru/channels/ispras.ru/lectures/2013/2013-03-07-lectures.uncut.mkv0:03:31 — вероятностная проверка тождеств.
  • http://video.ispras.ru/channels/ispras.ru/lectures/2013/2013-03-07-lectures.uncut.mkv0:37:40 — вероятностное округление для MAX-SAT


  • http://video.ispras.ru/channels/ispras.ru/lectures/2013/2013-03-13-lectures.uncut.mkv0:03:59 — криптография, 4 курс
  • http://video.ispras.ru/channels/ispras.ru/lectures/2013/2013-03-14-lectures.uncut.mkv0:01:10 — Дерандомизация MAX-SAT
  • http://video.ispras.ru/channels/ispras.ru/lectures/2013/2013-03-14-lectures.uncut.mkv0:55:40 — Вероятностные классы сложности сложности RP/ZPP.
  • http://video.ispras.ru/channels/ispras.ru/lectures/2013/2013-03-20-lectures.uncut.mkv2:02:34 — Вероятностные классы сложности BPP


  • http://video.ispras.ru/channels/ispras.ru/lectures/2013/2013-03-21-lectures.uncut.mkv0:00:20 — Полиномиальность в среднем, полиномиальный в среднем алгоритм для SAT.
  • http://video.ispras.ru/channels/ispras.ru/lectures/2013/2013-03-28-lectures.uncut.mkv0:00:30 — Рюкзак. Жадный, квазиполиномиальный и PTAS-алгоритм
  • http://video.ispras.ru/channels/ispras.ru/lectures/2013/2013-04-04-lectures.uncut.mkv0:01:12 — BPP, полиномиальная иерархия, схемная сложность.

Примечания и ссылки

Полезная сопутствующая литература по курсу.