Алгоритмы, Эриксон Д., 2023

Алгоритмы, Эриксон Д., 2023.

   В этом руководстве содержатся основные сведения об алгоритмах: анализируются различные типы алгоритмов, рассматриваются методы их построения (рекурсия, динамическое программирование и др.), приводятся практические примеры. В конце каждой главы приводятся упражнения, направленные на закрепление пройденного.
Для изучения материала требуется знание основ дискретной математики и методов доказательств, а также представление об основных вычислительных задачах и алгоритмах. Желателен практический опыт работы с языком программирования, поддерживающим косвенную адресацию и рекурсию.
Издание адресовано студентам и преподавателям технических вузов, а также тем, кто хочет изучить основы алгоритмизации.




Определение конкретной задачи.
Прежде чем начать разработку нового алгоритма, необходимо установить, для решения какой задачи предназначается этот алгоритм. Точно так же, прежде чем мы сможем приступить к описанию алгоритма, потребуется описание задачи, для решения которой предназначается этот алгоритм.

Алгоритмические задачи часто формулируются с использованием обычного английского (русского или любого другого) языка с употреблением слов, обозначающих объекты реального мира. Но мы, как проектировщики алгоритмов, обязаны переформулировать эти задачи в терминах формальных, абстрактных, математических объектов, т. е. в форме чисел, массивов, списков, графов, деревьев и т. п., - таким образом, мы можем мыслить формально. Кроме того, мы обязательно должны определить, содержит ли формулировка задачи какие-либо скрытые неявные предположения (допущения), и зафиксировать эти предположения в явной форме. (Например, в песне «п бутылок пива на стене» подразумевается, что n всегда является неотрицательным целым числом.)

