Алгоритмы. Список тем для изучения

Основные темы алгоритмов из настольных книг программиста

задачи по программированию

 

Содержания книг для быстрого ознакомления с курсом алгоритмов и поиска.

Т. Кормен  "Алгоритмы: построение и анализ"
Г. Уоррен "Алгоритмические трюки для программистов"
Р. Седжвик "Алгоритмы на C++. Фундаментальные алгоритмы и структуры данных"
Д. Кнут "Искусство программирования, том 1. Основные алгоритмы"
Д. Кнут "Искусство программирования, том 2. Получисленные алгоритмы"
Д. Кнут "Искусство программирования, том 3. Сортировка и поиск"
Н. Вирт "Алгоритмы и структуры данных"
А. Ахо "Структуры данных и алгоритмы"
Род Стивенс Алгоритмы. Теория и практическое применение
Дж. Клейнберг "Алгоритмы. Разработка и применение"
А. Бхаргава "Грокаем алгоритмы. Иллюстированное пособие для программистов и любопытствующих"

Т. Кормен  "Алгоритмы: построение и анализ"

Часть I. Основы 
Глава 1. Роль алгоритмов в вычислениях
Глава 2. Приступаем к изучению
Глава 3. Рост функций
Глава 4. Рекуррентные соотношения
Глава 5. Вероятностный анализ и рандомизированные алгоритмы

Часть II. Сортировка и порядковая статистика 
Глава 6. Пирамидальная сортировка
Глава 7. Быстрая сортировка
Глава 8. Сортировка за линейное время
Глава 9. Медианы и порядковые статистики

Часть III. Структуры данных 
Глава 10. Элементарные структуры данных
Глава 11. Хеш-таблицы
Глава 12. Бинарные деревья поиска
Глава 13. Красно-черные деревья
Глава 14. Расширение структур данных

Часть IV. Усовершенствованные методы разработки и анализа 
Глава 15. Динамическое программирование
Глава 16. Жадные алгоритмы
Глава 17. Амортизационный анализ

Часть V. Сложные структуры данных 
Глава 18. B-деревья
Глава 19. Биномиальные пирамиды
Глава 20. Фибоначчиевы пирамиды
Глава 21. Структуры данных для непересекающихся множеств

Часть VI. Алгоритмы для работы с графами 
Глава 22. Элементарные алгоритмы для работы с графами
Глава 23. Минимальные остовные деревья
Глава 24. Кратчайшие пути из одной вершины
Глава 25. Кратчайшие пути между всеми парами вершин
Глава 26. Задача о максимальном потоке

Часть VII. Избранные темы 
Глава 27. Сортирующие сети
Глава 28. Работа с матрицами
Глава 29. Линейное программирование
Глава 30. Полиномы и быстрое преобразование фурье
Глава 31. Теоретико-числовые алгоритмы
Глава 32. Поиск подстрок
Глава 33. Вычислительная геометрия
Глава 34. Np-полнота
Глава 35. Приближенные алгоритмы

Часть VIII. Приложения: математические основы 
Приложение А. Ряды
Приложение Б. Множества и прочие художества
Приложение В. Комбинаторика и теория вероятности
Библиография
Предметный указатель

Г. Уоррен "Алгоритмические трюки для программистов"

Глава 1. Введение
Глава 2. Основы
Глава 3. Округление к степени
Глава 4. Арифметические границы
Глава 5. Подсчет битов
Глава 6. Поиск в слове
Глава 7. Перестановка битов и байтов
Глава 8. Умножение
Глава 9. Целочисленное деление
Глава 10. Целое деление на константы
Глава 11. Некоторые элементарные функции
Глава 12. Системы счисления с необычными основаниями
Глава 13. Код грея
Глава 14. Циклический избыточный код
Глава 15. Коды с коррекцией ошибок
Глава 16. Кривая гильберта
Глава 17. Числа с плавающей точкой
Глава 18. Формулы для простых чисел

Р. Седжвик "Алгоритмы на C++. Фундаментальные алгоритмы и структуры данных"

Часть I. Анализ
Глава 1. Введение
Глава 2. Принципы анализа алгоритмов

Часть II. Структуры данных
Глава 3. Элементарные структуры данных
Глава 4. Абстрактные типы данных
Глава 5. Рекурсия и деревья

Часть III. Сортировка
Глава 6. Элементарные методы сортировки
Глава 7. Быстрая сортировка
Глава 8. Слияние и сортировка слиянием
Глава 9. Очереди с приоритетами и пирамидальная сортировка
Глава 10. Поразрядная сортировка
Глава 11. Специальные методы сортировки

Часть IV. Поиск
Глава 12. Таблицы символов и деревья бинарного поиска
Глава 13. Сбалансированные деревья
Глава 14. Хеширование
Глава 15. Поразрядный поиск
Глава 16. Внешний поиск

Часть V. Алгоритмы на графах
Глава 17. Виды графов и их свойства
Глава 18. Поиск на графе
Глава 19. Орграфы и DAG-графы
Глава 20. Минимальные остовные деревья
Глава 21. Кратчайшие пути
Глава 22. Потоки в сетях

Д. Кнут "Искусство программирования, том 1. Основные алгоритмы"

