Рефераты. Рекурсивные алгоритмы

Рекурсивные алгоритмы

Министерство образования Российской Федерации

Ставропольский Государственный университет

Кафедра математического анализа

 

 

 

 

 

 

 

 

 

 

Курсовая работа на тему:

«Рекурсивные алгоритмы»

 

 

 





Выполнил: студент  3го курса ФМФ специальности ПМИ группы «Б»

Симонян Сергей Олегович

Проверил: Ионисян А. Д.





 

 

Ставрополь, 2004 г.

 

 

 

 

 

 

 

 

 

 

 

Содержание

 

 

Введение. 3

Теория рекурсивных алгоритмов. 5

Дескриптивная теория. 5

Метрическая теория. 10

Программная реализация рекурсии. 18

Общие принципы реализации. 18

Пример: компилятор Turbo Pascal 7.0. 26

Заключение. 27

Список использованной литературы. 28

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Введение.

Не так давно человечество вступило в новый XXI век – век информации и компьютеров. Благодаря бурному развитию научных, технических и технологических исследований стало возможным хранить огромные объёмы данных и преобразовывать их со скоростями, которые ещё несколько десятилетий назад могли только сниться. При создании сложных информационных систем перед проектировщиками стали нетривиальные задачи, требующие разработки новых концепций программирования.

Для решения проблем такого рода, особенно при учёте человеческого фактора, возникает необходимость обеспечения понятности алгоритма, так называемой «читабельности» исходного кода программы, и как следствие модифицируемости и относительной лёгкости сопровождения конечного программного продукта. Часто этого можно достигнуть включением в  реализацию приложения рекурсивных подпрограмм, механизмы использования которых предоставляются практически всеми современными компиляторами и средами разработки.

Объект называется рекурсивным, если для своего определения или функционирования он прямо или косвенно обращается к объекту в некотором смысле такого же типа. Так, например, в теле рекурсивных подпрограмм, которые будут подробно рассмотрены ниже, в простейшем случае содержится вызов самих себя, но с другими параметрами.

Рекурсия является одним из наиболее мощных и, наверно, самым общим методом научного познания. Она эффективно применяется во многих прикладных и теоретических естественнонаучных дисциплинах, и стала неотъемлемой их частью.

Этому нетрудно найти множество подтверждений, однако один и тот же по сути метод, применительно к различным областям носит различные названия, такие как индукция, рекурсия или рекуррентные соотношения.  Различия касаются особенностей использования.

Под индукцией понимается метод доказательства утверждений с формулировкой зависящей от натурального переменного , который строится на базе индукции (правильности утверждения при  или ), затем утверждение полагается правильным при  и проводится доказательство для .

Термин рекуррентное соотношение связан с американским научным стилем и определяет математическое задание функции с помощью рекурсии.

Важную роль в теории алгоритмов сыграл аппарат рекурсивных функций, разработанный Алонзо Чёрчем и позволивший ему формализовать понятие алгоритма.

Последние двадцать лет получили бурное развитие созданная и глубоко развитая Бенуа Мандельбротом фрактальная геометрия, теория мультифракталов и их приложения. Нужно заметить, что в теориях понятие рекурсии одно из основных. Так, например, многие фрактальные геометрические фигуры, такие как совершенное канторово множество или салфетка Серпинского, определяются рекурсивно [1].

Как видим, понятие рекурсии очень широко и многогранно. В настоящей работе будет освещён лишь один аспект этого понятия, а именно рекурсивные алгоритмы. Они рассмотрены как с позиций теории алгоритмов и теории сложности, так и с точки зрения практического программирования. Читатель сможет узнать, как применять на практике алгоритмы, содержащие рекурсию, а главное когда стоит это делать. Важно сохранять баланс между изящностью и простотой восприятия, присущие рекурсивным алгоритмам, и сложностью его реализации на конкретной вычислительной системе.



 

 

Теория рекурсивных алгоритмов.

 

Дескриптивная теория.

Задача точного определения понятия алгоритма была полностью решена в 30-х годах XX века в двух формах: на основе описания алгоритмического процесса и на основе понятия рекурсивной функции.

Первый подход заключался в том, что был сконструирован формальный автомат, способный осуществлять ограниченный набор строго определённых элементарных операций (машина Тьюринга). Алгоритмом стали называть конечную последовательность таких операций и постулировали предложение, что любой интуитивный алгоритм является алгоритмом и в сформулированном выше смысле. То есть для каждого алгоритма можно подобрать реализующую его машину Тьюринга [2].

Развитие теории конечных автоматов позволило строго доказать алгоритмическую неразрешимость ряда важных математических проблем (10-й проблемы Гильберта [3], проблемы представимости матриц [4]  и др.). Однако её существенным недостатком является невозможность реализации такой полезной конструкции как рекурсия.

Этого недостатка лишён другой подход к формализации понятия алгоритма, развитый Гёделем и Чёрчем. Здесь теория построена на основе широкого класса так называемых частично рекурсивных функций [5].

Замечателен тот факт, что оба данных подхода, а также другие подходы (Марков, Пост) приводят к одному и тому же классу алгоритмически вычислимых функций [6]. Поэтому для дальнейшего изложения мы выберем именно теорию частично рекурсивных функций Чёрча, так как она позволяет доказать не только алгоритмическую разрешимость задач, но и существование для неё рекурсивного алгоритма.

Сначала определим и исследуем сам класс частично рекурсивных функций [7]. Данный класс определяется путем указания конкретных исходных функций и фиксированного множества операций получения новых функций из заданных.

В качестве базисных функций обычно берутся следующие:

1. Нуль- функция: ;

2. Функция следования: ;

3. Функция выбора аргументов: .

Допустимыми операциями над функциями являются операции суперпозиции (подстановки), рекурсии и минимизации.

Операция суперпозиции. Пусть даны -местная функция  и  функций . Считаем, что функции  зависят от одних и тех же переменных .Это можно сделать путем введения фиктивных переменных. Суперпозицией (подстановкой) функций  и  называется функция

.

Функция  на наборе переменных  определена тогда и только тогда, когда определены все функции  и функция  определена на наборе . Операцию суперпозиции обозначают: .

Операция рекурсии (точнее: примитивной рекурсии). Пусть заданы -местная функция  и -местная функция . Определим -местную функцию  индуктивным образом с помощью соотношений:

;

.

Ясно, что данные соотношения однозначно определяют функцию .  считается определённой в том и только в том случае, когда определены   и  при . Значит, если  неопределено, то и  неопределено при . Про функцию  говорят, что она получена рекурсией из функций  и , и обозначают: .

Операция минимизации. Пусть задана -местная функция . Зафиксируем набор  и рассмотрим уравнение относительно :

.

Будем решать данное уравнение, вычисляя последовательно , ,  и т.д. и сравнивая с . Наименьшее , для которого выполнено уравнение обозначим . При этом считаем, что  определено, если  определено при всех . В противном случае считаем, что  неопределено. Значение  есть функция  от переменных , про которую говорят, что она получена из  минимизацией и обозначают: .

Функция называется частично-рекурсивной, если она может быть получена из базисных функций , ,  применением конечного числа раз операций суперпозиции, рекурсии и минимизации.

Какая же связь между  частично рекурсивными функциями и теорией алгоритмов? Эту связь устанавливает «тезис Чёрча» [8], для формулировки которого введём понятие вычислимой функции.

Страницы: 1, 2, 3, 4



2012 © Все права защищены
При использовании материалов активная ссылка на источник обязательна.