Алгоритмы
Покупка
Тематика:
Программирование и алгоритмизация
Издательство:
ДМК Пресс
Автор:
Эриксон Джефф
Год издания: 2023
Кол-во страниц: 528
Дополнительно
Вид издания:
Монография
Уровень образования:
Профессиональное образование
ISBN: 978-5-97060-981-1
Артикул: 832696.01.99
В этом руководстве содержатся основные сведения об алгоритмах: анализируются различные типы алгоритмов, рассматриваются мето- ды их построения (рекурсия, динамическое программирование и др.), приводятся практические примеры. В конце каждой главы приводятся упражнения, направленные на закрепление пройденного. Для изучения материала требуется знание основ дискретной мате- матики и методов доказательств, а также представление об основных вычислительных задачах и алгоритмах. Желателен практический опыт работы с языком программирования, поддерживающим косвенную адресацию и рекурсию. Издание адресовано студентам и преподавателям технических вузов, а также тем, кто хочет изучить основы алгоритмизации.
Тематика:
ББК:
УДК:
ОКСО:
- ВО - Бакалавриат
- 01.03.02: Прикладная математика и информатика
- 09.03.01: Информатика и вычислительная техника
- ВО - Магистратура
- 01.04.02: Прикладная математика и информатика
ГРНТИ:
Скопировать запись
Фрагмент текстового слоя документа размещен для индексирующих роботов
Джефф Эриксон Алгоритмы
Algorithms Jeff Erickson
Москва 2023 Алгоритмы Джефф Эриксон
УДК 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 (англ.) © Copyright Jeff Erickson, 2019
ISBN 978-5-97060-981-1 (рус.) © Оформление, перевод на русский язык,
издание, ДМК Пресс, 2023
Ким, Кей и Ханне с любовью и восхищением. И Ирин с благодарностью за нарушение ее обещания.
Оглавление Предисловие от издательства.............................................................................................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 ♥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 Оглавление Второе рекуррентное выражение: что дальше?...................................................................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 Упражнения....................................................................................................................................... 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 Оглавление Глава 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