Книга «Эффективные алгоритмы и сложность вычислений».

ISBN 5-7417-0198-1, M:МФТИ, 2007 (издательство МФТИ).

В электронном виде доступна в формате PDF: «Эффективные алгоритмы и сложность вычислений».

В целом, при чтении на ноутбуке в портретном режиме («View/Rotate View + Fullscreen»), это никак не хуже бумажной версии, плюс удобство поиска, гиперссылок, цветные иллюстрации.

Мы рекомендуем читать PDF с использованием бесплатного PDF-броузера PDF-XCHANGE, который позволяет оставлять пометки и комментарии (Под Linux можно использовать pdfedit).

То есть вы можете читать, параллельно записывать свои комментарии (желательно конструктивные), после чего прислать их редактору. Конечно, можно оставлять комментарии и любым другим софтом (Acrobat и т.п.) или вовсе присылать их в любой доступной форме (текстовым списком). Но все же комментарии в PDF-файле - наиболее целостный и удобный способ.

Можно помечать ошибки, опечатки, неудачные стилистические обороты и просто непонятности — мы обязательно рассмотрим каждое замечание.

Если вы — наш студент, то эта деятельность будет обязательно учтена при выставлении оценки. В любом случае, мы будем очень благодарны за сотрудничество.

Содержание (приблизительное)

Предисловие

Введение

Глава 1. Алгоритмы и их сложность

1.1. Примеры задач и алгоритмов

1.1.1. Теоретико-числовые задачи: «НОД», «факториал», «возведение в степень»,

«дискретный логарифм»

1.1.2. Задачи на графах: «Коммивояжер»,«Кратчайшие пути»,«Остовные деревья»

1.1.3. Приближенные алгоритмы: «Составление расписаний»

1.1.4. «Сортировка слиянием»

1.1.5. «Быстрая сортировка»

1.2. Формально об алгоритмах. Несложно о сложности

1.2.1. «RAM»: машины с произвольным доступом 49

1.2.2. Сложность в худшем случае

1.2.3. Полиномиальные алгоритмы

1.2.4. Полиномиальность и эффективность

Глава 2. Аппроксимация с гарантированной точностью

2.1. Алгоритмы с оценками точности

2.1.1. Жадные алгоритмы для «Покрытия множеств»

2.1.2. Приближенные алгоритмы для «Вершинного покрытия»

2.1.3. Жадный алгоритм для «Рюкзака»

2.1.4. Алгоритм Кристофидеса

2.2. Аппроксимация с заданной точностью

2.2.1. «Рюкзак»: динамическое программирование

2.2.2. Полностью полиномиальная приближенная схема для «Рюкзака»

Глава 3. Вероятностный анализ алгоритмов

3.1. Сложность и полиномиальность в среднем

3.2. Задача упаковки

3.3. Выполнимость КНФ

3.4. Точность алгоритма для почти всех входов

3.5. «Рюкзак»: полиномиальность в среднем

Глава 4. Вероятностные алгоритмы и их анализ

4.1. Вероятностная проверка тождеств

4.2. Вероятностные методы в перечислительных задачах

4.3. Вероятностные методы в параллельных вычислениях

4.3.1. Максимальное по включению независимое множество в графе

4.3.2. Протокол византийского соглашения

4.4. Вероятностное округление

4.4.1. Вероятностное округление для задачи «MAX-SAT»

4.4.2. Максимальный разрез в графе

Глава 5. Методы дерандомизации

5.1. Метод условных вероятностей

5.2. Метод малых вероятностных пространств

Глава 6. Основы теории сложности вычислений

6.1. Сложность вычислений

6.1.1. Машины Тьюринга и вычислимость

6.1.2. Классы DT IME, DSPACE

6.1.3. Полиномиальные сводимости и NP-полнота

6.1.4. Сводимость по Куку

6.1.5. Недетерминированные алгоритмы

6.1.6. Сводимость по Карпу

6.2. Вероятностные вычисления

6.2.1. Классы RP/coRP. «Односторонние ошибки»

6.2.2. Класс BPP. «Двусторонние ошибки»

6.2.3. Класс PP

6.2.4. Класс ZPP. «Алгоритмы без ошибок»

6.2.5. Вероятностно проверяемые доказательства

6.2.6. PCP и неаппроксимируемость

6.2.7. Класс APX. Сводимости, сохраняющие аппроксимации

6.3. Схемы и схемная сложность

6.4. Коммуникационная сложность

6.5. Диаграмма классов сложности

Глава 7. Приложения

7.1. Введение в Python

7.2. Глоссарий

Список литературы

Списки иллюстраций

Список алгоритмов