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