Просмотр исходного текста страницы Курс «Эффективные алгоритмы» для МФТИ

__FORCETOC__
* [[Special:MediawikiQuizzer/GRE-CS-v01|Созвонный тест]]
<!--
* [[Special:MediawikiQuizzer/Python|Приветственная созвонная проверка]]
-->
{{SideBar|
{{Special:Wikilog/Blog:Advanced Algorithms/Template:BlogInformerLine/12/sort=wlp_talk_updated}}
|style=max-width:35%
}}
<!--
* [https://логос.испран.рф/mipt-course-03/hard-problems.svg Частичный обзор курса]
* [https://логос.испран.рф/mipt-course-06/course-algorigthms-balls.drawio.svg  Баллы и путь прохождения]
-->
----
* [[Blog:Advanced_Algorithms/2024-09-08_Презентация_курса_«на_осень_2024»]]
----

<!--
* [[Special:MediawikiQuizzer/Эффективные алгоритмы-Экзамен|Тест для экзамена]]
* [[Special:MediawikiQuizzer/Algs-6-course-ispras-weekly|Созвонный тест по теортемам]]
-->

Курс лекций «Эффективные алгоритмы» для 6 курса МФТИ.

----
<!-- {{:Blog:Advanced Algorithms/2021-09-03 Анонс «Эффективных алгоритмов-2021»}} -->
----

<!--
В целом голосование за время созвона прошло, результаты на странице [[Голосование за выбор времени созвона]],
но если сильно изменится ситуация — заходите и переголосуйте там.
-->

<!--
Семестровый курс по выбору<ref>К экзамену допускаются только студенты, зарегистрировавшиеся до 10 октября [mailto:stas-fomin@yandex.ru email].</ref>
для студентов 6-го курса ФУПМ МФТИ.
-->

;Преподаватель: [mailto:stas-fomin@yandex.ru С.А. Фомин]

<!-- Запись на курс 2021 года завершена, всем спасибо, исключений нет. -->

Для ФУПМов 6 курса, желающих записаться на курс по выбору «Эффективные алгоритмы», нужно:
{{:Как зарегистрироваться на курс}}

<!--
+ 
Зарегистрируйтесь на «лабе»
* [[Lab17]]
-->


<poll>
UNSAFE_ID=aa-20240901
ALTERNATIVE
OPEN_RESULTS
OPEN_VOTERS
AUTHORIZED
ALLOW_REVOTE
END_POLL 2024-11-27
Записываемся на курс «Advanced Algorithms-2024»?
Да
Нет
</poll>
* Первое установочное занятие будет 6 сентября, в 18-30 в 907 КПМ
<!--  Установочный созвон будет наверно 9 сентября, раньше обычно бессмысленно. -->

<!--
Прием экзамена, вторник, 2016-12-27, 11:30, [http://www.ispras.ru ИСПРАН], 301 аудитория. 
<poll>
UNSAFE_ID=2016-12-23-exam
ALTERNATIVE
OPEN_RESULTS
OPEN_VOTERS
AUTHORIZED
ALLOW_REVOTE
END_POLL 2016-12-23
Будете на экзамене 2016-12-23, 10:45?
Да
Нет
</poll>
* Если не набереться четырех студентов — возможно этот прием будет отменен.
Процесс сдачи будет включать:
* Фильтрацию входящих тестами (если совсем не готов —  не тратим время друг друга).
* Вопросы по теме («почему так»), или те самые задачи, которые вы решали.


Время последующих сдач пока не известно. 
-->

<!--
Вводное занятие проведено — всем изучать материалы на
[[Курс лекций «Эффективные алгоритмы»]] — книгу, видео и все-такое. 
Готовим темы из раздела [[#Фокус]]

{{!|Встречаемся в 903 КПМ, 4 октября, 18:30}}
-->

Формат flipped classroom — т.е. по существующим материалам не будем повторять лекции, встречаться будем только для семинаров, и активной работы (решение задач, разбор сложных моментов, что-нибудь интересное придумаю) по заранее изученным материалам. 

<!-- Возможно, если будут новые темы, будут удаленные лекции (которых попробуем и также записать и зафиксировать). -->


Вопросы пишите на [mailto:stas-fomin@yandex.ru почту], или задавайте в [{{active-telegram-group-link}} группе].

<!--
{{!|Важное:}} Деканат внезапно захотел список студентов <s>прямо сейчас</s> уже вчера. Так что просьба, определится быстрее и записаться как указано выше на курс ASAP.
-->

----

* Проблемы → [mailto:stas-fomin@yandex.ru Стасу Фомину]

<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_6FZElcGVLNjEtY3lfOHhkdkRQWTI1aUktUUE&single=true&gid=9&output=html" id="1695919049" frameborder="0" height="500" width="100%"></iframe></div></div>
</div>
</center></html>

В списке вы можете видеть разные цифры, отражающие вашу активность по темам курса.
В конце — некоторые суммарные метрики, рассчитанные по волшебным формулам.

Если вы в зеленой группе — вы кандидат на «отлично автоматом».

<!--
«Отличники-автоматом» будут выбраны с помощью жадного алгоритма, и вероятностого округления, с использованием настоящих случайных чисел с http://random.org
-->


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

== Блок 2 — «Бизнес-моделирование» ==
Моделирование труднорешаемых задач и решение из промышленными солверами.
{{:Моделирование бизнес-задач}}

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

== Блок 4 — Теоретический ==
Необязательно (если вы набрали нужные баллы другими блоками), но может быть полезно, у кого аллергия к коду, Pyomo, а хочется что-то читать и решать, как в старые добрые времена. 
Тут буду упражнения, и простые темы, по которым будут тесты.


== Бонусные квесты ==
=== Визуализация алгоритмов ===
{{:Визуализация алгоритмов}}

=== Изучение тестов по Computer Science ===
{{:Изучение тестов по Computer Science}}

=== ТеорУпражнения ===
Осенью 2024 достаточно 4 задач из двух тем.
{{:Решаем теоретические упражнения}}

=== Разбор статей ===
{{:Разбор статей}}


=== Для избранных ===
* Обычно согласовывается с посещающими студентами, выбор некой темы, связанной и с алгоритмами, сложностью и областью научно-практических интересов студента.



<!--
== Блок 3 ==

Выберем несколько тем и теоретических задач.

Те, кто по результатам предущих блоков вышел на  «хор», смогут улучшить оценку (но не затягивайте, держите в курсе, если это делаете).
----
{{:НаучныйПоиск}}
-->

<!--
== Блок 1 ==
{{vimeoembed|324745701|800|450}}

Простые классические алгоритмы. Динамическое программирование. 
Навыки мемоизации, работы с структурами данных.


=== Теория ===
* [[Несложно о сложности. Примеры алгоритмов]]
* [[Жадный алгоритм в задачах о покрытии]]
* [[Жадный алгоритм покрытия для почти всех исходных данных]]
* [[Жадный алгоритм в задаче о рюкзаке]]
* [[Динамическое программирование для задачи о рюкзаке]]
* [[Полностью полиномиальная аппроксимационная схема (FPTAS) для задачи о рюкзаке]]
* [[Вероятностная проверка тождеств]]

* [[Полиномиальный в среднем алгоритм для задачи упаковки]]
* [[Полиномиальный в среднем алгоритм для задачи о рюкзаке]]
* [[Полиномиальный в среднем алгоритм для SAT]]

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

* [[MAX-SAT: дерандомизация]]
* [[Приближенный алгоритм для метрической задачи коммивояжера]]
-->

<!--
<!--
== Блок 2 ==
;Квест «4 задачи»: До 3 декабря 
* [[Blog:Advanced_Algorithms/2021-10-15_Practical_Block]]
* Прохождение квеста гарантирует «уд»
* Непрохождение → «неуд»

;Квест «2 задачи из Spojcoding/Codechefing»
* До 15 декабря.
* Прохождение квеста гарантирует «хор» (7)
* Повторим условия:
** Не Leetcoding
** Только Python
** Да, должна проходить TL

;Квест «4 задачи из Spojcoding/Codechefing»
* До 15 декабря.
* Прохождение квеста гарантирует «отл» (8)
* Повторим условия:
** Не Leetcoding
** Только Python
** Да, должна проходить TL
-->


<!--
== Блок 3 ==
Выберем несколько тем и теоретических задач.

Те, кто по результатам предущих блоков вышел на  «хор» до 12 декабря, смогут улучшить оценку
* [[Blog:Advanced_Algorithms/2021-11-15_Research_Block]]
-->

=== ТеорТемы ===
Тут отобраны только детские темы про алгоритмы, никакой сложности, будем проверять, то что вы их читали тестами на созвонах — и так, можно будет набрать «переключающий балл» (отберем персентилями по сумме всех результатов). Плюс можно еще балл за задачи, ну или как-то вместе может они наберут балл, или как-то учтется в 10-бальной оценке.

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

* [[Несложно о сложности. Примеры алгоритмов]]

* [[Жадный алгоритм в задачах о покрытии]]
* [[Жадный алгоритм покрытия для почти всех исходных данных]]
* [[Жадный алгоритм в задаче о рюкзаке]]

* [[Динамическое программирование для задачи о рюкзаке]]
* [[Полностью полиномиальная аппроксимационная схема (FPTAS) для задачи о рюкзаке]]

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

* [[Формально об алгоритмах. Вычислительные модели]]
* [[Временная и пространственная сложность алгоритмов]]
* [[Полиномиальные сводимости и NP-полные задачи. Классы NP, coNP, NPC]]

<!--
=== Не будет на курсе в этом году === 

* [[Вероятностно проверяемые доказательства. PCP-системы. PCP-теорема]] 
* [[Вероятностные вычисления. Классы RP, coRP, ZPP, BPP]]
* [[PCP и аппроксимируемость]]
* [[Параллельный алгоритм Люби для максимального по включению независимого множества]]
-->

<!--
= Тренировка =
[[Special:MediawikiQuizzer/Эффективные алгоритмы|Проверь себя]], помнишь ли элементарные понятия и факты из курса.
Тест будет на экзамене, чтобы отсеять совсем невменяемых.

== Задачи ==
* [[LeetCoding]]
-->
<!--
Все статьи в этой категории — задачи, которые можно пытаться решать.
* [[:Category:Нерешенные задачи]].  Осталось  {{!|{{PAGESINCATEGORY: Нерешенные задачи}}}} нерешенных задач.

Решать надо создавая для решения ''подстраницу'' личной страницы, и ссылаясь в решении на задачу.
;Пример: Задача [[Вероятностная_проверка_тождеств/Задачи/determinant]] → Решение [[Участник:StasFomin/Задача determinant]].
Cтатьи-решения задач помечать вставляя строку
 
<pre><nowiki>[[Category:На проверку]]</nowiki></pre>
и подписываться на изменения («watch this page»).


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

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

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

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

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

Все статьи в этой категории — задачи, которые можно пытаться решать.
* [[:Category:Нерешенные задачи]].
Любая активность, даже попытки решения  — хорошо.
После того, как задача решена, она перейдет в архив:
* [[:Category:Решенные задачи]] — кстати, полезно смотреть чужие решения.

Cтатьи-решения задач помечать вставляя строку
 
<pre><nowiki>[[Category:На проверку]]</nowiki></pre>
и подписываться на изменения («watch this page»).

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

= Материалы =
Наверно не пригодятся для курса 2022 года.

<!--
== Видеолекции ==
* [[/Лекции осеннего семестра 2011]]
** [http://narod.ru/disk/63720373001.d936acd53e1a20473d5073cbd232bc49/discopal.torrent.html торрент] с прошлогодними видео.
* [[/Лекции осеннего семестра 2012]]
* [[Курс_лекций_«Сложность_алгоритмов»_(ИСПРАН,_3_курс_МФТИ)/Лекции_весеннего_семестра_2013]]
-->
== Книга ==

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

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

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

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

[[File:book-advanced-algorithms.pdf|512px]]

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


== Примечания и ссылки ==
* Рекомендуется прочитать хотя бы [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 первые лекции] по введению в Python и научные вычисления.

==  Полезная сопутствующая литература по курсу.  ==
 
* Очень хорошие лекции по классической теории сложности, написанные одним из корифеев оной: [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 Классические и квантовые вычисления] — замечательная книга. Содержит отличное введение в теорию сложности.
* ''С. Дасгупта, Х. Пападимитриу, У. Вазирани'', Алгоритмы [http://www.math.nsc.ru/LBRT/k5/OR-MMF/dasgupta_2014.pdf]


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