Совершенный алгоритм, Графовые алгоритмы и структуры данных, Рафгарден Т., 2019

Совершенный алгоритм, Графовые алгоритмы и структуры данных, Рафгарден Т., 2019.

  Алгоритмы — это сердце и душа computer science. Без них не обойтись, они есть везде — от сетевой маршрутизации и расчетов по геномике до криптографии и машинного обучения. «Совершенный алгоритм» превратит вас в настоящего профи, который будет ставить задачи и мастерски их решать как в жизни, так и на собеседовании при приеме на работу в любую IТ-компанию.
Во второй книге Тим Рафгарден, гуру алгоритмов, расскажет о графовом поиске и его применении, алгоритме поиска кратчайшего пути, а также об использовании и реализации некоторых структур данных: куч. деревьев поиска, хеш-таблиц и фильтра Блума.
Серия книг «Совершенный алгоритм» адресована тем. у кого уже есть опыт программирования, и основана на онлайн-курсах, которые регулярно проводятся с 2012 года. Вы перейдете на новый уровень, чтобы увидеть общую картину, разобраться в низкоуровневых концепциях и математических нюансах.




Поиск в графе и его применения.
Эта глава посвящена фундаментальным примитивам для графового поиска и их применениям. Один из интереснейших аспектов этого материала заключается в том. что все алгоритмы, которые мы рассмотрим, являются невероятно быстрыми (линейно-временными с небольшими константами), и понять, почему они работают, может быть довольно непросто. Кульминацией этой главы является вычисление сильно связных компонент ориентированного графа только с двумя проходами поиска в глубину (раздел 8.6) — оно наглядно иллюстрирует то. как быстрые алгоритмы нередко требуют глубокого понимания структуры задачи.

Мы начнем с обзорного материала (раздел 8.1), который охватывает несколько причин, почему вас должен заботить поиск в графе, общую стратегию графового поиска без выполнения какой-либо избыточной работы и высокоуровневое введение в две наиважнейшие стратегии поиска: поиск в ширину (breadth-first search. BFS) и поиск в глубину (depth-first search. DFS). Разделы 8.2 и 8.3 более подробно описывают поиск в ширину, включая применения для вычисления кратчайших путей и связных компонент неориентированного графа. Разделы 8.4 и 8.5 разъясняют поиск в глубину и его использование для вычисления топологического упорядочивания ориентированного ациклического графа (равным образом, для построения последовательности операций при соблюдении ограничений по предшествованию). В разделе 8.6 используется поиск в глубину для вычисления сильно связных компонент ориентированного графа за линейное время. В разделе 8.7 дается объяснение того, как этот быстрый графовый примитив может быть использован для разведывания структуры Всемирной паутины.

