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

Материал из DISCOPAL
Перейти к: навигация, поиск
(Темы)
 
(не показано 114 промежуточных версий этого же участника)
Строка 1: Строка 1:
<!-- [[Special:MediawikiQuizzer/Algs-3-course-ispras-weekly|Еженедельная проверка]] -->
+
{{SideBar|
* [[Special:MediawikiQuizzer/Algs-3-course-ispras-exam|Тест перед экзаменом]]  
+
{{Special:Wikilog/Blog:Advanced Algorithms/Template:BlogInformerLine/11/sort=wlp_talk_updated}}
 +
|style=max-width:35%
 +
}}
 +
* Логинимся, и разогревочный тест проверки заданий который были в фокусе несколько недель →  [[Special:MediawikiQuizzer/Algs-3-course-ispras-weekly|Cозвонный тест]]
 +
<!--
 +
* [[Special:MediawikiQuizzer/Algs-3-course-ispras-weekly|Cозвонный тест]]
 +
* [[Special:MediawikiQuizzer/Python|Приветственная созвонная проверка]]
 +
-->
  
<!-- [[Special:MediawikiQuizzer/GRE-CS-v01|Еженедельная проверка — сегодня экспериментальная]] -->
+
* [https://i.0x1.tv/apps/raw/s/mipt-course-03/hard-problems.svg Обзор курса]
 +
 
 +
 
 +
<!--
 +
* [[Special:MediawikiQuizzer/Algs-3-course-ispras-exam|Тест для экстренного набора очков]]
 +
-->
 +
 
 +
<!--
 +
Зум-созвон, пока по четвергам, 10:00.
 +
 
 +
<blockquote>
 +
https://ispras.zoom.us/j/6020710675?pwd=SWxUb3ZjK3NxUzhHTzJRY2Z4YmwxZz09
 +
Meeting ID: 602 071 0675
 +
Passcode: 1729
 +
</blockquote>
 +
-->
 +
 
 +
 
 +
 
 +
 
 +
 
 +
Проходим квест:
 +
{{:Как зарегистрироваться на курс}}
 +
 
 +
----
 +
<poll>
 +
UNSAFE_ID=aa-20240210
 +
ALTERNATIVE
 +
OPEN_RESULTS
 +
OPEN_VOTERS
 +
AUTHORIZED
 +
ALLOW_REVOTE
 +
END_POLL 2024-03-15
 +
Записываемся на курс «Сложность алгоритмов-2024»?
 +
Да
 +
Нет
 +
</poll>
 +
 
 +
 
 +
 
 +
<!--
 +
<poll>
 +
UNSAFE_ID=git-20220210
 +
ALTERNATIVE
 +
AUTHORIZED
 +
ALLOW_REVOTE
 +
END_POLL 2022-02-25
 +
Знаете ли вы Git?
 +
Да
 +
Нет
 +
</poll>
 +
-->
 +
<!--
 +
* [[Special:MediawikiQuizzer/GRE-CS-v01|Сегодняшний квест]]
 +
-->
 +
 
 +
<!-- * [[Special:MediawikiQuizzer/Algs-3-course-ispras-exam|Тест перед экзаменом]] -->
 +
<!--
 +
[[Special:MediawikiQuizzer/GRE-CS-v01|Обещанный тест на повышение оценки с 15:00-15:30]]
 +
-->
  
 
__TOC__
 
__TOC__
Строка 26: Строка 92:
 
<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): Никто не пришел, ведомости заполнены, пытайтесь поймать меня или НН с отрывным. Всем успехов.
 
[[Участник:StasFomin|StasFomin]] 11:25, 29 мая 2019 (MSK): Никто не пришел, ведомости заполнены, пытайтесь поймать меня или НН с отрывным. Всем успехов.
Строка 50: Строка 115:
 
[[Special:MediawikiQuizzer/Algs-3-course-ispras-exam|Предэкзаменационный тест]]
 
[[Special:MediawikiQuizzer/Algs-3-course-ispras-exam|Предэкзаменационный тест]]
 
-->
 
-->
 
{{SideBar|
 
{{Special:Wikilog/Blog:Advanced Algorithms/Template:BlogInformerLine/3/sort=wlp_talk_updated}}
 
|style=max-width:35%
 
}}
 
  
 
