Рекурсивные функции и алгоритмы. Рекурсивные алгоритмы и методы их анализа
Рекурсивные функции и реализация алгоритмов, методы решения данных соотношений. Анализ трудоемкости механизма вызова процедуры и вычисления факториала, логарифмические тождества. Рекурсивные алгоритмы и основная теорема о рекуррентных соотношениях.
| Рубрика | Программирование, компьютеры и кибернетика |
| Вид | реферат |
| Язык | русский |
| Дата добавления | 12.07.2010 |
| Размер файла | 62,6 K |
Отправить свою хорошую работу в базу знаний просто. Используйте форму, расположенную ниже
Студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будут вам очень благодарны.
ГОСУДАРСТВЕННОЕ УЧРЕЖДЕНИЕ
ВЫСШЕГО ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ
«БЕЛОРУССКО-РОССИЙСКИЙ УНИВЕРСИТЕТ»
Кафедра «Автоматизированные системы управления»
Реферат на тему:
«РЕКУРСИВНЫЕ ФУНКЦИИ И АЛГОРИТМЫ. РЕКУРСИВНЫЕ АЛГОРИТМЫ И МЕТОДЫ ИХ АНАЛИЗА»
по дисциплине
«Математическая логика и теория алгоритмов»
Выполнил: ______________
Проверил: ______________
Могилев, 2010
СОДЕРЖАНИЕ
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! (2n)1/2 *(nn)/(en)
Эта рекурсивная функция определяет числа Фибоначчи: 1 1 2 3 5 8 13, которые достаточно часто возникают при анализе различных задач, в том числе и при анализе алгоритмов. Отметим, что асимптотически (n) [1,618n] [9].
Для получения функции в явном виде рассмотрим ее последовательные значения: (0)=1, (1)=2, (2)=4, (3)=8, что позволяет предположить, что (n)=2n, точное доказательство выполняется по индукции.
Мы имеем дело с примером того, что одна и та же функция может иметь различные рекурсивные определения - (n)=2n, как и в примере 4, что проверяется элементарной подстановкой.
В этом случае мы можем получить решение в замкнутой форме, сопоставив значениям функции соответствующие степени двойки:
(2) = 2 = 21
(3) = 4 = 22
(4) = 8 = 23
(5) = 32 = 25
(6) = 256 = 28
Обозначив через Fn - n -ое число Фибоначчи, имеем: (n)=2Fn.
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 ac = c * logb a;
logb a = 1/loga b
logb a = logc a / logc b в записи (ln(x)) основание логарифма не существенно, если он больше единицы, т.к. константа скрывается обозначением .
a logb c=c logb a
Можно показать, что для любого > 0 ln(n )= о(n), при n
6 МЕТОДЫ РЕШЕНИЯ РЕКУРСИВНЫХ СООТНОШЕНИЙ
В математике разработан ряд методов, с помощью которых можно получить явный вид рекурсивно заданной функции - метод индукции, формальные степенные ряды, метод итераций и т.д. Рассмотрим некоторые из них:
а) Метод индукции. Метод состоит в том, что бы сначала угадать решение, а затем доказать его правильность по индукции. Пример:
(0)=1
(n+1)=2*f(n)
Предположение: (n)=2n
Базис: если (n)=2n , то (0)=1, что выполнено по определению.
Индукция: Пусть (n)=2n , тогда для n+1 (n+1)= 2 * 2 n =2 n+1
Заметим, что базис существенно влияет на решение, так, например. Если (0)=0, то (n)=0;если (0)=1/7, то (n)=(1/7)*2n ; если (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/16+3*(n/64) }],
и раскрывая скобки, получаем:
(n)=n+3*n/4+9*n/16+27*n/64+…+3i*n/4i
Остановка рекурсии произойдет при (n / 4 i) 1 i log4 n, в этом случае последнее слагаемое не больше, чем 3 log4 n* (1) = n log4 3* (1).
(n) = n* (3/4) k + n log4 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(nlogba-), >0, то (n)=(nlogba)
Пример:(n) = 8(n/2)+n2 , тогда (n) = (n3)
2) Если g(n)=(nlog6a), то (n)=(nlogba*log n)
Пример: fA(n)= 2 * fA( n/2 )+ (n), тогда (n) = (n*log n)
3) Если g(n) = (nlogba+e), e > 0, то (n) = (g(n))
Пример: (n)=2*(n/2)+n2, имеем:
nlogba = n1, и следовательно: (n) = (n2)
Данная теорема является мощным средством анализа асимптотической сложности рекурсивных алгоритмов, к сожалению, она не дает возможности получить полный вид функции трудоемкости.
Подобные документы
История развития средств вычислительной техники. Машина Тьюринга: понятие и свойства. Теория переменных и типов данных в 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Структура языка Паскаль, встроенные процедуры и функции. Составление алгоритма решения уравнения, описывающего работу кривошипно-шатунного механизма, с помошью метода итерации, метода Гаусса и метода Зейделя. Блок-схемы алгоритмов и текст программы.
курсовая работа [64,6 K], добавлен 07.05.2011Сведения о языке программирования Macromedia Flash. Последовательность шагов, поля ввода единичек и логических функций. Разработка интерфейса приложения. Покадровая анимация лекции. Рекурсивные процедуры и функции. Разработка игры-головоломки "Танграм".
дипломная работа [2,8 M], добавлен 17.11.2013Исследование понятия рекурсии в программировании. Описание метода, который позволяет разбить задачу на части все меньшего и меньшего размера. Изучение схемы работы рекурсивной процедуры. Способы изображения древовидных структур. Избавление от рекурсии.
презентация [486,1 K], добавлен 22.10.2013Разработка программной реализации решения задачи о минимальном покрывающем дереве графа (построение минимального остова), используя алгоритмы Прима и Крускала. Подсчет времени работы алгоритмов. Их программная реализация на практике с помощью Delphi 7.
курсовая работа [538,1 K], добавлен 29.08.2010