Глава 1. ОСНОВНЫЕ ПОНЯТИЯ
1.1. АЛГОРИТМЫ
1.2. МАТЕМАТИЧЕСКОЕ ВВЕДЕНИЕ
1.2.1. Математическая индукция
1.2.2. Числа, степени и логарифмы
1.2.3. Суммы и произведения
1.2.4. Целочисленные функции и элементарная теория чисел
1.2.5. Перестановки и факториалы
1.2.6. Биномиальные коэффициенты
1.2.7. Гармонические числа
1.2.8. Числа Фибоначчи
1.2.9. Производящие функции
1.2.10.Анализ алгоритма
*1.2.11.Асимптотические представления
*1.2.11.1. Символ O
*1.2.11.2. Формула суммирования Эйлера
*1.2.11.3. Применение асимптотических формул

1.3. MIX
1.3.1. Описание MIX
1.3.2. Язык ассемблера компьютера MIX
1.3.3. Применение к перестановкам

1.4. НЕКОТОРЫЕ ФУНДАМЕНТАЛЬНЫЕ МЕТОДЫ ПРОГРАММИРОВАНИЯ
1.4.1. Подпрограммы
1.4.2. Сопрограммы
1.4.3. Программы-интерпретаторы
1.4.3.1. Имитатор MIX
*1.4.3.2. Программы трассировки
1.4.4. Ввод и вывод
1.4.5. История и библиография

Глава 2. ИНФОРМАЦИОННЫЕ СТРУКТУРЫ
2.1. ВВЕДЕНИЕ
2.2. ЛИНЕЙНЫЕ СПИСКИ
2.2.1. Стеки, очереди и деки
2.2.2. Последовательное распределение
2.2.3. Связанное распределение
2.2.4. Циклические списки
2.2.5. Дважды связанные списки
2.2.6. Массивы и ортогональные списки
2.3. ДЕРЕВЬЯ
2.3.1. Обход бинарных деревьев
2.3.2. Представление деревьев в виде бинарных деревьев
2.3.3. Другие представления деревьев
2.3.4. Основные математические свойства деревьев
2.3.4.1. Свободные деревья
2.3.4.2. Ориентированные деревья
*2.3.4.3. Лемма о бесконечном дереве
*2.3.4.4. Перечисление деревьев
2.3.4.5. Длина пути
*2.3.4.6. История и библиография
2.3.5. Списки и “сборка мусора”
2.4. МНОГОСВЯЗНЫЕ СТРУКТУРЫ
2.5. ДИНАМИЧЕСКОЕ ВЫДЕЛЕНИЕ ПАМЯТИ
2.6. ИСТОРИЯ И БИБЛИОГРАФИЯ

ОТВЕТЫ К УПРАЖНЕНИЯМ
ПРИЛОЖЕНИЕ A. ТАБЛИЦЫ ЗНАЧЕНИЙ НЕКОТОРЫХ КОНСТАНТ
A.1. Основные константы (десятичные)
A.2. Основные константы (восьмеричные)
A.3. Значения гармонических чисел, чисел Бернулли и чисел Фибоначчи
ПРИЛОЖЕНИЕ Б. ОСНОВНЫЕ ОБОЗНАЧЕНИЯ

Д. Кнут "Искусство программирования, том 2. Получисленные алгоритмы"

Глава 3. СЛУЧАЙНЫЕ ЧИСЛА
3.1. ВВЕДЕНИЕ

3.2. ГЕНЕРИРОВАНИЕ РАВНОМЕРНО РАСПРЕДЕЛЕННЫХ СЛУЧАЙНЫХ ЧИСЕЛ
3.2.1. Линейный конгруэнтный метод
3.2.1.1. Выбор модуля
3.2.1.2. Выбор множителя
3.2.1.3. Потенциал
3.2.2. Другие методы

3.3. СТАТИСТИЧЕСКИЕ КРИТЕРИИ
3.3.1. Основные критерии проверки случайных наблюдений
3.3.2. Эмпирические критерии
*3.3.3. Теоретические критерии
3.3.4. Спектральный критерий

3.4. ДРУГИЕ ВИДЫ СЛУЧАЙНЫХ ПОСЛЕДОВАТЕЛЬНОСТЕЙ
3.4.1. Численные распределения
3.4.2. Случайные выборки и перемешивания

*3.5. ЧТО ТАКОЕ СЛУЧАЙНАЯ ПОСЛЕДОВАТЕЛЬНОСТЬ
3.6. ВЫВОДЫ

Глава 4. АРИФМЕТИКА
4.1. ПОЗИЦИОННЫЕ СИСТЕМЫ СЧИСЛЕНИЯ

4.2. АРИФМЕТИКА ЧИСЕЛ С ПЛАВАЮЩЕЙ ТОЧКОЙ
4.2.1. Вычисления с однократной точностью
4.2.2. Точность арифметических операций с плавающей точкой
*4.2.3. Вычисления с удвоенной точностью
4.2.4. Распределение чисел в формате с плавающей точкой

4.3. АРИФМЕТИКА МНОГОКРАТНОЙ ТОЧНОСТИ
4.3.1. Классические алгоритмы
*4.3.2. Модулярная арифметика
*4.3.3. Насколько быстро можно выполнять умножение

