О г л а в л е н и е

 

Предисловие

13

1.  Введение

18

1.1.  Алгоритмы

18

1.2.  Анализ алгоритмов

22

1.3.  Построение алгоритмов

26

1.4. О пользе быстрых алгоритмов

29

I  Математические основы анализа алгоритмов

 

Введение

35

2.  Скорость роста функций

36

2.1.  Aсимптотические обозначения

36

2.2.   Стандартные функции и обозначения

41

3.  Суммирование

49

3.1.  Суммы и их свойства

49

3.2.  Оценки сумм

52

4.  Рекуррентные соотношения

59

4.1.  Метод подстановки

60

4.2.  Метод итераций

63

4.3.  Общий рецепт

66

4.4  Доказательство теоремы 4.1

68

5.  Множества

78

5.1.  Множества

78

5.2.  Отношения

83

5.3.  Функции

85

5.4.  Графы

88

5.5.  Деревья

92

6.  Комбинаторика и вероятность

101

6.1.  Подсчёт количеств

101

6.2.  Вероятность

106

6.3.  Дискретные случайные величины

112

6.4.  Геометрическое и биномиальное распределения

116

* 6.5  Хвосты биномиального распределения

121

6.6. Вероятностный анализ

125

II  Сортировка и порядковые статистики

 

Введение

135

7.  Сортировка с помощью кучи

138

7.1.  Кучи

138

7.2.  Сохранение основного свойства кучи

140

7.3.  Построение кучи

142

7.4.  Алгоритм сортировки с помощью кучи

145

7.5.  Очереди с приоритетами

147

8.  Быстрая сортировка

151

8.1.  Описание быстрой сортировки

151

8.2.  Работа быстрой сортировки

154

8.3.  Вероятностные алгоритмы быстрой сортировки

157

8.4.  Анализ быстрой сортировки

159

9.  Сортировка за линейное время

168

9.1.  Нижние оценки для сортировки

168

9.2.  Сортировка подсчётом

171

9.3.  Цифровая сортировка

173

9.4.  Сортировка вычерпыванием

175

10.  Медианы и порядковые статистики

180

10.1.  Минимум и максимум

181

10.2.  Выбор за линейное в среднем время

182

10.3.  Выбор за линейное в худшем случае время

184

III  Структуры данных

 

Введение

191

11.  Элементарные структуры данных

194

11.1.  Стеки и очереди

194

11.2.  Связанные списки

198

11.3.  Реализация указателей и записей с несколькими полями

202

11.4.  Представление корневых деревьев

207

12.  Хеш-таблицы

213

12.1.  Прямая адресация

213

12.2.  Хеш-таблицы

215

12.3.  Хеш-функции

220

12.4.  Открытая адресация

226

13.  Двоичные деревья поиска

236

13.1.  Что такое двоичное дерево поиска?

236

13.2.  Поиск в двоичном дереве

238

13.3.  Добавление и удаление элемента

242

* 13.4.  Случайные двоичные деревья поиска

246

14.  Красно-чёрные деревья

254

14.1.  Свойства красно-чёрных деревьев

254

14.2.  Вращения

256

14.3.  Добавление вершины

258

14.4.  Удаление

262

15.  Пополнение структур данных

271

15.1.  Динамические порядковые статистики

271

15.2.  Общая схема работы с дополнительной информацией

276

15.3.  Деревья промежутков

278

IV  Методы построения и анализа алгоритмов

 

Введение

287

16.  Динамическое программирование

288

16.1.  Перемножение нескольких матриц

289

16.2.  Когда применимо динамическое программирование

296

16.3.  Наибольшая общая подпоследовательность

300

16.4.  Оптимальная триангуляция многоугольника

305

17  Жадные алгоритмы

313

17.1.  Задача о выборе заявок

313

17.2.  Когда применим жадный алгоритм?

317

17.3.  Коды Хаффмена

320

* 17.4.  Теоретические основы жадных алгоритмов

327

* 17.5. Задача о расписании

332

18  Амортизационный анализ

337

18.1.  Метод группировки

338

18.2.  Метод предоплаты

341

18.3.  Метод потенциалов

343

18.4.  Динамические таблицы

346

V  Более сложные структуры данных

 

Введение

357

19  Б-деревья

359

19.1.  Определение Б-дерева

361

19.2.  Основные операции с Б-деревьями

364

19.3.  Удаление элемента из Б-дерева

371

20  Биномиальные кучи

376

20.1.  Биномиальные деревья и биномиальные кучи

377

20.2.  Операции с биномиальными кучами

381

21  Фибоначчиевы кучи

395

21.1.  Строение фибоначчиевой кучи

396

21.2.  Операции, предусмотренные для сливаемых куч

398

21.3.  Уменьшение ключа и удаление вершины

406

21.4.  Оценка максимальной степени

