Книжная полка Сохранить
Размер шрифта:
А
А
А
|  Шрифт:
Arial
Times
|  Интервал:
Стандартный
Средний
Большой
|  Цвет сайта:
Ц
Ц
Ц
Ц
Ц

Алгоритмы

Покупка
Артикул: 832696.01.99
Доступ онлайн
1 999 ₽
В корзину
В этом руководстве содержатся основные сведения об алгоритмах: анализируются различные типы алгоритмов, рассматриваются мето- ды их построения (рекурсия, динамическое программирование и др.), приводятся практические примеры. В конце каждой главы приводятся упражнения, направленные на закрепление пройденного. Для изучения материала требуется знание основ дискретной мате- матики и методов доказательств, а также представление об основных вычислительных задачах и алгоритмах. Желателен практический опыт работы с языком программирования, поддерживающим косвенную адресацию и рекурсию. Издание адресовано студентам и преподавателям технических вузов, а также тем, кто хочет изучить основы алгоритмизации.
134
452
Эриксон, Дж. Алгоритмы / Д. Эриксон. - Москва : ДМК Пресс, 2023. - 528 с. - ISBN 978-5-97060-981-1. - Текст : электронный. - URL: https://znanium.ru/catalog/product/2150523 (дата обращения: 18.11.2026). – Режим доступа: по подписке.
Фрагмент текстового слоя документа размещен для индексирующих роботов
Джефф Эриксон
Алгоритмы


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


Доступ онлайн
1 999 ₽
В корзину