Совершенный алгоритм, Жадные алгоритмы и динамическое программирование, Рафгарден Т., 2020

Совершенный алгоритм, Жадные алгоритмы и динамическое программирование, Рафгарден Т., 2020.

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




Темы жадной парадигмы.
Вот несколько тем, которые следует высматривать в наших примерах (возможно, для того чтобы этот раздел казался менее абстрактным, вы захотите перечитать его после просмотра одного или нескольких примеров). Во-первых, во многих задачах удивительно легко придумать один или даже несколько жадных алгоритмов, причем вполне работоспособных. В действительности жадные алгоритмы могут быть отличным лекарством от преодоления писательского тупика, в котором вы застряли на вполне обыденной задачке, но при этом они могут быть трудноприменимыми для оценки того, какой именно жадный подход является наиболее перспективным. Во-вторых, анализ времени выполнения часто отличается афористичностью. Например, многие жадные алгоритмы сводятся к сортировке (плюс линейное количество дополнительной обработки), и в этом случае расчетное время выполнения реализации будет составлять О(n log n), где n — число объектов для сортировки (обозначение O-большое подавляет постоянные множители, а различные логарифмические функции отличаются постоянным множителем, поэтому нет необходимости указывать основание логарифма). Наконец, часто трудно понять, действительно ли предлагаемый жадный алгоритм возвращает правильный выход для каждого возможного входа. Риск в том. что одно из необратимых близоруких решений алгоритма вернется и будет вас преследовать, а задним числом будет обнаружено, что алгоритм никуда не годится. И даже когда жадный алгоритм является формально правильным, доказать это бывает трудно.

