Просмотр исходного текста страницы Курс по книге «Эффективные алгоритмы и сложность вычислений»

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

<!-- * [[Special:MediawikiQuizzer/GRE-CS-v01|Еженедельная проверка — сегодня экспериментальная]] -->
* [[Special:MediawikiQuizzer/Algs-3-course-ispras-weekly|Cозвонный тест]]

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

* [https://логос.испран.рф/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-20250206
ALTERNATIVE
OPEN_RESULTS
OPEN_VOTERS
AUTHORIZED
ALLOW_REVOTE
END_POLL 2025-05-15
Записываемся на курс «Сложность алгоритмов-2025»?
Да
Нет
</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 пишите], будем договариваться.
-->

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

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

== Книга ==
На растерзание отдается <!-- [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-CUT: вероятностное округление]]
* [[MAX-SAT: дерандомизация]]
* [[Вероятностный подсчет числа выполняемых наборов для ДНФ]]

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

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

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


----

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

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

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

<!--

=== Визуализация алгоритмов ===
{{:Визуализация алгоритмов}}
-->


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

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

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

== Теоретические упражнения ==
<!-- 
Достаточно 3 задач из двух тем.
* Дает от 2-4 баллов.
* Минимум 2, каждая бонусная задача дает отдельно 1 балл.
-->

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

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

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

----

== Бонусные квесты ==
=== Простые ===
==== «Ката» на Python ====
{{:Ката_на_Питоне}}

<!--
=== Среднесложно ===
==== Изучение тестов по Computer Science ====
{{:Изучение тестов по Computer Science}}
-->

=== Исследовательские ===
==== Разбор статей ====
{{:Разбор статей}}


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

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

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

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

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

[[: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 интерактивный учебник].

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

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


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

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

<references/>