Программирование: теоремы и задачи

Практический задачник по применению алгоритмов.

А. Шень «Программирование: теоремы и задачи» МЦНМО, 2017 год, 320 стр. 6-е издание, дополненное, (1,25 мб. pdf)

В книге представлены задачи по программированию различной сложности, как простые так и трудные. К большинству задач даются решения, некоторые по силам и начинающим, другие же требуют определенного уровня подготовки. Большинство задач имеют целью обучение технологии и методам построения корректных и быстрых алгоритмов.

В качестве языка для записи программ был выбран паскаль, но в целом для изучения алгоритмов это не имеет значения, реализация может быть любой. Книга ориентирована на учителей информатики, старшеклассников, студентов младших курсов высших учебных заведений.

Пособие может быть использовано на кружковых и факультативных занятиях в общеобразовательных учреждениях, в школах с углублённым изучением математики и информатики, а также в иных целях, не противоречащих законодательству РФ. Предыдущее издание книги вышло в 2014 г. ISBN: 978-5-4439-0685-0

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

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. Алгоритмы порядка n log 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. Кратчайшие пути htbook.ru146
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

Скачать техническую литературу бесплатно1,25 мб. pdf

Похожая литература