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

2-е изд., испр. и доп. - М.: 2004. — 296 с.

Книга содержит задачи по программированию различной трудности. Большинство задач приводятся с решениями. Цель книги — научить основным методам построения корректных и быстрых алгоритмов. Для учителей информатики, старшеклассников, студентов младших курсов высших учебных заведений. Пособие может быть использовано на кружковых и факультативных занятиях в общеобразовательных учреждениях, в школах с углублённым изучением математики и информатики, а также в иных целях, не противоречащих законодательству РФ.

Формат: pdf

Размер: 1,7 Мб

Смотреть, скачать: docs.google.com ;

Содержание
1. Переменные, выражения, присваивания 8
1.1. Задачи без массивов 8
1.2. Массивы 23
1.3. Индуктивные функции (по А. Г. Кушниренко) 37
2. Порождение комбинаторных объектов 42
2.1. Размещения с повторениями 42
2.2. Перестановки 43
2.3. Подмножества 44
2.4. Разбиения 47
2.5. Коды Грея и аналогичные задачи 48
2.6. Несколько замечаний 54
2.7. Подсчёт количеств 56
3. Обход дерева. Перебор с возвратами 59
3.1. Ферзи, не бьющие друг друга: обход дерева позиций ... 59
3.2. Обход дерева в других задачах 69
4. Сортировка 71
4.1. Квадратичные алгоритмы 71
4.2. Алгоритмы порядка nlogn 72
4.3. Применения сортировки 79
4.4. Нижние оценки для числа сравнений при сортировке ... 80
4.5. Родственные сортировке задачи 82
5. Конечные автоматы и обработка текстов 89
5.1. Составные символы, комментарии и т. п 89
5.2. Ввод чисел 91
6. Типы данных 95
6.1. Стеки 95
6.2. Очереди 102
6.3. Множества 110
6.4. Разные задачи 114
7. Рекурсия 116
7.1. Примеры рекурсивных программ 116
7.2. Рекурсивная обработка деревьев 119
7.3. Порождение комбинаторных объектов, перебор 122
7.4. Другие применения рекурсии 126
8. Как обойтись без рекурсии 134
8.1. Таблица значений (динамическое программирование) . . 134
8.2. Стек отложенных заданий 139
8.3. Более сложные случаи рекурсии 142
9. Разные алгоритмы на графах 145
9.1. Кратчайшие пути 145
9.2. Связные компоненты, поиск в глубину и ширину 149
10. Сопоставление с образцом 155
10.1. Простейший пример 155
10.2. Повторения в образце — источник проблем 158
10.3. Вспомогательные утверждения 160
10.4. Алгоритм Кнута - Морриса - Пратта 160
10.5. Алгоритм Бойера-Мура 163
10.6. Алгоритм Рабина 165
10.7. Более сложные образцы и автоматы 167
10.8. Суффиксные деревья 174
11. Анализ игр 187
11.1. Примеры игр 187
11.2. Цена игры 189
11.3. Вычисление цены: полный обход 197
11.4. Альфа-бета-процедура 200
11.5. Ретроспективный анализ 204
12. Оптимальное кодирование 206
12.1. Коды 206
12.2. Неравенство Крафта- Макмиллана 207
12.3. Код Хаффмена 211
12.4. Код Шеннона - Фано 213
13. Представление множеств. Хеширование 217
13.1. Хеширование с открытой адресацией 217
13.2. Хеширование со списками 220
14. Деревья. Сбалансированные деревья 226
14.1. Представление множеств с помощью деревьев 226
14.2. Сбалансированные деревья 234
15. Контекстно-свободные грамматики 245
15.1. Общий алгоритм разбора 245
15.2. Метод рекурсивного спуска 251
15.3. Алгоритм разбора для ЬЬ(1)-грамматик 262
16. Синтаксический разбор слева направо (LR) 270
16.1. LR-процессы 270
16.2. Ы1(0)-грамматики 276
16.3. 8ЬК(1)-грамматики 282
16.4. Ы1(1)-грамматики, ЬАЫ1(1)-грамматики 283
16.5. Общие замечания о разных методах разбора 286
Книги для чтения 288
Предметный указатель 289
Указатель имён 295

Несколько замечаний вместо предисловия
Книга написана по материалам занятий программированием со школьниками математических классов школы № 57 г. Москвы и студентами младших курсов (Московский государственный университет, Независимый московский университет, университет г. Uppsala, Швеция).
Книга написана в убеждении, что программирование имеет свой предмет, не сводящийся ни к конкретным языкам и системам, ни к методам построения быстрых алгоритмов.
Кто-то однажды сказал, что можно убедить в правильности алгоритма, но не в правильности программы. Одна из целей книги — попытаться продемонстрировать, что это не так.
В принципе, возможность практического исполнения программ не является непременным условием изучения программирования. Однако она является сильнейшим стимулом — без такого стимула вряд ли у кого хватит интереса и терпения.
Выбранный жанр книги по необходимости ограничивает её «программированием в малом», оставляя в стороне необходимую часть программистского образования — работу по модификации больших программ. Автор продолжает мечтать о наборе учебных программных систем эталонного качества, доступных для модификации школьниками.
Кажется, Хоар сказал, что эстетическая прелесть программы — это не архитектурное излишество, а то, что отличает в программировании успех от неудачи. Если, решая задачи из этой книги, читатель почувствует прелесть хорошо написанной программы, в которой «ни убавить, ни прибавить», и сомнения в правильности которой кажутся нелепыми, то автор будет считать свою цель достигнутой.
Характер глав различен: в одних предлагается набор мало связанных друг с другом задач с решениями, в других по существу излагается один-единственный алгоритм. Темы глав во многом пересекаются, и мы предпочли кое-какие повторения формальным ссылкам.
Уровень трудности задач и глав весьма различен. Мы старались включить как простые задачи, которые могут быть полезны для начинающих, так и трудные задачи, которые могут посадить в лужу сильного школьника. (Хоть и редко, но это бывает полезно.)