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

Материал из DISCOPAL
Перейти к: навигация, поиск
(не показано 45 промежуточных версий 2 участников)
Строка 1: Строка 1:
<!-- [[Special:MediawikiQuizzer/Algs-3-course-ispras-exam|Предэкзаменационный тест]] -->
+
[[Special:MediawikiQuizzer/Algs-3-course-ispras-weekly|Еженедельная проверка]]
 
+
  
 
__TOC__
 
__TOC__
  
 +
<!-- Если кто-то еще хочет в этом семестре сдавать — [mailto:stas-fomin@yandex.ru пишите], будем договариваться.
 +
-->
  
Залогиньтесь, выбирайте удобное время (у вас три голоса), и записывайтесь.
+
<!--
 
<poll>
 
<poll>
POINTS 3
 
 
AUTHORIZED
 
AUTHORIZED
UNSAFE ID=2016-05-18-when-exam
+
ALTERNATIVE
 +
UNSAFE ID=2017-05-25-record-for-exam
 
REVOTE
 
REVOTE
 
OPEN_RESULTS
 
OPEN_RESULTS
 
OPEN_VOTERS
 
OPEN_VOTERS
Удобный вам день для зачета по нашему курсу:
+
Вы будете сдавать зачет в 9:00, 25 мая 2017, в четверг, в 301?
2016-05-20
+
Да
2016-05-23
+
Нет
2016-05-24
+
2016-05-25
+
2016-05-26
+
2016-05-27
+
2016-05-30
+
2016-05-31
+
2016-06-01
+
2016-06-02
+
2016-06-03
+
 
</poll>
 
</poll>
 +
-->
  
 +
<!--
 +
<poll>
 +
AUTHORIZED
 +
POINTS 3
 +
UNSAFE ID=2017-05-26-record-for-exam
 +
REVOTE
 +
OPEN_RESULTS
 +
OPEN_VOTERS
 +
Какие дни утром удобны для сдачи? Можно использовать три голоса.
 +
2017-05-30, вторник
 +
2017-05-31, среда
 +
2017-06-01, четверг
 +
2017-06-02, пятница
 +
</poll>
 +
-->
  
 
<!--
 
<!--
Строка 46: Строка 54:
 
Солженицына, можно найти в общем, 110 аудитория.
 
Солженицына, можно найти в общем, 110 аудитория.
  