ОГЛАВЛЕНИЕ.
Предисловие от издательства.
Предисловие.
Об этой книге.
Обязательный минимум.
Дополнительные ссылки.
Упражнения в этой книге.
Стащите эту книгу.
Благодарности.
Предостережение для преподавателя.
Глава 0. Введение.
0.1. Что такое алгоритм.
0.2.Умножение.
Умножение методом решетки.
Удваивание и усреднение.
Циркуль и линейка.
0.3. Распределение мест в Конгрессе США.
0.4. Отрицательный пример.
0.5. Описание алгоритмов.
Определение конкретной задачи.
Описание алгоритма.
0.6. Анализ алгоритмов.
Корректность.
Время выполнения.
Упражнения.
Глава 1. Рекурсия.
1.1. Сведение.
1.2. Упрощение и делегирование.
1.3. Ханойские башни.
1.4. Сортировка слиянием.
Корректность.
Анализ.
1.5. Быстрая сортировка.
Корректность.
Анализ.
1.6. Шаблон.
1.7. Рекурсивные деревья.
Исключение нижних и верхних границ - это правильный подход, даю честное слово.
1.8. Линейный алгоритм выбора.
Алгоритм быстрого выбора.
Правильные опорные элементы.
Анализ.
Проверка достоверности.
1.9. Быстрое умножение.
1.10. Возведение в степень.
Упражнения.
Ханойские башни.
Рекурсивные деревья.
Сортировка.
Выбор.
Арифметика.
Массивы.
Деревья.
Глава 2. Поиск с возвратом.
2.1. Задача об n ферзях.
2.2. Деревья игры.
2.3. Задача о сумме подмножеств.
Корректность.
Анализ.
Варианты.
2.4. Общий шаблон.
2.5. Сегментация текста (Interpunctio Verborum).
2.6. Максимальная возрастающая подпоследовательность.
2.7. Максимальная возрастающая подпоследовательность, дубль 2.
2.8. Оптимальные двоичные деревья поиска.
Упражнения.
Глава 3. Динамическое программирование.
3.1. Matravrtta.
Алгоритм поиска с возвратом может быть медленным.
Мемоизация (запоминание): помнить все.
Динамическое программирование: осмысленное заполнение.
И все же не следует запоминать все подряд.
3.2. Небольшое отступление: еще более быстрое определение чисел Фибоначчи.
Стоп! Не так быстро.
3.3. Interpunctio verborum redux (И снова о пунктуации).
3.4. Шаблон: интеллектуальная рекурсия.
3.5. Внимание: жадность - это глупость.
3.6. Максимальная возрастающая подпоследовательность.
Первое рекуррентное выражение: кто следующий?.
Второе рекуррентное выражение: что дальше?.
3.7. Расстояние редактирования.
Рекурсивная структура.
Рекуррентное выражение.
Динамическое программирование.
3.8. Задача о сумме подмножеств.
3.9. Оптимальные двоичные деревья поиска.
3.10. Динамическое программирование для деревьев.
Упражнения.
Последовательности/Массивы.
Разделение последовательностей/массивов.
Деревья и поддеревья.
Глава 4. Жадные алгоритмы.
4.1. Сохранение файлов на магнитной ленте.
4.2. Планирование учебных курсов.
4.3. Общий шаблон.
4.4. Коды Хаффмана.
4.5. Задача о стабильных браках.
Некоторые неудачные идеи.
Алгоритмы Boston Pool и Гэйла-Шепли.
Время выполнения.
Корректность.
Оптимальность.
Упражнения.
Глава 5. Основные графовые алгоритмы.
5.1. Введение и историческая справка.
5.2. Основные определения.
5.3. Представления и примеры.
5.4. Структуры данных.
Списки смежных вершин.
Матрицы смежности.
Сравнение.
5.5. Поиск в любом направлении.
Анализ.
5.6. Важные варианты.
Стек: поиск в глубину.
Очередь: поиск в ширину.
Очередь с приоритетами: поиск по первому наилучшему совпадению.
Несвязные графы.
Направленные графы.
5.7. Редукция графа: сплошная заливка.
Упражнения.
Графы.
Алгоритмы обхода.
Сведения.
Глава 6. Поиск в глубину.
6.1. Обход в прямом и обратном порядке.
Классификация вершин и ребер.
6.2. Обнаружение циклов.
6.3. Топологическая сортировка.
Неявная топологическая сортировка.
6.4. Мемоизация и динамическое программирование.
Динамическое программирование в НАГ.
6.5. Сильная связность.
6.6. Сильные компоненты за линейное время.
Алгоритм Косараджу-Шарира.
Алгоритм Тарьяна.
Упражнения.
Поиск в глубину, топологическая сортировка и сильные компоненты.
Динамическое программирование.
Глава 7. Минимальные остовные деревья.
7.1. Различные веса ребер.
7.2. Единственный алгоритм минимального остовного дерева.
7.3. Алгоритм Борувки.
Это тот самый алгоритм МОД, который вам нужен.
7.4. Алгоритм Ярника (Прима).
Улучшенный алгоритм Ярника.
7.5. Алгоритм Краскала.
Упражнения.
Глава 8. Кратчайшие пути.
8.1. Деревья кратчайшего пути.
8.2. Отрицательные ребра.
8.3. Единственный алгоритм SSSP.
8.4. Невзвешенные графы: поиск в ширину.
8.5. Направленный ациклический граф: поиск в глубину.
8.6. Поиск по первому наилучшему совпадению: алгоритм Дейкстры.
Отсутствие отрицательных ребер.
Отрицательные ребра.
8.7. Ослабление напряжения всех ребер: алгоритм Беллмана-Форда.
Улучшение Мура.
Формулировка с использованием динамического программирования.
Упражнения.
Глава 9. Кратчайшие пути между всеми парами вершин в графе.
9.1. Введение.
9.2. Множество отдельных источников.
9.3. Изменение весов.
9.4. Алгоритм Джонсона.
9.5. Динамическое программирование.
9.6. Разделяй и властвуй.
9.7. Странное умножение матриц.
9.8. Алгоритм (Клини-Роя-)Флойда-Уоршелла(-Ингермана).
Упражнения.
Глава 10. Максимальные потоки и наименьшие разрезы.
10.1. Потоки.
10.2. Разрезы.
10.3. Теорема о максимальном потоке и наименьшем разрезе (Maxflow-Mincut).
10.4. Алгоритм увеличивающего пути Форда и Фалкерсона.
Иррациональные пропускные способности.
10.5. Объединения и разбиения потоков.
10.6. Алгоритмы Эдмондса и Карпа.
Самые насыщенные увеличивающие пути.
Кратчайшие увеличивающие пути.
10.7. Дальнейшее развитие.
Упражнения.
Глава 11. Приложения потоков и разрезов.
11.1. Реберно-непересекающиеся пути.
11.2. Пропускные способности вершин и вершинно-непересекающиеся пути.
11.3. Задача о паросочетании в двудольном графе.
11.4. Выбор кортежа.
Расписание экзаменов.
11.5. Покрытия непересекающихся путей.
Набор минимального преподавательского состава.
11.6. Алгоритм исключения для бейсбола.
11.7. Выбор проекта.
Упражнения.
Глава 12. NP-трудность.
12.1. Игра, которую невозможно выиграть.
12.2. Р против NP.
12.3. NP-трудная, NP-легкая и NP-полная задача.
12.4. Формальные определения (НС SVNT DRACONES - Тут [обитают] драконы).
12.5. Редукции и задача Sat.
12.6. 3Sat (от CircuitSat).
12.7. Максимальное независимое множество (от 3Sat).
12.8. Общий шаблон.
12.9. Клика и вершинное покрытие (от независимого множества).
12.10. Раскраска графа (от 3Sat).
12.11. Гамильтонов цикл.
От вершинного покрытия.
От 3Sat.
Варианты и расширения.
12.12. Задача о сумме подмножеств (от задачи вершинного покрытия).
Да будет осмотрителен выполняющий редукцию!.
12.13. Другие полезные NP-трудные задачи.
12.14. Выбор правильной задачи.
12.15. Простой пример из реальной жизни.
12.16. Что дальше.
Полиномиальное пространство.
Экспоненциальное время.
Все выше и выше!.
Упражнения.
Предметный указатель.
Список алгоритмов на псевдокоде.

Купить .





Теги: учебник по программированию :: программирование :: Эриксон :: алгоритмизация