Теория рекурсии для программистов (Головешкин Василий Адамович, Ульянов Михаил Васильевич) ; Физматлит, 2006

Предисловие
Введение
Глава 1. Введение в теорию рекурсии
§ 1. Основные понятия и определения
§2. Рекурсивно заданные последовательности и
функции
§3. Классификация рекурсивно заданных
последовательностей и
функций
§4. Методы исследования и решения рекуррентных
соотношений
Задачи и упражнения к главе 1
Глава 2. Рекурсивные алгоритмы и особенности их
программных
реализаций
§ 1. Рекурсивные алгоритмы
§2. Особенности программных реализаций
рекурсивных алгоритмов
§3. Механизм обслуживания рекурсивного вызова
§4. Представление последовательности
рекурсивных вызовов в виде
дерева рекурсии
Задачи и упражнения к главе 2
Глава 3. Методы разработки рекурсивных
алгоритмов
§ 1. Метод рекуррентных соотношений
§2. Метод декомпозиции
§3. Метод динамического программирования
Задачи и упражнения к главе 3
Глава 4. Элементы теории ресурсной
эффективности вычисли
тельных алгоритмов
§1. Терминология и обозначения в теории
ресурсной эффективности
вычислительных алгоритмов
§2. Функции ресурсной эффективности алгоритмов
и их программных
реализаций
§3. Классы открытых и закрытых задач и
теоретическая нижняя граница временной
сложности
§4. Классификации вычислительных алгоритмов по
трудоемкости
§5. Информационная и размерностная
чувствительность вычислительных алгоритмов
§6. Классификация вычислительных алгоритмов по
дополнительной
памяти
Глава 5. Специальные главы теории рекурсии
§ 1. Основная теорема о рекуррентных
соотношениях и некоторые особые случаи
§2. Производящие функции
§3. Методы исчисления конечных сумм
§4. Функция 0i (п) и другие специальные функции
§5. Комбинаторные соотношения и их связь с
рекурсивными алгоритмами
Задачи и упражнения к главе 5
Глава 6. Методы теоретического анализа
ресурсной эффективности рекурсивных алгоритмов
§ 1. Базовые операции процедурного языка
высокого уровня и методика анализа основных
алгоритмических конструкций
§2. Особенности анализа временной и емкостной
эффективности ре
курсивных алгоритмов
§ 3. Анализ трудоемкости методом подсчета
вершин дерева рекурсии
§4. Анализ трудоемкости методом рекуррентных
соотношений
§5. Способы повышения ресурсной эффективности
рекурсивных алгоритмов
Задачи и упражнения к главе б
Глава 7. Рекурсивные алгоритмы решения
некоторых задач и их
теоретический анализ
§ 1. Алгоритм вычисления факториала
§2. Алгоритм вычисления чисел Фибоначчи
§3. Алгоритм вычисления квадратного корня
§4. Алгоритм быстрого возведения числа в целую
степень
§5. Алгоритм Карацубы умножения длинных целых
чисел
§6. Алгоритм фон Неймана сортировки массива
чисел слиянием
§7. Генетический алгоритм эвристического поиска
экстремума функции нескольких переменных
§8. Алгоритм Тарьяна поиска остовного дерева в
графе
§9. Алгоритм Беллмана оптимальной одномерной
упаковки
Задачи и упражнения к главе 7
Приложение АД. Брейман, Г.П. Рябов.
Программные реализации рекурсивных алгоритмов
и их экспериментальное исследование