Алгоритмы (5000,00 руб.)

Стр.5

Стр.7

Стр.8

Стр.9

Стр.10

Стр.11

Стр.12

УДК 004.021 ББК 32.973.05 Э77 Э77 Джефф Эриксон Алгоритмы / пер. с англ. А. В. Снастина, П. Б. Иванова. – М.: ДМК Пресс, 2023. – 526 с.: ил. ISBN 978-5-97060-981-1 В этом руководстве содержатся основные сведения об алгоритмах: анализируются различные типы алгоритмов, рассматриваются методы их построения (рекурсия, динамическое программирование и др.), приводятся практические примеры. В конце каждой главы приводятся упражнения, направленные на закрепление пройденного. Для изучения материала требуется знание основ дискретной математики и методов доказательств, а также представление об основных вычислительных задачах и алгоритмах. Желателен практический опыт работы с языком программирования, поддерживающим косвенную адресацию и рекурсию. Издание адресовано студентам и преподавателям технических вузов, а также тем, кто хочет изучить основы алгоритмизации. УДК 004.021 ББК 32.973.05 Все права защищены. Любая часть этой книги не может быть воспроизведена в какой бы то ни было форме и какими бы то ни было средствами без письменного разрешения владельцев авторских прав. Материал, изложенный в данной книге, многократно проверен. Но, поскольку вероятность технических ошибок все равно существует, издательство не может гарантировать абсолютную точность и правильность приводимых сведений. В связи с этим издательство не несет ответственности за возможные ошибки, связанные с использованием книги. ISBN 978-1-79264-483-2 (англ.) ISBN 978-5-97060-981-1 (рус.) © Copyright Jeff Erickson, 2019 © Оформление, перевод на русский язык, издание, ДМК Пресс, 2023

Стр.5

Оглавление Предисловие от издательства ............................................................................................12 Предисловие ..........................................................................................................................13 Об этой книге ......................................................................................................................................13 Обязательный минимум .................................................................................................................13 Дополнительные ссылки ................................................................................................................15 Упражнения в этой книге ...............................................................................................................17 Стащите эту книгу ..............................................................................................................................18 Благодарности ....................................................................................................................................19 Предостережение для преподавателя .....................................................................................20 Глава 0. Введение ..................................................................................................................22 0.1. Что такое алгоритм ...................................................................................................................22 0.2. Умножение ...................................................................................................................................24 Умножение методом решетки ........................................................................................................ 24 Удваивание и усреднение ................................................................................................................ 27 Циркуль и линейка .............................................................................................................................. 29 0.3. Распределение мест в Конгрессе США .............................................................................30 0.4. Отрицательный пример ..........................................................................................................32 0.5. Описание алгоритмов .............................................................................................................33 Определение конкретной задачи ................................................................................................. 34 Описание алгоритма .......................................................................................................................... 35 0.6. Анализ алгоритмов ...................................................................................................................37 Корректность ......................................................................................................................................... 37 Время выполнения .............................................................................................................................. 37 Упражнения .........................................................................................................................................40 Глава 1. Рекурсия ...................................................................................................................45 1.1. Сведéние .......................................................................................................................................45 1.2. Упрощение и делегирование ...............................................................................................46 1.3. Ханойские башни ......................................................................................................................48 1.4. Сортировка слиянием..............................................................................................................51 Корректность ......................................................................................................................................... 52 Анализ ...................................................................................................................................................... 53 1.5. Быстрая сортировка .................................................................................................................54 Корректность ......................................................................................................................................... 55 Анализ ...................................................................................................................................................... 55 1.6. Шаблон ..........................................................................................................................................57 1.7. Рекурсивные деревья ..............................................................................................................57 ♥Исключение нижних и верхних границ – это правильный подход, даю честное слово ................................................................................................................... 60

Стр.7

Оглавление  7 ♥1.8. Линейный алгоритм выбора .................................................................................................62 Алгоритм быстрого выбора ............................................................................................................. 62 Правильные опорные элементы ................................................................................................... 63 Анализ ...................................................................................................................................................... 64 Проверка достоверности .................................................................................................................. 66 1.9. Быстрое умножение .................................................................................................................67 1.10. Возведение в степень ...........................................................................................................70 Упражнения .........................................................................................................................................72 Ханойские башни ................................................................................................................................ 72 Рекурсивные деревья ........................................................................................................................ 77 Сортировка ............................................................................................................................................. 78 Выбор ........................................................................................................................................................ 82 Арифметика ............................................................................................................................................ 85 Массивы ................................................................................................................................................... 89 Деревья .................................................................................................................................................... 95 Глава 2. Поиск с возвратом ................................................................................................102 2.1. Задача об n ферзях ............................................................................................................... 103 2.2. Деревья игры ........................................................................................................................... 105 2.3. Задача о сумме подмножеств ........................................................................................... 108 Корректность .......................................................................................................................................109 Анализ ....................................................................................................................................................109 Варианты ...............................................................................................................................................110 2.4. Общий шаблон ........................................................................................................................ 111 2.5. Сегментация текста (Interpunctio Verborum) ............................................................... 113 2.6. Максимальная возрастающая подпоследовательность ......................................... 120 2.7. Максимальная возрастающая подпоследовательность, дубль 2 ........................ 124 2.8. Оптимальные двоичные деревья поиска ..................................................................... 126 Упражнения ...................................................................................................................................... 129 Глава 3. Динамическое программирование ...................................................................134 3.1. Mātrāv.rtta .................................................................................................................................. 134 Алгоритм поиска с возвратом может быть медленным .....................................................136 Мемоизация (запоминание): помнить все ...............................................................................137 Динамическое программирование: осмысленное заполнение .....................................138 И все же не следует запоминать все подряд .........................................................................140 ♥3.2. Небольшое отступление: еще более быстрое определение чисел Фибоначчи ...................................................................................................................... 140 Стоп! Не так быстро ..........................................................................................................................142 3.3. Interpunctio verborum redux (И снова о пунктуации) ............................................. 143 3.4. Шаблон: интеллектуальная рекурсия ............................................................................ 144 3.5. Внимание: жадность – это глупость ................................................................................ 146 3.6. Максимальная возрастающая подпоследовательность ......................................... 147 Первое рекуррентное выражение: кто следующий? ..........................................................147

