Программирование, Теоремы и задачи, Шень А., 2004


Программирование, Теоремы и задачи, Шень А., 2004.

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

Программирование, Теоремы и задачи, Шень А., 2004

Примеры.
Даны две целые переменные а, b. Составить фрагмент программы, после исполнения которого значения переменных поменялись бы местами (новое значение а равно старому значению b и наоборот).

Решить предыдущую задачу, не используя дополнительных переменных (и предполагая, что значениями целых переменных могут быть произвольные целые числа).

Дано целое число а и натуральное (целое неотрицательное) число п. Вычислить аn. Другими словами, необходимо составить программу, при исполнении которой значения переменных а и п не меняются, а значение некоторой другой переменной (например, b) становится равным аn.(При этом разрешается использовать и другие переменные.)

Дано натуральное (целое неотрицательное) число а и целое положительное число d. Вычислить частное q и остаток r при делении а на d, не используя операций div и mod.

Содержание
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. Алгоритм разбора для LL(1)-грамматик 262
16. Синтаксический разбор слева направо (LR) 270
16.1. LR-процессы 270
16.2. LR(0)-грамматики 276
16.3. SLR(1)-грамматики 282
16.4. LR(1)-грамматики, LALR(1)-грамматики 283
16.5. Общие замечания о разных методах разбора 286
Книги для чтения 288
Предметный указатель 289
Указатель имён 295.



Бесплатно скачать электронную книгу в удобном формате и читать:

Скачать книгу Программирование, Теоремы и задачи, Шень А., 2004 - fileskachat.com, быстрое и бесплатное скачивание.

Скачать




Скачать книгу Программирование, Теоремы и задачи, Шень А., 2004 - pdf - Яндекс.Диск.
Дата публикации:





Теги: :: ::


Следующие учебники и книги:
Предыдущие статьи:


 


 


Книги, учебники, обучение по разделам




Не нашёл? Найди:





2016-12-05 23:21:48