4.4. ПРЕОБРАЗОВАНИЕ ИЗ ОДНОЙ СИСТЕМЫ СЧИСЛЕНИЯ В ДРУГУЮ

4.5. АРИФМЕТИКА РАЦИОНАЛЬНЫХ ЧИСЕЛ
4.5.1. Дроби
4.5.2. Наибольший общий делитель
*4.5.3. Анализ алгоритма Евклида
4.5.4. Разложение на простые множители

4.6.     ПОЛИНОМИАЛЬНАЯ АРИФМЕТИКА 469
4.6.1.     Деление полиномов 471
*4.6.2. Разложение полиномов на множители 490
4.6.3.     Вычисление степеней 513
4.6.4.     Вычисление полиномов 538

*4.7. ОПЕРАЦИИ СО СТЕПЕННЫМИ РЯДАМИ 579

ОТВЕТЫ К УПРАЖНЕНИЯМ 593

ПРИЛОЖЕНИЕ А. ТАБЛИЦЫ ЗНАЧЕНИЙ НЕКОТОРЫХ КОНСТАНТ . 791
А.1. Таблица 1. Величины, часто используемые в стандартных подпрограммах и при анализе компьютерных программ (40 десятичных знаков)
А.2. Таблица 2. Величины, часто используемые в стандартных подпрограммах и при анализе компьютерных программ (45 восьмеричных знаков)
А.З. Таблица 3. Значения гармонических чисел, чисел Бернулли и чисел Фибоначчи для малых значений n

ПРИЛОЖЕНИЕ Б. ОСНОВНЫЕ ОБОЗНАЧЕНИЯ 795

Д. Кнут "Искусство программирования, том 3. Сортировка и поиск"

Глава 5. СОРТИРОВКА
5.1. КОМБИНАТОРНЫЕ СВОЙСТВА ПЕРЕСТАНОВОК
5.1.1. Инверсии
5.1.2. Перестановки мультимножества
5.1.3. Серии
5.1.4. Диаграммы и инволюции5.2. ВНУТРЕННЯЯ СОРТИРОВКА
5.2.1. Сортировка путем вставок
5.2.2. Обменная сортировка
5.2.3. Сортировка посредством выбора
5.2.4. Сортировка методом слияния
5.2.5. Сортировка методом распределения5.3. ОПТИМАЛЬНАЯ СОРТИРОВКА
5.3.1. Сортировка с минимальным числом сравнений
5.3.2. Слияние с минимальным числом сравнений
5.3.3. Выбор с минимальным числом сравнений
5.3.4. Сети сортировки5.4. ВНЕШНЯЯ СОРТИРОВКА
5.4.1. Многопутевое слияние и выбор с замещением
5.4.2. Многофазное слияние
5.4.3. Каскадное слияние
5.4.4. Чтение ленты в обратном направлении
5.4.5. Осциллирующая сортировка
5.4.6. Практическая реализация слияния на лентах
5.4.7. Внешняя поразрядная сортировка
5.4.8. Сортировка с двумя лентами
5.4.9. Диски и барабаны5.5. РЕЗЮМЕ. ИСТОРИЯ И БИБЛИОГРАФИЯГлава 6. ПОИСК
6.1. ПОСЛЕДОВАТЕЛЬНЫЙ ПОИСК6.2. ПОИСК ПУТЕМ СРАВНЕНИЯ КЛЮЧЕЙ
6.2.1. Поиск в упорядоченной таблице
6.2.2. Поиск по бинарному дереву
6.2.3. Сбалансированные деревья
6.2.4. Сильноветвящиеся деревья6.3. ЦИФРОВОЙ ПОИСК6.4. ХЕШИРОВАНИЕ6.5. ВЫБОРКА ПО ВТОРИЧНЫМ КЛЮЧАМ

ОТВЕТЫ К УПРАЖНЕНИЯМ
ПРИЛОЖЕНИЕ А. ТАБЛИЦЫ ЗНАЧЕНИЙ НЕКОТОРЫХ КОНСТАНТ
А.1. Основные константы (десятичные)
А.2. Основные константы (восьмеричные)
А.З. Значения гармонических чисел, чисел Бернулли и чисел Фибоначчи
ПРИЛОЖЕНИЕ Б. ОСНОВНЫЕ ОБОЗНАЧЕНИЯ

Н. Вирт "Алгоритмы и структуры данных"

Глава 1. Фундаментальные структуры данных
1.1. Введение
1.2. Понятие типа данных
1.3. Стандартные примитивные типы
1.4. Массивы
1.5. Записи
1.6. Представление массивов, записей и множеств
1.7. Файлы или последовательности
1.8. Поиск
1.9. Поиск образца в тексте (string search)
Упражнения
Литература
Глава 2. Сортировка
2.1. Введение
2.2. Сортировка массивов
2.3. Эффективные методы сортировки
2.4. Сортировка последовательностей
Упражнения
Литература
Глава 3. Рекурсивные алгоритмы
3.1. Введение
3.2. Когда не следует использовать рекурсию
3.3. Два примера рекурсивных программ
3.4. Алгоритмы с возвратом
3.5. Задача о восьми ферзях
3.6. Задача о стабильных браках
3.7. Задача оптимального выбора
Упражнения
Литература
Глава 4. Динамические структуры данных
4.1. Рекурсивные типы данных
4.2. Указатели
4.3. Линейные списки
4.4. Деревья
4.5. Сбалансированные деревья
4.6. Оптимальные деревья поиска
4.7. Б-деревья (B-trees)
4.8. Приоритетные деревья поиска
Упражнения
Литература
Глава 5. Хэширование
5.1. Введение
5.2. Выбор хэш-функции
5.3. Разрешение коллизий
5.4. Анализ хэширования
Упражнения
Литература
Приложение А. Множество символов ASCII
Приложение В. Синтаксис Оберона
Приложение С. Цикл Дейкстры

