Просмотр исходного текста страницы Курс «Эффективные алгоритмы для труднорешаемых задач»

{{SideBar|
{{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/GRE-CS-v01|Еженедельная проверка — сегодня экспериментальная]]

<!--
* [[Special:MediawikiQuizzer/Algs-3-course-ispras-weekly|Cозвонный тест]]
* [[Special:MediawikiQuizzer/Python|Приветственная созвонная проверка]]
-->

* [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-20240901
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__

<!-- Если кто-то еще хочет в этом семестре сдавать — [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]]

==  Темы ==
[[Файл:Усвоим весь объем — вовсе нет.png|360px|right]]
* [[Формально об алгоритмах. Вычислительные модели]]
* [[Временная и пространственная сложность алгоритмов]]
* [[Полиномиальные сводимости и NP-полные задачи. Классы NP, coNP, NPC]]
* [[Вероятностные вычисления. Классы RP, coRP, ZPP, BPP]]
* [[Жадный алгоритм в задачах о покрытии]]
* [[Жадный алгоритм в задаче о рюкзаке]]
* [[Динамическое программирование для задачи о рюкзаке]]
* [[Полностью полиномиальная аппроксимационная схема (FPTAS) для задачи о рюкзаке]]
* [[Полиномиальный в среднем алгоритм для задачи о рюкзаке]]
* [[Полиномиальный в среднем алгоритм для SAT]]
* [[Полиномиальный в среднем алгоритм для задачи упаковки]]
* [[Приближенный алгоритм для метрической задачи коммивояжера]]
* [[Вероятностная проверка тождеств]]
* [[MAX-SAT: вероятностное округление]]
* [[MAX-SAT: дерандомизация]]
* [[MAX-CUT: вероятностное округление]]
* [[Вероятностный подсчет числа выполняемых наборов для ДНФ]]
* [[Вероятностно проверяемые доказательства. PCP-системы. PCP-теорема]]
* [[PCP и аппроксимируемость]]
* [[Полиномиальная иерархия]]
* [[Схемная сложность]]

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

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

----

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

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

[[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 реакция «обычных программистов»]

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

* Рекомендуем изучить 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 интерактивный учебник].

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

{{:Дополнительные_материалы_по_сложности_вычислений}} 
{{:Дополнительные материалы по приближенным алгоритмам}} 
----
{{:Библиотека}}


<references/>