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

{{SideBar|
{{Special:Wikilog/Blog:Advanced Algorithms/Template:BlogInformerLine/11/sort=wlp_talk_updated}}
|style=max-width:35%
}}

<!--
* Логинимся, и разогревочный тест проверки заданий который были в фокусе 5 недель →  [[Special:MediawikiQuizzer/Algs-3-course-ispras-weekly|Cозвонный тест]]
-->

<!--
* [[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-20230210
ALTERNATIVE
OPEN_RESULTS
OPEN_VOTERS
AUTHORIZED
ALLOW_REVOTE
END_POLL 2023-03-15
Записываемся на курс «Сложность алгоритмов-2023»?
Да
Нет
</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__

<!-- Если кто-то еще хочет в этом семестре сдавать — [mailto:stas-fomin@yandex.ru пишите], будем договариваться.
-->

<!--
<poll>
AUTHORIZED
UNSAFE ID=2019-05-21-record-for-exam
REVOTE
OPEN_RESULTS
OPEN_VOTERS
Выберите удобный день для сдачи зачета (можно несколько).
2019-05-27
2019-05-28
2019-05-29
2019-05-30
2019-05-31
</poll>

<s>Хорошо, по результатам голосования встречаемся в четверг, в 11:00, 2019-05-30</s>
Хорошо, по результатам переголосования встречаемся в среду, в 10:00, 2019-05-29

[[Участник:StasFomin|StasFomin]] 11:25, 29 мая 2019 (MSK): Никто не пришел, ведомости заполнены, пытайтесь поймать меня или НН с отрывным. Всем успехов.
-->

<!--
<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>
-->

<!--
[[Special:MediawikiQuizzer/Algs-3-course-ispras-exam|Предэкзаменационный тест]]
-->

<!-- Курс лекций «Сложность алгоритмы» для 3 курса курса МФТИ. -->

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

;Лекторы: [mailto:stas-fomin@yandex.ru Стас Фомин], 


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

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

<!--
[https://titanpad.com/discopal Интерактивная Доска]
-->
----

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

Ведется [https://docs.google.com/spreadsheet/pub?key=0Ao6tsK_6FZEldFhKM3F6TzlQWmtXY3owalpvT3BRS2c&single=true&gid=11&output=html список посещений].

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



<html><center>
</p><div class="sites-embed-align-left-wrapping-off"><div class="sites-embed-border-on sites-embed sites-embed-full-width" style="width: 100%;"><h4 class="sites-embed-title">Успеваемость зарегистрированных студентов</h4><div class="sites-embed-object-title" style="display: none;">Эффективные алгоритмы(студенты).2007</div><div class="sites-embed-content sites-embed-type-spreadsheet"><iframe src="https://docs.google.com/spreadsheet/pub?key=0Ao6tsK_6FZEldFhKM3F6TzlQWmtXY3owalpvT3BRS2c&single=true&gid=11&output=html" id="1695919049" frameborder="0" height="400" width="100%"></iframe></div></div></div>
</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 и подтвердить его. Почту от mail.ru не используйте. Она ужасно проблемная (все нотификации уйдут в спам или отразятся сервисом).
* На своей личной странице, написать хотя бы ФИО и группу.
* На странице [[Blog:Advanced Algorithms]] найти вкладку «следить», и подписаться на этот блог. Но по опыту последних лет, народ разучился пользоватся RSS-подписками… с другой стороны — на ФУПМ МФТИ тотально используется VK — все студенты и администрации в этой сети. Поэтому заведена группа, https://vk.com/discopal, подписывайтесь и туда, туда тоже будут идти обьявления, плюс там же открытые обсуждения и все такое.
-->

== Книга ==
На растерзание отдается <!-- [https://www.dropbox.com/s/co3zye1k98efsfa/book-advanced-algorithms.pdf?dl=0 свежая сборка] --> 
[[:Файл:Book-advanced-algorithms.pdf|свежая сборка]]
— можно искать в ней ошибки (они 100% есть — даже орфографические).

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

=== ? ===
* [[https://www.math.ucdavis.edu/~greg/zoology/diagram.xml zoo]]

==  Темы ==
=== Пройдено ===
* [[Формально об алгоритмах. Вычислительные модели]]
* [[Временная и пространственная сложность алгоритмов]]
* [[Полиномиальные сводимости и NP-полные задачи. Классы NP, coNP, NPC]]
* [[Жадный алгоритм в задачах о покрытии]]
* [[Жадный алгоритм в задаче о рюкзаке]]
* [[Вероятностные вычисления. Классы RP, coRP, ZPP, BPP]]
* [[Динамическое программирование для задачи о рюкзаке]]
* [[Полностью полиномиальная аппроксимационная схема (FPTAS) для задачи о рюкзаке]]

=== Фокус ===
* [[Полиномиальный в среднем алгоритм для задачи о рюкзаке]]
* [[Полиномиальный в среднем алгоритм для SAT]]
* [[Полиномиальный в среднем алгоритм для задачи упаковки]]
* [[Приближенный алгоритм для метрической задачи коммивояжера]]
* [[Вероятностная проверка тождеств]]
* [[MAX-SAT: вероятностное округление]]
* [[MAX-SAT: дерандомизация]]
* [[MAX-CUT: вероятностное округление]]
* [[Вероятностный подсчет числа выполняемых наборов для ДНФ]]

=== Не пройдено ===

=== Не будем === 
* [[Вероятностно проверяемые доказательства. PCP-системы. PCP-теорема]]
* [[PCP и аппроксимируемость]]
* [[Полиномиальная иерархия]]
* [[Схемная сложность]]

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

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

https://cs9.pikabu.ru/post_img/2020/07/10/7/1594377617181633223.webp

----

<!--
* [[Приближенный алгоритм для метрической задачи коммивояжера]]
* [[Вероятностный подсчет числа выполняемых наборов для ДНФ]]
-->

== Тренировка ==

[[Special:MediawikiQuizzer/Algs-3-course-ispras-weekly|Проверь себя]], помнишь ли элементарные понятия и факты из курса.

== Практика ==
{{:Практикуемся В Алгоритмах}}

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

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

== Теоретические упражнения ==
Достаточно 3 задач из двух тем.

{{:Решаем теоретические упражнения}}

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

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

----



<!--
* Дискретный логарифм
** Почему ДЛ обратим в среднем так же плохо, как в худшем.
* Начала криптографии (односторонние функции)
** Протокол диффи-хелмана
-->

== Книга ==
Специальная верстка для чтения с ноутбуков и КПК:
* альбомная ориентация
* крупные беззасечные шрифты

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

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

[[:File:book-advanced-algorithms.pdf]]

Смешное — [https://vk.com/im?sel=1712504&w=wall-54530371_213451%2F1a6855f382934ad3ee реакция «обычных программистов»]

==== Видео ====

;Update: Можно не смотреть, технология многопоточных MKV-перестала работать, будет новое видео, небольшими блоками.
{{/Лекции весеннего семестра 2013}}

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

* Рекомендуем изучить 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://www.wisdom.weizmann.ac.il/%7Eoded/cc.html Introduction to Complexity Theory by Oded Goldreich]
* Более краткий [http://www.cs.technion.ac.il/%7Ecs236313/ курс по классической теории сложности], университет Technion.
* Еще один классический [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 Классические и квантовые вычисления] — замечательная книга. Содержит отличное введение в теорию сложности.
* Лекции [https://www.youtube.com/watch?v=NzeS8XoGCLI&list=PL4_hYwCyhAvbXd4YjOILzI5nPZMIzotMG Сложность вычислений (3 курс, осень 2019) - лектор -- Мусатов Д.В.]

----
{{:Библиотека}}


<!--
== Нужно знать! ==

[[File:Что ждут на курсе по криптографии от вас.jpg|800px|center]]
-->

<references/>