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

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

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




КАК ОБОЙТИСЬ БЕЗ РЕКУРСИИ.
Для универсальных языков программирования (каковым является паскаль) рекурсия не даёт ничего нового: для всякой рекурсивной программы можно написать эквивалентную программу без рекурсии. Мы не будем доказывать этого, а продемонстрируем некоторые приёмы, позволяющие избавиться от рекурсии в конкретных ситуациях.

Зачем это нужно? Ответ прагматика мог бы быть таким: во многих компьютерах (в том числе, к сожалению, и в современных, использующих так называемые RISC-процессоры), рекурсивные программы в несколько раз медленнее соответствующих нерекурсивных программ. Ещё один возможный ответ: в некоторых языках программирования рекурсивные программы запрещены. А главное, при удалении рекурсии возникают изящные и поучительные конструкции.

ОГЛАВЛЕНИЕ.
1. Переменные, выражения, присваивания.
1.1. Задачи без массивов.
1.2. Массивы.
1.3. Индуктивные функции (по А. Г. Кушниренко).
2. Порождение комбинаторных объектов.
2.1. Размещения с повторениями.
2.2. Перестановки.
2.3. Подмножества.
2.4. Разбиения.
2.5. Коды Грея и аналогичные задачи.
2.6. Несколько замечаний.
2.7. Подсчёт количеств.
3. Обход дерева. Перебор с возвратами 60
3.1. Ферзи, не бьющие друг друга: обход дерева позиций.
3.2. Обход дерева в других задачах.
4. Сортировка.
4.1. Квадратичные алгоритмы.
4.2. Алгоритмы порядка ???? log ????.
4.3. Применения сортировки.
4.4. Нижние оценки для числа сравнений при сортировке.
4.5. Родственные сортировке задачи.
5. Конечные автоматы и обработка текстов.
5.1. Составные символы, комментарии и т. п.
5.2. Ввод чисел.
6. Типы данных.
6.1. Стеки.
6.2. Очереди.
6.3. Множества.
6.4. Разные задачи.
7. Рекурсия.
7.1. Примеры рекурсивных программ.
7.2. Рекурсивная обработка деревьев.
7.3. Порождение комбинаторных объектов, перебор.
7.4. Другие применения рекурсии.
8. Как обойтись без рекурсии.
8.1. Таблица значений (динамическое программирование).
8.2. Стек отложенных заданий.
8.3. Более сложные случаи рекурсии.
9. Разные алгоритмы на графах.
9.1. Кратчайшие пути.
9.2. Связные компоненты, поиск в глубину и ширину.
9.3. Сети, потоки и разрезы.
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. Ретроспективный анализ.
12. Оптимальное кодирование.
12.1. Коды.
12.2. Неравенство Крафта-Макмиллана.
12.3. Код Хаффмана.
12.4. Код Шеннона-Фано.
13. Представление множеств. Хеширование.
13.1. Хеширование с открытой адресацией.
13.2. Хеширование со списками.
14. Деревья. Сбалансированные деревья.
14.1. Представление множеств с помощью деревьев.
14.2. Сбалансированные деревья.
15. Контекстно-свободные грамматики.
15.1. Общий алгоритм разбора.
15.2. Метод рекурсивного спуска.
15.3. Алгоритм разбора для LL(1)-грамматик.
16. Синтаксический разбор слева направо (LR).
16.1. LR-процессы.
16.2. LR(0)-грамматики.
16.3. SLR(1)-грамматики.
16.4. LR(1)-грамматики, LALR(1)-грамматики.
16.5. Общие замечания о разных методах разбора.
Книги для чтения.
Предметный указатель.
Указатель имён.



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

Скачать pdf
Ниже можно купить эту книгу, если она есть в продаже, и похожие книги по лучшей цене со скидкой с доставкой по всей России.Купить книги


Скачать - pdf - Яндекс.Диск.




Теги: учебник по программированию :: программирование :: Шень :: алгоритм Рабина