Учебное пособие по алгоритмам в информатике.
Перевод: Кириленко Вадим (главы 1-12), Волошко Роман Владимирович (главы13-19)
Москва : Издательство «Э», 2016. - 544 с. - (Мировой компьютерный бестселлер).
ISBN 978-5-699-81729-0
Тираж 2000 экз. Алгоритмы — это рецепты, которые делают возможным эффективное программирование. Их изучение позволяет усвоить общие подходы к решению задач и накапливать полезные методики для их решения. В этой книге представлено множество классических алгоритмов; вы узнаете, где они применяются и как их анализировать, чтобы понять их поведение.
Эта книга может быть полезной не только в вашей текущей профессиональной деятельности, но и может помочь вам получить новую работу. Оглавление: Об авторе
Благодарности Введение
Выбор алгоритма
Для кого предназначена книга
Как извлечь наибольшую пользу из книги
Сайты с материалами книги
Структура книги
Что нужно для работы с книгой
Условные обозначения
Обратная связь Основы алгоритмизации
Метод
Алгоритм и структура данных
Псевдокод Свойства алгоритма
Асимптотическая сложность алгоритма
Обычные функции рабочего цикла
Визуализация функций
Практические рекомендации
Резюме
Упражнения Численные алгоритмы
Рандомизация данных
Генерирование случайных величин
Рандомизация массивов
Генерирование неравномерных распределений
Нахождение наибольшего общего делителя
Возведение в степень
Работа с простыми числами
Нахождение простых множителей 56
Нахождение простых элементов
Проверка на простоту
Численное интегрирование
Формула прямоугольников
Формула трапеций
Адаптивная квадратура
Интеграция Монте-Карло
Нахождение нулей
Резюме
Упражнения Связные списки
Основные положения
Однонаправленные связные списки
Передвижение по спискам
Нахождение ячеек
Использование ограничителей
Добавление ячеек в начало списка
Добавление ячеек в конец списка
Вставка ячеек
Удаление ячеек
Двунаправленные связные списки
Сортированные списки
Алгоритмы для работы со связными списками
Копирование
Сортировка вставкой
Сортировка методом выбора
Многопотоковые связные списки
Связные списки с циклами
Маркировка ячеек
Использование хеш-таблиц
Повторная трассировка списка
Реверсирование списка
Черепаха и кролик
Циклы в двунаправленных связных списках
Резюме
Упражнения Массивы
Основные положения
Одномерные массивы
Нахождение элементов
Нахождение минимальной, максимальной и средней величин
Вставка элементов
Удаление элементов
Ненулевые нижние пределы
Двумерные массивы
Массивы высокой размерности
Треугольные массивы
Массивы с разрывом
Нахождение строки и столбца
Получение значения
Установка значения
Удаление значения
Матрицы
Резюме
Упражнения Стеки и очереди
Стеки
Стеки связных списков
Стеки массивов
Двойные стеки
Алгоритмы с использованием стеков
Очереди
Очереди связных списков
Очереди массивов
Специализированные очереди
Резюме
Упражнения Сортировка
Алгоритмы O(N2)
Сортировка вставкой в массивах
Сортировка выбором в массивах
Пузырьковая сортировка
Алгоритмы O(N×logN)
Пирамидальная сортировка
Быстрая сортировка
Сортировка слиянием
Алгоритмы быстрее O(N×logN)
Сортировка подсчетом
Блочная сортировка
Резюме
Упражнения Поиск
Линейный поиск
Бинарный поиск
Интерполяционный поиск
Резюме
Упражнения Хеш-таблицы
Основы хеш-таблиц
Прямое связывание
Открытая адресация
Удаление элементов
Линейное пробирование
Квадратичное пробирование
Псевдослучайное пробирование
Двойное хеширование
Упорядоченное хеширование
Резюме
Упражнения Рекурсия
Базовые алгоритмы
Факториал
Числа Фибоначчи
Ханойская башня
Графические алгоритмы
Кривые Коха
Кривая Гильберта
Кривая Серпинского
Салфетки
Алгоритмы с возвратом
Задача о восьми ферзях
Ход коня
Сочетания и размещения
Сочетания с циклами
Сочетания с повторениями
Сочетания без повторений
Размещения с повторениями
Размещения без повторений
Удаление рекурсии
Удаление хвостовой рекурсии
Хранение промежуточных значений
Удаление общей рекурсии
Резюме
Упражнения Деревья
Терминология
Свойства бинарного дерева
Представление деревьев
Общие правила построения деревьев
Построение завершенных деревьев
Обход дерева
Обход в прямом порядке
Симметричный обход
Обход в обратном порядке
Обход в ширину
Время выполнения обхода
Упорядоченные деревья
Добавление вершин
Поиск вершин
Удаление вершин
Связные деревья
Построение связных деревьев
Использование связных деревьев
Специализированные алгоритмы
Игра «Животные»
Расчет математических выражений
Деревья квадрантов
Префиксные деревья
Резюме
Упражнения Сбалансированные деревья
АВЛ-деревья
Добавление значений
Удаление значений
2-3-деревья
Добавление значений
Удаление значений
B-деревья
Добавление значений
Удаление значений
Разновидности сбалансированных деревьев
Иерархически организованные B-деревья
B+-деревья
Резюме
Упражнения Деревья принятия решений
Поиск по деревьям игры
Минимакс
Начальные ходы и реакции
Эвристика дерева игры
Поиск по деревьям принятия решений
Задачи оптимизации
Метод полного перебора
Метод ветвей и границ
Эвристика дерева принятия решений
Другие задачи дерева принятия решений
Резюме
Упражнения Основные сетевые алгоритмы
Терминология
Разные представления сети
Обход сети
Обход в глубину
Обход в ширину
Проверка связности
Остовные деревья
Минимальные остовные деревья
Поиск путей
Поиск произвольного пути
Поиск кратчайшего пути с помощью установки меток
Поиск кратчайшего пути с помощью коррекции меток
Поиск кратчайшего пути между всеми парами вершин
Резюме
Упражнения Дополнительные сетевые алгоритмы
Топологическая сортировка
Поиск циклов
Раскрашивание карты
Закрашивание двумя цветами
Закрашивание тремя цветами
Закрашивание четырьмя цветами
Закрашивание пятью цветами
Другие алгоритмы закрашивания карт
Максимальный поток
Распределение рабочих мест
Минимальный разрез в потоке
Резюме
Упражнения Строковые алгоритмы
Парные скобки
Вычисление арифметических выражений
Синтаксические деревья
Сопоставление с шаблоном
Детерминированные конечные автоматы
Построение ДКА для регулярных выражений
Недетерминированные конечные автоматы
Поиск строк
Вычисление редакционного расстояния
Резюме
Упражнения Криптография
Терминология
Перестановочные шифры
Перестановка строк/столбцов
Перестановка столбцов
Маршрутные шифры
Шифры подстановки
Шифр Цезаря
Шифр Виженера
Простая подстановка
Схема одноразовых блокнотов
Блочные шифры
Подстановочно-перестановочные сети
Шифр Фейстеля
Шифрование с открытым ключом и RSA
Функция Эйлера
Обратные величины
Пример использования RSA
Практические соображения
Другие области применения криптографии
Резюме
Упражнения Теория вычислительной сложности
Обозначения
Классы сложности
Сведение
3SAT
Паросочетание в двудольном графе
NP-сложность
Задачи обнаружения, сообщения и оптимизации
Обнаружение ≤p Сообщение
Обнаружение ≤p Оптимизация
Сообщение ≤p Обнаружение
Оптимизация ≤p Сообщение
NP-полные задачи
Резюме
Упражнения Распределенные алгоритмы
Виды параллелизма
Систолические массивы
Распределенные вычисления
Многопроцессорные вычисления
Состояние гонки
Взаимная блокировка
Квантовые вычисления
Распределенные алгоритмы
Отладка распределенных алгоритмов
Чрезвычайно параллельные алгоритмы
Сортировка слиянием
Задача обедающих философов
Задача двух генералов
Задача византийских генералов
Согласование
Выбор лидера
Снимок
Синхронизация часов
Резюме
Упражнения Головоломки, встречающиеся на собеседованиях
Как задавать вопросы с подвохом
Как отвечать на вопросы с подвохом
Резюме
Упражнения Приложение А. Собрание алгоритмических понятий
Приложение Б. Решения к упражнениям Глоссарий
Алфавитный указатель
Перевод: Кириленко Вадим (главы 1-12), Волошко Роман Владимирович (главы13-19)
Москва : Издательство «Э», 2016. - 544 с. - (Мировой компьютерный бестселлер).
ISBN 978-5-699-81729-0
Тираж 2000 экз. Алгоритмы — это рецепты, которые делают возможным эффективное программирование. Их изучение позволяет усвоить общие подходы к решению задач и накапливать полезные методики для их решения. В этой книге представлено множество классических алгоритмов; вы узнаете, где они применяются и как их анализировать, чтобы понять их поведение.
Эта книга может быть полезной не только в вашей текущей профессиональной деятельности, но и может помочь вам получить новую работу. Оглавление: Об авторе
Благодарности Введение
Выбор алгоритма
Для кого предназначена книга
Как извлечь наибольшую пользу из книги
Сайты с материалами книги
Структура книги
Что нужно для работы с книгой
Условные обозначения
Обратная связь Основы алгоритмизации
Метод
Алгоритм и структура данных
Псевдокод Свойства алгоритма
Асимптотическая сложность алгоритма
Обычные функции рабочего цикла
Визуализация функций
Практические рекомендации
Резюме
Упражнения Численные алгоритмы
Рандомизация данных
Генерирование случайных величин
Рандомизация массивов
Генерирование неравномерных распределений
Нахождение наибольшего общего делителя
Возведение в степень
Работа с простыми числами
Нахождение простых множителей 56
Нахождение простых элементов
Проверка на простоту
Численное интегрирование
Формула прямоугольников
Формула трапеций
Адаптивная квадратура
Интеграция Монте-Карло
Нахождение нулей
Резюме
Упражнения Связные списки
Основные положения
Однонаправленные связные списки
Передвижение по спискам
Нахождение ячеек
Использование ограничителей
Добавление ячеек в начало списка
Добавление ячеек в конец списка
Вставка ячеек
Удаление ячеек
Двунаправленные связные списки
Сортированные списки
Алгоритмы для работы со связными списками
Копирование
Сортировка вставкой
Сортировка методом выбора
Многопотоковые связные списки
Связные списки с циклами
Маркировка ячеек
Использование хеш-таблиц
Повторная трассировка списка
Реверсирование списка
Черепаха и кролик
Циклы в двунаправленных связных списках
Резюме
Упражнения Массивы
Основные положения
Одномерные массивы
Нахождение элементов
Нахождение минимальной, максимальной и средней величин
Вставка элементов
Удаление элементов
Ненулевые нижние пределы
Двумерные массивы
Массивы высокой размерности
Треугольные массивы
Массивы с разрывом
Нахождение строки и столбца
Получение значения
Установка значения
Удаление значения
Матрицы
Резюме
Упражнения Стеки и очереди
Стеки
Стеки связных списков
Стеки массивов
Двойные стеки
Алгоритмы с использованием стеков
Очереди
Очереди связных списков
Очереди массивов
Специализированные очереди
Резюме
Упражнения Сортировка
Алгоритмы O(N2)
Сортировка вставкой в массивах
Сортировка выбором в массивах
Пузырьковая сортировка
Алгоритмы O(N×logN)
Пирамидальная сортировка
Быстрая сортировка
Сортировка слиянием
Алгоритмы быстрее O(N×logN)
Сортировка подсчетом
Блочная сортировка
Резюме
Упражнения Поиск
Линейный поиск
Бинарный поиск
Интерполяционный поиск
Резюме
Упражнения Хеш-таблицы
Основы хеш-таблиц
Прямое связывание
Открытая адресация
Удаление элементов
Линейное пробирование
Квадратичное пробирование
Псевдослучайное пробирование
Двойное хеширование
Упорядоченное хеширование
Резюме
Упражнения Рекурсия
Базовые алгоритмы
Факториал
Числа Фибоначчи
Ханойская башня
Графические алгоритмы
Кривые Коха
Кривая Гильберта
Кривая Серпинского
Салфетки
Алгоритмы с возвратом
Задача о восьми ферзях
Ход коня
Сочетания и размещения
Сочетания с циклами
Сочетания с повторениями
Сочетания без повторений
Размещения с повторениями
Размещения без повторений
Удаление рекурсии
Удаление хвостовой рекурсии
Хранение промежуточных значений
Удаление общей рекурсии
Резюме
Упражнения Деревья
Терминология
Свойства бинарного дерева
Представление деревьев
Общие правила построения деревьев
Построение завершенных деревьев
Обход дерева
Обход в прямом порядке
Симметричный обход
Обход в обратном порядке
Обход в ширину
Время выполнения обхода
Упорядоченные деревья
Добавление вершин
Поиск вершин
Удаление вершин
Связные деревья
Построение связных деревьев
Использование связных деревьев
Специализированные алгоритмы
Игра «Животные»
Расчет математических выражений
Деревья квадрантов
Префиксные деревья
Резюме
Упражнения Сбалансированные деревья
АВЛ-деревья
Добавление значений
Удаление значений
2-3-деревья
Добавление значений
Удаление значений
B-деревья
Добавление значений
Удаление значений
Разновидности сбалансированных деревьев
Иерархически организованные B-деревья
B+-деревья
Резюме
Упражнения Деревья принятия решений
Поиск по деревьям игры
Минимакс
Начальные ходы и реакции
Эвристика дерева игры
Поиск по деревьям принятия решений
Задачи оптимизации
Метод полного перебора
Метод ветвей и границ
Эвристика дерева принятия решений
Другие задачи дерева принятия решений
Резюме
Упражнения Основные сетевые алгоритмы
Терминология
Разные представления сети
Обход сети
Обход в глубину
Обход в ширину
Проверка связности
Остовные деревья
Минимальные остовные деревья
Поиск путей
Поиск произвольного пути
Поиск кратчайшего пути с помощью установки меток
Поиск кратчайшего пути с помощью коррекции меток
Поиск кратчайшего пути между всеми парами вершин
Резюме
Упражнения Дополнительные сетевые алгоритмы
Топологическая сортировка
Поиск циклов
Раскрашивание карты
Закрашивание двумя цветами
Закрашивание тремя цветами
Закрашивание четырьмя цветами
Закрашивание пятью цветами
Другие алгоритмы закрашивания карт
Максимальный поток
Распределение рабочих мест
Минимальный разрез в потоке
Резюме
Упражнения Строковые алгоритмы
Парные скобки
Вычисление арифметических выражений
Синтаксические деревья
Сопоставление с шаблоном
Детерминированные конечные автоматы
Построение ДКА для регулярных выражений
Недетерминированные конечные автоматы
Поиск строк
Вычисление редакционного расстояния
Резюме
Упражнения Криптография
Терминология
Перестановочные шифры
Перестановка строк/столбцов
Перестановка столбцов
Маршрутные шифры
Шифры подстановки
Шифр Цезаря
Шифр Виженера
Простая подстановка
Схема одноразовых блокнотов
Блочные шифры
Подстановочно-перестановочные сети
Шифр Фейстеля
Шифрование с открытым ключом и RSA
Функция Эйлера
Обратные величины
Пример использования RSA
Практические соображения
Другие области применения криптографии
Резюме
Упражнения Теория вычислительной сложности
Обозначения
Классы сложности
Сведение
3SAT
Паросочетание в двудольном графе
NP-сложность
Задачи обнаружения, сообщения и оптимизации
Обнаружение ≤p Сообщение
Обнаружение ≤p Оптимизация
Сообщение ≤p Обнаружение
Оптимизация ≤p Сообщение
NP-полные задачи
Резюме
Упражнения Распределенные алгоритмы
Виды параллелизма
Систолические массивы
Распределенные вычисления
Многопроцессорные вычисления
Состояние гонки
Взаимная блокировка
Квантовые вычисления
Распределенные алгоритмы
Отладка распределенных алгоритмов
Чрезвычайно параллельные алгоритмы
Сортировка слиянием
Задача обедающих философов
Задача двух генералов
Задача византийских генералов
Согласование
Выбор лидера
Снимок
Синхронизация часов
Резюме
Упражнения Головоломки, встречающиеся на собеседованиях
Как задавать вопросы с подвохом
Как отвечать на вопросы с подвохом
Резюме
Упражнения Приложение А. Собрание алгоритмических понятий
Приложение Б. Решения к упражнениям Глоссарий
Алфавитный указатель