[https://titanpad.com/discopal Интерактивная Доска]
+
* В этом году это не экзамен, а дифференцированный зачет. Почти все получили оценку<ref>10 мая</ref> по результатам активности на семинарах и в домашних задачах.
 +
** Пара оставшихся будет сдавать зачет Николаю Николаевичу Кузюрину, следите за обьявлениями. Ближайший прием — вторник, 29 мая, c 13:00 до 16-17, 301.
 +
** Если кто-то недоволен оценкой — пишите, договаривайтесь о пересдаче и т.п.
 +
** Ведомости пока не заполнены, буду заполнены и сданы по гуглтаблице где-то в июне.
 +
 
  
 
<!--
 
<!--
В этом году это не экзамен, а дифференцированный зачет.
+
[https://titanpad.com/discopal Интерактивная Доска]
Если кто-то недоволен оценкой — пишите, договаривайтесь о пересдаче и т.п.
+
Ведомости пока не заполнены, буду заполнены и сданы по гуглтаблице где-то 25 июня.
+
 
-->
 
-->
 
----
 
----
Строка 67: Строка 77:
  
 
== Надо зарегистрироваться ==
 
== Надо зарегистрироваться ==
* Зарегистрироваться здесь. Залогинится.
+
* Зарегистрироваться здесь. Залогиниться.
 
* Зайти на страницу [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 и подтвердить его.
 
* На своей личной странице, написать хотя бы ФИО и группу.
 
* На своей личной странице, написать хотя бы ФИО и группу.
 
* На странице [[Blog:Advanced Algorithms]] найти вкладку «следить», и подписаться на этот блог. Но по опыту последних лет, народ разучился пользоватся RSS-подписками… с другой стороны — на ФУПМ МФТИ тотально используется VK — все студенты и администрации в этой сети. Поэтому заведена группа, https://vk.com/discopal, подписывайтесь и туда, туда тоже будут идти обьявления, плюс там же открытые обсуждения и все такое.
 
* На странице [[Blog:Advanced Algorithms]] найти вкладку «следить», и подписаться на этот блог. Но по опыту последних лет, народ разучился пользоватся RSS-подписками… с другой стороны — на ФУПМ МФТИ тотально используется VK — все студенты и администрации в этой сети. Поэтому заведена группа, https://vk.com/discopal, подписывайтесь и туда, туда тоже будут идти обьявления, плюс там же открытые обсуждения и все такое.
 
  
 
== Книга ==
 
== Книга ==
На растерзание отдается [https://www.dropbox.com/s/69yfnlcf1332090/book-advanced-algorithms.book.pdf?dl=0 свежая сборка] — можно искать в ней ошибки (они 100% есть — даже орфографические).
+
На растерзание отдается [https://www.dropbox.com/s/co3zye1k98efsfa/book-advanced-algorithms.book.pdf?dl=0 свежая сборка] — можно искать в ней ошибки (они 100% есть — даже орфографические).
  
 
Специально искать опечатки смысла мало, проще действовать по принципу WIN-WIN, читать с помощью PDFXChange или другого ридера, позволяющего делать комментарии, делать пометки по ходу чтения и отсылать (каждый день) помеченный вариант на mailto:stas-fomin@yandex.ru.
 
Специально искать опечатки смысла мало, проще действовать по принципу WIN-WIN, читать с помощью PDFXChange или другого ридера, позволяющего делать комментарии, делать пометки по ходу чтения и отсылать (каждый день) помеченный вариант на mailto:stas-fomin@yandex.ru.
 
И каждый день скачивать заново — ибо книга будет пересобираться и меняться постоянно.
 
И каждый день скачивать заново — ибо книга будет пересобираться и меняться постоянно.
  
== Пройденные темы ==
+
 
 +
 
 +
 
 +
=== ? ===
 +
* [[https://www.math.ucdavis.edu/~greg/zoology/diagram.xml zoo]]
 +
 
 +
== Пройдено ==
 
* [[Формально об алгоритмах. Вычислительные модели]]
 
* [[Формально об алгоритмах. Вычислительные модели]]
 
* [[Временная и пространственная сложность алгоритмов]]
 
* [[Временная и пространственная сложность алгоритмов]]
 
* [[Полиномиальные сводимости и NP-полные задачи. Классы NP, coNP, NPC]]
 
* [[Полиномиальные сводимости и NP-полные задачи. Классы NP, coNP, NPC]]
 
* [[Вероятностные вычисления. Классы RP, coRP, ZPP, BPP]]
 
* [[Вероятностные вычисления. Классы RP, coRP, ZPP, BPP]]
 
 
* [[Жадный алгоритм в задачах о покрытии]]
 
* [[Жадный алгоритм в задачах о покрытии]]
 
* [[Жадный алгоритм в задаче о рюкзаке]]
 
* [[Жадный алгоритм в задаче о рюкзаке]]
 
* [[Динамическое программирование для задачи о рюкзаке]]
 
* [[Динамическое программирование для задачи о рюкзаке]]
 
* [[Полностью полиномиальная аппроксимационная схема (FPTAS) для задачи о рюкзаке]]
 
* [[Полностью полиномиальная аппроксимационная схема (FPTAS) для задачи о рюкзаке]]
 +
 +
== Фокус ==
 +
* [[Полиномиальный в среднем алгоритм для SAT]]
 +
* [[Полиномиальный в среднем алгоритм для задачи упаковки]]
 
* [[Полиномиальный в среднем алгоритм для задачи о рюкзаке]]
 
* [[Полиномиальный в среднем алгоритм для задачи о рюкзаке]]
 
 
* [[Вероятностная проверка тождеств]]
 
* [[Вероятностная проверка тождеств]]
 
* [[MAX-SAT: вероятностное округление]]
 
* [[MAX-SAT: вероятностное округление]]
 
* [[MAX-SAT: дерандомизация]]
 
* [[MAX-SAT: дерандомизация]]
* [[Полиномиальный в среднем алгоритм для SAT]]
+
 
  
 
== Темы ==
 
== Темы ==
 
+
На этих страницах слайды презентаций, задачи, и т.п.
Рассмотренные в курсе темы.
+
Замечания по каждой презентации можно (и нужно) писать на вкладку «Обсуждение», для соотвествующего PDF-файла.
  
 
В книге (и прошлых лекциях) всего сильно больше, но мы сфокусируемся именно на этих темах — на экзамене спрашивать будем только по ним.
 
В книге (и прошлых лекциях) всего сильно больше, но мы сфокусируемся именно на этих темах — на экзамене спрашивать будем только по ним.
 
Но можно конечно читать и больше, найденные ошибки зачтутся, а знания скорее всего пригодятся на шестом курсе.  
 
Но можно конечно читать и больше, найденные ошибки зачтутся, а знания скорее всего пригодятся на шестом курсе.  
  
На этих страницах слайды презентаций, задачи, и т.п.
 
Замечания по каждой презентации можно (и нужно) писать на вкладку «Обсуждение», для соотвествующего PDF-файла.
 
  
* [[Жадный алгоритм в задачах о покрытии]]
+
 
* [[Жадный алгоритм в задаче о рюкзаке]]
+
* [[Полиномиальная иерархия]]
 +
* [[Схемная сложность]]
 +
----
 +
 
 +
 
 +
<!--
 
* [[Приближенный алгоритм для метрической задачи коммивояжера]]
 
* [[Приближенный алгоритм для метрической задачи коммивояжера]]
* [[Динамическое программирование для задачи о рюкзаке]]
 
* [[Полностью полиномиальная аппроксимационная схема (FPTAS) для задачи о рюкзаке]]
 
* [[Полиномиальный в среднем алгоритм для SAT]]
 
* [[Вероятностная проверка тождеств]]
 
* [[MAX-SAT: вероятностное округление]]
 
* [[MAX-SAT: дерандомизация]]
 
 
* [[Вероятностный подсчет числа выполняемых наборов для ДНФ]]
 
* [[Вероятностный подсчет числа выполняемых наборов для ДНФ]]
* [[Формально об алгоритмах. Вычислительные модели]]
+
-->
* [[Временная и пространственная сложность алгоритмов]]
+
 
* [[Полиномиальные сводимости и NP-полные задачи. Классы NP, coNP, NPC]]
+
== Тренировка ==
* [[Вероятностные вычисления. Классы RP, coRP, ZPP, BPP]]
+
 
* [[Полиномиальная иерархия]]
+
[[Special:MediawikiQuizzer/Algs-3-course-ispras-weekly|Проверь себя]], помнишь ли элементарные понятия и факты из курса.
 +
 
 +
== Задачи ==
 +
Все статьи в этой категории — задачи, которые можно пытаться решать.
 +
* [[:Category:Нерешенные задачи]].  Осталось  {{!|{{PAGESINCATEGORY: Нерешенные задачи}}}} нерешенных задач.
 +
 
 +
Решать надо создавая для решения ''подстраницу'' личной страницы, и ссылаясь в решении на задачу.
 +
;Пример: Задача [[Вероятностная_проверка_тождеств/Задачи/determinant]] → Решение [[Участник:StasFomin/Задача determinant]].
 +
Cтатьи-решения задач помечать вставляя строку
 +
 +
<pre><nowiki>[[Category:На проверку]]</nowiki></pre>
 +
и подписываться на изменения («watch this page»).
 +
 
 +
 
 +
Любая активность, даже попытки решения  — хорошо.
 +
После того, как задача решена, она перейдет в архив:
 +
* [[:Category:Решенные задачи]].
 +
 
 +
Проверенное решение перейдет в [[:Category:Решения]] или,
 +
если возникнут вопросы-возражения в [[:Category:Проблемы в решении]].
 +
 
 +
Т.е. очередь решений на проверку → [[:Category:На проверку]] (там сейчас {{!|{{PAGESINCATEGORY: На проверку}}}} задач), проверяйте, что ваши решения в правильной категории (а то их так и не проверят...).
 +
 
 +
Отдельно, пробуем новую инициативу — те, кто решил хоть несколько задач, и понял принцип оформления, предлагайте задачи с решениями по теме курса (можно взять из любых знакомых вам курсов и книг с алгоритмами).
 +
Этих задач на экзамене не будет, но возможно они пригодятся в следующем году, ну и за них будет выписано много премиальных баллов (2× … 3×… ) по сравнению с решением существующих задач.
 +
 
 +
Эти задачи заводим в
 +
[[:Category:Предложенные студентами задачи]]
 +
 
  
= Тренировка =
 
  
[[Special:MediawikiQuizzer/Algs-3-course-ispras|Проверь себя]], помнишь ли элементарные понятия и факты из курса.
 
Тест возможно будет на экзамене, чтобы отсеять совсем невменяемых.
 
  
= Задачи =
 
 
Все статьи в этой категории — задачи, которые можно пытаться решать.
 
Все статьи в этой категории — задачи, которые можно пытаться решать.
 
* [[:Category:Нерешенные задачи]].
 
* [[:Category:Нерешенные задачи]].

Версия 09:34, 27 мая 2018

Еженедельная проверка




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

Лекторы
д.ф.-м.н. Н.Н. Кузюрин, С.А. Фомин

Место чтения курса - ИСПРАН, Солженицына, можно найти в общем, 110 аудитория.

  • В этом году это не экзамен, а дифференцированный зачет. Почти все получили оценку[1] по результатам активности на семинарах и в домашних задачах.
    • Пара оставшихся будет сдавать зачет Николаю Николаевичу Кузюрину, следите за обьявлениями. Ближайший прием — вторник, 29 мая, c 13:00 до 16-17, 301.
    • Если кто-то недоволен оценкой — пишите, договаривайтесь о пересдаче и т.п.
    • Ведомости пока не заполнены, буду заполнены и сданы по гуглтаблице где-то в июне.





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

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

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

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

  • Зарегистрироваться здесь. Залогиниться.
  • Зайти на страницу настроек, указать свой email и подтвердить его.
  • На своей личной странице, написать хотя бы ФИО и группу.
  • На странице 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:На проверку (там сейчас 10 задач), проверяйте, что ваши решения в правильной категории (а то их так и не проверят...).

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

Эти задачи заводим в 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, полиномиальная иерархия, схемная сложность.

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


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


  1. 10 мая