Рекурсивные функции и алгоритмы. Рекурсивные алгоритмы и методы их анализа
Рекурсивные функции и реализация алгоритмов, методы решения данных соотношений. Анализ трудоемкости механизма вызова процедуры и вычисления факториала, логарифмические тождества. Рекурсивные алгоритмы и основная теорема о рекуррентных соотношениях.
Рубрика Программирование, компьютеры и кибернетика Вид реферат Язык русский Дата добавления 12.07.2010 Размер файла 62,6 K Отправить свою хорошую работу в базу знаний просто. Используйте форму, расположенную нижеСтуденты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будут вам очень благодарны.
ВЫСШЕГО ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ
Кафедра «Автоматизированные системы управления»
Реферат на тему:
«РЕКУРСИВНЫЕ ФУНКЦИИ И АЛГОРИТМЫ. РЕКУРСИВНЫЕ АЛГОРИТМЫ И МЕТОДЫ ИХ АНАЛИЗА»
«Математическая логика и теория алгоритмов»
СОДЕРЖАНИЕ
1 Рекурсивные функции
2 Рекурсивная реализация алгоритмов
3 Анализ трудоемкости механизма вызова процедуры
4 Анализ трудоемкости алгоритма вычисления факториала
5 Логарифмические тождества
6 Методы решения рекурсивных соотношений
7 Рекурсивные алгоритмы
8 Основная теорема о рекуррентных соотношениях
1 РЕКУРСИВНЫЕ ФУНКЦИИ
а) Терминологическое введение. По сути один и тот же метод, применительно к различным областям носит различные названия - это индукция, рекурсия и рекуррентные соотношения - различия касаются особенностей использования.
Под индукцией понимается метод доказательства утверждений, который строится на базе индукции при n=0,1, затем утверждение полагается правильным при n=n b и проводится доказательство для n+1.
Под рекурсией понимается метод определения функции через её предыдущие и ранее определенные значения, а так же способ организации вычислений, при котором функция вызывает сама себя с другим аргументом.
Термин рекуррентные соотношения связан с американским научным стилем и определяет математическое задание функции с помощью рекурсии.
Основной задачей исследования рекурсивно заданных функций является получение (n) в явной или как еще говорят «замкнутой» форме, т.е. в виде аналитически заданной функции. В связи с этим рассмотрим ряд примеров:
б) Примеры рекурсивного задания функций
Здесь нетрудно сообразить, что (n)=n.
Последовательная подстановка дает - (n)=1*2*3*…*n = n!
Для полноты сведений приведем формулу Стирлинга для приближенного вычисления факториала для больших n:
n! (2 n) 1/2 *(n n )/(e n )
Эта рекурсивная функция определяет числа Фибоначчи: 1 1 2 3 5 8 13, которые достаточно часто возникают при анализе различных задач, в том числе и при анализе алгоритмов. Отметим, что асимптотически (n) [1,618 n ] [9].
Для получения функции в явном виде рассмотрим ее последовательные значения: (0)=1, (1)=2, (2)=4, (3)=8, что позволяет предположить, что (n)=2 n , точное доказательство выполняется по индукции.
Мы имеем дело с примером того, что одна и та же функция может иметь различные рекурсивные определения - (n)=2 n , как и в примере 4, что проверяется элементарной подстановкой.
В этом случае мы можем получить решение в замкнутой форме, сопоставив значениям функции соответствующие степени двойки:
(2) = 2 = 2 1
(3) = 4 = 2 2
(4) = 8 = 2 3
(5) = 32 = 2 5
(6) = 256 = 2 8
Обозначив через Fn - n -ое число Фибоначчи, имеем: (n)=2 Fn .
2 РЕКУРСИВНАЯ РЕАЛИЗАЦИЯ АЛГОРИТМОВ
Большинство современных языков высокого уровня поддерживают механизм рекурсивного вызова, когда функция, как элемент структуры языка программирования, возвращающая вычисленное значение по своему имени, может вызывать сама себя с другим аргументом. Эта возможность позволяет напрямую реализовывать вычисление рекурсивно определенных функций. Отметим, что в силу тезиса Черча-Тьюринга аппарат рекурсивных функций Черча равномощен машине Тьюринга, и, следовательно, любой рекурсивный алгоритм может быть реализован итерационно.
Рассмотрим пример рекурсивной функции, вычисляющий факториал:
F(n);
If n=0 or n=1 (проверка возможности прямого вычисления)
Then F 1 Else
F n*F(n-1); (рекурсивный вызов функции)
Return (F);
End;
Анализ трудоемкости рекурсивных реализаций алгоритмов, очевидно, связан как с количеством операций, выполняемых при одном вызове функции, так и с количеством таких вызовов. Графическое представление порождаемой данным алгоритмом цепочки рекурсивных вызовов называется деревом рекурсивных вызовов. Более детальное рассмотрение приводит к необходимости учета затрат как на организацию вызова функции и передачи параметров, так и на возврат вычисленных значений и передачу управления в точку вызова.
Можно заметить, что некоторая ветвь дерева рекурсивных вызовов обрывается при достижении такого значения передаваемого параметра, при котором функция может быть вычислена непосредственно. Таким образом, рекурсия эквивалентна конструкции цикла, в котором каждый проход есть выполнение рекурсивной функции с заданным параметром.
Рассмотрим пример для функции вычисления факториала (рис 1):
Рисунок 1 - Дерево рекурсии при вычислении факториала - F(5)
Дерево рекурсивных вызовов может иметь и более сложную структуру, если на каждом вызове порождается несколько обращений - фрагмент дерева рекурсий для чисел Фибоначчи представлен на рис 2:
Рисунок 2 - Фрагмент дерева рекурсии при вычислении чисел Фибоначчи - F(5)
3 АНАЛИЗ ТРУДОЕМКОСТИ МЕХАНИЗМА ВЫЗОВА ПРОЦЕДУРЫ
Механизм вызова функции или процедуры в языке высокого уровня существенно зависит от архитектуры компьютера и операционной системы. В рамках IBM PC совместимых компьютеров этот механизм реализован через программный стек. Как передаваемые в процедуру или функцию фактические параметры, так и возвращаемые из них значения помещаются в программный стек специальными командами процессора. Дополнительно сохраняются значения необходимых регистров и адрес возврата в вызывающую процедуру. Схематично этот механизм иллюстрирован на рис 3.
Для подсчета трудоемкости вызова будем считать операции помещения слова в стек и выталкивания из стека элементарными операциями в формальной системе. Тогда при вызове процедуры или функции в стек помещается адрес возврата, состояние необходимых регистров процессора, адреса возвращаемых значений и передаваемые параметры.
Рисунок 3 - Механизм вызова процедуры с использованием программного стека
После этого выполняется переход по адресу на вызываемую процедуру, которая извлекает переданные фактические параметры, выполняет вычисления, помещает их по указанным в стеке адресам, и при завершении работы восстанавливает регистры, выталкивает из стека адрес возврата и осуществляет переход по этому адресу. Обозначив через:
m - количество передаваемых фактических параметров,
k - количество возвращаемых процедурой значений,
r - количество сохраняемых в стеке регистров, имеем:
fвызова = m+k+r+1+m+k+r+1 = 2*(m+k+r+1) элементарных операций на один вызов и возврат.
Анализ трудоемкости рекурсивных алгоритмов в части трудоемкости самого рекурсивного вызова можно выполнять разными способами в зависимости от того, как формируется итоговая сумма элементарных операций - рассмотрением в отдельности цепочки рекурсивных вызовов и возвратов, или совокупно по вершинам дерева рекурсивных вызовов.
4 АНАЛИЗ ТРУДОЕМКОСТИ АЛГОРИТМА ВЫЧИСЛЕНИЯ ФАКТОРИАЛА
Для рассмотренного выше рекурсивного алгоритма вычисления факториала количество вершин рекурсивного дерева равно, очевидно, n, при этом передается и возвращается по одному значению (m=1, k=1), в предположении о сохранении четырех регистров - r=4, а на последнем рекурсивном вызове значение функции вычисляется непосредственно - в итоге:
fA(n)=n*2*(1+1+4+1)+(n-1)*(1+3)+1*2=18*n - 2
Отметим, что n - параметр алгоритма, а не количество слов на входе.
5 ЛОГАРИФМИЧЕСКИЕ ТОЖДЕСТВА
При анализе рекурсивных алгоритмов достаточно часто используются логарифмические тождества, далее предполагается, что, a > 0, b > 0, c > 0, основание логарифма не равно единице:
b logba = a;
e lnx = x;
logb a c = c * logb a;
logb a = 1/loga b
logb a = logc a / logc b в записи (ln(x)) основание логарифма не существенно, если он больше единицы, т.к. константа скрывается обозначением .
a log b c =c log b a
Можно показать, что для любого > 0 ln(n )= о(n ), при n
6 МЕТОДЫ РЕШЕНИЯ РЕКУРСИВНЫХ СООТНОШЕНИЙ
В математике разработан ряд методов, с помощью которых можно получить явный вид рекурсивно заданной функции - метод индукции, формальные степенные ряды, метод итераций и т.д. Рассмотрим некоторые из них:
а) Метод индукции. Метод состоит в том, что бы сначала угадать решение, а затем доказать его правильность по индукции. Пример:
(n+1)=2*f(n)
Предположение: (n)=2 n
Базис: если (n)=2 n , то (0)=1, что выполнено по определению.
Индукция: Пусть (n)=2 n , тогда для n+1 (n+1)= 2 * 2 n =2 n +1
Заметим, что базис существенно влияет на решение, так, например. Если (0)=0, то (n)=0;если (0)=1/7, то (n)=(1/7)*2 n ; если (0)=1/64, то (n)=(2) n-6
б) Метод итерации (подстановки). Суть метода состоит в последовательной подстановке - итерации рекурсивного определения, с последующим выявлением общих закономерностей. Пусть (n)=3*(n/4)+n, тогда:
(n)=n+3*(n/4)=n+3*[n/4+3*(n/16)]=n+3* [n/4+3],
и раскрывая скобки, получаем:
(n)=n+3*n/4+9*n/16+27*n/64+…+3 i *n/4 i
Остановка рекурсии произойдет при (n / 4 i ) 1 i log4 n, в этом случае последнее слагаемое не больше, чем 3 log 4 n * (1) = n log 4 3 * (1).
(n) = n* (3/4) k + n log 4 3 * (1), т.к. (3/4) k = 4*n, то окончательно:
(n) = 4 * n + n log4 3 * (1) = (n)
7 РЕКУРСИВНЫЕ АЛГОРИТМЫ
Основной метод построения рекурсивных алгоритмов - это метод декомпозиции. Идея метода состоит в разделении задачи на части меньшей размерности, получение решение для полученных частей и объединение решений.
В общем виде, если происходит разделение задачи на b подзадач, которое приводит к необходимости решения a подзадач размерностью n/b, то общий вид функции трудоемкости имеет вид:
fA(n )= a * fA( n/b )+d(n)+U(n) (9.1),
где d(n) - трудоемкость алгоритма деления задачи на подзадачи,
U(n) - трудоемкость алгоритма объединения полученных решений.
Рассмотрим, например, известный алгоритм сортировки слиянием, принадлежащий Дж. Фон Нейману [6]:
На каждом рекурсивном вызове переданный массив делится пополам, что дает оценку для d(n) = (1), далее рекурсивно вызываем сортировку полученных массивов половинной длины (до тех пор, пока длина массива не станет равной единице), и сливаем возвращенные отсортированные массивы за (n).
Тогда ожидаемая трудоемкость на сортировку составит:
fA(n )= 2 * fA( n/2 )+ (1)+ (n)
Тем самым возникает задача о получении оценки сложности функции трудоемкости, для произвольных значений a и b.
8 ОСНОВНАЯ ТЕОРЕМА О РЕКУРРЕНТНЫХ СООТНОШЕНИЯХ
Следующая теорема принадлежит Дж. Бентли, Д. Хакен и Дж. Саксу (1980 г.). Теорема. Пусть a 1, b > 1 - константы, g(n) - функция, пусть далее:
(n)=a*(n/b)+g(n), где n/b = (n/b) или (n/b)
1) Если g(n) = O(n logba- ), >0, то (n)= (n logba )
Пример:(n) = 8(n/2)+n 2 , тогда (n) = (n 3 )
2) Если g(n)= (n log6a ), то (n)= (n logba *log n)
Пример: fA(n)= 2 * fA( n/2 )+ (n), тогда (n) = (n*log n)
3) Если g(n) = (n logba+e ), e > 0, то (n) = (g(n))
Пример: (n)=2*(n/2)+n 2 , имеем:
n logba = n 1 , и следовательно: (n) = (n 2 )
Данная теорема является мощным средством анализа асимптотической сложности рекурсивных алгоритмов, к сожалению, она не дает возможности получить полный вид функции трудоемкости.
Подобные документыИстория развития средств вычислительной техники. Машина Тьюринга: понятие и свойства. Теория переменных и типов данных в ANSI C. Обменные сортировки, их виды. Исходный, объектный и машинный код. Функции компилятора и линковщика. Рекурсивные алгоритмы.
шпаргалка [432,5 K], добавлен 04.05.2015
Определение понятия графа как набора вершин и связей между ними. Способы решения задач по программированию согласно теории графов на примерах заданий "Дороги", "Перекрестки", "Скрудж Мак-Дак", используя рекурсивные функции и рекуррентные соотношения.
курсовая работа [36,2 K], добавлен 10.03.2010
Использование рекурсии в предметных областях. Рекурсивные процедуры и функции в программировании. Создание алгоритмов для рисования графических изображений с использованием рекурсии в среде программирования Pascal ABC. Примеры рекурсии в графике.
творческая работа [6,7 M], добавлен 01.02.2014
Классификация и стек рекурсивных функций. Методика распознавания формулы, записанной в строке. Реализация салфетки Серпинского и задачи о Ханойских башнях. Алгоритм быстрой сортировки. Создание функции, сортирующей массив с использованием рекурсии.
лабораторная работа [160,8 K], добавлен 06.07.2009
Методы и алгоритмы вычисления определенных интегралов: метод трапеций и метод Симпсона (метод парабол). Оформление функции вычисления заданного определённого интеграла на Visual Basic 6.0. Программный код функции. Создание приложения для вычисления.
курсовая работа [483,6 K], добавлен 25.06.2014
Обзор алгоритмов решения задачи: точные методы, генетический и жадный алгоритмы. Характеристика жадного алгоритма: его описание, анализ точности приближения, вычислительной сложности. Программная реализация и проверка корректности и быстродействия.
курсовая работа [228,7 K], добавлен 14.10.2017
Структура языка Паскаль, встроенные процедуры и функции. Составление алгоритма решения уравнения, описывающего работу кривошипно-шатунного механизма, с помошью метода итерации, метода Гаусса и метода Зейделя. Блок-схемы алгоритмов и текст программы.