Стр.8

8  Оглавление Второе рекуррентное выражение: что дальше? ...................................................................149 3.7. Расстояние редактирования............................................................................................... 150 Рекурсивная структура ....................................................................................................................151 Рекуррентное выражение ..............................................................................................................152 Динамическое программирование ............................................................................................153 3.8. Задача о сумме подмножеств ........................................................................................... 155 3.9. Оптимальные двоичные деревья поиска ..................................................................... 157 3.10. Динамическое программирование для деревьев ................................................. 161 Упражнения ...................................................................................................................................... 163 Последовательности/Массивы .....................................................................................................164 Разделение последовательностей/массивов .........................................................................185 Деревья и поддеревья .....................................................................................................................197 Глава 4. Жадные алгоритмы ..............................................................................................205 4.1. Сохранение файлов на магнитной ленте ..................................................................... 205 4.2. Планирование учебных курсов ........................................................................................ 208 4.3. Общий шаблон ........................................................................................................................ 211 4.4. Коды Хаффмана ...................................................................................................................... 212 4.5. Задача о стабильных браках ............................................................................................. 218 Некоторые неудачные идеи ..........................................................................................................219 Алгоритмы Boston Pool и Гэйла–Шепли ...................................................................................221 Время выполнения ............................................................................................................................223 Корректность .......................................................................................................................................223 Оптимальность ....................................................................................................................................224 Упражнения ...................................................................................................................................... 225 Глава 5. Основные графовые алгоритмы ........................................................................238 5.1. Введение и историческая справка.................................................................................. 238 5.2. Основные определения ....................................................................................................... 242 5.3. Представления и примеры ................................................................................................. 244 5.4. Структуры данных .................................................................................................................. 248 Списки смежных вершин ................................................................................................................248 Матрицы смежности .........................................................................................................................249 Сравнение .............................................................................................................................................250 5.5. Поиск в любом направлении ............................................................................................ 252 Анализ ....................................................................................................................................................255 5.6. Важные варианты .................................................................................................................. 255 Стек: поиск в глубину .......................................................................................................................255 Очередь: поиск в ширину ...............................................................................................................255 Очередь с приоритетами: поиск по первому наилучшему совпадению .....................256 Несвязные графы ...............................................................................................................................257 Направленные графы.......................................................................................................................259 5.7. Редукция графа: сплошная заливка ................................................................................ 259

Стр.9

Оглавление  9 Упражнения ...................................................................................................................................... 261 Графы ......................................................................................................................................................261 Алгоритмы обхода .............................................................................................................................263 Сведéния ...............................................................................................................................................267 Глава 6. Поиск в глубину ....................................................................................................281 6.1. Обход в прямом и обратном порядке ........................................................................... 283 Классификация вершин и ребер .................................................................................................284 6.2. Обнаружение циклов ........................................................................................................... 287 6.3. Топологическая сортировка ............................................................................................... 288 Неявная топологическая сортировка ........................................................................................289 6.4. Мемоизация и динамическое программирование .................................................. 291 Динамическое программирование в НАГ ...............................................................................292 6.5. Сильная связность .................................................................................................................. 294 6.6. Сильные компоненты за линейное время ................................................................... 295 Алгоритм Косараджу–Шарира .....................................................................................................296 ♥Алгоритм Тарьяна ...............................................................................................................................298 Упражнения ...................................................................................................................................... 301 Поиск в глубину, топологическая сортировка и сильные компоненты .......................301 Динамическое программирование ............................................................................................308 Глава 7. Минимальные остовные деревья ......................................................................316 7.1. Различные веса ребер .......................................................................................................... 317 7.2. Единственный алгоритм минимального остовного дерева .................................. 318 7.3. Алгоритм Борувки ................................................................................................................... 320 Это тот самый алгоритм МОД, который вам нужен ..............................................................322 7.4. Алгоритм Ярника (Прима) ................................................................................................... 323 ♥Улучшенный алгоритм Ярника......................................................................................................324 7.5. Алгоритм Краскала ................................................................................................................ 326 Упражнения ...................................................................................................................................... 328 Глава 8. Кратчайшие пути ..................................................................................................334 8.1. Деревья кратчайшего пути ................................................................................................. 335 ♥8.2. Отрицательные ребра .......................................................................................................... 336 8.3. Единственный алгоритм SSSP ........................................................................................... 337 8.4. Невзвешенные графы: поиск в ширину ........................................................................ 340 8.5. Направленный ациклический граф: поиск в глубину ............................................. 344 8.6. Поиск по первому наилучшему совпадению: алгоритм Дейкстры .................... 347 Отсутствие отрицательных ребер ...............................................................................................348 ♥Отрицательные ребра ......................................................................................................................352 8.7. Ослабление напряжения всех ребер: алгоритм Беллмана–Форда ................... 354 Улучшение Мура .................................................................................................................................356 Формулировка с использованием динамического программирования .....................358 Упражнения ...................................................................................................................................... 361