<!-- Курс лекций «Сложность алгоритмы» для 3 курса курса МФТИ. -->
 
<!-- Курс лекций «Сложность алгоритмы» для 3 курса курса МФТИ. -->
Строка 60: Строка 120:
 
Семестровый курс по выбору для студентов 3-го курса ФУПМ МФТИ.
 
Семестровый курс по выбору для студентов 3-го курса ФУПМ МФТИ.
  
;Лектор: [mailto:stas-fomin@yandex.ru Стас Фомин]
+
;Лекторы: [mailto:stas-fomin@yandex.ru Стас Фомин],
  
Место чтения курса - ИСПРАН,
+
 
Солженицына, можно найти в общем, 110 аудитория.
+
<!-- Место чтения курса - ИСПРАН, Станиславского 19.
 +
Солженицына, можно найти в общем, 110 аудитория. -->
  
 
<!--
 
<!--
Строка 77: Строка 138:
 
----
 
----
  
 +
Формат проведения лекций: демонстрация с проектором с параллельным обсуждением, проверка тестами знаний по предыдущим темам. Подразумевается параллельное изучение студентами электронной версии курса, просмотра видео лекций, решение задач.
  
 +
Ведется [https://docs.google.com/spreadsheet/pub?key=0Ao6tsK_6FZEldFhKM3F6TzlQWmtXY3owalpvT3BRS2c&single=true&gid=11&output=html список посещений].
  
 +
<blockquote>
 +
В карантинное время — занимаемся самостоятельно по темам из раздела «Фокус»,
 +
читаем книгу, смотрим видео и слайды, решаем задачи, см. ниже.
 +
</blockquote>
  
Формат проведения лекций: демонстрация с проектором с параллельным обсуждением, проверка тестами знаний по предыдущим темам. Подразумевается параллельное изучение студентами электронной версии курса, просмотра видео лекций, решение задач.
 
  
Ведется [https://docs.google.com/spreadsheet/pub?key=0Ao6tsK_6FZEldFhKM3F6TzlQWmtXY3owalpvT3BRS2c&single=true&gid=11&output=html список посещений].
 
  
 
<html><center>
 
<html><center>
Строка 88: Строка 153:
 
</center></html>
 
</center></html>
  
 +
<!--
 
== Надо зарегистрироваться ==
 
== Надо зарегистрироваться ==
* Зарегистрироваться здесь. Залогиниться.
+
* Зарегистрироваться здесь. Залогиниться.  
* Зайти на страницу [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, подписывайтесь и туда, туда тоже будут идти обьявления, плюс там же открытые обсуждения и все такое.
 +
-->
  
 
== Книга ==
 
== Книга ==
Строка 101: Строка 168:
 
Специально искать опечатки смысла мало, проще действовать по принципу 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]]
 
* [[https://www.math.ucdavis.edu/~greg/zoology/diagram.xml zoo]]
  
== Пройдено ==
+
== Темы ==
 
+
=== Пройдено ===
 
+
[[Файл:Усвоим весь объем — вовсе нет.png|360px|right]]
== Фокус ==
+
 
* [[Формально об алгоритмах. Вычислительные модели]]
 
* [[Формально об алгоритмах. Вычислительные модели]]
 
* [[Временная и пространственная сложность алгоритмов]]
 
* [[Временная и пространственная сложность алгоритмов]]
 +
* [[Полиномиальные сводимости и NP-полные задачи. Классы NP, coNP, NPC]]
  
 
+
=== Фокус ===
== Темы ==
+
* [[Полиномиальные сводимости и NP-полные задачи. Классы NP, coNP, NPC]]
+
 
* [[Вероятностные вычисления. Классы RP, coRP, ZPP, BPP]]
 
* [[Вероятностные вычисления. Классы RP, coRP, ZPP, BPP]]
* [[Вероятностно проверяемые доказательства. PCP-системы. PCP-теорема]]
 
* [[PCP и аппроксимируемость]]
 
 
* [[Жадный алгоритм в задачах о покрытии]]
 
* [[Жадный алгоритм в задачах о покрытии]]
 
* [[Жадный алгоритм в задаче о рюкзаке]]
 
* [[Жадный алгоритм в задаче о рюкзаке]]
Строка 126: Строка 186:
 
* [[Полностью полиномиальная аппроксимационная схема (FPTAS) для задачи о рюкзаке]]
 
* [[Полностью полиномиальная аппроксимационная схема (FPTAS) для задачи о рюкзаке]]
 
* [[Полиномиальный в среднем алгоритм для задачи о рюкзаке]]
 
* [[Полиномиальный в среднем алгоритм для задачи о рюкзаке]]
 +
 +
=== Не пройдено ===
 +
 +
* [[Приближенный алгоритм для метрической задачи коммивояжера]]
 +
 
* [[Полиномиальный в среднем алгоритм для SAT]]
 
* [[Полиномиальный в среднем алгоритм для SAT]]
 
* [[Полиномиальный в среднем алгоритм для задачи упаковки]]
 
* [[Полиномиальный в среднем алгоритм для задачи упаковки]]
 +
* [[Приближенный алгоритм для метрической задачи коммивояжера]]
 
* [[Вероятностная проверка тождеств]]
 
* [[Вероятностная проверка тождеств]]
 
* [[MAX-SAT: вероятностное округление]]
 
* [[MAX-SAT: вероятностное округление]]
 
* [[MAX-SAT: дерандомизация]]
 
* [[MAX-SAT: дерандомизация]]
 
 
* [[MAX-CUT: вероятностное округление]]
 
* [[MAX-CUT: вероятностное округление]]
 +
* [[Вероятностный подсчет числа выполняемых наборов для ДНФ]]
  
 
+
=== Может и не будем ===
 
+
* [[Вероятностно проверяемые доказательства. PCP-системы. PCP-теорема]]
 +
* [[PCP и аппроксимируемость]]
 +
* [[Полиномиальная иерархия]]
 +
* [[Схемная сложность]]
  
 
На этих страницах слайды презентаций, задачи, и т.п.
 
На этих страницах слайды презентаций, задачи, и т.п.
Строка 144: Строка 213:
  
  
 
* [[Полиномиальная иерархия]]
 
* [[Схемная сложность]]
 
 
----
 
----
 
  
 
<!--
 
<!--
* [[Приближенный алгоритм для метрической задачи коммивояжера]]
 
 
* [[Вероятностный подсчет числа выполняемых наборов для ДНФ]]
 
* [[Вероятностный подсчет числа выполняемых наборов для ДНФ]]
 
-->
 
-->
Строка 159: Строка 223:
 
[[Special:MediawikiQuizzer/Algs-3-course-ispras-weekly|Проверь себя]], помнишь ли элементарные понятия и факты из курса.
 
[[Special:MediawikiQuizzer/Algs-3-course-ispras-weekly|Проверь себя]], помнишь ли элементарные понятия и факты из курса.
  
== Задачи ==
+
== Практика ==
Все статьи в этой категории — задачи, которые можно пытаться решать.
+
{{:Практикуемся В Алгоритмах}}
* [[:Category:Нерешенные задачи]].  Осталось  {{!|{{PAGESINCATEGORY: Нерешенные задачи}}}} нерешенных задач.
+
  
Решать надо создавая для решения ''подстраницу'' личной страницы, и ссылаясь в решении на задачу.
+
== Моделирование труднорешаемых задач ==
;Пример: Задача [[Вероятностная_проверка_тождеств/Задачи/determinant]] → Решение [[Участник:StasFomin/Задача determinant]].
+
{{:Моделирование труднорешаемых задач}}
Cтатьи-решения задач помечать вставляя строку
+
+
<pre><nowiki>[[Category:На проверку]]</nowiki></pre>
+
и подписываться на изменения («watch this page»).
+
  
 +
----
 +
Кому надо 10-баллов — запишите видеоролики по вашим питон-ноутбукам, см. [[Blog:Advanced Algorithms/2022-12-01 Кто решил бизнес-задачи, запишите по ним видеоролики]]
  
Любая активность, даже попытки решения  — хорошо.
+
== Теоретические упражнения ==
После того, как задача решена, она перейдет в архив:
+
Достаточно 3 задач из двух тем.
* [[:Category:Решенные задачи]].
+
  
Проверенное решение перейдет в [[:Category:Решения]] или,
+
{{:Решаем теоретические упражнения}}
если возникнут вопросы-возражения в [[:Category:Проблемы в решении]].
+
 
+
Т.е. очередь решений на проверку → [[:Category:На проверку]] (там сейчас {{!|{{PAGESINCATEGORY: На проверку}}}} задач), проверяйте, что ваши решения в правильной категории (а то их так и не проверят...).
+
  
 +
<!--
 
Отдельно, пробуем новую инициативу — те, кто решил хоть несколько задач, и понял принцип оформления, предлагайте задачи с решениями по теме курса (можно взять из любых знакомых вам курсов и книг с алгоритмами).
 
Отдельно, пробуем новую инициативу — те, кто решил хоть несколько задач, и понял принцип оформления, предлагайте задачи с решениями по теме курса (можно взять из любых знакомых вам курсов и книг с алгоритмами).
 
Этих задач на экзамене не будет, но возможно они пригодятся в следующем году, ну и за них будет выписано много премиальных баллов (2× … 3×… ) по сравнению с решением существующих задач.
 
Этих задач на экзамене не будет, но возможно они пригодятся в следующем году, ну и за них будет выписано много премиальных баллов (2× … 3×… ) по сравнению с решением существующих задач.
Строка 185: Строка 243:
 
Эти задачи заводим в
 
Эти задачи заводим в
 
[[:Category:Предложенные студентами задачи]]
 
[[:Category:Предложенные студентами задачи]]
 +
-->
  
 +
----
  
 
 
Все статьи в этой категории — задачи, которые можно пытаться решать.
 
* [[:Category:Нерешенные задачи]].
 
Любая активность, даже попытки решения  — хорошо.
 
После того, как задача решена, она перейдет в архив:
 
* [[:Category:Решенные задачи]] — кстати, полезно смотреть чужие решения.
 
 
Cтатьи-решения задач помечать вставляя строку
 
 
<pre><nowiki>[[Category:На проверку]]</nowiki></pre>
 
и подписываться на изменения («watch this page»).
 
 
Проверенное решение перейдет в [[:Category:Решения]] или,
 
если возникнут вопросы-возражения в [[:Category:Проблемы в решении]].
 
 
Т.е. очередь решений на проверку → [[:Category:На проверку]], проверяйте, что ваши решения в правильной категории (а то их так и не проверят...).
 
 
Отдельно, пробуем новую инициативу — те, кто решил хоть несколько задач, и понял принцип оформления, предлагайте задачи с решениями по теме курса (можно взять из любых знакомых вам курсов и книг с алгоритмами).
 
Этих задач на экзамене не будет, но возможно они пригодятся в следующем году, ну и за них будет выписано много премиальных баллов (2× … 3×… ) по сравнению с решением существующих задач.
 
 
Эти задачи заводим в
 
[[:Category:Предложенные студентами задачи]]
 
 
 
----
 
  
  
Строка 232: Строка 266:
  
 
[[:File:book-advanced-algorithms.pdf]]
 
[[:File:book-advanced-algorithms.pdf]]
 +
 +
Смешное — [https://vk.com/im?sel=1712504&w=wall-54530371_213451%2F1a6855f382934ad3ee реакция «обычных программистов»]
  
 
==== Видео ====
 
==== Видео ====
 +
 +
;Update: Можно не смотреть, технология многопоточных MKV-перестала работать, будет новое видео, небольшими блоками.
 
{{/Лекции весеннего семестра 2013}}
 
{{/Лекции весеннего семестра 2013}}
  
 
== Примечания и ссылки ==
 
== Примечания и ссылки ==
  
* Рекомендуем изучить 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 интерактивный учебник].
+
 
+
  
 
==  Полезная сопутствующая литература по курсу.  ==
 
==  Полезная сопутствующая литература по курсу.  ==
Строка 248: Строка 284:
 
* Еще один классический [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) - лектор -- Мусатов Д.В.], [https://vk.com/video-176869000_456239030 трейлер]
  
 +
----
 +
{{:Библиотека}}
  
 +
 +
<!--
 
== Нужно знать! ==
 
== Нужно знать! ==
  
 
[[File:Что ждут на курсе по криптографии от вас.jpg|800px|center]]
 
[[File:Что ждут на курсе по криптографии от вас.jpg|800px|center]]
 
+
-->
  
 
<references/>
 
<references/>

Текущая версия на 15:42, 11 марта 2024


  • Логинимся, и разогревочный тест проверки заданий который были в фокусе несколько недель → Cозвонный тест





Проходим квест:

  • Зарегистрироваться здесь. Залогинится.
  • Зайти на страницу настроек, указать свой email и подтвердить его.
  • На своей личной странице (это не страница настроек, это то, что сверху слева, с иконкой человечка), написать хотя бы ФИО и группу.
    • Боже, как много народу с рассеянным вниманием уже до сюда не дочитывает.
  • Присоединится к телеграмм-группе.
  • Отметится в этом голосовании:

Записываемся на курс «Сложность алгоритмов-2024»?

Да17
94%
Alexpaniman, Dainbow, Danmax2003, Dany, DeGekata, Ermakov, Kosty, Mishaglik, Nemoumbra, Protobarhatus, Schet, Sferf, Stanislav, Taekwandodo, Xdlolik, Гусаков Игорь, КрисУкралРис
Нет1
6%
ArtemMaslov

Вы должны войти в систему, чтобы участвовать в этом голосовании.






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

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




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

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

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


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


Книга

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

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

?

Темы

Пройдено

Усвоим весь объем — вовсе нет.png

Фокус

Не пройдено

Может и не будем

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

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




Тренировка

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

Практика

2021-10-15 Practical Block 2021-11-03 14-27-56 image0.png

Концептуально:

2021-10-15 Practical Block 2021-11-03 15-02-30 image0.png

2021-10-15 Practical Block 2021-11-03 14-24-09 image0.png

(Их там 66)

    • Не нужно брать десятки задач на себя сразу, и освобождайте то, что не получается.
  • Решенное
    • Ну смотрите, как оформлено в прошлые годы
    • Решение на подстранице вашей личной страницы
      • Вики-ссылка на задачу
      • Python-код в «<source lang="python"></source>»
      • Метка «{{checkme}}», когда решите.
2021-10-15 Practical Block 2021-11-03 14-22-47 image0.png

(Их там 10)


  • Как легче решать Python
    • Загрузка данных
    • Выбирайте более свежий CPython или PyPy.

Моделирование труднорешаемых задач

Обязательно посмотрите

Цели: для осеннего курса 2023, где собрались скорее заинтересованные практикой, чем сложностью задач, можно

  • Сделать одну задачу целиком (визуализация, постановка в ЦЛП и сведение от 3SAT)
  • Или пару задач «поверхностно» — постановка + визуализация (это легкая часть), без части про сведение от 3SAT и тестирования (это может быть очень головоломно).
  • Можно сделать и больше, такой же блок, может заменить решение задачи из Моделирование бизнес-задач, если те почему-то не понравились.
  • Может можно будет даже сделать и меньше, если будет сделано качественно (красивая визуализация, или сложная задача и т.п) — т.е. не надо гнать количество, лучше сделать хорошо и красиво.
  • Разумеется, можно использовать все, что найдете в интернете (код, статьи, книги), или подскажут нейросети (но они обычно подсказывают неверно).


Проблема текущих подходов.

Моделирование труднорешаемых задач 2023-04-24 14-45-02 image0.png

Проблема текущих подходов к преподаванию вычислительной сложности и труднорешаемых задач:

  • «ненужная заумь для ботанов»
  • «всякой фигни как матло у нас нет, у нас проектный подход»© (день открытых дверей МФТИ).
  • множество книг, слайдов, видео и т.п. — но все как правило перепев «ГД», на досках или одноразовых веселых видео.
    • но не «живые модели»!

Результат .

  • Нет навыков проверяемых доказательств
  • Не получаются навыки работы с труднорешаемыми задачами.
    • Мучать «эвристики» и «нейросети» не приходя в сознание.
      • «Какая у вас задача» — ну мы тут «GAN» сети пробовали, вот теперь трансформеры… — Задача то какая?


Что делать?.

  • Научится формализованно формулировать
    • ЦЛП
    • 3SAT
  • Использовать решатели
    • ЦЛП (cbc, coin, SCIP, CPLEX, GUROBI, COPT, MIPT…)
    • SAT (см. SAT-Races [1]).

Тогда можно .

  • Часто решить задачу для реальных данных сходу
    • Или покрутить постановку чтобы задача решалась (релаксация бизнес-ограничений).
  • Начать тестировать
    • Алгоритмы полиномиальные в среднем
    • Приближенные алгоритмы с гарантией точности
    • Вероятностные алгоритмы
    • Эвристики
  • Доказать труднорешаемость
    • Конструктивное сведение кодом, тестирование
    • Потом статья с объяснением.

Конструктивные алгоритмические доказательства .

Что вы получите .


  • → Бизнес-аналитик-алгоритмист! (нарасхват!)
  • → Курсовые-дипломы-статьи в JN
    • В любой ситуации

С чем работаем .

  • Настоящие классические задачи в одном месте (ГД+ВК+…)
    • Open Classic Hard Problems
      • Не пугайтесь, вам достаточно изучить одну задачу… но можно и все.
        • Не «книга, толщиной защищающая от прочтения»
  • Там (см. беджики-ссылки)
    • Постановки
    • Наброски ноутбуков для всех задач в Lab17
    • Частично готовая модель
        • тестовые данные (генератор)
        • визуализация
        • сведение к ЦЛП через Pyomo
        • сведение с 3SAT к задаче
        • вероятностное тестирование
        • видео с разьяснениями

Начать с простого .

Ваш квест .

  • Pyomo-сведение к ЦЛП → PyomoLogo.png — есть Pyomo-формулировка для ЦЛП., Data-vis-logo.png — есть тестовые данные и визуализация.
  • 3SAT-сведение к задаче → Npc-reduction-python-logo.png — есть сведение на Python NP-полной задачи к данной.
  • Вероятностное тестирование → Yes-you-can-icon.png Можно доработать — сделать Вероятностное тестирование NPC-сведения!
  • Можно
    • все для одной задачи,
    • можно для разных (исправление ошибки или улучшение — ОК)
Желательно напрямую с 3SAT .

Без классического дерева сведения (но можно копировать функции сведения тех задач).

Моделирование труднорешаемых задач 2023-04-27 00-05-30 image0.png

Как с этим работаем .

  • Выбирайте задачи из Open Classic Hard Problems, переходите к редактированию по «Беру…» →
    • Зарезервированные задачи просто помечаются в том же списке, для простоты.
    • Воркфлоу «взятия задачи» аналогичен блоку «Практикуемся_В_Алгоритмах»
    • Только здесь, в вики, на «странице решения» обсуждаем постановку (если что-то непонятно), а решением будет юпитер-ноутбук в Lab17.
  • Всего должно хватать в нашем Lab17
  • Как поотлаживаться локально через VSCode — потом.


Еще раз обо всем этом на одном слайде .

Файл:Idea-hard-problems-course.svg

Картинка в полный размер


Кому надо 10-баллов — запишите видеоролики по вашим питон-ноутбукам, см. Blog:Advanced Algorithms/2022-12-01 Кто решил бизнес-задачи, запишите по ним видеоролики

Теоретические упражнения

Достаточно 3 задач из двух тем.

  • Нужно быть залогиненным
    • Скрыто из интернета
  • Надо решить N задач из M разных разделов.
  • Либо одну бонусную задачу — считаем, что ее решение закрывает квест.
  • Выбирайте задачи из Open Exercises, переходите к редактированию по «Беру…»
    • помечайте их как {{reserve-task|~~~~~}}
    • Решение на подстранице вашей личной страницы
      • Вики-ссылка на задачу
      • Решение — можно использовать текст, латех целиком внутри тега «latex», или просто вставки математики внутри тега «m»
      • На худой конец — очень аккуратно оформить на листочке, сфотографировать, загрузить файлы (разберетесь).
      • Метка «{{checkme}}», когда решите.
      • Внизу вставка всего этого по клику →
  • Они попадут в Категория:На проверку
  • Все как обычно в наших квестах.





Книга

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

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

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

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

File:book-advanced-algorithms.pdf

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

Видео

Update
Можно не смотреть, технология многопоточных MKV-перестала работать, будет новое видео, небольшими блоками.


Записанное видео лекций Николая Николаевича Кузюрина и Стаса Фомина, за весенний семестр 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, полиномиальная иерархия, схемная сложность.

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

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