А. Ахо "Структуры данных и алгоритмы"

Глава 1. Построение и анализ алгоритмов
Глава 2. Основные абстрактные типы данных
Глава 3. Деревья
Глава 4. Основные операторы множеств
Глава 5. Специальные методы представления множеств
Глава 6. Ориентированные графы
Глава 7. Неориентированные графы
Глава 8. Сортировка
Глава 9. Методы анализа алгоритмов
Глава 10. Методы разработки алгоритмов
Глава 11. Структуры данных и алгоритмы для внешней памяти
Глава 12. Управление памятью
Список литературы

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

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

 

Дж. Клейнберг "Алгоритмы. Разработка и применение"

Предисловие 17
Общие сведения 18
Учебные аспекты и дополнения 19
Краткое содержание 20
Как пользоваться книгой 22
Благодарности 24
Глава 1 Введение: некоторые типичные задачи 
1.1 Первая задача: устойчивые паросочетания 27
Задача 27
Проектирование алгоритма 32
Расширения 35
1.2 Пять типичных задач 39
Интервальное планирование 40
Взвешенное интервальное планирование 41
Двудольные паросочетания 41
Независимое множество 43
Задача конкурентного размещения 45
Упражнения с решениями 46
Упражнение с решением 1 46
Упражнение с решением 2 47
Упражнения 50
Примечания и дополнительная литература 55
Глава 2 Основы анализа алгоритмов 
2.1 Вычислительная разрешимость 56
Первые попытки определения эффективности 57
Худшее время выполнения и поиск методом «грубой силы» 58
Полиномиальное время как показатель эффективности 60
2.2 Асимптотический порядок роста 62
O, Ω и Θ 63
Свойства асимптотических скоростей роста 66
Асимптотические границы для некоторых
распространенных функций 67
2.3 Реализация алгоритма устойчивых паросочетаний
со списками и массивами 70
Массивы и списки 71
Реализация алгоритма устойчивых паросочетаний 73
Оглавление 7
2.4 Обзор типичных вариантов времени выполнения 74
Линейное время 75
Время O(n log n) 77
Квадратичное время 78
Кубическое время 79
Время O(nk) 80
За границами полиномиального времени 81
Сублинейное время 82
2.5 Более сложная структура данных: приоритетная очередь 83
Задача 84
Структура данных для реализации приоритетной очереди 85
Реализация операций с кучей 87
Реализация приоритетной очереди на базе кучи 90
Упражнения с решениями 91
Упражнение с решением 1 91
Упражнение с решением 2 92
Упражнения 93
Примечания и дополнительная литература 96
Глава 3 Графы 
3.1 Основные определения и применения 98
3.2 Связность графа и обход графа 103
Поиск в ширину 104
Связная компонента 106
Поиск в глубину 107
Набор всех компонент связности 110
3.3 Реализация перебора графа с использованием очередей и стеков 111
Представление графов 111
Очереди и стеки 113
Реализация поиска в ширину 114
Реализация поиска в глубину 116
Определение всех компонент связности 117
3.4 Проверка двудольности: практическое применение поиска в ширину 118
Задача 118
Проектирование алгоритма 119
Анализ алгоритма 119
3.5 Связность в направленных графах 121
Представление направленных графов 121
Алгоритмы поиска 121
Сильная связность 122
3.6 Направленные ациклические графы и топологическое упорядочение 123
Задача 124
Проектирование и анализ алгоритма 126
Упражнения с решениями 128
Упражнение с решением 1 128
Упражнение с решением 2 129
Упражнения 131
Примечания и дополнительная литература 136