Содержание.
Предисловие.
О чем эта книга.
Навыки, которые вы приобретете.
В чем особенность книг этой серии.
Для кого эта книга?.
Дополнительные ресурсы.
Благодарности.
От издательства.
Глава 7. Графы: основы.
7.1. Термины.
7.2. Несколько приложений.
7.3. Измерение размера графа.
7.3.1. Число ребер в графе.
7.3.2. Разреженные и плотные графы.
7.3.3. Решение тестового задания 7.1.
7.4. Представление графа.
7.4.1. Списки смежности.
7.4.2. Матрица смежности.
7.4.3. Сравнение представлений.
7.4.4. Решения тестовых заданий 7.2-7.3.
Задачи на закрепление материала.
Глава 8. Поиск в графе и его применения.
8.1. Краткий обзор.
8.1.1. Некоторые приложения.
8.1.2. Бесплатные графовые примитивы.
8.1.3. Обобщенный графовый поиск.
8.1.4. Поиск в ширину и в глубину.
8.1.5. Правильность алгоритма GenericSearch.
8.2. Поиск в ширину и кратчайшие пути.
8.2.1. Высокоуровневая идея.
8.2.2. Псевдокод для алгоритма BF5.
8.2.3. Пример.
8.2.4. Правильность и время выполнения.
8.2.5. Кратчайший путь.
8.2.6. Решение тестового задания 8.1.
8.3. Вычисление связных компонент.
8.3.1. Связные компоненты.
8.3.2. Применения.
8.3.3. Алгоритм UCC.
8.3.4. Пример.
8.3.5. Правильность и время выполнения.
8.3.6. Решение тестового задания 8.2.
8.4. Поиск в глубину.
8.4.1. Пример.
8.4.2. Псевдокод для алгоритма DF5.
8.4.3. Правильность и время выполнения.
8.5. Топологическая сортировка.
8.5.1. Топологические упорядочивания.
8.5.2. Когда есть топологическое упорядочивание?.
8.5.3. Вычисление топологического упорядочивания.
8.5.4. Топологическая сортировка посредством алгоритма DFS.
8.5.5. Пример.
8.5.6. Правильность и время выполнения.
8.5.7. Решения тестовых заданий 8.3-8.4.
*8.6. Вычисление сильно связных компонент.
8.6.1. Определение сильно связных компонент.
8.6.2. Почему поиск в глубину?.
8.6.3. Почему обратный граф?.
8.6.4. Псевдокод для алгоритма Косарайю.
8.6.5. Пример.
8.6.6. Правильность и время выполнения.
8.6.7. Решения тестовых заданий 8.5-8.6.
8.7. Структура Всемирной паутины.
8.7.1. Веб-граф.
8.7.2. «Галстук-бабочка».
8.7.3. Основные выводы.
Задача повышенной сложности.
Задача по программированию.
Глава 9. Алгоритм кратчайшего пути Дейкстры.
9.1. Задача о кратчайшем пути с единственным истоком.
9.1.1. Определение задачи.
9.1.2. Несколько допущений.
9.1.3. Почему не поиск в ширину?.
9.1.4. Решение тестового задания 9.1.
9.2. Алгоритм Дейкстры.
9.2.1. Псевдокод.
9.2.2. Пример.
*9.3. Почему алгоритм Дейкстры правилен?.
9.3.1. Фиктивная редукция.
9.3.2. Плохой пример алгоритма Дейкстры.
9.3.3. Правильность с неотрицательными реберными длинами.
9.4. Реализация и время выполнения.
Задачи на закрепление материала.
Задача повышенной сложности.
Задача по программированию.
Глава 10. Куча.
10.1. Структуры данных: краткий обзор.
10.1.1. Выбор правильной структуры данных.
10.1.2. Переход на следующий уровень.
10.2. Поддерживаемые операции.
10.2.1. Вставка и извлечение минимума.
10.2.2. Дополнительные операции.
10.3. Применения.
10.3.1. Применение: сортировка.
10.3.2. Применение: событийный менеджер.
10.3.3. Применение: поддержка медианы.
10.4. Ускорение алгоритма Дейкстры.
10.4.1. Почему именно кучи?.
10.4.2. План.
10.4.3. Поддержание инварианта.
10.4.4. Время выполнения.
*10.5. Детали реализации.
10.5.1. Кучи в виде деревьев.
10.5.2. Кучи в виде массива.
10.5.3. Реализация операции «Вставить» со временем О(log n).
10.5.4. Реализация операции «Извлечь минимум»
со временем О(log n).
Задачи на закрепление материала.
Задачи повышенной сложности.
Задача по программированию.
Глава 11. Дерево поиска.
11.1. Отсортированные массивы.
11.1.1. Отсортированные массивы: поддерживаемые операции.
11.1.2. Неподдерживаемые операции.
11.2. Деревья поиска: поддерживаемые операции.
*11.3. Детали реализации.
11.3.1. Свойство дерева поиска.
11.3.2. Высота дерева поиска.
11.3.3. Реализация операции «Отыскать» со временем О(высота).
11.3.4. Реализация операций «Минимум» и «Максимум» за время О (высота).
11.3.5. Реализация операции «Предшественник» со временем О (высота).
11.3.6. Реализация операции «Вывести в отсортированном порядке» со временем О(n).
11.3.7. Реализация операции «Вставить» со временем О (высота).
11.3.8. Реализация операции «Удалить» со временем О(высота).
11.3.9. Расширенные деревья поиска для операции «Выбрать».
11.3.10. Решение тестового задания 11.1.
*11.4. Сбалансированные деревья поиска.
11.4.1. Более напряженные усилия для улучшения баланса.
11.4.2. Повороты.
Задачи на закрепление материала.
Задача по программированию.
Глава 12. Хеш-таблицы и фильтры Блума.
12.1. Поддерживаемые операции.
12.1.1. Решение тестового задания 12.1.
12.2. Применения.
12.2.1. Применение: устранение дублирования.
12.2.2. Применение: задача о сумме двух чисел.
12.2.3. Применение: поиск в огромных пространствах состояний.
12.2.4. Решение тестового задания 12.2.
*12.3. Реализация: высокоуровневая идея.
12.3.1. Два простых решения.
12.3.2. Хеш-функции.
12.3.3. Коллизии неизбежны.
12.3.4. Разрешение коллизий: сцепление.
12.3.5. Разрешение коллизий: открытая адресация.
12.3.6. Что делает хеш-функцию хорошей?.
12.3.7. Решения тестовых заданий 12.3-12.5.
*12.4. Дополнительные детали реализации.
12.4.1. Загрузка против результативности.
12.4.2. Управление загрузкой вашей хеш-таблицы.
12.4.3. Выбор своей хеш-функции.
12.4.4. Выбор стратегии разрешения коллизий.
12.4.5. Решение тестового задания 12.6.
12.5. Фильтры Блума: основы.
12.5.1. Поддерживаемые операции.
12.5.2. Применения.
12.5.3. Реализация.
*12.6. Фильтр Блума: эвристический анализ.
12.6.1. Эвристические допущения.
12.6.2. Доля установленных бит (равных 1).
12.6.3. Вероятность ложного утверждения.
12.6.4. Кульминационный момент.
12.6.5. Решение тестового задания 12.7.
Задачи на закрепление материала.
Задача по программированию.
Приложение В. Краткий обзор асимптотической формы записи.
В.1. Суть.
В.2. Обозначение О-большое.
В.З. Примеры.
В.4. Обозначения Омега-большое и Тета-большое.
Решения отдельных задач.

Купить .





Теги: учебник по программированию :: программирование :: Рафгарден :: алгоритм