409

22  Системы непересекающихся множеств

414

22.1.  Операции с непересекающимися множествами

414

22.2.  Реализация с помощью списков

417

22.3.  Лес непересекающихся множеств

420

* 22.4.  Объединение по pангам со сжатием путей: анализ

424

VI  Алгоритмы на графах

 

Введение

435

23  Основные алгоритмы на графах

436

23.1.  Представление графов

436

23.2.  Поиск в ширину

439

23.3.  Поиск в глубину

446

23.4.  Топологическая сортировка

453

23.5.  Сильно связные компоненты

456

24  Минимальные покрывающие деревья

465

24.1.  Построение минимального покрывающего дерева

466

24.2.  Алгоритмы Крускала и Прима

470

25  Кратчайшие пути из одной вершины

479

25.1.  Кратчайшие пути и релаксация

483

25.2.  Алгоритм Дейкстры

489

25.3.  Алгоритм Беллмана - Форда

494

25.4.  Кратчайшие пути в ациклическом ориентированном графе

497

25.5.  Ограничения на разности и кратчайшие пути

499

26  Кратчайшие пути для всех пар вершин

509

26.1.  Кратчайшие пути и умножение матриц

511

26.2.  Алгоритм Флойда - Уоршолла

517

26.3.  Алгоритм Джонсона для разреженных графов

523

* 26.4.  Замкнутые полукольца: общая схема для задач о путях

527

27  Максимальный поток

535

27.1.  Потоки в сетях

536

27.2.  Метод Форда-Фалкерсона

542

27.3.  Максимальное паросочетание в двудольном графе

552

* 27.4.  Алгоритм «проталкивания предпотока»

556

* 27.5.  Алгоритм «поднять-и-в-начало»

564

VII  Дополнительные главы

 

Введение

581

28  Сортирующие сети

584

28.1.  Сети компараторов

584

28.2.  Правило нуля и единицы

588

28.3.  Битонический сортировщик

590

28.4.  Сливающая сеть

594

28.5.  Сортирующая сеть

597

29  Арифметические схемы

602

29.1.  Схемы из функциональных элементов

602

29.2.  Схемы для сложения

607

29.3.  Схемы для умножения

616

29.4.  Тактированные схемы

623

30  Алгоритмы параллельных вычислений

632

30.1.  Переходы по указателям

635

30.2.  CRCW- и EREW-алгоритмы

643

30.3.  Теорема Брента и эффективность по затратам

651

* 30.4. Эффективная параллельная обработка префиксов

655

30.5.  Нарушение симметрии (детерминированный алгоритм)

660

31  Матрицы и действия с ними

670

31.1.  Матрицы и их свойства

670

31.2.  Алгоритм Штрассена умножения матриц

679

* 31.3  Алгебраические системы и умножение булевых матриц

684

31.4.  Решение систем линейных уравнений

688

31.5.  Обращение матриц

700

31.6.  Положительно определённые симметрические матрицы

704

32  Многочлены и быстрое преобразование Фурье

714

32.1.  Представление многочленов

716

32.2.  Дискретное преобразование Фурье. Быстрый алгоритм

721

32.3.  Эффективные реализации быстрого преобразования Фурье

728

33  Теоретико-числовые алгоритмы

736

33.1.  Начальные сведения из теории чисел

737

33.2.  Наибольший общий делитель

742

33.3.  Модулярная арифметика

746

33.4.  Решение линейных диофантовых уравнений

750

33.5.  Китайская теорема об остатках

753

33.6.  Степени элемента

756

33.7.  Криптосистема RSА с открытым ключом

759

* 33.8.  Проверка чисел на простоту

765

* 33.9.  Разложение чисел на множители

772

34  Поиск подстрок

780

34.1.  Простейший алгоритм

782

34.2.  Алгоритм Рабина-Карпа

784

34.3.  Поиск подстрок с помощью конечных автоматов

788

34.4.  Алгоритм Кнута - Морриса - Пратта

794

34.5.  Алгоритм Бойера-Мура

801

35  Вычислительная геометрия

810

35.1.  Свойства отрезков

810

35.2.  Есть ли пересекающиеся отрезки?.

816

35.3.  Построение выпуклой оболочки

822

35.4.  Отыскание пары ближайших точек

830

36   NР -полнота

837

36.1.  Полиномиальное время

838

36.2.  Проверка принадлежности языку и класс NР

845

36.3.  NР-полнота и сводимость

849

36.4.  Доказательства NР-полноты

857

36.5.  NР-полные задачи

864

37  Приближенные алгоритмы

880

37.1.  Задача о вершинном покрытии

882

37.2.  Задача коммивояжёра

884

37.3.  Задача о покрытии множествами

889

37.4.  Задача о суммах подмножеств

893

Литература

901

Предметный указатель

915

Именной указатель

951