Алгоритмы. Построение и анализ

Учебник.

Т. Кормен, Ч. Лейзерсон, Р. Ривест, К. Штайн "Алгоритмы. Построение и анализ" Вильямс, 2013 год, 1324 стр. Издание 3-е, (18,0 мб. djvu) ( 99,1 мб. pdf)

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

Каждая глава описывает один из алгоритмов с методом его разработки и порядком его использования. Если у вас есть хоть минимальный опыт программирования, то описания работы алгоритма (он представлен с помощью псевдокода, без использования какого либо конкретного языка программирования) не вызовет у вас затруднений, тем более, что все проиллюстрировано рисунками (в книге их 244).

Книгой можно пользоваться, как учебником по теории алгоритмов - студентам и аспирантам, изучающим алгоритмы, построение и анализ, а так же структуры данных. Третье издание книги претерпела некоторые изменения в сравнении со вторым: добавлены новые главы ( деревья ван Эмде Боаса и многопоточные алгоритмы) и разделы, пересмотрен псевдокод. Убрали из книги две главы и один раздел (полный список изменений смотрите ниже - цитата авторов).

Теперь к задачам (а в книге 957 упражнений и 158 задач) вы можете найти решение на сайте http: / /mitpress .mit.edu/algorithms/. Книга большая по объему и не вкладывается в стандартный курс изучения алгоритмов, каждая из глав может служить отдельной темой при изучении всего курса.

Большая часть представленных в учебнике, алгоритмов имеют практическое значение и поэтому рассмотрены вопросы их реализации - преобразования псевдокода в один из популярных языков программирования. Адресовано издание студентам и аспирантам, а также специалистам технического профиля по роду деятельности занятых разработкой алгоритмов, математикам.
ISBN: 978-5-8459-1794-2

Список внесенных изменений в третьей редакции книги.

Изменения в третьей редакции книги

Оглавление книги.

1 Роль алгоритмов в вычислениях 26
1.1 Что такое алгоритмы 26
1.2 Алгоритмы как технология 32

2 Приступаем к изучению 38
2.1 Сортировка вставкой 38
2.2 Анализ алгоритмов 45
2.3 Разработка алгоритмов 52

3 Рост функций 67
3.1 Асимптотические обозначения 68
3.2 Стандартные обозначения и часто встречающиеся функции 78

4 Разделяй и властвуй 90
4.1 Задача поиска максимального подмассива 93
4.2 Алгоритм Штрассена для умножения матриц 100
4.3 Метод подстановки решения рекуррентных соотношений 108
4.4 Метод деревьев рекурсии 113
4.5 Основной метод 119
4.6 Доказательство основной теоремы 123

5 Вероятностный анализ и рандомизированные алгоритмы 140
5.1 Задача о найме 140
5.2 Индикаторная случайная величина 144
5.3 Рандомизированные алгоритмы 148
5.4 Вероятностный анализ и дальнейшее применение индикаторных случайных величин 156

II Сортировка и порядковая статистика 173
Введение 174

6 Пирамидальная сортировка 179
6.1 Пирамиды 179
6.2 Поддержка свойства пирамиды 182
6.3 Построение пирамиды 185
6.4 Алгоритм пирамидальной сортировки 188
6.5 Очереди с приоритетами 190

7 Быстрая сортировка 198
7.1 Описание быстрой сортировки 198
7.2 Производительность быстрой сортировки 202
7.3 Рандомизированная быстрая сортировка 207
7.4 Анализ быстрой сортировки 208

8 Сортировка за линейное время 220
8.1 Нижние границы для алгоритмов сортировки 220
8.2 Сортировка подсчетом 223
8.3 Поразрядная сортировка 226
8.4 Карманная сортировка 230

9 Медианы и порядковые статистики 243
9.1 Минимум и максимум 244
9.2 Выбор в течение линейного ожидаемого времени 245
9.3 Алгоритм выбора с линейным временем работы в наихудшем случае 250

III Структуры данных 259
Введение 260

10 Элементарные структуры данных 264
10.1 Стеки и очереди 264
10.2 Связанные списки 268
10.3 Реализация указателей и объектов 273
10.4 Представление корневых деревьев 277

11. Хеширование и хеш-таблицы 285
11.1 Таблицы с прямой адресацией 286
11.2 Хеш-таблицы 288
11.3 Хеш-функции 294
11.4 Открытая адресация 302
11.5 Идеальное хеширование 310

12 Бинарные деревья поиска 319
12.1 Что такое бинарное дерево поиска 319
12.2 Работа с бинарным деревом поиска 322
12.3 Вставка и удаление 327
12.4 Случайное построение бинарных деревьев поиска 332

13 Красно-черные деревья 341
13.1 Свойства красно-черных деревьев 341
13.2 Повороты 345
13.3 Вставка 348
13.4 Удаление 356

14 Расширение структур данных 372
14.1 Динамические порядковые статистики 372
14.2 Расширение структур данных 378
14.3 Деревья отрезков 381

IV Усовершенствованные методы разработки и анализа 389
Введение 390

15 Динамическое программирование 392
15.1 Разрезание стержня 393
15.2 Перемножение цепочки матриц 403
15.3 Элементы динамического программирования 412
15.4 Наидлиннейшая общая подпоследовательность 424
15.5 Оптимальные бинарные деревья поиска 431

16 Жадные алгоритмы 448
16.1 Задача о выборе процессов 449
16.2 Элементы жадной стратегии 457
16.3 Коды Хаффмана 463
16.4 Матроиды и жадные методы 471
16.5 Планирование заданий как матроид 479

17 Амортизационный анализ 487
17.1 Групповой анализ 488
17.2 Метод бухгалтерского учета 492
17.3 Метод потенциалов 495
17.4 Динамические таблицы 500

