Эффективные алгоритмы и сложность вычислений, Кузюрин Н.Н., Фомин С.А., 2009

Эффективные алгоритмы и сложность вычислений, Кузюрин Н.Н., Фомин С.А., 2009.

   Эта книга написана но материалам двух спецкурсов, читавшихся авторами в течение нескольких лет для студентов 4-го и 6-го курсов Московского физико-технического института. Она знакомит читателей как с классическими результатами в разработке эффективных алгоритмов для решения вычислительно трудных задач, полученными еще в 1960-1970-х годах, так и с новыми результатами, полученными в последние годы. Именно в рассмотрении современных подходов к решению вычислительно трудных задач и заключается основное отличие данного пособия от традиционных книг по разработке и анализу эффективных алгоритмов.
Для студентов факультетов управления и прикладной математики, нанотехнологий и информатики, инноваций и высоких технологий Московского физико-технического института. Рекомендуется также студентам и аспирантам других ВУЗов, изучающих информатику, теорию алгоритмов и сложность вычислений.




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

Во-первых, при несущественных модификациях вычислительной модели сложность обычно изменяется не более чем на некоторую (как правило, довольно небольшую) мультипликативную константу. Например, если мы разрешим в машинах со случайным доступом оператор цикла for, то ввиду наличия моделирования (см. рис. 1.8) сложность от этого может уменьшиться не более чем в два раза. Следовательно, если мы игнорируем мультипликативные константы, можем свободно использовать в машинах со случайным доступом for-do-endfor циклы и другие алголоподобные конструкции, не оговаривая всякий раз это специально.

ОГЛАВЛЕНИЕ.
Предисловие.
Введение.
Глава 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.2.3. Сложность в среднем.
1.2.4. Полиномиальные алгоритмы.
1.2.5. Полиномиальность и эффективность.
Глава 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. Вероятностное округление для задачи «МАХ-БАТ».
4.4.2. Максимальный разрез в графе.
Глава 5. Методы дерандомизации.
5.1. Метод условных вероятностей.
5.2. Метод малых вероятностных пространств.
Глава 6. Основы теории сложности вычислений.
6.1. Сложность вычислений.
6.1.1. Машины Тьюринга и вычислимость.
6.1.2. Классы DTIME, DSPACE.
6.2. Полиномиальные сводимости и NР-полнота.
6.2.1. Сводимость по Куку.
6.2.2. Недетерминированные алгоритмы.
6.2.3. Сводимость по Карпу.
6.3. Вероятностные вычисления.
6.3.1. Классы RP/coRP. «Односторонние ошибки».
6.3.2. Класс BPP. «Двусторонние ошибки».
6.3.3. Класс PP.
6.3.4. Класс ZPP. «Алгоритмы без ошибок».
6.3.5. Вероятностно проверяемые доказательства.
6.3.6. VCV и неаппроксимируемость.
6.3.7. Класс APX. Сводимости, сохраняющие аппроксимации.
6.4. Схемы и схемная сложность.
6.5. Коммуникационная сложность.
6.6. Диаграмма классов сложности.
Глава 7. Приложения.
7.1. Введение в Python.
7.2. Глоссарий.
Глава 8. Сборник упражнений (ИСПРАН-2008-весна).
Список литературы.
Списки иллюстраций.
Список алгоритмов.



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

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


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




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