Глава 4 Жадные алгоритмы 
4.1 Интервальное планирование: жадный алгоритм опережает 138
Проектирование жадного алгоритма 138
Анализ алгоритма 141
Расширения 143
Взаимосвязанная задача: планирование всех интервалов 143
4.2 Планирование для минимизации задержки: метод замены 147
Задача 147
Проектирование алгоритма 148
Анализ алгоритма 149
Расширения 152
4.3 Оптимальное кэширование: более сложный пример замены 153
Задача 153
Разработка и анализ алгоритма 154
Расширения: кэширование в реальных рабочих условиях 157
4.4 Кратчайшие пути в графе 158
Задача 158
Разработка алгоритма 159
Анализ алгоритма 160
4.5 Задача нахождения минимального остовного дерева 163
Задача 163
Разработка алгоритма 164
Анализ алгоритмов 165
Реализация алгоритма Прима 170
Расширения 171
4.6 Реализация алгоритма Крускала: структура Union-Find 172
Задача 172
Простая структура данных для структуры Union-Find 173
Усовершенствованная структура данных Union-Find 175
Дальнейшие улучшения 176
Реализация алгоритма Крускала 178
4.7 Кластеризация 179
Задача 179
Разработка алгоритма 180
Анализ алгоритма 181
4.8 Коды Хаффмана и сжатие данных 182
Задача 183
Разработка алгоритма 187
Анализ алгоритма 194
Расширения 196
4.9.* Ориентированные деревья с минимальной стоимостью:
многофазный жадный алгоритм 197
Задача 198
Разработка алгоритма 199
Анализ алгоритма 202
Упражнения с решениями 203
Упражнение с решением 1 203
Упражнение с решением 2 206
Упражнение с решением 3 207
Оглавление 9
Упражнения 209
Примечания и дополнительная литература 224
Глава 5 Разделяй и властвуй
5.1 Первое рекуррентное отношение: алгоритм сортировки слиянием 227
Методы разрешения рекуррентности 228
Раскрутка рекуррентности в алгоритме сортировки слиянием 229
Подстановка решения в рекуррентное отношение сортировки
слиянием 230
Использование частичной подстановки 230
5.2 Другие рекуррентные отношения 231
Случай q > 2 подзадач 232
Случай одной подзадачи 234
Похожее рекуррентное отношение: T(n) ≤ 2T(n/2) + O(n2) 236
5.3 Подсчет инверсий 238
Задача 238
Разработка и анализ алгоритма 239
5.4 Поиск ближайшей пары точек 242
Задача 242
Разработка алгоритма 242
Анализ алгоритма 247
5.5 Целочисленное умножение 248
Задача 248
Разработка алгоритма 248
Анализ алгоритма 250
5.6 Свертки и быстрое преобразование Фурье 250
Задача 250
Разработка и анализа алгоритма 254
Упражнения с решениями 258
Упражнение с решением 1 258
Упражнение с решением 2 260
Упражнения 262
Примечания и дополнительная литература 265
Глава 6 Динамическое программирование 
6.1 Взвешенное интервальное планирование: рекурсивная процедура 267
Разработка рекурсивного алгоритма 267
Мемоизация рекурсии 271
Анализ мемоизированной версии 271
Вычисление решения помимо его значения 272
6.2 Принципы динамического программирования: мемоизация
или итерации с подзадачами 272
Разработка алгоритма 273
Анализ алгоритма 273
Основная схема динамического программирования 274
6.3 Сегментированные наименьшие квадраты: многовариантный выбор 275
Задача 276
Разработка алгоритма 278
Анализ алгоритма 280
6.4 Задача о сумме подмножеств и задача о рюкзаке:
добавление переменной 281
Задача 281
Разработка алгоритма 282
Анализ алгоритма 284
6.5 Вторичная структура РНК: динамическое программирование
по интервалам 286
Задача 287
Разработка и анализ алгоритма 289
6.6 Выравнивание последовательностей 291
Задача 291
Разработка алгоритма 294
Анализ алгоритма 296
6.7 Выравнивание последовательностей в линейном пространстве
по принципу «разделяй и властвуй» 297
Задача 298
Разработка алгоритма 298
Анализ алгоритма 302
6.8 Кратчайшие пути в графе 303
Задача 303
Разработка и анализ алгоритма 305
Расширения: основные усовершенствования алгоритма 308
6.9 Кратчайшие пути и дистанционно-векторные протоколы 311
Недостатки дистанционно-векторного протокола 313
6.10 Отрицательные циклы в графе 315
Задача 315
Разработка и анализ алгоритма 316
Расширения: улучшенные алгоритмы нахождения кратчайшего
пути и отрицательного цикла 317
Упражнения с решениями 320
Упражнение с решением 1 320
Упражнение с решением 2 322
Упражнения 325
Примечания и дополнительная литература 345
Глава 7 Нахождение потока в сети 
7.1 Задача о максимальном потоке и алгоритм Форда–Фалкерсона 348
Разработка алгоритма 351
Анализ алгоритма: завершение и время выполнения 355
7.2 Максимальные потоки и минимальные разрезы 356
Анализ алгоритма: потоки и разрезы 356
Анализ алгоритма: максимальный поток равен
минимальному разрезу 358
Дальнейший анализ: целочисленные потоки 360
7.3 Выбор хороших увеличивающих путей 362
Разработка ускоренного алгоритма потока 362
Анализ алгоритма 364
Расширения: сильные полиномиальные алгоритмы 366
7.4.* Алгоритм проталкивания предпотока 367
Разработка алгоритма 367
Анализ алгоритма 370
Расширения: улучшенная версия алгоритма 374
Реализация алгоритма проталкивания предпотока 375
7.5 Первое применение: задача о двудольном паросочетании 377
Задача 377
Разработка алгоритма 377
Анализ алгоритма 378
Расширения: структура двудольных графов
без идеального паросочетания 380
7.6 Непересекающиеся пути в направленных и ненаправленных графах 383
Задача 383
Разработка алгоритма 383
Анализ алгоритма 384
Расширения: непересекающиеся пути в ненаправленных графах 387
7.7 Расширения задачи о максимальном потоке 388
Задача: циркуляция с потреблением 388
Разработка и анализ алгоритма для циркуляций 390
Задача: циркуляция с потреблением и нижние границы 392
Разработка и анализ алгоритма с нижними границами 392
7.8 Планирование опроса 394
Задача 395
Разработка алгоритма 396
Анализ алгоритма 396
7.9 Планирование авиаперелетов 397
Задача 397
Разработка алгоритма 399
Анализ алгоритма 400
Расширения: моделирование других аспектов задачи 400
7.10 Сегментация изображений 401
Задача 401
Разработка и анализ алгоритма 403
7.11 Выбор проекта 405
Задача 406
Разработка алгоритма 406
Анализ алгоритма 407
7.12 Выбывание в бейсболе 409
Задача 410
Разработка и анализ алгоритма 411
Характеристика выбывания команды 413
7.13.* Добавление стоимостей в задачу паросочетаний 414
Задача 414
Разработка и анализ алгоритма 415
Расширения: экономическая интерпретация цен 419
Упражнения с решениями 420
Упражнение с решением 1 420
Упражнение с решением 2 421
Упражнения 424
Примечания и дополнительная литература 456
Глава 8 NP-полнота и вычислительная неразрешимость 
8.1 Полиномиальное сведение 459
Первое сведение: независимое множество и вершинное покрытие 461
Сведение к более общему случаю: вершинное покрытие
к покрытию множества 463
8.2 Сведение с применением «регуляторов»: задача выполнимости 466
Задачи SAT и 3-SAT 466
Сведение задачи 3-SAT к задаче о независимом множестве 467
Транзитивность сведения 469
8.3 Эффективная сертификация и определение NP 470
Задачи и алгоритмы 470
Эффективная сертификация 471
NP: класс задач 471
8.4 NP-полные задачи 473
Выполнимость булевой схемы: первая NP-полная задача 473
Пример 475
Доказательство NP-полноты других задач 476
Общая стратегия доказательства NP-полноты новых задач 479
8.5 Задачи упорядочения 480
Задача коммивояжера 480
Задача о гамильтоновом цикле 481
Доказательство NP-полноты задачи о гамильтоновом цикле 482
Доказательство NP-полноты задачи коммивояжера 485
Расширения: задача о гамильтоновом пути 486
8.6 Задачи о разбиении 487
Задача о трехмерном сочетании 487
Доказательство NP-полноты трехмерного сочетания 488
8.7 Задача о раскраске графа 492
Задача о раскраске графа 492
Вычислительная сложность задачи о раскраске графа 493
Доказательство NP-полноты задачи о 3-раскраске 494
Заключение: о проверке гипотезы четырех цветов 497
8.8 Численные задачи 497
Задача о суммировании подмножеств 497
Доказательство NP-полноты задачи о суммировании подмножеств 498
Расширения: сложность некоторых задач планирования 500
Внимание: суммирование подмножеств с полиномиально
ограничиваемыми числами 501
8.9 Co-NP и асимметрия NP 502
Хорошая характеризация: класс NPҏco-NP 503
8.10 Частичная классификация сложных задач 504
Задачи упаковки 505
Задачи покрытия 505
Задачи разбиения 505
Задачи упорядочения 506
Численные задачи 506
Задачи соблюдения ограничений 507
Упражнения с решениями 507
Упражнение с решением 1 507
Упражнение с решением 2 509
Упражнения 511
Примечания и дополнительная литература 532
Глава 9 PSPACE: класс задач за пределамиNP 
9.1 PSPACE 534
9.2 Некоторые сложные задачи из PSPACE 536
Задачи построения плана 536
Кванторы 537
Игры 538
9.3 Решение задач с кванторами и игровых задач в полиномиальном
пространстве 539
Разработка алгоритма для QSAT 539
Анализ алгоритма 540
Расширения: алгоритм для задачи конкурентного размещения 540
9.4 Решение задачи построения плана с полиномиальным пространством 541
Задача 541
Разработка алгоритма 543
Анализ алгоритма 545
9.5 Доказательство PSPACE-полноты задач 546
Связь задач с кванторами с игровыми задачами 546
Доказательство PSPACE-полноты задачи конкурентного
размещения 547
Упражнения с решениями 549
Упражнение с решением 1 549
Упражнения 552
Примечания и дополнительная литература 553
Глава 10 Расширение пределов разрешимости 
10.1 Поиск малых вершинных покрытий 556
Задача 557
Разработка алгоритма 557
Анализ алгоритма 559
10.2 Решение NP-сложных задач для деревьев 559
Жадный алгоритм для задачи о независимом множестве
для деревьев 560
Независимое множество с максимальным весом для деревьев 562
10.3 Раскраска множества дуг 564
Задача 564
Разработка алгоритма 567
Анализ алгоритма 572
10.4.* Декомпозиция графа в дерево 573
Определение древовидной ширины 574
Свойства декомпозиции 576
Динамическое программирование и древовидная декомпозиция 580
10.5.* Построение древовидной декомпозиции 584
Задача 585
Разработка и анализ алгоритма 585
Упражнения с решениями 591
Упражнение с решением 1 591
14 Оглавление
Упражнения 594
Примечания и дополнительная литература 598
Глава 11 Аппроксимирующие алгоритмы 
11.1 Жадные алгоритмы и ограничения оптимума:
задача распределения нагрузки 600
Задача 600
Разработка алгоритма 600
Анализ алгоритма 601
Расширения: улучшенный аппроксимирующий алгоритм 604
11.2 Задача о выборе центров 605
Задача 605
Разработка и анализ алгоритма 606
11.3 Покрытие множества: обобщенная жадная эвристика 611
Задача 611
Разработка алгоритма 612
Анализ алгоритма 612
11.4 Метод назначения цены: вершинное покрытие 616
Задача 617
Разработка алгоритма: метод назначения цены 618
Анализ алгоритма 621
11.5 Максимизация методом назначения цены:
задача о непересекающихся путях 622
Задача 622
Разработка и анализ жадного алгоритма 624
Разработка и анализ алгоритма назначения цены 626
11.6 Линейное программирование и округление: применение к задаче
о вершинном покрытии 629
Линейное программирование как обобщенный метод 629
Задача о вершинном покрытии как целочисленная программа 632
Использование линейного программирования для задачи
вершинного покрытия 634
11.7.* Снова о распределении нагрузки: более сложное применение LP 635
Задача 636
Разработка и анализ алгоритма 637
11.8 Аппроксимации с произвольной точностью: задача о рюкзаке 642
Задача 643
Разработка алгоритма 644
Анализ алгоритма 645
Новый алгоритм динамического программирования для задачи
о рюкзаке 646
Упражнения с решениями 648
Упражнение с решением 1 648
Решение 648
Упражнения 649
Примечания и дополнительная литература 657
Глава 12 Локальный поиск
12.1 Задача оптимизации в перспективе 660
Потенциальная энергия 660
Связь с оптимизацией 662
Локальный поиск в задаче о вершинном покрытии 663
12.2 Алгоритм Метрополиса и имитация отжига 665
Алгоритм Метрополиса 665
Имитация отжига 667
12.3 Применение локального поиска в нейронных сетях Хопфилда 669
Задача 669
Разработка алгоритма 670
Анализ алгоритма 671
12.4 Аппроксимация задачи о максимальном разрезе
с применением локального поиска 674
Задача 674
Разработка алгоритма 675
Анализ алгоритма 675
12.5Выбор соседского отношения 677
Алгоритмы локального поиска при разбиении графов 678
12.6.* Классификация на базе локального поиска 679
Задача 680
Разработка алгоритма 681
Анализ алгоритма 686
12.7 Динамика наилучших ответов и равновесия Нэша 688
Задача 688
Динамика наилучших ответов и равновесия Нэша:
определения и примеры 689
Связь с локальным поиском 691
Два основных вопроса 693
Поиск хорошего равновесия Нэша 694
Упражнения с решениями 698
Упражнение с решением 1 698
Упражнения 700
Примечания и дополнительная литература 703
Глава 13 Рандомизированные алгоритмы 
13.1 Первое применение: разрешение конфликтов 705
Задача 706
Разработка рандомизированного алгоритма 706
Анализ алгоритма 706
13.2 Нахождение глобального минимального разреза 711
Задача 711
Разработка алгоритма 712
Анализ алгоритма 713
Дальнейший анализ: количество глобальных
минимальных разрезов 715
13.3 Случайные переменные и ожидания 716
Пример: ожидание первого успеха 717
Линейность ожидания 717
Пример: угадывание карт 718
Пример: сбор купонов 719
Последнее определение: условное ожидание 721
13.4 Рандомизированный аппроксимирующий алгоритм
для задачи MAX 3-SAT 721
Задача 721
Разработка и анализ алгоритма 722
Дальнейший анализ: поиск хорошего присваивания 723
13.5 Рандомизация принципа ««разделяй и властвуй»:
нахождение медианы и быстрая сортировка 725
Задача: нахождение медианы 725
Разработка алгоритма 725
Анализ алгоритма 728
Второй пример: быстрая сортировка 729
13.6 Хеширование: рандомизированная реализация словарей 731
Задача 732
Разработка структуры данных 733
Универсальные классы хеш-функций 735
Анализ структуры данных 737
13.7 Нахождение ближайшей пары точек: рандомизированный метод 738
Задача 739
Разработка алгоритма 740
Описание алгоритма 743
Анализ алгоритма 743
13.8 Рандомизация кэширования 747
Задача 747
Разработка класса алгоритмом маркировки 748
Анализ алгоритмов маркировки 749
Разработка рандомизированного алгоритма маркировки 751
Анализ рандомизированного алгоритма маркировки 752
13.9 Границы Чернова 754
13.10 Распределение нагрузки 756
Задача 756
Анализ случайного распределения заданий 757
13.11 Маршрутизация пакетов 759
Задача 759
Разработка алгоритма 762
Анализ алгоритма 763
13.12 Основные вероятностные определения 765
Конечные вероятностные пространства 765
Условная вероятность и независимость 767
Бесконечные пространства выборки 770
Упражнения с решениями 772
Упражнение с решением 1 772
Упражнение с решением 2 775
Упражнения 778
Примечания и дополнительная литература 789
Эпилог: алгоритмы, которые работают бесконечно 791
Задача 792
Разработка алгоритма 795
Анализ алгоритма 799
Об авторах 800