V Сложные структуры данных 517
Введение 518

18 В-деревья 521
18.1 Определение В-деревьев 525
18.2 Основные операции с В-деревьями 528
18.3 Удаление ключа из В-дерева 536

19 Фибоначчиевы пирамиды 542
19.1 Структура фибоначчиевых пирамид 544
19.2 Операции над объединяемыми пирамидами 547
19.3 Уменьшение ключа и удаление узла 555
19.4 Оценка максимальной степени 559

20 Деревья ван Эмде Боаса 568
20.1 Предварительные подходы 569
20.2 Рекурсивная структура 573
20.3 Дерево ван Эмде Боаса 582

21 Структуры данных для непересекающихся множеств 597
21.1 Операции над непересекающимися множествами 597
21.2 Представление непересекающихся множеств с помощью связанных списков 600
21.3 Леса непересекающихся множеств 604
21.4 Анализ объединения по рангу со сжатием пути 608

VI Алгоритмы для работы с графами 623
Введение 624

22 Элементарные алгоритмы для работы с графами 626
22.1 Представление графов 626
22.2 Поиск в ширину 630
22.3 Поиск в глубину 639
22.4 Топологическая сортировка 649
22.5 Сильно связные компоненты 652

23 Минимальные остовные деревья 661
23.1 Выращивание минимального остовного дерева 662
23.2 Алгоритмы Крускала и Прима 667

24 Кратчайшие пути из одной вершины 680
24.1 Алгоритм Беллмана-Форда 688
24.2 Кратчайшие пути из одной вершины в ориентированных ациклических графах 693
24.3 Алгоритм Дейкстры 696
24.4 Разностные ограничения и кратчайшие пути 702
24.5 Доказательства свойств кратчайших путей 709

25 Кратчайшие пути между всеми парами вершин 722
25.1 Задача о кратчайших путях и умножение матриц 724
25.2 Алгоритм Флойда-Уоршелла 731
25.3 Алгоритм Джонсона для разреженных графов 738

26 Задача о максимальном потоке 747
26.1 Транспортные сети 748
26.2 Метод Форда-Фалкерсона 753
26.3 Максимальное паросочетание 771
26.4 Алгоритмы проталкивания предпотока 775
26.5 Алгоритм “поднять-в-начало” 788

VII Избранные темы 807
Введение 808

27 Многопоточные алгоритмы 811
27.1 Основы динамической многопоточности 813
27.2 Многопоточное умножение матриц 832

21.3 Многопоточная сортировка слиянием 836

28 Работа с матрицами 852
28.1 Решение систем линейных уравнений 852
28.2 Обращение матриц 866
28.3 Симметричные положительно определенные матрицы и метод наименьших квадратов 872

29 Линейное программирование 883
29.1 Стандартная и каноническая формы задачи линейного программирования 891
29.2 Формулировка задач в виде задач линейного программирования 899
29.3 Симплекс-алгоритм 905
29.4 Двойственность 921
29.5 Начальное базисное допустимое решение 927

30 Полиномы и быстрое преобразование Фурье 940
30.1 Представление полиномов 942
30.2 ДПФ и БПФ 949
30.3 Эффективные реализации БПФ 957

31 Теоретико-числовые алгоритмы 968
31.1 Элементарные понятия теории чисел 970
31.2 Наибольший общий делитель 976
31.3 Модульная арифметика 982
31.4 Решение модульных линейных уравнений 990
31.5 Китайская теорема об остатках 994
31.6 Степени элемента 997
31.7 Криптосистема с открытым ключом RSА 1002
31.8 Проверка простоты 1009
31.9 Целочисленное разложение 1021

32 Поиск подстрок 1031
32.1 Простейший алгоритм поиска подстрок 1034
32.2 Алгоритм Рабина-Карпа 1036
32.3 Поиск подстрок с помощью конечных автоматов 1041
32.4 Алгоритм Кнута-Морриса-Пратта 1048

33 Вычислительная геометрия 1060
33.1 Свойства отрезков 1061
33.2 Определение наличия пересекающихся отрезков 1068
33.3 Поиск выпуклой оболочки 1075
33.4 Поиск пары ближайших точек 1086

34 NP-полнота 1096
34.1 Полиномиальное время 1102
34.2 Проверка за полиномиальное время 1110
34.3 NP-полнота и приводимость 1115
34.4 Доказательства NP-полноты 1127
34.5 NP-полные задачи 1136

35 Приближенные алгоритмы 1157
35.1 Задача о вершинном покрытии 1159
35.2 Задача о коммивояжере 1163
35.3 Задача о покрытии множества 1169
35.4 Рандомизация и линейное программирование 1175
35.5 Задача о сумме подмножества 1180

VIII Приложения: математические основы 1195
Введение 1196

А Суммы и ряды 1198
А.1 Суммы и их свойства 1198
А.2 Оценки сумм 1202

Б. Множества и прочие художества 1210
Б.1 Множества 1210
Б.2 Отношения 1215
Б.З Функции 1218
Б.4 Графы 1221
Б.5 Деревья 1226

В Комбинаторика и теория вероятности 1235
В.1 Основы комбинаторики 1235
В.2 Вероятность 1241
В.З Дискретные случайные величины 1248
В.4 Геометрическое и биномиальное распределения 1254
В.5 Хвосты биномиального распределения 1260

Г Матрицы 1269
Г.1 Матрицы и матричные операции 1269
Г.2 Основные свойства матриц 1274
Техническая литература 1282
Предметный указатель 1299

Скачать книгу бесплатно99,1 мб. pdf Скачать книгу бесплатно18,0 мб. djvu