Головешкин В.А., Ульянов М.В. Теория рекурсии для программистов

М.: Физматлит, 2006. — 296 с.Книга является учебным пособием по теории рекурсии в аспекте ее применения в области программирования. В ней рассматриваются основы теории рекурсии, и ее использование в области разработки и анализа рекурсивных алгоритмов. Приводятся основные сведения о рекурсивных последовательностях и функциях, даны примеры рекурсивных алгоритмов, разработанных на основе рекуррентных соотношений, метода декомпозиции и метода динамического программирования, излагаются методы разработки рекурсивных алгоритмов и их теоретического анализа, в том числе элементы теории ресурсной эффективности вычислительных алгоритмов.
Детально изложены методы анализа рекурсивных алгоритмов, проиллюстрированные целым рядом примеров. Приложение содержит тексты программ, реализующих рекурсивные алгоритмы, рассмотренные в основном тексте книги, и результаты экспериментальных исследований. Учебное пособие ориентировано на специалистов в области информатики и анализа алгоритмов, разработчиков алгоритмического обеспечения и предназначено для студентов, аспирантов и преподавателей вузов, специализирующихся в области математической информатики, теории рекурсии, разработки, анализа и исследования рекурсивных алгоритмов.Введение в теорию рекурсии.
Основные понятия и определения.
Рекурсивно заданные последовательности и функции.
Классификация рекурсивно заданных последовательностей и функций.
Методы исследования и решения рекуррентных соотношений.
Задачи и упражненияРекурсивные алгоритмы и особенности их программных реализаций.
Рекурсивные алгоритмы.
Особенности программных реализаций рекурсивных алгоритмов
Механизм обслуживания рекурсивного вызова.
Представление последовательности рекурсивных вызовов в виде дерева рекурсии.
Задачи и упражненияМетоды разработки рекурсивных алгоритмов
Метод рекуррентных соотношений.
Метод декомпозиции.
Метод динамического программирования
Задачи и упражненияЭлементы теории ресурсной эффективности вычислительных алгоритмов.
Терминология и обозначения в теории ресурсной эффективности вычислительных алгоритмов.
Функции ресурсной эффективности алгоритмов и их программных реализаций.
Классы открытых и закрытых задач и теоретическая нижняя граница временной сложности.
Классификации вычислительных алгоритмов по трудоемкости.
Информационная и размерностная чувствительность вычислительных алгоритмов.
Классификация вычислительных алгоритмов по дополнительной памяти.Специальные главы теории рекурсии.
Основная теорема о рекуррентных соотношениях и некоторые особые случаи.
Производящие функции.
Методы исчисления конечных сумм.
Функция Betta_1(n) и другие специальные функции.
Комбинаторные соотношения и их связь с рекурсивными алгоритмами.
Задачи и упражненияМетоды теоретического анализа ресурсной эффективности рекурсивных алгоритмов.
Базовые операции процедурного языка высокого уровня и методика анализа основных алгоритмических конструкций.
Особенности анализа временной и емкостной эффективности рекурсивных алгоритмов.
Анализ трудоемкости методом подсчета вершин дерева рекурсии
Анализ трудоемкости методом рекуррентных соотношений.
Способы повышения ресурсной эффективности рекурсивных алгоритмов.
Задачи и упражненияРекурсивные алгоритмы решения некоторых задач и их теоретический анализ.
Алгоритм вычисления факториала.
Алгоритм вычисления чисел Фибоначчи.
Алгоритм вычисления квадратного корня.
Алгоритм быстрого возведения числа в целую степень
Алгоритм Карацубы умножения длинных целых чисел.
Алгоритм фон Неймана сортировки массива чисел слиянием.
Генетический алгоритм эвристического поиска экстремума функции нескольких переменных.
Алгоритм Тарьяна поиска остовногo дерева в графе.
Алгоритм Беллмана оптимальной одномерной упаковки
Задачи и упражненияПрограммные реализации рекурсивных алгоритмов и их экспериментальное исследование.