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