Программирование: теоремы и задачи [Александр Ханиевич Шень] (pdf) читать постранично, страница - 2

(Монпелье, Франция), университет г. Уппсала (Швеция ), агенттическое общество

ситет г. Бордо, фонд «Культурная инициатива», фонды STINT

ство ANR (грант RaCAF, ANR-15-CE40-0016-01), Российский фонд фундаментальных исследований

(гранты 02-01-22001 НЦНИа, 03-01-00475 и дру-

гие ), а также Совет поддержки научных школ при Президенте РФ (грант
НШ-358.2003.1 ) за поддержку. Вместе с тем содержание книги отражает
точку зрения автора, за ошибки которого указанные организации и лица
ответственности не несут

(и наоборот ).

Содержание
1. Переменные, выражения, присваивания

8

1.1. Задачи без массивов . . . . . . . . . . . . . . . . . . . . . . 8
1.2. Массивы . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
1.3. Индуктивные функции (по А. Г. Кушниренко) . . . . . . . 38

2. Порождение комбинаторных объектов

2.1.
2.2.
2.3.
2.4.
2.5.
2.6.
2.7.

Размещения с повторениями . . .
Перестановки . . . . . . . . . . . .
Подмножества . . . . . . . . . . .
Разбиения . . . . . . . . . . . . . .
Коды Грея и аналогичные задачи
Несколько замечаний . . . . . . .
Подсчёт количеств . . . . . . . . .

.
.
.
.
.
.
.

.
.
.
.
.
.
.

.
.
.
.
.
.
.

.
.
.
.
.
.
.

.
.
.
.
.
.
.

.
.
.
.
.
.
.

.
.
.
.
.
.
.

.
.
.
.
.
.
.

.
.
.
.
.
.
.

.
.
.
.
.
.
.

.
.
.
.
.
.
.

.
.
.
.
.
.
.

.
.
.
.
.
.
.

.
.
.
.
.
.
.

43

43
44
45
48
49
55
57

3. Обход дерева. Перебор с возвратами

60

4. Сортировка

72

3.1. Ферзи, не бьющие друг друга: обход дерева позиций . . . 60
3.2. Обход дерева в других задачах . . . . . . . . . . . . . . . 70

4.1.
4.2.
4.3.
4.4.
4.5.

Квадратичные алгоритмы . . . . . . . . . . . . . . .
Алгоритмы порядка 𝑛 log 𝑛 . . . . . . . . . . . . . . .
Применения сортировки . . . . . . . . . . . . . . . . .
Нижние оценки для числа сравнений при сортировке
Родственные сортировке задачи . . . . . . . . . . . .

5. Конечные автоматы и обработка текстов

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

72
73
80
82
84
90

5.1. Составные символы, комментарии и т. п. . . . . . . . . . . 90
5.2. Ввод чисел . . . . . . . . . . . . . . . . . . . . . . . . . . . . 92

6

Содержание

6. Типы данных

6.1.
6.2.
6.3.
6.4.

Стеки . . . . .
Очереди . . . .
Множества . .
Разные задачи

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

7. Рекурсия

7.1.
7.2.
7.3.
7.4.

Примеры рекурсивных программ . . . . . . . .
Рекурсивная обработка деревьев . . . . . . . . .
Порождение комбинаторных объектов, перебор
Другие применения рекурсии . . . . . . . . . . .

.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.

96

. 96
. 103
. 111
. 115
117

. 117
. 120
. 123
. 127

8. Как обойтись без рекурсии

135

9. Разные алгоритмы на графах

146

8.1. Таблица значений (динамическое программирование) . . 135
8.2. Стек отложенных заданий . . . . . . . . . . . . . . . . . . 140
8.3. Более сложные случаи рекурсии . . . . . . . . . . . . . . . 143
9.1. Кратчайшие пути . . . . . . . . . . . . . . . . . . . . . . . 146
9.2. Связные компоненты, поиск в глубину и ширину . . . . . 152
9.3. Сети, потоки и разрезы . . . . . . . . . . . . . . . . . . . . 157

10. Сопоставление с образцом

10.1.
10.2.
10.3.
10.4.
10.5.
10.6.
10.7.
10.8.

Простейший пример . . . . . . . . . . . . . .
Повторения в образце | источник проблем
Вспомогательные утверждения . . . . . . . .
Алгоритм Кнута { Морриса { Пратта . . . .
Алгоритм Бойера { Мура . . . . . . . . . . .
Алгоритм Рабина . . . . . . . . . . . . . . . .
Более сложные образцы и автоматы . . . . .
Суффиксные деревья . . . . . . . . . . . . . .

11. Анализ игр

11.1.
11.2.
11.3.
11.4.
11.5.

Примеры игр . . . . . . . . . . .
Цена игры . . . . . . . . . . . . .
Вычисление цены: полный обход
Альфа-бета-процедура . . . . . .
Ретроспективный анализ . . . .

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

178

.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.

.
.
.
.
.
.
.
.

. 178
. 181
. 183
. 183
. 186
. 188
. 190
. 197

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

. 210
. 212
. 220
. 223
. 227

210

7

Содержание
12. Оптимальное кодирование

12.1.
12.2.
12.3.
12.4.

Коды . . . . . . . . . . . . . . . . . .
Неравенство Крафта { Макмиллана
Код Хаффмана . . . . . . . . . . . .
Код Шеннона { Фано . . . . . . . . .

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

230

. 230
. 231
. 235
.