Стр.10

10  Оглавление Глава 9. Кратчайшие пути между всеми парами вершин в графе .............................374 9.1. Введение .................................................................................................................................... 374 9.2. Множество отдельных источников ................................................................................. 375 9.3. Изменение весов .................................................................................................................... 376 9.4. Алгоритм Джонсона ............................................................................................................... 377 9.5. Динамическое программирование ................................................................................ 378 9.6. Разделяй и властвуй.............................................................................................................. 380 9.7. Странное умножение матриц ............................................................................................ 382 9.8. Алгоритм (Клини–Роя–)Флойда–Уоршелла(–Ингермана) .................................... 383 Упражнения ...................................................................................................................................... 386 Глава 10. Максимальные потоки и наименьшие разрезы ...........................................393 10.1. Потоки ...................................................................................................................................... 394 10.2. Разрезы .................................................................................................................................... 396 10.3. Теорема о максимальном потоке и наименьшем разрезе (Maxflow-Mincut) .................................................................................................................... 397 10.4. Алгоритм увеличивающего пути Форда и Фалкерсона ....................................... 400 ♥Иррациональные пропускные способности ...........................................................................401 10.5. Объединения и разбиения потоков ............................................................................. 403 10.6. Алгоритмы Эдмондса и Карпа ........................................................................................ 407 Самые насыщенные увеличивающие пути .............................................................................407 Кратчайшие увеличивающие пути .............................................................................................409 10.7. Дальнейшее развитие ........................................................................................................ 411 Упражнения ...................................................................................................................................... 413 Глава 11. Приложения потоков и разрезов ....................................................................422 11.1. Реберно-непересекающиеся пути ................................................................................ 422 11.2. Пропускные способности вершин и вершинно-непересекающиеся пути ......423 11.3. Задача о паросочетании в двудольном графе ........................................................ 424 11.4. Выбор кортежа ..................................................................................................................... 427 Расписание экзаменов ....................................................................................................................428 11.5. Покрытия непересекающихся путей ........................................................................... 431 Набор минимального преподавательского состава ............................................................432 11.6. Алгоритм исключения для бейсбола ........................................................................... 434 11.7. Выбор проекта ...................................................................................................................... 437 Упражнения ...................................................................................................................................... 439 Глава 12. NP-трудность.......................................................................................................452 12.1. Игра, которую невозможно выиграть .......................................................................... 452 12.2. P против NP ............................................................................................................................ 454 12.3. NP-трудная, NP-легкая и NP-полная задача ............................................................. 456 ♥12.4. Формальные определения (HC SVNT DRACONES – Тут [обитают] драконы) ....................................................................................................................................... 458 12.5. Редукции и задача Sat ....................................................................................................... 460

Стр.11

Оглавление  11 12.6. 3Sat (от CircuitSat) ............................................................................................................... 462 12.7. Максимальное независимое множество (от 3Sat) .................................................. 465 12.8. Общий шаблон...................................................................................................................... 467 12.9. Клика и вершинное покрытие (от независимого множества) .......................... 469 12.10. Раскраска графа (от 3Sat) .............................................................................................. 470 12.11. Гамильтонов цикл .............................................................................................................. 473 От вершинного покрытия ...............................................................................................................474 От 3Sat ....................................................................................................................................................476 Варианты и расширения .................................................................................................................478 12.12. Задача о сумме подмножеств (от задачи вершинного покрытия) ................ 479 Да будет осмотрителен выполняющий редукцию! ..............................................................480 12.13. Другие полезные NP-трудные задачи ...................................................................... 481 12.14. Выбор правильной задачи ............................................................................................ 484 12.15. Простой пример из реальной жизни ........................................................................ 485 ♥12.16. Что дальше .......................................................................................................................... 489 Полиномиальное пространство ...................................................................................................489 Экспоненциальное время ..............................................................................................................491 Все выше и выше! ..............................................................................................................................491 Упражнения ...................................................................................................................................... 493 Предметный указатель ......................................................................................................509 Список алгоритмов на псевдокоде ..................................................................................523

Стр.12