Оглавление.
Предисловие.
О чем эта книга.
Навыки, которые вы приобретете.
В чем особенность книг этой серии.
Для кого эта книга?.
Дополнительные ресурсы.
Благодарности.
От издательства.
Глава 13. Введение в жадные алгоритмы.
13.1. Парадигма проектирования жадных алгоритмов.
13.1.1. Парадигмы алгоритмов.
13.1.2. Темы жадной парадигмы.
13.2. Задача планирования.
13.2.1. Постановка.
13.2.2. Сроки завершения.
13.2.3. Целевая функция.
13.2.4. Решение упражнения 13.1.
13.3. Разработка жадного алгоритма.
13.3.1. Два частных случая.
13.3.2. Дуэльные жадные алгоритмы.
13.3.3. Решения упражнений 13.2–13.3.
13.4. Доказательство правильности.34
13.4.1. Случай отсутствия совпадающих значений: высокоуровневый план.
13.4.2. Обмен работами при последовательной инверсии.
13.4.3. Анализ стоимости и преимущества.
13.4.4. Обработка совпадений значений.
13.4.5. Решения упражнений 13.4–13.5.
Задачи на закрепление материала.
Задачи по программированию.
Глава 14. Коды Хаффмана.
14.1. Коды.
14.1.1. Двоичные коды фиксированной длины.
14.1.2. Коды переменной длины.
14.1.3. Беспрефиксные коды.
14.1.4. Преимущества беспрефиксных кодов.
14.1.5. Определение задачи.
14.1.6. Решения упражнений 14.1–14.2.
14.2. Коды в виде деревьев.
14.2.1. Три примера.
14.2.2. Какие деревья представляют беспрефиксные коды?.
14.2.3. Определение задачи (в новой формулировке).
14.3. Жадный алгоритм Хаффмана.
14.3.1. Построение деревьев путем последовательных слияний.
14.3.2. Жадный критерий Хаффмана.
14.3.3. Псевдокод.
14.3.4. Пример.
14.3.5. Более крупный пример.
14.3.6. Время выполнения.
14.3.7. Решение упражнения 14.3.
14.4. Доказательство правильности.
14.4.1. Высокоуровневый план.
14.4.2. Подробности.
Задачи на закрепление материала.
Сложные задачи.
Задачи по программированию.
Глава 15. Минимальные остовные деревья.
15.1. Определение задачи.
15.1.1. Графы.
15.1.2. Остовные деревья.
15.1.3. Решение упражнения 15.1.
15.2. Алгоритм Прима.
15.2.1. Пример.
15.2.2. Псевдокод.
15.2.3. Простая реализация.
15.3. Ускорение алгоритма Prim посредством куч.
15.3.1. В поисках времени выполнения, близкого к линейному.
15.3.2. Кучевая структура данных.
15.3.3. Как использовать кучи в алгоритме Прима.
15.3.4. Псевдокод.
15.3.5. Анализ времени выполнения.
15.3.6. Решение упражнения 15.3.
15.4. Алгоритм Прима: доказательство правильности.
15.4.1. Свойство минимального узкого места.
15.4.2. Интересные факты об остовных деревьях.
15.4.3. Доказательство теоремы 15.6 (из свойства минимального узкого места следует минимальное остовное дерево).
15.4.4. Сводя все воедино.
15.5. Алгоритм Краскала.
15.5.1. Пример.
15.5.2. Псевдокод.
15.5.3. Простая реализация.
15.6. Ускорение алгоритма Краскала с помощью структуры данных Union-Find.
15.6.1. Структура данных Union-Find.
15.6.2. Псевдокод.
15.6.3. Анализ времени выполнения.
15.6.4. Быстрая и приближенная реализация структуры данных Union-Find.
15.6.5. Решения упражнений 15.5–15.7.
15.7. Алгоритм Краскала: доказательство правильности.
15.8. Применение: кластеризация с одиночной связью.
15.8.1. Кластеризация.
15.8.2. Восходящая кластеризация.
Задачи на закрепление материала.
Задачи повышенной сложности.
Задачи по программированию.
Глава 16. Введение в динамическое программирование.
16.1. Задача о взвешенном независимом множестве.
16.1.1. Определение задачи.
16.1.2. Естественный жадный алгоритм оказывается безуспешным.
16.1.3. Подход «разделяй и властвуй»?.
16.1.4. Решения упражнений 16.1–16.2.
16.2. Линейно-временной алгоритм для взвешенного независимого множества на путях.
16.2.1. Оптимальная подструктура и рекуррентное соотношение.
16.2.2. Наивный рекурсивный подход.
16.2.3. Рекурсия с кэшем.
16.2.4. Восходящая итеративная реализация.
16.2.5. Решения упражнений 16.3–16.4.
16.3. Алгоритм реконструкции.
16.4. Принципы динамического программирования.
16.4.1. Трехшаговый рецепт.
16.4.2. Желаемые свойства подзадач.
16.4.3. Повторяемый мыслительный процесс.
16.4.4. Динамическое программирование против «разделяй и властвуй».
16.4.5. Почему «динамическое программирование»?.
16.5. Задача о ранце.
16.5.1. Определение задачи.
16.5.2. Оптимальная подструктура и рекурренция.
16.5.3. Подзадачи.
16.5.4. Алгоритм динамического программирования.
16.5.5. Пример.
16.5.6. Реконструкция.
16.5.7. Решения упражнений 16.5–16.6.
Задачи на закрепление материала.
Задачи повышенной сложности.
Задачи по программированию.
Глава 17. Расширенное динамическое программирование.
17.1. Выравнивание последовательностей.
17.1.1. Актуальность.
17.1.2. Определение задачи.
17.1.3. Оптимальная подструктура.
17.1.4. Рекуррентное соотношение.
17.1.5. Подзадачи.
17.1.6. Алгоритм динамического программирования.
17.1.7. Реконструкция.
17.1.8. Решение упражнений 17.1–17.3.
17.2. Оптимальные бинарные деревья поиска.
17.2.1. Обзор бинарного дерева поиска.
17.2.2. Среднее время поиска.
17.2.3. Определение задачи.
17.2.4. Оптимальная подструктура.
17.2.5. Рекуррентные соотношения.
17.2.6. Подзадачи.
17.2.7. Алгоритм динамического программирования.
17.2.8. Улучшение времени выполнения.
17.2.9. Решения упражнений 17.4–17.5.
Задачи на закрепление материала.
Задачи повышенной сложности.
Задачи по программированию.
Глава 18. Кратчайшие пути повторно.
18.1. Кратчайшие пути с отрицательными длинами ребер.
18.1.1. Задача о кратчайшем пути с единственным истоком.
18.1.2. Отрицательные циклы.
18.1.3. Решение упражнения 18.1.
18.2. Алгоритм Беллмана—Форда.
18.2.1. Подзадачи.
18.2.2. Оптимальная подструктура.
18.2.3. Рекурренция.
18.2.4. Когда следует остановиться?.
18.2.5. Псевдокод.
18.2.6. Пример.
18.2.7. Время выполнения.
18.2.8. Маршрутизация интернета.
18.2.9. Решения упражнений 18.2–18.3.
18.3. Задача о кратчайшем пути для всех пар.
18.3.1. Определение задачи.
18.3.2. Сведение до кратчайших путей с единственным истоком.
18.3.3. Решение упражнения 18.4.
18.4. Алгоритм Флойда—Уоршелла.
18.4.1. Подзадачи.
18.4.2. Оптимальная подструктура.
18.4.3. Псевдокод.
18.4.4. Обнаружение отрицательного цикла.
18.4.5. Резюме и открытые вопросы.
18.4.6. Решения упражнений 18.5–18.6.
Задачи на закрепление материала.
Задачи повышенной сложности.
Задачи по программированию.
Эпилог: руководство по разработке алгоритмов.
Подсказки и решения избранных задач.

Купить .





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