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

== Книга ==
На растерзание отдается <!-- [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|Проверь себя]], помнишь ли элементарные понятия и факты из курса.

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

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

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

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

----


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

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

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

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

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

<!--
==== Видео ====

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

-->

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

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


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

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

<references/>