Совершенный алгоритм, Алгоритмы для NP-трудных задач, Рафгарден Т., 2021

Совершенный алгоритм, Алгоритмы для NP-трудных задач, Рафгарден Т., 2021.

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




Безуспешные попытки решить задачу коммивояжера.
Я мог бы рассказать дурацкую историю о коммивояжере, но не хочу вас запутать. Если увидите серию операций, расположенных в ряде, при том что стоимость или время выполнения операции зависит от предыдущей операции. — это замаскированная задача коммивояжера.

Например, операции могут представлять сборку автомобилей на заводе. Время сборки автомобиля равно сумме фиксированной стоимости сборки и стоимости настройки, которая зависит от разницы заводских конфигураций для этого и предыдущего автомобиля. Максимально быстрая сборка всех автомобилей сводится к минимизации суммы стоимостей настройки, что и составляет задачу коммивояжера.

Возьмем совершенно другое применение. Представьте кучу перекрывающихся фрагментов генома, которые нужно правдоподобно упорядочить. Имея в руках «меру правдоподобия», назначающую стоимость каждой паре фрагментов (например, производную от длины их наибольшей общей подстроки), вы можете свести задачу упорядочения к задаче коммивояжера.

Содержание.
Предисловие.
О чем эти книги.
Навыки, которые вы приобретете.
В чем особенность этой книги.
Для кого эта книга?.
Дополнительные ресурсы.
Благодарности.
От издательства.
Глава 19. Что такое NP-трудность?.
19.1. Задача о минимальном остовном дереве и задача коммивояжера: алгоритмическая загадка.
19.1.1. Задача о минимальном остовном дереве.
19.1.2. Задача коммивояжера.
19.1.3. Безуспешные попытки решить задачу коммивояжера.
19.1.4. Решения к тестовым заданиям 19.1–19.2.
19.2. Возможные уровни профессиональной компетенции.
19.3. «Легкие» и «трудные» задачи.
19.3.1. Полиномиально-временные алгоритмы.
19.3.2. Полиномиальное время против экспоненциального.
19.3.3. Легкорешаемые задачи.
19.3.4. Относительная труднорешаемость.
19.3.5. Трудные задачи.
19.3.6. Предположение, что P ≠ NP.
19.3.7. Предварительное определение NP-трудности.
19.3.8. Рандомизированные и квантовые алгоритмы.
19.3.9. Тонкости.
19.4. Алгоритмические стратегии для NP-трудных задач.
19.4.1. Универсальный, правильный, быстрый (выбрать два).
19.4.2. Компромисс в отношении универсальности.
19.4.3. Компромисс в отношении правильности.
19.4.4. Компромисс в отношении скорости.
19.4.5. Ключевые выводы.
19.5. Доказательство NP-трудности: простой рецепт.
19.5.1. Редукции.
19.5.2. Использование упрощений для разработки быстрых алгоритмов.
19.5.3. Использование упрощений для распространения NP-трудности.
19.5.4. NP-трудность бесцикловых кратчайших путей.
19.5.5. Решение к тестовому заданию 19.3.
19.6. Ошибки новичков и допустимые неточности.
Задачи на закрепление материала.
Задачи повышенной сложности.
Задача по программированию.
Глава 20. Компромисс в отношении правильности: эффективные неточные алгоритмы.
20.1. Минимизация производственной продолжительности.
20.1.1. Определение задачи.
20.1.2. Жадные алгоритмы.
20.1.3. Алгоритм Грэма.
20.1.4. Время работы.
20.1.5. Приближенная правильность.
20.1.6. Доказательство теоремы 20.1.
20.1.7. Сначала самое длительное время обработки.
20.1.8. Доказательство теоремы 20.4.
20.1.9. Решения к тестовым заданиям 20.1–20.3.
20.2. Максимальный охват.
20.2.1. Определение задачи.
20.2.2. Дальнейшие применения.
20.2.3. Жадный алгоритм.
20.2.4. Плохие примеры для GreedyCoverage.
20.2.5. Приближенная правильность.
20.2.6. Ключевая лемма.
20.2.7. Доказательство теоремы 20.7.
20.2.8. Решения к тестовым заданиям 20.4–20.5.
20.3. Максимизация влияния.
20.3.1. Каскады в социальных сетях.
20.3.2. Пример.
20.3.3. Задача о максимизации влияния.
20.3.4. Жадный алгоритм.
20.3.5. Приближенная правильность.
20.3.6. Влияние есть взвешенная сумма функций охвата.
20.3.7. Доказательство теоремы 20.9.
20.3.8. Решение к тестовому заданию 20.6.
20.4. Эвристический алгоритм двукратной замены для задачи коммивояжера.
20.4.1. Решение задачи коммивояжера.
20.4.2. Улучшение тура двукратной заменой.
20.4.3. Алгоритм двукратной замены 2-OPT.
20.4.4. Время работы.
20.4.5. Качество решения.
20.4.6. Решения к тестовым заданиям 20.7–20.8.
20.5. Принципы локального поиска.
20.5.1. Метаграф допустимых решений.
20.5.2. Парадигма проектирования алгоритма локального поиска.
20.5.3. Три модельных решения.
20.5.4. Два решения по проектированию алгоритма.
20.5.5. Время выполнения и качество решения.
20.5.6. Избегание плохих локальных оптимумов.
20.5.7. Когда использовать локальный поиск?.
20.5.8. Решения к тестовым заданиям 20.9–20.10.
Задачи на закрепление материала.
Задачи повышенной сложности.
Задачи по программированию.
Глава 21. Компромисс в отношении скорости: точные неэффективные алгоритмы.
21.1. Алгоритм Беллмана — Хелда — Карпа для задачи коммивояжера.
21.1.1. Базовый уровень: исчерпывающий поиск.
21.1.2. Динамическое программирование.
21.1.3. Оптимальная подструктура.
21.1.4. Рекуррентное уравнение.
21.1.5. Подзадачи.
21.1.6. Алгоритм Беллмана — Хелда — Карпа.
21.1.7. Решение к тестовому заданию 21.1.
21.2. Поиск длинных путей посредством цветового кодирования.
21.2.1. Актуальность.
21.2.2. Определение задачи.
21.2.3. Первая атака на подзадачи.
21.2.4. Цветовое кодирование.
21.2.5. Вычисление самого дешевого панхроматического пути.
21.2.6. Правильность и время выполнения.
21.2.7. Рандомизация спешит на помощь.
21.2.8. Окончательный алгоритм.
21.2.9. Время выполнения и правильность.
21.2.10. Пересмотр сетей белок-белковых взаимодействий.
21.2.11. Решения к тестовым заданиям 21.2–21.4.
21.3. Алгоритмы для конкретных задач против волшебных ящиков.
21.3.1. Редукции и волшебные ящики.
21.3.2. Решатели задач MIP и SAT.
21.3.3. Чему вы научитесь и чему не научитесь.
21.3.4. Ошибки новичка повторно.
21.4. Решатели задач MIP.
21.4.1. Пример: задача о рюкзаке.
21.4.2. Задачи MIP в более общем случае.
21.4.3. Решатели задач MIP: некоторые отправные точки.
21.5. Решатели задач SAT.
21.5.1. Пример: раскраска графа.
21.5.2. Выполнимость булевых формул.
21.5.3. Кодирование раскраски графа как задачи SAT.
21.5.4. Решатели задач SAT: некоторые отправные точки.
Задачи на закрепление материала.
Задачи повышенной сложности.
Задачи по программированию.
Глава 22. Доказательство NP-трудных задач.
22.1. Редукции повторно.
22.2. Задача 3-SAT и теорема Кука — Левина.
22.3. Общая картина.
22.3.1. Ошибка новичка повторно.
22.3.2. Восемнадцать редукций.
22.3.3. Зачем продираться через доказательства NP-трудности?.
22.3.4. Решение к тестовому заданию 22.1.
22.4. Шаблон для редукций.
22.5. Задача о независимом множестве является NP-трудной.
22.5.1. Главная идея.
22.5.2. Доказательство теоремы 22.2.
22.6. Ориентированный гамильтонов путь является NP-трудным.
22.6.1. Кодирование переменных и присвоение истинности.
22.6.2. Кодирование ограничений.
22.6.3. Доказательство теоремы 22.4.
22.7. Задача коммивояжера является NP-трудной.
22.7.1. Задача о неориентированном гамильтоновом пути.
22.7.2. Доказательство теоремы 22.7.
22.8. Задача о сумме подмножества является NP-трудной.
22.8.1. Базовый подход.
22.8.2. Пример: четырехвершинный цикл.
22.8.3. Пример: пятивершинный цикл.
22.8.4. Доказательство теоремы 22.9.
Задачи на закрепление материала.
Задачи повышенной сложности.
Глава 23. P, NP и все такое прочее.
23.1. Накопление свидетельств труднорешаемости.
23.1.1. Построение убедительного случая с помощью редукций.
23.1.2. Выборка множества C для задачи коммивояжера.
23.2. Решение, поиск и оптимизация.
23.3. NP: задачи с легко распознаваемыми решениями.
23.3.1. Определение класса сложности NP.
23.3.2. Примеры задач в NP.
23.3.3. Задачи NP поддаются решению исчерпывающим поиском.
23.3.4. NP-трудные задачи.
23.3.5. Теорема Кука — Левина повторно.
23.3.6. Решение к тестовому заданию 23.1.
23.4. Предположение, что P ≠ NP.
23.4.1. P: задачи NP, поддающиеся решению за полиномиальное время.
23.4.2. Формальное определение предположения.
23.4.3. Статус предположения, что P ≠ NP.
23.5. Гипотеза об экспоненциальном времени.
23.5.1. Требуют ли NP-трудные задачи экспоненциального времени?.
23.5.2. Сильная гипотеза об экспоненциальном времени.
23.5.3. Нижние границы времени выполнения для простых задач.
23.6. NP-полнота.
23.6.1. Редукции Левина.
23.6.2. Самые трудные задачи в NP.
23.6.3. Существование NP-полных задач.
Задачи на закрепление материала.
Задачи повышенной сложности.
Глава 24. Практический пример: стимулирующий аукцион FCC.
24.1. Перенацеливание беспроводного спектра.
24.1.1. От телевидения к мобильным телефонам.
24.1.2. Недавнее перераспределение спектра.
24.2. Жадные эвристики для выкупа лицензий.
24.2.1. Четыре временных упрощающих допущения.
24.2.2. Засада со стороны взвешенного независимого множества.
24.2.3. Жадные эвристические алгоритмы.
24.2.4. Многоканальный случай.
24.2.5. Засада со стороны раскраски графа.
24.2.6. Решение к тестовому заданию 24.1.
24.3. Проверка допустимости.
24.3.1. Кодирование в качестве задачи выполнимости.
24.3.2. Встраивание реберных ограничений.
24.3.3. Задача о переупаковке.
24.3.4. Трюк № 1: предварительные решатели (в поисках легкого выхода).
24.3.5. Трюк № 2: предварительная обработка и упрощение.
24.3.6. Трюк № 3: портфель решателей задач SAT.
24.3.7. Терпимость к отказам.
24.3.8. Решение к тестовому заданию 24.2.
24.4. Реализация в виде нисходящего тактового аукциона.
24.4.1. Аукционы и алгоритмы.
24.4.2. Пример.
24.4.3. Переосмысление жадного алгоритма FCCGreedy.
24.4.4. Пора получить компенсацию.
24.5. Окончательный результат.
Задачи на закрепление материала.
Задача повышенной сложности.
Задача по программированию.
Эпилог: полевое руководство по разработке алгоритмов.
Подсказки и решения.
Книги Тима Рафгардена.

Купить .





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