Род Стивенс - Алгоритмы. Теория и практическое применение (2016)

1.Об авторе
2.Благодарности
3.Введение
1.Выбор алгоритма
2.Для кого предназначена книга
3.Как извлечь наибольшую пользу из книги
4.Сайты с материалами книги
5.Структура книги
6.Что нужно для работы с книгой
7.Условные обозначения
8.Обратная связь
4.Глава 1. Основы алгоритмизации
1.Метод
2.Алгоритм и структура данных
3.Псевдокод
4.Свойства алгоритма
1.Асимптотическая сложность алгоритма
2.Обычные функции рабочего цикла
3.Визуализация функций
5.Практические рекомендации
6.Резюме
7.Упражнения
5.Глава 2. Численные алгоритмы
1.Рандомизация данных
1.Генерирование случайных величин
2.Рандомизация массивов
3.Генерирование неравномерных распределений
2.Нахождение наибольшего общего делителя
3.Возведение в степень
4.Работа с простыми числами
1.Нахождение простых множителей
2.Нахождение простых элементов
3.Проверка на простоту
5.Численное интегрирование
1.Формула прямоугольников
2.Формула трапеций
3.Адаптивная квадратура
4.Интеграция Монте-Карло
6.Нахождение нулей
7.Резюме
8.Упражнения
6.Глава 3. Связные списки
1.Основные положения
2.Однонаправленные связные списки
1.Передвижение по спискам
2.Нахождение ячеек
3.Использование ограничителей
4.Добавление ячеек в начало списка
5.Добавление ячеек в конец списка
6.Вставка ячеек
7.Удаление ячеек
3.Двунаправленные связные списки
4.Сортированные списки
5.Алгоритмы для работы со связными списками
1.Копирование
2.Сортировка вставкой
3.Сортировка методом выбора
6.Многопотоковые связные списки
7.Связные списки с циклами
1.Маркировка ячеек
2.Использование хеш-таблиц
3.Повторная трассировка списка
4.Реверсирование списка
5.Черепаха и кролик
6.Циклы в двунаправленных связных списках
8.Резюме
9.Упражнения
7.Глава 4. Массивы
1.Основные положения
2.Одномерные массивы
1.Нахождение элементов
2.Нахождение минимальной, максимальной и средней величин
3.Вставка элементов
4.Удаление элементов
3.Ненулевые нижние пределы
1.Двумерные массивы
2.Массивы высокой размерности
4.Треугольные массивы
5.Массивы с разрывом
1.Нахождение строки и столбца
2.Получение значения
3.Установка значения
4.Удаление значения
6.Матрицы
7.Резюме
8.Упражнения
8.Глава 5. Стеки и очереди
1.Стеки
1.Стеки связных списков
2.Стеки массивов
3.Двойные стеки
4.Алгоритмы с использованием стеков
2.Очереди
1.Очереди связных списков
2.Очереди массивов
3.Специализированные очереди
3.Резюме
4.Упражнения
9.Глава 6. Сортировка
1.Алгоритмы O(N^2)
1.Сортировка вставкой в массивах
2.Сортировка выбором в массивах
3.Пузырьковая сортировка
2.Алгоритмы O(N x log N)
1.Пирамидальная сортировка
2.Быстрая сортировка
3.Сортировка слиянием
3.Алгоритмы быстрее O(N x log N)
1.Сортировка подсчетом
2.Блочная сортировка
4.Резюме
5.Упражнения
10.Глава 7. Поиск
1.Линейный поиск
2.Бинарный поиск
3.Интерполяционный поиск
4.Резюме
5.Упражнения
11.Глава 8. Хеш-таблицы
1.Основы хеш-таблиц
2.Прямое связывание
3.Открытая адресация
1.Удаление элементов
2.Линейное пробирование
3.Квадратичное пробирование
4.Псевдослучайное пробирование
5.Двойное хеширование
6.Упорядоченное хеширование
4.Резюме
5.Упражнения
12.Глава 9. Рекурсия
1.Базовые алгоритмы
1.Факториал
2.Числа Фибоначчи
3.Ханойская башня
2.Графические алгоритмы
1.Кривые Коха
2.Кривая Гильберта
3.Кривая Серпинского
4.Салфетки
3.Алгоритмы с возвратом
1.Задача о восьми ферзях
2.Ход коня
3.Сочетания и размещения
4.Сочетания с циклами
5.Сочетания с повторениями
6.Сочетания без повторений
7.Размещения с повторениями
8.Размещения без повторений
4.Удаление рекурсии
1.Удаление хвостовой рекурсии
2.Хранение промежуточных значений
3.Удаление общей рекурсии
5.Резюме
6.Упражнения
13.Глава 10. Деревья
1.Терминология
2.Свойства бинарного дерева
3.Представление деревьев
1.Общие правила построения деревьев
2.Построение завершенных деревьев
4.Обход дерева
1.Обход в прямом порядке
2.Симметричный обход
3.Обход в обратном порядке
4.Обход в ширину
5.Время выполнения обхода
5.Упорядоченные деревья
1.Добавление вершин
2.Поиск вершин
3.Удаление вершин
6.Связные деревья
1.Построение связных деревьев
2.Использование связных деревьев
7.Специализированные алгоритмы
1.Игра "Животные"
2.Расчет математических выражений
3.Деревья квадрантов
4.Префиксные деревья
8.Резюме
9.Упражнения
14.Глава 11. Сбалансированные деревья
1.АВЛ-деревья
1.Добавление значений
2.Удаление значений
2.2-3-деревья
1.Добавление значений
2.Удаление значений
3.B-деревья
1.Добавление значений
2.Удаление значений
4.Разновидности сбалансированных деревьев
1.Иерархически организованные B-деревья
2.B+-деревья
5.Резюме
6.Упражнения
15.Глава 12. Деревья принятия решений
1.Поиск по деревьям игры
1.Минимакс
2.Начальные ходы и реакции
3.Эвристика дерева игры
2.Поиск по деревьям принятия решений
1.Задачи оптимизации
2.Метод полного перебора
3.Метод ветвей и границ
4.Эвристика дерева принятия решений
5.Другие задачи дерева принятия решений
3.Резюме
4.Упражнения
16.Глава 13. Основные сетевые алгоритмы
1.Терминология
2.Разные представления сети
3.Обход сети
1.Обход в глубину
2.Обход в ширину
3.Проверка связности
4.Остовные деревья
5.Минимальные остовные деревья
4.Поиск путей
1.Поиск произвольного пути
2.Поиск кратчайшего пути с помощью установки меток
3.Поиск кратчайшего пути с помощью коррекции меток
4.Поиск кратчайшего пути между всеми парами вершин
5.Резюме
6.Упражнения
17.Глава 14. Дополнительные сетевые алгоритмы
1.Топологическая сортировка
2.Поиск циклов
3.Раскрашивание карты
1.Закрашивание двумя цветами
2.Закрашивание тремя цветами
3.Закрашивание четырьмя цветами
4.Закрашивание пятью цветами
5.Другие алгоритмы закрашивания карт
4.Максимальный поток
1.Распределение рабочих мест
2.Минимальный разрез в потоке
5.Резюме
6.Упражнения
18.Глава 15. Строковые алгоритмы
1.Парные скобки
1.Вычисление арифметических выражений
2.Синтаксические деревья
2.Сопоставление с шаблоном
1.Детерминированные конечные автоматы
2.Построение ДКА для регулярных выражений
3.Недетерминированные конечные автоматы
3.Поиск строк
4.Вычисление редакционного расстояния
5.Резюме
6.Упражнения
19.Глава 16. Криптография
1.Терминология
2.Перестановочные шифры
1.Перестановка строк/столбцов
2.Перестановка столбцов
3.Маршрутные шифры
3.Шифры подстановки
1.Шифр Цезаря
2.Шифр Виженера
3.Простая подстановка
4.Схема одноразовых блокнотов
4.Блочные шифры
1.Подстановочно-перестановочные сети
2.Шифр Фейстеля
5.Шифрование с открытым ключом и RSA
1.Функция Эйлера
2.Обратные величины
3.Пример использования RSA
4.Практические соображения
6.Другие области применения криптографии
7.Резюме
8.Упражнения
20.Глава 17. Теория вычислительной сложности
1.Обозначения
2.Классы сложности
3.Сведение
1.3SAT
2.Паросочетание в двудольном графе
4.NP-сложность
5.Задачи обнаружения, сообщения и оптимизации
1.Обнаружение <=p Сообщение
2.Обнаружение <=p Оптимизация
3.Сообщение <=p Обнаружение
4.Оптимизация <=p Сообщение
6.NP-полные задачи
7.Резюме
8.Упражнения
21.Глава 18. Распределенные алгоритмы
1.Виды параллелизма
1.Систолические массивы
2.Распределенные вычисления
3.Многопроцессорные вычисления
4.Состояние гонки
5.Взаимная блокировка
6.Квантовые вычисления
2.Распределенные алгоритмы
1.Отладка распределенных алгоритмов
2.Чрезвычайно параллельные алгоритмы
3.Сортировка слиянием
4.Задача обедающих философов
5.Задача двух генералов
6.Задача византийских генералов
7.Согласование
8.Выбор лидера
9.Снимок
10.Синхронизация часов
3.Резюме
4.Упражнения
22.Глава 19. Головоломки, встречающиеся на собеседованиях
1.Как задавать вопросы с подвохом
2.Как отвечать на вопросы с подвохом
3.Резюме
4.Упражнения
23.Приложение А. Собрание алгоритмических понятий
24.Приложение Б. Решения к упражнениям
25.Глоссарий
Алфавитный указатель