Сложность комбинаторных алгоритмов, Курс лекций, Кузюрин Н.Н., Фомин С.А., 2007

Сложность комбинаторных алгоритмов, Курс лекций, Кузюрин Н.Н., Фомин С.А., 2007.
 
Фрагмент из книги.
Понятие алгоритма в математике используется давно, но различные его формализации были предложены только в середине 30-х годов прошлого столетия, когда и стала складываться теория алгоритмов.
Классическая теория алгоритмов вообще не интересуется сложностными аспектами (временем решения задач на реальных вычислителях). В рамках классической теории алгоритмов, ставятся и решаются задачи о разрешимости различных задач, однако вычислительная сложность полученных решений принципиально не исследуется.




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

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

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

ОГЛАВЛЕНИЕ.
1. Элементы теории сложности.
1.1. Несложно о сложности. Примеры алгоритмов.
1.1.1 Примеры задач на натуральных числах.
1.1.2. Приближенные алгоритмы. Многопроцессорные расписания.
1.1.3. Примеры задач на графах. Кратчайшие пути и задача коммивояжера.
1.1.4. Сортировка слиянием.
1.1.5. Быстрая сортировка. Анализ в среднем и вероятностная версия.
1.2. Формально об алгоритмах .
1.2.1. Машины с произвольным доступом (RAM).
1.2.2. Машины Тьюринга и вычислимость.
1.3. Сложность алгоритмов.
1.3.1. Сложность в худшем случае (Worst Case Complexity).
1.3.2. Полиномиальные алгоритмы.
1.3.3. Полиномиальность и эффективность.
1.3.4. Эффективность и классы DTIME, DSPACE.
1.3.5. Полиномиальные сводимости и NP-полнота.
1.3.6. Сводимость по Куку.
1.3.7. Недетерминированные алгоритмы.
1.3.8. Сводимость по Карпу.
1.4. Вероятностные вычисления.
1.4.1. Классы RP и coRP. Распознавание с односторонней ошибкой.
1.4.2. Класс ВРР. Эффективное распознавание с двухсторонней ошибкой.
1.4.3. Класс РР..
1.4.4. Класс ZPP. Вероятностное распознавание без ошибок.
1.5. Вероятностно проверяемые доказательства.
1.5.1. РСР и неаппроксимируемость.
1.6. Схемы и схемная сложность.
1.7. Коммуникационная сложность.
1.8. Диаграмма классов сложности.
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.1.1. Задача упаковки. Анализ сложности в среднем.
3.1.2. Точность жадного алгоритма для почти всех исходных данных.
3.1.3. Полиномиальный в среднем алгоритм для задачи о рюкзаке .
3.2. Вероятностные алгоритмы.
3.2.1. Алгоритм Фрейвалда.
3.2.2. Вероятностные методы в перечислительных алгоритмах. Подсчет числа выполняющих наборов для ДНФ.
3.2.3. Вероятностный алгоритм Луби нахождения максимального по включению независимого множества в графе.
3.3. Вероятностные методы в распределенных вычислениях.
3.3.1. Протокол византийского соглашения.
3.4. Вероятностное округление и дерандомизация.
3.4.1. Вероятностное округление.
3.4.2. Приближенный алгоритм для задачи о максимальном сечении.
3.4.3. Дерандомизация и метод условных вероятностей.
3.4.4. Дерандомизация вероятностного алгоритма Луби нахождения максимального по включению независимого множества в графе.
4. Криптография.
4.1. Генераторы.
4.1.1. Псевдослучайные генераторы. Генератор Нисана-Вигдерсона.
4.1.2. Полиномиальный алгоритм распознавания простоты числа.
4.2. Элементы криптографии с открытым ключом.
4.2.1. Односторонние функции.
4.2.2. Дискретный логарифм. Обмен ключами.
4.2.3. Система RSA и ее анализ.
5. Приложения.
5.1. Глоссарий.
5.2. Введение в Python.



Бесплатно скачать электронную книгу в удобном формате, смотреть и читать:
Скачать книгу Сложность комбинаторных алгоритмов, Курс лекций, Кузюрин Н.Н., Фомин С.А., 2007 - fileskachat.com, быстрое и бесплатное скачивание.

Скачать pdf
Ниже можно купить эту книгу, если она есть в продаже, и похожие книги по лучшей цене со скидкой с доставкой по всей России.Купить книги


Скачать - pdf - Яндекс.Диск.




Теги: учебник по программированию :: программирование :: Кузюрин :: Фомин :: алгоритм