В издательстве “БХВ” вышло третье издание бестселлера Стивена Скиены: “Алгоритмы. Руководство по разработке. 3-е изд.“.
Книга является наиболее полным руководством по разработке эффективных алгоритмов. Первая часть книги содержит практические рекомендации по разработке алгоритмов: приводятся основные понятия, дается анализ алгоритмов, рассматриваются типы структур данных, основные алгоритмы сортировки, операции обхода графов и алгоритмы для работы со взвешенными графами, примеры использования комбинаторного поиска, эвристических методов и динамического программирования. Вторая часть книги содержит обширный список литературы и каталог из 75 наиболее распространенных алгоритмических задач, для которых перечислены существующие программные реализации.
В третьем издании расширен набор рандомизированных алгоритмов, алгоритмов хеширования, аппроксимации и квантовых вычислений. Добавлено более 100 новых задач, даны ссылки к реализациям на C, C++ и Java.
Книгу можно использовать в качестве справочника по алгоритмам для программистов, исследователей и в качестве учебного пособия для студентов соответствующих специальностей.
Наиболее полное руководство по разработке эффективных алгоритмов
Расширенное и обновленное третье издание классического бестселлера продолжает раскрывать «загадку» разработки алгоритмов и анализа их эффективности. Книга является основным учебником для курсов по разработке алгоритмов, пособием для самоподготовки к собеседованиям, сохраняя при этом свой статус главного практического справочника по алгоритмам для программистов, исследователей и студентов.
Первая часть представляет собой общее введение в технические приемы разработки и анализа компьютерных алгоритмов.
Вторая часть содержит обширный список литературы и каталог наиболее распространенных алгоритмических задач, для которых перечислены существующие программные реализации.
Новое в третьем издании
• Расширенный набор рандомизированных алгоритмов, хеширования, алгоритмов «разделяй и властвуй», аппроксимации и квантовых вычислений.
• Онлайн-поддержка для преподавателей, включающая слайды и видеоуроки.
• Полноцветные иллюстрации и код, наглядно разъясняющие сложные концепции
• Новые «истории из жизни», рассказывающие об опыте работы с реальными приложениями.
• Более 100 новых задач, включая задачи по программированию от LeetCode и Hackerrank.
• Актуальные ссылки к лучшим реализациям на языках C, C++ и Java.
От автора
Читатели предыдущих изданий одобрили три аспекта руководства: каталог алгоритмических задач, истории из жизни и электронную версию книги. Эти элементы сохранены и в настоящем издании.
- Каталог алгоритмических задач. Не так-то просто узнать, что уже известно о стоящей перед вами задаче. Именно поэтому в книге имеется каталог 75 наиболее важных задач, часто возникающих в реальной жизни.
- Истории из жизни. Чтобы продемонстрировать, как алгоритмические задачи возникают в реальной жизни, в материал книги включены неприукрашенные истории, описывающие мой опыт по решению практических задач.
- Онлайновый компонент. На моем веб-сайте (www.algorist.com) в полном объеме представлены конспекты лекций, а также Wiki-энциклопедия решений задач. Этот веб-сайт был обновлен совместно с книгой.
На веб-сайте автора www.algorist.com в полном объеме представлены конспекты лекций, а также Wiki-энциклопедия решений задач. Этот веб-сайт был обновлен совместно с книгой.
Преподаватели смогут загрузить здесь полный набор лекционных слайдов для проведения занятий по материалам книги. Кроме того, выложены аудио- и видеолекции с использованием этих слайдов для преподавания полного курса продолжительностью в один семестр.
Оригинальная книга: “The Algorithm Design Manual (Texts in Computer Science)” 3rd ed. 2020 Editionby Steven S. Skiena (Author)
Отзывы
Это руководство — мой абсолютный фаворит для подготовки к собеседованию. Больше, чем любая другая книга, она помогла мне понять, насколько поразительно распространены… проблемы с графами — они должны быть частью набора инструментов каждого работающего программиста. В книге также рассматриваются основные структуры данных и алгоритмы сортировки, что является приятным бонусом, а простые и понятные картинки облегчают запоминание.
Стив Йегге, публикация «Get that Job at Google»
Эта книга сохраняет за собой звание лучшего и наиболее полного практического руководства по алгоритмам … Каждый программист должен ее прочитать и держать под рукой. … Это лучшая инвестиция…, которую может сделать программист.
Гарольд Тимблби, журнал «Times Higher Education»
Замечательно открыть книгу на любой странице и обнаружить интересный алгоритм. Это единственный учебник, который я храню со студенческих лет!
Кори Барт, Делавэрский университет
Стивен Соль Скиена — ученый-компьютерщик и заслуженный профессор компьютерных наук в Университете Стоуни-Брук, директор Института искусственного интеллекта в Стоуни-Брук. Автор нескольких популярных книг в области алгоритмов, программирования и математики. Его книга Алгоритмы. Руководство по разработке (The Algorithm Design Manual) широко используется в качестве учебника по алгоритмам и для подготовки к собеседованию в технической индустрии. В 2001 году Скиена была награждена премией IEEE Computer Science and Engineering для студентов-преподавателей «За выдающийся вклад в высшее образование в области алгоритмов и дискретной математики, а также за влиятельные учебники и программное обеспечение» (Источник: Википедия).
-
Алгоритмы. Руководство по разработке. 3-е изд.
2000 ₽
1700 ₽
Предисловие…………………………………………………………………………………………… 17
Читателю…………………………………………………………………………………………………………………………………….. 17
Преподавателю………………………………………………………………………………………………………………………….. 19
Благодарности…………………………………………………………………………………………………………………………… 20
Ограничение ответственности………………………………………………………………………………………………….. 21
Часть I. Практическая разработка алгоритмов…………………. 23
Глава 1. Введение в разработку алгоритмов…………………………………………… 25
1.1. Оптимизация маршрута робота………………………………………………………………………………………… 26
1.2. Задача календарного планирования………………………………………………………………………………… 30
1.3. Обоснование правильности алгоритмов…………………………………………………………………………… 33
1.3.1. Задачи и свойства…………………………………………………………………………………………………….. 34
1.3.2. Представление алгоритмов……………………………………………………………………………………… 35
1.3.3. Демонстрация неправильности алгоритма……………………………………………………………. 35
Остановка для размышлений: «Жадные» кинозвезды?……………………………………………………. 37
1.3.4. Индукция и рекурсия………………………………………………………………………………………………… 38
Остановка для размышлений: Правильность инкрементных алгоритмов……………………… 39
1.4. Моделирование задачи………………………………………………………………………………………………………. 40
1.4.1. Комбинаторные объекты…………………………………………………………………………………………. 41
1.4.2. Рекурсивные объекты……………………………………………………………………………………………….. 42
1.5. Доказательство от противного………………………………………………………………………………………….. 44
1.6. Истории из жизни………………………………………………………………………………………………………………… 45
1.7. История из жизни. Моделирование проблемы ясновидения…………………………………………… 45
1.8. Прикидка……………………………………………………………………………………………………………………………… 49
Замечания к главе………………………………………………………………………………………………………………………. 50
1.9. Упражнения…………………………………………………………………………………………………………………………. 50
Поиск контрпримеров………………………………………………………………………………………………………… 50
Доказательство правильности………………………………………………………………………………………….. 51
Математическая индукция………………………………………………………………………………………………… 52
Приблизительные подсчеты………………………………………………………………………………………………. 52
Проекты по реализации……………………………………………………………………………………………………… 53
Задачи, предлагаемые на собеседовании………………………………………………………………………… 53
LeetCode………………………………………………………………………………………………………………………………. 54
HackerRank…………………………………………………………………………………………………………………………. 54
Задачи по программированию………………………………………………………………………………………….. 54
Глава 2. Анализ алгоритмов…………………………………………………………………… 55
2.1. Модель вычислений RAM………………………………………………………………………………………………….. 55
2.1.1. Анализ сложности наилучшего, наихудшего и среднего случая………………………… 56
2.2. Асимптотические («Big Oh») обозначения………………………………………………………………………… 58
Остановка для размышлений: Возвращение к определениям…………………………………………. 61
Остановка для размышлений: Квадраты…………………………………………………………………………… 61
2.3. Скорость роста и отношения доминирования………………………………………………………………….. 61
2.3.1. Отношения доминирования……………………………………………………………………………………… 63
2.4. Работа с асимптотическими обозначениями……………………………………………………………………. 64
2.4.1. Сложение функций……………………………………………………………………………………………………. 64
2.4.2. Умножение функций…………………………………………………………………………………………………. 64
Остановка для размышлений: Транзитивность………………………………………………………………… 65
2.5. Оценка эффективности……………………………………………………………………………………………………….. 65
2.5.1. Сортировка методом выбора…………………………………………………………………………………… 65
Доказываем временную сложность Θ-большое…………………………………………………….. 66
2.5.2. Сортировка вставками……………………………………………………………………………………………… 67
Доказываем временную сложность Θ-большое…………………………………………………….. 68
2.5.3. Сравнение строк……………………………………………………………………………………………………….. 68
Доказываем время исполнения по Θ-большое………………………………………………………. 69
2.5.4. Умножение матриц…………………………………………………………………………………………………… 70
2.6. Суммирование…………………………………………………………………………………………………………………….. 71
Остановка для размышлений: Формулы факториала………………………………………………………. 72
2.7. Логарифмы и их применение……………………………………………………………………………………………… 73
2.7.1. Логарифмы и двоичный поиск…………………………………………………………………………………. 73
2.7.2. Логарифмы и деревья……………………………………………………………………………………………….. 74
2.7.3. Логарифмы и биты……………………………………………………………………………………………………. 74
2.7.4. Логарифмы и умножение…………………………………………………………………………………………. 75
2.7.5. Быстрое возведение в степень…………………………………………………………………………………. 75
2.7.6. Логарифмы и сложение……………………………………………………………………………………………. 76
2.7.7. Логарифмы и система уголовного судопроизводства…………………………………………… 76
2.8. Свойства логарифмов…………………………………………………………………………………………………………. 77
Остановка для размышлений: Важно ли деление точно пополам………………………………….. 79
2.9. История из жизни. Загадка пирамид…………………………………………………………………………………. 79
2.10. Анализ высшего уровня (*)………………………………………………………………………………………………. 82
2.10.1. Малораспространенные функции……………………………………………………………………….. 83
2.10.2. Пределы и отношения доминирования……………………………………………………………….. 84
Замечания к главе………………………………………………………………………………………………………………………. 85
2.11. Упражнения……………………………………………………………………………………………………………………….. 86
Анализ программ………………………………………………………………………………………………………………. 86
Упражнения по асимптотическим обозначениям………………………………………………………….. 87
Суммирование…………………………………………………………………………………………………………………… 92
Логарифмы………………………………………………………………………………………………………………………… 93
Задачи, предлагаемые на собеседовании………………………………………………………………………. 93
LeetCode…………………………………………………………………………………………………………………………….. 94
HackerRank……………………………………………………………………………………………………………………….. 94
Задачи по программированию………………………………………………………………………………………… 94
Глава 3. Структуры данных…………………………………………………………………… 95
3.1. Смежные и связные структуры данных…………………………………………………………………………….. 95
3.1.1. Массивы…………………………………………………………………………………………………………………….. 96
3.1.2. Указатели и связные структуры данных………………………………………………………………… 97
Поиск элемента в связном списке……………………………………………………………………………. 98
Вставка элемента в связный список……………………………………………………………………….. 99
Удаление элемента из связного списка………………………………………………………………….. 99
3.1.3. Сравнение……………………………………………………………………………………………………………….. 100
3.2. Стеки и очереди………………………………………………………………………………………………………………… 101
3.3. Словари……………………………………………………………………………………………………………………………… 102
Остановка для размышлений: Сравнение реализаций словаря (I)……………………………….. 103
Остановка для размышлений: Сравнение реализаций словаря (II)……………………………… 105
3.4. Двоичные деревья поиска………………………………………………………………………………………………… 108
3.4.1. Реализация двоичных деревьев…………………………………………………………………………….. 108
Поиск в дереве………………………………………………………………………………………………………… 109
Поиск наименьшего и наибольшего элементов дерева………………………………………. 110
Обход дерева………………………………………………………………………………………………………….. 110
Вставка элементов в дерево………………………………………………………………………………….. 111
Удаление элемента из дерева……………………………………………………………………………….. 112
3.4.2. Эффективность двоичных деревьев поиска………………………………………………………….. 112
3.4.3. Сбалансированные деревья поиска……………………………………………………………………… 113
Остановка для размышлений: Использование сбалансированных деревьев поиска….. 114
3.5. Очереди с приоритетами………………………………………………………………………………………………….. 115
Остановка для размышлений: Построение базовых очередей с приоритетами………….. 115
3.6. История из жизни. Триангуляция…………………………………………………………………………………….. 117
3.7. Хеширование…………………………………………………………………………………………………………………….. 121
3.7.1. Коллизии…………………………………………………………………………………………………………………. 121
3.7.2. Выявление дубликатов с помощью хеширования……………………………………………….. 123
3.7.3. Прочие приемы хеширования……………………………………………………………………………….. 125
3.7.4. Каноникализация……………………………………………………………………………………………………. 125
3.7.5. Уплотнение……………………………………………………………………………………………………………… 126
3.8. Специализированные структуры данных………………………………………………………………………. 126
3.9. История из жизни. Геном человека………………………………………………………………………………….. 127
Замечания к главе……………………………………………………………………………………………………………………. 131
3.10. Упражнения…………………………………………………………………………………………………………………….. 131
Стеки, очереди и списки…………………………………………………………………………………………………. 131
Элементарные структуры данных………………………………………………………………………………… 132
Деревья и другие словарные структуры………………………………………………………………………. 132
Применение древовидных структур……………………………………………………………………………… 134
Задачи по реализации……………………………………………………………………………………………………. 135
Задачи, предлагаемые на собеседовании……………………………………………………………………. 136
LeetCode………………………………………………………………………………………………………………………….. 137
HackerRank……………………………………………………………………………………………………………………… 137
Задачи по программированию……………………………………………………………………………………… 137
Глава 4. Сортировка и поиск……………………………………………………………….. 138
4.1. Применение сортировки…………………………………………………………………………………………………… 138
Остановка для размышлений: Поиск пересечения множеств………………………………………… 141
Остановка для размышлений: Использование хеша для решения задач……………………… 142
4.2. Практические аспекты сортировки…………………………………………………………………………………. 143
4.3. Пирамидальная сортировка…………………………………………………………………………………………….. 145
4.3.1. Пирамиды………………………………………………………………………………………………………………… 146
Остановка для размышлений: Поиск в пирамиде…………………………………………………………… 148
4.3.2. Создание пирамиды……………………………………………………………………………………………….. 148
4.3.3. Наименьший элемент пирамиды…………………………………………………………………………… 149
4.3.4. Быстрый способ создания пирамиды (*)……………………………………………………………… 151
Остановка для размышлений: Расположение элемента в пирамиде…………………………….. 153
4.3.5. Сортировка вставками…………………………………………………………………………………………… 154
4.4. История из жизни. Билет на самолет………………………………………………………………………………. 155
4.5. Сортировка слиянием. Метод «разделяй и властвуй»…………………………………………………… 158
4.6. Быстрая сортировка. Рандомизированная версия…………………………………………………………. 160
4.6.1. Интуиция: ожидаемое время исполнения алгоритма быстрой сортировки………. 163
4.6.2. Рандомизированные алгоритмы……………………………………………………………………………. 164
Остановка для размышлений: Болты и гайки…………………………………………………………………. 166
4.6.3. Действительно ли алгоритм быстрой сортировки работает быстро?……………….. 167
4.7. Сортировка распределением. Метод блочной сортировки………………………………………….. 167
4.7.1. Нижние пределы для сортировки………………………………………………………………………….. 168
4.8. История из жизни. Скиена в суде…………………………………………………………………………………….. 170
Замечания к главе……………………………………………………………………………………………………………………. 172
4.9. Упражнения……………………………………………………………………………………………………………………….. 172
Применение сортировки: сортировка чисел………………………………………………………………….. 172
Применение сортировки: интервалы и множества………………………………………………………… 174
Пирамиды………………………………………………………………………………………………………………………….. 175
Быстрая сортировка…………………………………………………………………………………………………………. 175
Сортировка слиянием………………………………………………………………………………………………………. 176
Другие алгоритмы сортировки……………………………………………………………………………………….. 177
Нижние пределы………………………………………………………………………………………………………………. 178
Поиск…………………………………………………………………………………………………………………………………. 178
Задачи по реализации……………………………………………………………………………………………………… 178
Задачи, предлагаемые на собеседовании……………………………………………………………………… 179
LeetCode……………………………………………………………………………………………………………………………. 179
HackerRank……………………………………………………………………………………………………………………….. 180
Задачи по программированию……………………………………………………………………………………….. 180
Глава 5. Метод «разделяй и властвуй»…………………………………………………. 181
5.1. Двоичный поиск и связанные с ним алгоритмы……………………………………………………………… 181
5.1.1. Частота вхождения элемента………………………………………………………………………………… 182
5.1.2. Односторонний двоичный поиск…………………………………………………………………………… 183
5.1.3. Корни числа……………………………………………………………………………………………………………. 184
5.2. История из жизни. Поиск «бага в баге»…………………………………………………………………………… 184
5.3. Рекуррентные соотношения…………………………………………………………………………………………….. 186
5.3.1. Рекуррентные соотношения метода «разделяй и властвуй»………………………………. 187
5.4. Решение рекуррентных соотношений типа «разделяй и властвуй» (*)……………………….. 188
5.5. Быстрое умножение………………………………………………………………………………………………………….. 190
5.6. Поиск наибольшего поддиапазона и ближайшей пары………………………………………………… 192
5.7. Параллельные алгоритмы……………………………………………………………………………………………….. 194
5.7.1. Параллелизм на уровне данных……………………………………………………………………………. 194
5.7.2. Подводные камни параллелизма………………………………………………………………………….. 195
5.8. История из жизни. «Торопиться в никуда»……………………………………………………………………… 196
5.9. Свертка (*)…………………………………………………………………………………………………………………………. 197
5.9.1. Применение свертки……………………………………………………………………………………………….. 198
5.9.2. Быстрое полиномиальное умножение (**)…………………………………………………………… 199
Замечания к главе……………………………………………………………………………………………………………………. 202
5.10. Упражнения…………………………………………………………………………………………………………………….. 202
Двоичный поиск……………………………………………………………………………………………………………… 202
Алгоритмы типа «разделяй и властвуй»………………………………………………………………………. 203
Рекуррентные соотношения…………………………………………………………………………………………… 203
LeetCode………………………………………………………………………………………………………………………….. 204
HackerRank……………………………………………………………………………………………………………………… 204
Задачи по программированию……………………………………………………………………………………… 205
Глава 6. Хеширование и рандомизированные алгоритмы……………………. 206
Остановка для размышлений: Город быстрой сортировки…………………………………………… 207
6.1. Обзор теории вероятностей……………………………………………………………………………………………… 207
6.1.1. Теория вероятностей………………………………………………………………………………………………. 207
6.1.2. Составные события и независимость……………………………………………………………………. 209
6.1.3. Условная вероятность……………………………………………………………………………………………. 210
6.1.4. Распределения вероятностей…………………………………………………………………………………. 211
6.1.5. Среднее и дисперсия………………………………………………………………………………………………. 212
6.1.6. Броски монет…………………………………………………………………………………………………………… 212
Остановка для размышлений: Случайный обход графа……………………………………………….. 213
6.2. Задача мячиков и контейнеров………………………………………………………………………………………… 214
6.2.1. Задача о собирании купонов………………………………………………………………………………… 216
Остановка для размышлений: Время покрытия для Kn………………………………………………….. 216
6.3. Почему хеширование является рандомизированным алгоритмом?…………………………….. 217
6.4. Фильтры Блума…………………………………………………………………………………………………………………. 218
6.5. Парадокс дня рождения и идеальное хеширование………………………………………………………. 220
6.6. Метод минимальных хеш-кодов……………………………………………………………………………………… 222
Остановка для размышлений: Приблизительная оценка численности популяции……… 224
6.7. Эффективный поиск подстроки в строке…………………………………………………………………………. 225
6.8. Тестирование чисел на простоту…………………………………………………………………………………….. 226
6.9. История из жизни. Как я дал Кнуту свой средний инициал………………………………………….. 228
6.10. Откуда берутся случайные числа?……………………………………………………………………………….. 229
Замечания к главе……………………………………………………………………………………………………………………. 230
6.11. Упражнения…………………………………………………………………………………………………………………….. 230
Вероятность…………………………………………………………………………………………………………………….. 230
Хеширование…………………………………………………………………………………………………………………… 231
Рандомизированные алгоритмы……………………………………………………………………………………. 231
LeetCode………………………………………………………………………………………………………………………….. 232
HackerRank……………………………………………………………………………………………………………………… 232
Задачи по программированию……………………………………………………………………………………… 232
Глава 7. Обход графов………………………………………………………………………….. 233
7.1. Разновидности графов………………………………………………………………………………………………………. 234
7.1.1. Граф дружеских отношений………………………………………………………………………………….. 237
7.2. Структуры данных для графов………………………………………………………………………………………… 240
7.3. История из жизни. Жертва закона Мура………………………………………………………………………… 244
7.4. История из жизни. Создание графа…………………………………………………………………………………. 248
7.5. Обход графа………………………………………………………………………………………………………………………. 250
7.6. Обход в ширину………………………………………………………………………………………………………………… 251
7.6.1. Применение обхода………………………………………………………………………………………………… 254
7.6.2. Поиск путей…………………………………………………………………………………………………………….. 255
7.7. Применение обхода в ширину…………………………………………………………………………………………. 256
7.7.1. Компоненты связности…………………………………………………………………………………………… 256
7.7.2. Раскраска графов двумя цветами………………………………………………………………………….. 257
7.8. Обход в глубину………………………………………………………………………………………………………………… 259
7.9. Применение обхода в глубину…………………………………………………………………………………………. 263
7.9.1. Поиск циклов…………………………………………………………………………………………………………… 263
7.9.2. Шарниры графа………………………………………………………………………………………………………. 264
7.10. Обход в глубину ориентированных графов…………………………………………………………………. 268
7.10.1. Топологическая сортировка………………………………………………………………………………… 270
7.10.2. Сильно связные компоненты……………………………………………………………………………….. 272
Замечания к главе……………………………………………………………………………………………………………………. 274
7.11. Упражнения…………………………………………………………………………………………………………………….. 275
Алгоритмы для эмуляции графов………………………………………………………………………………….. 275
Обход графов………………………………………………………………………………………………………………….. 276
Приложения…………………………………………………………………………………………………………………….. 277
Разработка алгоритмов…………………………………………………………………………………………………. 278
Ориентированные графы……………………………………………………………………………………………….. 280
Шарниры графа……………………………………………………………………………………………………………… 281
Задачи, предлагаемые на собеседовании……………………………………………………………………. 282
LeetCode………………………………………………………………………………………………………………………….. 282
HackerRank…………………………………………………………………………………………………………………….. 282
Задачи по программированию……………………………………………………………………………………… 282
Глава 8. Алгоритмы для работы со взвешенными графами………………….. 283
8.1. Минимальные остовные деревья…………………………………………………………………………………….. 284
8.1.1. Алгоритм Прима……………………………………………………………………………………………………… 285
8.1.2. Алгоритм Крускала………………………………………………………………………………………………… 288
8.1.3. Структура данных непересекающихся множеств……………………………………………….. 290
8.1.4. Разновидности остовных деревьев……………………………………………………………………….. 293
8.2. История из жизни. И всё на свете — только сети……………………………………………………………. 295
8.3. Поиск кратчайшего пути………………………………………………………………………………………………….. 298
8.3.1. Алгоритм Дейкстры………………………………………………………………………………………………… 299
Остановка для размышлений: Кратчайший путь с учетом веса вершин……………………… 302
8.3.2. Кратчайшие пути между всеми парами вершин………………………………………………….. 302
8.3.3. Транзитивное замыкание……………………………………………………………………………………….. 304
8.4. История из жизни. Печатаем с помощью номеронабирателя……………………………………….. 305
8.5. Потоки в сетях и паросочетание в двудольных графах………………………………………………… 309
8.5.1. Паросочетание в двудольном графе…………………………………………………………………….. 310
8.5.2. Вычисление потоков в сети……………………………………………………………………………………. 311
8.6. Произвольный минимальный разрез……………………………………………………………………………….. 315
8.7. Разрабатывайте не алгоритмы, а графы…………………………………………………………………………. 316
Остановка для размышлений: Нить Ариадны………………………………………………………………… 317
Остановка для размышлений: Упорядочивание последовательности…………………………. 317
Остановка для размышлений: Размещение прямоугольников по корзинам…………………. 318
Остановка для размышлений: Конфликт имен файлов………………………………………………….. 318
Остановка для размышлений: Разделение текста…………………………………………………………… 318
Замечания к главе……………………………………………………………………………………………………………………. 319
8.8. Упражнения……………………………………………………………………………………………………………………….. 319
Алгоритмы для эмуляции графов……………………………………………………………………………………. 319
Минимальные остовные деревья…………………………………………………………………………………….. 319
Поиск-объединение………………………………………………………………………………………………………….. 321
Поиск кратчайшего пути…………………………………………………………………………………………………. 321
Потоки в сети и паросочетание………………………………………………………………………………………. 323
LeetCode……………………………………………………………………………………………………………………………. 323
HackerRank……………………………………………………………………………………………………………………….. 323
Задачи по программированию……………………………………………………………………………………….. 323
Глава 9. Комбинаторный поиск…………………………………………………………… 324
9.1. Перебор с возвратом…………………………………………………………………………………………………………. 324
9.2. Примеры перебора с возвратом………………………………………………………………………………………. 327
9.2.1. Генерирование всех подмножеств………………………………………………………………………… 327
9.2.2. Генерирование всех перестановок……………………………………………………………………….. 329
9.2.3. Генерирование всех путей в графе……………………………………………………………………….. 330
9.3. Отсечение вариантов поиска…………………………………………………………………………………………… 332
9.4. Судоку……………………………………………………………………………………………………………………………….. 333
9.5. История из жизни. Покрытие шахматной доски…………………………………………………………….. 339
9.6. Поиск методом «лучший-первый»…………………………………………………………………………………… 342
9.7. Эвристический алгоритм А*……………………………………………………………………………………………. 345
Замечания к главе……………………………………………………………………………………………………………………. 347
9.8. Упражнения……………………………………………………………………………………………………………………….. 347
Перестановки……………………………………………………………………………………………………………………. 347
Перебор с возвратом………………………………………………………………………………………………………… 348
Игры и головоломки…………………………………………………………………………………………………………. 349
Комбинаторная оптимизация………………………………………………………………………………………….. 350
Задачи, предлагаемые на собеседовании……………………………………………………………………… 350
LeetCode……………………………………………………………………………………………………………………………. 351
HackerRank……………………………………………………………………………………………………………………….. 351
Задачи по программированию……………………………………………………………………………………….. 351
Глава 10. Динамическое программирование………………………………………… 352
10.1. Кэширование и вычисления…………………………………………………………………………………………… 353
10.1.1. Генерирование чисел Фибоначчи методом рекурсии…………………………………….. 353
10.1.2. Генерирование чисел Фибоначчи посредством кэширования……………………….. 354
10.1.3. Генерирование чисел Фибоначчи посредством динамического программирования 356
10.1.4. Биномиальные коэффициенты…………………………………………………………………………… 358
10.2. Поиск приблизительно совпадающих строк………………………………………………………………… 360
10.2.1. Применение рекурсии для вычисления расстояния редактирования…………….. 361
10.2.2. Применение динамического программирования для вычисления
расстояния редактирования………………………………………………………………………………………….. 362
10.2.3. Восстановление пути…………………………………………………………………………………………. 364
10.2.4. Разновидности расстояния редактирования……………………………………………………. 366
10.3. Самая длинная возрастающая подпоследовательность…………………………………………….. 370
10.4. История из жизни. Сжатие текста для штрихкодов……………………………………………………… 372
10.5. Неупорядоченное разбиение или сумма подмножества…………………………………………….. 376
10.6. История из жизни: Баланс мощностей………………………………………………………………………….. 378
10.7. Задача упорядоченного разбиения………………………………………………………………………………. 381
10.8. Синтаксический разбор………………………………………………………………………………………………….. 384
Остановка для размышлений: Экономичный синтаксический разбор……………………… 386
10.9. Ограничения динамического программирования: задача коммивояжера………………… 387
10.9.1. Вопрос правильности алгоритмов динамического программирования………… 388
10.9.2. Эффективность алгоритмов динамического программирования……………………. 389
10.10. История из жизни. Динамическое программирование и язык Prolog………………………… 390
Замечания к главе……………………………………………………………………………………………………………………. 393
10.11. Упражнения…………………………………………………………………………………………………………………… 394
Простые рекуррентные соотношения…………………………………………………………………………. 394
Расстояние редактирования………………………………………………………………………………………… 394
«Жадные» алгоритмы…………………………………………………………………………………………………… 396
Числовые задачи…………………………………………………………………………………………………………… 397
Задачи на графы…………………………………………………………………………………………………………… 399
Задачи по разработке………………………………………………………………………………………………….. 399
Задачи, предлагаемые на собеседовании………………………………………………………………….. 402
LeetCode………………………………………………………………………………………………………………………… 402
HackerRank…………………………………………………………………………………………………………………… 402
Задачи по программированию……………………………………………………………………………………. 402
Глава 11. NP-полнота…………………………………………………………………………… 403
11.1. Сведение задач……………………………………………………………………………………………………………….. 403
11.1.1. Ключевая идея…………………………………………………………………………………………………….. 404
11.1.2. Задачи разрешимости………………………………………………………………………………………… 405
11.2. Сведение для создания новых алгоритмов…………………………………………………………………… 406
11.2.1. Поиск ближайшей пары……………………………………………………………………………………… 406
11.2.2. Максимальная возрастающая подпоследовательность…………………………………. 407
11.2.3. Наименьшее общее кратное………………………………………………………………………………. 408
11.2.4. Выпуклая оболочка (*)………………………………………………………………………………………. 409
11.3. Простые примеры сведения сложных задач………………………………………………………………… 410
11.3.1. Гамильтонов цикл……………………………………………………………………………………………….. 410
11.3.2. Независимое множество и вершинное покрытие……………………………………………… 412
Остановка для размышлений: Сложность общей задачи календарного планирования 413
11.3.3. Задача о клике…………………………………………………………………………………………………….. 415
11.4. Задача выполнимости булевых формул………………………………………………………………………. 416
11.4.1. Задача выполнимости в 3-конъюнктивной нормальной форме
(задача 3-SAT)…………………………………………………………………………………………………………………. 417
11.5. Нестандартные сведения задачи SAT…………………………………………………………………………… 419
11.5.1. Вершинное покрытие………………………………………………………………………………………….. 419
11.5.2. Целочисленное программирование…………………………………………………………………… 421
11.6. Искусство доказательства сложности………………………………………………………………………….. 423
11.7. История из жизни. Наперегонки со временем………………………………………………………………. 425
11.8. История из жизни. Полный провал………………………………………………………………………………… 427
11.9. Сравнение классов сложности P и NP…………………………………………………………………………… 430
11.9.1. Верификация решения и поиск решения…………………………………………………………… 430
11.9.2. Классы сложности P и NP………………………………………………………………………………….. 431
11.9.3. Почему задача выполнимости является сложной?…………………………………………. 432
11.9.4. NP-сложность по сравнению с NP-полнотой……………………………………………………. 432
Замечания к главе……………………………………………………………………………………………………………………. 433
11.10. Упражнения…………………………………………………………………………………………………………………… 434
Преобразования и выполнимость……………………………………………………………………………….. 434
Базовые сведения………………………………………………………………………………………………………….. 435
Нестандартные сведения…………………………………………………………………………………………….. 437
Алгоритмы для решения частных случаев задач……………………………………………………… 438
P или NP?……………………………………………………………………………………………………………………….. 439
LeetCode………………………………………………………………………………………………………………………… 439
HackerRank…………………………………………………………………………………………………………………… 439
Задачи по программированию……………………………………………………………………………………. 439
Глава 12. Решение сложных задач……………………………………………………….. 440
12.1. Аппроксимирующие алгоритмы……………………………………………………………………………………. 440
12.2. Аппроксимация вершинного покрытия…………………………………………………………………………. 441
Остановка для размышлений: Вершинное покрытие в остатке…………………………………. 443
12.2.1. Рандомизированный эвристический алгоритм вершинного покрытия…………. 444
12.3. Задача коммивояжера в евклидовом пространстве…………………………………………………….. 445
12.3.1. Эвристический алгоритм Кристофидеса………………………………………………………….. 446
12.4. Когда среднее достаточно хорошее……………………………………………………………………………… 448
12.4.1. Задача максимальной k-SAT……………………………………………………………………………… 448
12.4.2. Максимальный бесконтурный подграф……………………………………………………………. 449
12.5. Задача о покрытии множества………………………………………………………………………………………. 449
12.6. Эвристические методы поиска………………………………………………………………………………………. 451
12.6.1. Произвольная выборка……………………………………………………………………………………….. 452
Остановка для размышлений: Выбор пары…………………………………………………………………. 454
12.6.2. Локальный поиск………………………………………………………………………………………………… 455
12.6.3. Имитация отжига………………………………………………………………………………………………… 459
Реализация…………………………………………………………………………………………………………… 462
12.6.4. Применение метода имитации отжига………………………………………………………………. 463
Задача максимального разреза…………………………………………………………………………. 463
Независимое множество…………………………………………………………………………………….. 463
Размещение компонентов на печатной плате………………………………………………….. 464
12.7. История из жизни. Только это не радио………………………………………………………………………… 465
12.8. История из жизни. Отжиг массивов……………………………………………………………………………….. 468
12.9. Генетические алгоритмы и другие эвристические методы поиска…………………………….. 471
12.9.1. Генетические алгоритмы……………………………………………………………………………………. 471
12.10. Квантовые вычисления………………………………………………………………………………………………… 472
12.10.1. Свойства «квантовых» компьютеров………………………………………………………………. 473
12.10.2. Алгоритм Гровера для поиска в базе данных………………………………………………… 475
Решение задачи о выполнимости…………………………………………………………………….. 475
12.10.3. Более быстрое «преобразование Фурье»……………………………………………………….. 476
12.10.4. Алгоритм Шора для разложения целых чисел на множители……………………… 477
12.10.5. Перспективы квантовых вычислений……………………………………………………………… 479
Замечания к главе……………………………………………………………………………………………………………………. 481
12.11. Упражнения…………………………………………………………………………………………………………………… 482
Частные случаи сложных задач…………………………………………………………………………………. 482
Аппроксимирующие алгоритмы…………………………………………………………………………………. 482
Комбинаторная оптимизация……………………………………………………………………………………… 483
«Квантовые» вычисления…………………………………………………………………………………………….. 484
LeetCode………………………………………………………………………………………………………………………… 484
HackerRank…………………………………………………………………………………………………………………… 484
Задачи по программированию……………………………………………………………………………………. 484
Глава 13. Как разрабатывать алгоритмы?……………………………………………. 485
13.1. Список вопросов для разработчика алгоритмов…………………………………………………………. 486
13.2. Подготовка к собеседованию в технологических компаниях…………………………………….. 489
Часть II. Каталог алгоритмических задач…………………………. 493
Глава 14. Описание каталога……………………………………………………………….. 495
14.1. Предостережения……………………………………………………………………………………………………………. 496
Глава 15. Структуры данных……………………………………………………………….. 497
15.1. Словари……………………………………………………………………………………………………………………………. 497
15.2. Очереди с приоритетами………………………………………………………………………………………………… 503
15.3. Суффиксные деревья и массивы…………………………………………………………………………………….. 507
15.4. Графы………………………………………………………………………………………………………………………………. 511
15.5. Множества………………………………………………………………………………………………………………………. 515
15.6. Kd-деревья……………………………………………………………………………………………………………………….. 519
Глава 16. Численные задачи………………………………………………………………… 525
16.1. Решение системы линейных уравнений………………………………………………………………………… 526
16.2. Уменьшение ширины ленты матрицы…………………………………………………………………………… 530
16.3. Умножение матриц…………………………………………………………………………………………………………. 532
16.4. Определители и перманенты…………………………………………………………………………………………. 535
16.5. Условная и безусловная оптимизация………………………………………………………………………….. 538
16.6. Линейное программирование………………………………………………………………………………………… 542
16.7. Генерирование случайных чисел………………………………………………………………………………….. 547
16.8. Разложение на множители и проверка чисел на простоту…………………………………………. 552
16.9. Арифметика произвольной точности……………………………………………………………………………. 555
16.10. Задача о рюкзаке………………………………………………………………………………………………………….. 560
16.11. Дискретное преобразование Фурье…………………………………………………………………………….. 565
Глава 17. Комбинаторные задачи…………………………………………………………. 569
17.1. Сортировка……………………………………………………………………………………………………………………… 570
17.2. Поиск………………………………………………………………………………………………………………………………… 575
17.3. Поиск медианы и выбор элементов……………………………………………………………………………….. 579
17.4. Генерирование перестановок………………………………………………………………………………………… 582
17.5. Генерирование подмножеств…………………………………………………………………………………………. 587
17.6. Генерирование разбиений……………………………………………………………………………………………… 590
17.7. Генерирование графов……………………………………………………………………………………………………. 595
17.8. Календарные вычисления……………………………………………………………………………………………… 599
17.9. Календарное планирование………………………………………………………………………………………….. 601
17.10. Выполнимость………………………………………………………………………………………………………………. 605
Глава 18. Задачи на графах c полиномиальным временем исполнения… 609
18.1. Компоненты связности…………………………………………………………………………………………………… 610
18.2. Топологическая сортировка………………………………………………………………………………………….. 613
18.3. Минимальные остовные деревья…………………………………………………………………………………… 617
18.4. Поиск кратчайшего пути………………………………………………………………………………………………… 622
18.5. Транзитивное замыкание и транзитивная редукция……………………………………………………. 627
18.6. Паросочетание………………………………………………………………………………………………………………… 630
18.7. Задача поиска эйлерова цикла и задача китайского почтальона…………………………….. 634
18.8. Реберная и вершинная связность…………………………………………………………………………………… 637
18.9. Потоки в сети…………………………………………………………………………………………………………………… 641
18.10. Рисование графов………………………………………………………………………………………………………….. 644
18.11. Рисование деревьев………………………………………………………………………………………………………. 649
18.12. Планарность………………………………………………………………………………………………………………….. 652
Глава 19. NP-сложные задачи на графах………………………………………………. 655
19.1. Задача о клике………………………………………………………………………………………………………………… 655
19.2. Независимое множество…………………………………………………………………………………………………. 658
19.3. Вершинное покрытие……………………………………………………………………………………………………… 661
19.4. Задача коммивояжера……………………………………………………………………………………………………. 664
19.5. Гамильтонов цикл…………………………………………………………………………………………………………… 668
19.6. Разбиение графов……………………………………………………………………………………………………………. 672
19.7. Вершинная раскраска…………………………………………………………………………………………………….. 675
19.8. Реберная раскраска………………………………………………………………………………………………………… 679
19.9. Изоморфизм графов………………………………………………………………………………………………………… 680
19.10. Дерево Штейнера………………………………………………………………………………………………………….. 685
19.11. Разрывающее множество ребер или вершин……………………………………………………………… 689
Глава 20. Вычислительная геометрия…………………………………………………… 693
20.1. Элементарные задачи вычислительной геометрии…………………………………………………….. 693
20.2. Выпуклая оболочка………………………………………………………………………………………………………… 698
20.3. Триангуляция………………………………………………………………………………………………………………….. 702
20.4. Диаграммы Вороного…………………………………………………………………………………………………….. 706
20.5. Поиск ближайшей точки………………………………………………………………………………………………… 709
20.6. Поиск в области………………………………………………………………………………………………………………. 713
20.7. Местоположение точки………………………………………………………………………………………………….. 716
20.8. Выявление пересечений…………………………………………………………………………………………………. 720
20.9. Разложение по контейнерам………………………………………………………………………………………….. 724
20.10. Преобразование к срединной оси……………………………………………………………………………….. 728
20.11. Разбиение многоугольника на части…………………………………………………………………………… 731
20.12. Упрощение многоугольников………………………………………………………………………………………. 734
20.13. Выявление сходства фигур………………………………………………………………………………………….. 737
20.14. Планирование перемещений……………………………………………………………………………………….. 740
20.15. Конфигурации прямых…………………………………………………………………………………………………. 744
20.16. Сумма Минковского……………………………………………………………………………………………………… 747
Глава 21. Множества и строки……………………………………………………………… 750
21.1. Поиск покрытия множества……………………………………………………………………………………………. 750
21.2. Задача укладки множества……………………………………………………………………………………………. 755
21.3. Сравнение строк……………………………………………………………………………………………………………… 758
21.4. Нечеткое сравнение строк……………………………………………………………………………………………… 761
21.5. Сжатие текста…………………………………………………………………………………………………………………. 766
21.6. Криптография………………………………………………………………………………………………………………….. 770
21.7. Минимизация конечного автомата……………………………………………………………………………….. 776
21.8. Максимальная общая подстрока………………………………………………………………………………….. 779
21.9. Поиск минимальной общей надстроки…………………………………………………………………………. 782
Глава 22. Ресурсы………………………………………………………………………………… 786
22.1. Программные системы……………………………………………………………………………………………………. 786
22.1.1. Библиотека LEDA………………………………………………………………………………………………. 786
22.1.2. Библиотека CGAL………………………………………………………………………………………………. 787
22.1.3. Библиотека Boost……………………………………………………………………………………………….. 787
22.1.4. Библиотека Netlib……………………………………………………………………………………………….. 788
22.1.5. Коллекция алгоритмов ассоциации ACM………………………………………………………… 788
22.1.6. Сайты GitHub и SourceForge………………………………………………………………………………. 788
22.1.7. Система Stanford GraphBase……………………………………………………………………………… 789
22.1.8. Пакет Combinatorica…………………………………………………………………………………………… 789
22.1.9. Программы из книг……………………………………………………………………………………………… 789
Книга «Programming Challenges»……………………………………………………………………….. 790
Книга «Combinatorial Algorithms for Computers and Calculators»…………………… 790
Книга «Computational Geometry in C»………………………………………………………………. 790
Книга «Algorithms in C++»………………………………………………………………………………….. 790
Книга «Discrete Optimization Algorithms in Pascal»…………………………………………… 791
22.2. Источники данных………………………………………………………………………………………………………….. 791
22.3. Библиографические ресурсы…………………………………………………………………………………………. 791
22.4. Профессиональные консалтинговые услуги………………………………………………………………… 792
Глава 23. Список литературы………………………………………………………………. 793
Приложение. Описание электронного архива………………………………………. 838
Предметный указатель…………………………………………………………………………. 839
-
Алгоритмы. Руководство по разработке. 3-е изд.
2000 ₽
1700 ₽