Название: Алгоритмы
Автор: Дасгупта Санджой, Пападимитриу Х., Вазирани У.
Издательство: М.: МЦНМО
Год: 2014
Формат: pdf
Страниц: 320
Размер: 27 mb
Язык: русский
В этой книге, предназначенной для студентов математических и программистских специальностей (начиная с младших курсов), подробно разбираются основные методы построения и анализа эффективных алгоритмов. Она основана на лекциях авторов в университетах Сан-Диего и Беркли. Выбор материала не вполне стандартный (скажем, о сортировке и структурах данных, связанных с хранением упорядоченных множеств в сбалансированных деревьях, не говорится, зато обсуждаются линейное программирование и даже квантовые вычисления). Авторы старались выделить основные идеи и излагать доказательства наглядно, не злоупотребляя формализмом, но и не жертвуя математической строгостью; оригинальный подход авторов делает книгу интересной не только студентам, но и опытным преподавателям. Каждый раздел снабжён упражнениями.
Содержание:
Предисловие.
Пролог.
Книги и алгоритмы.
Вычисление чисел Фибоначчи.
O-символика.
Упражнения.
Числовые алгоритмы.
Элементарная арифметика.
Арифметика сравнений.
Проверка чисел на простоту.
Криптография.
Универсальное хеширование.
Упражнения.
Метод «разделяй и властвуй».
Умножение чисел.
Рекуррентные соотношения.
Сортировка слиянием.
Медианы.
Умножение матриц.
Быстрое преобразование Фурье.
Упражнения.
Декомпозиция графов.
Откуда берутся графы.
Поиск в глубину в неориентированных графах.
Поиск в глубину в ориентированных графах.
Компоненты сильной связности.
Упражнения.
Пути в графах.
Расстояния в графе.
Поиск в ширину.
Длины рёбер.
Алгоритм Дейкстры.
Реализации очередей с приоритетами.
Кратчайшие пути и отрицательные веса.
Кратчайшие пути в ациклических графах.
Упражнения.
Жадные алгоритмы.
Покрывающие деревья.
Кодирование Хаффмана.
Формулы Хорна.
Покрытие множествами.
Упражнения.
Динамическое программирование.
Ещё раз о кратчайших путях в ориентированных ациклических графах.
Наибольшая возрастающая подпоследовательность.
Расстояние редактирования.
Задача о рюкзаке.
Произведение матриц.
Кратчайшие пути.
Независимые множества в деревьях.
Упражнения.
Линейное программирование и сводящиеся к нему задачи.
Введение в линейное программирование.
Потоки в сетях.
Паросочетания в двудольных графах.
Принцип двойственности.
Игры с нулевой суммой.
Симплекс-метод.
Эпилог: вычисление значения схемы.
Упражнения.
NP-полные задачи.
Задачи поиска.
NP-полные задачи: определения и примеры.
Сведения.
Упражнения.
Решение NP-полных задач.
Оптимизация перебора.
Приближённые алгоритмы.
Эвристики локального поиска.
Упражнения.
Квантовые алгоритмы.
Кубиты, суперпозиция, измерения.
План действий.
Квантовое преобразование Фурье.
Периодичность.
Квантовые схемы.
Периодичность и разложение на множители.
Квантовый алгоритм разложения на множители.
Упражнения.
Нашел ошибку? Есть жалоба? Жми!
Пожаловаться администрации