А. Бхаргава "Грокаем алгоритмы. Иллюстированное пособие для программистов и любопытствующих"

Предисловие 11
Благодарности 12
О книге 14
Структура книги 15
Как работать с этой книгой 16
Для кого предназначена эта книга 16
Условные обозначения и загружаемые материалы 17
Об авторе 17
От издательства 17
Глава 1 Знакомство с алгоритмами 
Введение 18
Что вы узнаете об эффективности алгоритмов 19
Что вы узнаете о решении задач 19
Бинарный поиск 20
Более эффективный поиск 23
Упражнения 27
Время выполнения 28
«O-большое» 29
Время выполнения алгоритмов растет с разной скоростью 29
Наглядное представление «O-большое» 32
«O-большое» определяет время выполнения в худшем случае 34
Типичные примеры «O-большого» 35
Упражнения 36
Задача о коммивояжере 37
Шпаргалка 39
Глава 2 Сортировка выбором 
Как работает память 41
Массивы и связанные списки 43
Связанные списки 45
Массивы 46
Терминология 47
Упражнения 48
Вставка в середину списка 49
Удаление 50
Упражнения 51
Сортировка выбором 53
Пример кода 57
Шпаргалка 58
Глава 3 Рекурсия 
Рекурсия 60
Базовый случай и рекурсивный случай 63
Стек 65
Стек вызовов 66
Упражнения 68
Стек вызовов с рекурсией 69
Упражнения 73
Шпаргалка 74
Глава 4 Быстрая сортировка 
«Разделяй и властвуй» 76
Упражнения 85
Быстрая сортировка 85
Снова об «O-большом» 92
Сортировка слиянием и быстрая сортировка 93
Средний и худший случай 95
Упражнения 99
Шпаргалка 99
Оглавление  7
Глава 5 Хеш-таблицы 
Хеш-функции 103
Упражнения 107
Примеры использования 107
Использование хеш-таблиц для поиска 108
Исключение дубликатов 110
Использование хеш-таблицы как кэша 112
Шпаргалка 116
Коллизии 116
Быстродействие 119
Коэффициент заполнения 122
Хорошая хеш-функция 124
Упражнения 125
Шпаргалка 126
Глава 6 Поиск в ширину 
Знакомство с графами 128
Что такое граф? 131
Поиск в ширину 132
Поиск кратчайшего пути 135
Очереди 136
Упражнения 137
Реализация графа 138
Реализация алгоритма 141
Время выполнения 146
Упражнения 147
Шпаргалка 150
Глава 7 Алгоритм Дейкстры 
Работа с алгоритмом Дейкстры 152
Терминология 157
История одного обмена 160
Ребра с отрицательным весом 167
Реализация 170
Упражнения 181
Шпаргалка 181
Глава 8 Жадные алгоритмы 
Задача составления расписания 183
Задача о рюкзаке 185
Упражнения 187
Задача о покрытии множества 187
Приближенные алгоритмы 189
Упражнения 196
NP-полные задачи 196
Задача о коммивояжере — шаг за шагом 197
Как определить, что задача является NP-полной? 202
Упражнения 205
Шпаргалка 205
Глава 9 Динамическое программирование 
Задача о рюкзаке 206
Простое решение 207
Динамическое программирование 208
Задача о рюкзаке: вопросы 217
Что произойдет при добавлении элемента? 217
Упражнения 220
Что произойдет при изменении порядка строк? 220
Можно ли заполнять таблицу по столбцам, а не по строкам? 221
Что произойдет при добавлении меньшего элемента? 221
Можно ли взять часть предмета? 221
Оптимизация туристического маршрута 223
Взаимозависимые элементы 224
Может ли оказаться, что решение требует более двух «подрюкзаков»? 225
Возможно ли, что при лучшем решении в рюкзаке остается пустое место? 226
Упражнения 226
Самая длинная общая подстрока 226
Построение таблицы 228
Заполнение таблицы 229
Решение 230
Самая длинная общая подпоследовательность 232
Самая длинная общая подпоследовательность — решение 233
Упражнения 235
Шпаргалка 235
Глава 10 Алгоритм k ближайших соседей 
Апельсины и грейпфруты 236
Построение рекомендательной системы 239
Извлечение признаков 240
Упражнения 245
Регрессия 245
Выбор признаков 248
Упражнения 249
Знакомство с машинным обучением 249
OCR 250
Построение спам-фильтра 251
Прогнозы на биржевых торгах 252
Шпаргалка 252
Глава 11 Что дальше? 
Деревья 254
Инвертированные индексы 258
Преобразование Фурье 259
Параллельные алгоритмы 260
MapReduce 261
Для чего нужны распределенные алгоритмы? 261
Функция map 261
Функция reduce 262
Фильтры Блума и HyperLogLog 263
Фильтры Блума 265
HyperLogLog 265
Алгоритмы SHA 266
Сравнение файлов 267
Проверка паролей 268
Локально-чувствительное хеширование 269
Обмен ключами Диффи—Хеллмана 270
Линейное программирование 272
Эпилог 273
Ответы к упражнениям 274

 

Один комментарий к “Алгоритмы. Список тем для изучения

  1. Существует ли обзорное описание всего этого необъятного материала? Что бы получить общее представление о всем, этом многообразии. Что для чего и почему?

Комментарии закрыты