Книга охватывает почти весь круг теоретических и практических вопросов, относящихся к рекурсии и рекурсивному программированию, что делает её прекрасным дополнением к уже существующим немногочисленным книгам на эту тему. На множестве примеров и задач – от простых к сложным – читатель постепенно погружается в рекурсию, учится мыслить рекурсивно и, отталкиваясь от декларативной парадигмы программирования, создавать рекурсивные алгоритмы с использованием пошаговой методики и специальных схем декомпозиции задач. При этом автор беспристрастно сопоставляет рекурсивные алгоритмы с итерационными, отмечая достоинства и недостатки тех и других.
Все алгоритмы в книге реализованы на языке Python 3.
Издание предназначено студентам вузов, преподавателям, а также широкому кругу разработчиков, желающих эффективно применять рекурсивные алгоритмы в своей работе.
Предисловие
Целевая аудитория
Содержание и структура книги
Примерные учебные курсы
Благодарности
Глава 1. Основные понятия рекурсивного программирования
1.1. Распознание рекурсии
1.2. Декомпозиция задачи
1.3. Рекурсивный код
1.4. Индукция
1.4.1. Математические доказательства методом индукции
1.4.2. Рекурсивная убеждённость
1.4.3. Императивное и декларативное программирование
1.5. Рекурсия против итерации
1.6. Типы рекурсии
1.6.1. Линейная рекурсия
1.6.2. Хвостовая рекурсия
1.6.3. Множественная рекурсия
1.6.4. Взаимная рекурсия
1.6.5. Вложенная рекурсия
1.7. Упражнения
Глава 2. Методика рекурсивного мышления
2.1. Шаблон проектирования рекурсивных алгоритмов
2.2. Размер задачи
2.3. Начальные условия
2.4. Декомпозиция задачи
2.5. Рекурсивные условия, индукция и схемы
2.5.1. Рекурсивное мышление посредством схем
2.5.2. Конкретные экземпляры задачи
2.5.3. Альтернативные обозначения
2.5.4. Процедуры
2.5.5. Несколько подзадач
2.6. Тестирование
2.7. Упражнения
Глава 3. Анализ времени выполнения рекурсивных алгоритмов
3.1. Предварительные математические соглашения
3.1.1. Степени и логарифмы
3.1.2. Биномиальные коэффициенты
3.1.3. Пределы и правило Лопиталя
3.1.4. Суммы и произведения
3.1.5. Верхняя и нижняя границы
3.1.6. Тригонометрия
3.1.7. Векторы и матрицы
3.2. ВременнАя сложность вычислений
3.2.1. Порядок роста функций
3.2.2. Асимптотические обозначения
3.3. Рекуррентные соотношения
3.3.1. Метод расширения
3.3.2. Общий метод решения разностных уравнений
3.4. Упражнения
Глава 4. Линейная рекурсия I: основные алгоритмы
4.1. Арифметические операции
4.1.1. Степенная функция
4.1.2. Медленное сложение
4.1.3. Двойная сумма
4.2. Системы счисления
4.2.1. Двоичное представление неотрицательного целого числа
4.2.2. Приведение десятичного числа к другому основанию
4.3. Строки
4.3.1. Обращение строки
4.3.2. Является ли строка палиндромом?
4.4. Дополнительные задачи
4.4.1. Сортировка выбором
4.4.2. Схема Горнера
4.4.3. Треугольник Паскаля
4.4.4. Резистивная цепь
4.5. Упражнения
Глава 5. Линейная рекурсия II: хвостовая рекурсия
5.1. Логические функции
5.1.1. Есть ли в неотрицательном целом числе заданная цифра?
5.1.2. Равны ли строки?
5.2. Алгоритмы поиска в списке
5.2.1. Линейный поиск
5.2.2. Двоичный поиск в сортированном списке
5.3. Двоичные деревья поиска
5.3.1. Поиск элемента
5.3.2. Вставка элемента
5.4. Схемы разбиения
5.4.1. Основная схема разбиения
5.4.2. Метод разбиения Хоара
5.5. Алгоритм quickselect
5.6. Двоичный поиск корня функции
5.7. Задача лесоруба
5.8. Алгоритм Евклида
5.9. Упражнения
Глава 6. Множественная рекурсия I: «разделяй и властвуй»
6.1. Отсортирован ли список?
6.2. Сортировка
6.2.1. Алгоритм сортировки слиянием
6.2.2. Алгоритм быстрой сортировки
6.3. Мажоритарный элемент списка
6.4. Быстрое целочисленное умножение
6.5. Умножение матриц
6.5.1. Умножение матриц методом «разделяй и властвуй»
6.5.2. Алгоритм Штрассена умножения матриц
6.6. Задача укладки тримино
6.7. Задача очертания
6.8. Упражнения
Глава 7. Множественная рекурсия II: пазлы, фракталы и прочее
7.1. Путь через болото
7.2. Ханойская башня
7.3. Обходы дерева
7.3.1. Внутренний обход
7.3.2. Прямой и обратный обходы
7.4. Самый длинный палиндром в строке
7.5. Фракталы
7.5.1. Снежинка Коха
7.5.2. Ковёр Серпиньского
7.6. Упражнения
Глава 8. Задачи подсчёта
8.1. Перестановки
8.2. Размещения с повторениями
8.3. Сочетания
8.4. Подъём по лестнице
8.5. Путь по Манхэттену
8.6. Триангуляция выпуклого многоугольника
8.7. Пирамиды из кругов
8.8. Упражнения
Глава 9. Взаимная рекурсия
9.1. Чётность числа
9.2. Игры со многими игроками
9.3. Размножение кроликов
9.3.1. Зрелые и незрелые пары кроликов
9.3.2. Родовое дерево кроликов
9.4. Задача о станциях водоочистки
9.4.1. Переток воды между городами
9.4.2. Сброс воды в каждом городе
9.5. Циклические ханойские башни
9.6. Грамматики и синтаксический анализатор на основе рекурсивного спуска
9.6.1. Лексический анализ входной строки
9.6.2. Синтаксический анализатор на основе рекурсивного спуска
9.7. Упражнения
Глава 10. Выполнение программы
10.1. Поток управления между подпрограммами
10.2. Деревья рекурсии
10.2.1. Анализ времени выполнения
10.3. Программный стек
10.3.1. Стековые кадры
10.3.2. Трассировка стека
10.3.3. Пространственная сложность вычислений
10.3.4. Ошибки предельной глубины рекурсии и переполнения стека
10.3.5. Рекурсия как альтернатива стеку
10.4. Мемоизация и динамическое программирование
10.4.1 Мемоизация
10.4.2. Граф зависимости и динамическое программирование
10.5. Упражнения
Глава 11. Вложенная рекурсия и снова хвостовая
11.1. Хвостовая рекурсия и итерация
11.2. Итерационный подход к хвостовой рекурсии
11.2.1. Факториал
11.2.2. Приведение десятичного числа к другому основанию
11.3. Вложенная рекурсия
11.3.1. Функция Аккермана
11.3.2. Функция-91 Маккарти
11.3.3. Цифровой корень
11.4. К хвостовой и вложенной рекурсии через обобщённую функцию
11.4.1. Факториал
11.4.2. Приведение десятичного числа к к другому основанию
11.5. Упражнения
Глава 12. Множественная рекурсия III: перебор с возвратами
12.1. Введение
12.1.1. Частичные и полные решения
12.1.2. Рекурсивная структура
12.2. Генерация комбинаторных объектов
12.2.1. Подмножества
12.2.2. Перестановки
12.3. Задача n ферзей
12.3.1. Поиск всех решений
12.3.2. Поиск одного решения
12.4. Задача о сумме элементов подмножества
12.5. Путь в лабиринте
12.6. Судоку
12.7. Задача о рюкзаке 0–1
12.7.1. Стандартный алгоритм перебора с возвратами
12.7.2. Алгоритм ветвей и границ
12.8. Упражнения
Что ещё почитать
Монографии о рекурсии
Разработка и анализ алгоритмов
Функциональное программирование
Язык Python
Исследования в обучении и изучении рекурсии
Дополнительная литература
Список рисунков
Список таблиц
Список листингов
Предметный указатель
Название: Введение в рекурсивное программирование
Автор: Мануэль Рубио-Санчес
Год: 2019
Жанр: программирование
Издательство: М.: ДМК Пресс
Язык: Русский
Формат: pdf
Качество: eBook
Страниц: 436
Размер: 9,5 MB
Скачать Мануэль Рубио-Санчес - Введение в рекурсивное программирование (2019)
