Шень А. - Программирование: теоремы и задачи (2017)

Несколько замечаний вместо предисловия 3
Содержание 5
1. Переменные, выражения, присваивания 8
1.1. Задачи без массивов 8
1.2. Массивы 23
1.3. Индуктивные функции (по А.Г. Кушниренко) 38
2. Порождение комбинаторных объектов 43
2.1. Размещения с повторениями 43
2.2. Перестановки 44
2.3. Подмножества 45
2.4. Разбиения 48
2.5. Коды Грея и аналогичные задачи 49
2.6. Несколько замечаний 55
2.7. Подсчёт количеств 57
3. Обход дерева. Перебор с возвратами 60
3.1. Ферзи, не бьющие друг друга: обход дерева позиций 60
3.2. Обход дерева в других задачах 70
4. Сортировка 72
4.1. Квадратичные алгоритмы 72
4.2. Алгоритмы порядка nlog n 73
4.3. Применения сортировки 80
4.4. Нижние оценки для числа сравнений при сортировке 82
4.5. Родственные сортировке задачи 84
5. Конечные автоматы и обработка текстов 90
5.1. Составные символы, комментарии и т.п. 90
5.2. Ввод чисел 92
6. Типы данных 96
6.1. Стеки 96
6.2. Очереди 103
6.3. Множества 111
6.4. Разные задачи 115
7. Рекурсия 117
7.1. Примеры рекурсивных программ 117
7.2. Рекурсивная обработка деревьев 120
7.3. Порождение комбинаторных объектов, перебор 123
7.4. Другие применения рекурсии 127
8. Как обойтись без рекурсии 135
8.1. Таблица значений (динамическое программирование) 135
8.2. Стек отложенных заданий 140
8.3. Более сложные случаи рекурсии 143
9. Разные алгоритмы на графах 146
9.1. Кратчайшие пути 146
9.2. Связные компоненты, поиск в глубину и ширину 150
9.3. Сети, потоки и разрезы 156
10. Сопоставление с образцом 176
10.1. Простейший пример 176
10.2. Повторения в образце - источник проблем 179
10.3. Вспомогательные утверждения 181
10.4. Алгоритм Кнута-Морриса-Пратта 181
10.5. Алгоритм Бойера-Мура 184
10.6. Алгоритм Рабина 186
10.7. Более сложные образцы и автоматы 188
10.8. Суффиксные деревья 195
11. Анализ игр 208
11.1. Примеры игр 208
11.2. Цена игры 210
11.3. Вычисление цены: полный обход 218
11.4. Альфа-бета-процедура 221
11.5. Ретроспективный анализ 225
12. Оптимальное кодирование 228
12.1. Коды 228
12.2. Неравенство Крафта-Макмиллана 229
12.3. Код Хаффмана 233
12.4. Код Шеннона-Фано 235
13. Представление множеств. Хеширование 239
13.1. Хеширование с открытой адресацией 239
13.2. Хеширование со списками 242
14. Деревья. Сбалансированные деревья 248
14.1. Представление множеств с помощью деревьев 248
14.2. Сбалансированные деревья 256
15. Контекстно-свободные грамматики 267
15.1. Общий алгоритм разбора 267
15.2. Метод рекурсивного спуска 273
15.3. Алгоритм разбора для LL(1)-грамматик 284
16. Синтаксический разбор слева направо (LR) 292
16.1. LR-процессы 292
16.2. LR(0)-грамматики 298
16.3. SLR(1)-грамматики 304
16.4. LR(1)-грамматики, LALR(1)-грамматики 305
16.5. Общие замечания о разных методах разбора 308
Книги для чтения 310
Предметный указатель 311
Указатель имён 317