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

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

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

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

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

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

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

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

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

Ставрополь, <st1:metricconverter ProductID=«2004 г» w:st=«on»>2004 г</st1:metricconverter>.

Содержание

TOC o «1-2» f h z u Введение.PAGEREF _Toc105389907 h 3

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

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

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

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

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

Пример:компилятор TurboPascal7.0.PAGEREF _Toc105389964 h 26

Заключение.PAGEREF _Toc105389971 h 27

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

Введение.

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

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

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

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

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

Под индукцией понимается метод доказательства утверждений сформулировкой зависящей от натурального переменного <img src="/cache/referats/20085/image002.gif" v:shapes="_x0000_i1025"><img src="/cache/referats/20085/image004.gif" v:shapes="_x0000_i1026"> или <img src="/cache/referats/20085/image006.gif" v:shapes="_x0000_i1027"><img src="/cache/referats/20085/image008.gif" v:shapes="_x0000_i1028"> и проводитсядоказательство для <img src="/cache/referats/20085/image010.gif" v:shapes="_x0000_i1029">

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

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

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

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

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

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

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

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

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

, проблемы представимости матриц [4] и др.). Однако еёсущественным недостатком является невозможность реализации такой полезнойконструкции как рекурсия.

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

Замечателен тот факт, что оба данных подхода, атакже другие подходы (Марков, Пост) приводят к одному и тому же классу алгоритмическивычислимых функций [6]

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

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

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

1. Нуль- функция: <img src="/cache/referats/20085/image012.gif" v:shapes="_x0000_i1030">

2. Функция следования: <img src="/cache/referats/20085/image014.gif" v:shapes="_x0000_i1031">

3. Функция выборааргументов: <img src="/cache/referats/20085/image016.gif" v:shapes="_x0000_i1032">

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

Операция суперпозиции. Пусть даны <img src="/cache/referats/20085/image002.gif" v:shapes="_x0000_i1033"><img src="/cache/referats/20085/image018.gif" v:shapes="_x0000_i1034"> и <img src="/cache/referats/20085/image002.gif" v:shapes="_x0000_i1035"> функций <img src="/cache/referats/20085/image020.gif" v:shapes="_x0000_i1036"><img src="/cache/referats/20085/image020.gif" v:shapes="_x0000_i1037"> зависят от одних и техже переменных <img src="/cache/referats/20085/image023.gif" v:shapes="_x0000_i1038">.Это можносделать путем введения фиктивных переменных. Суперпозицией (подстановкой)функций <img src="/cache/referats/20085/image018.gif" v:shapes="_x0000_i1039"> и <img src="/cache/referats/20085/image020.gif" v:shapes="_x0000_i1040"> называется функция

Функция <img src="/cache/referats/20085/image028.gif" v:shapes="_x0000_i1042"> на наборе переменных <img src="/cache/referats/20085/image030.gif" v:shapes="_x0000_i1043"> определена тогда и толькотогда, когда определены все функции <img src="/cache/referats/20085/image032.gif" v:shapes="_x0000_i1044"> и функция <img src="/cache/referats/20085/image028.gif" v:shapes="_x0000_i1045"> определена на наборе <img src="/cache/referats/20085/image032.gif" v:shapes="_x0000_i1046">Операциюсуперпозиции обозначают: <img src="/cache/referats/20085/image035.gif" v:shapes="_x0000_i1047">

Операция рекурсии(точнее: примитивнойрекурсии). Пусть заданы <img src="/cache/referats/20085/image002.gif" v:shapes="_x0000_i1048"><img src="/cache/referats/20085/image037.gif" v:shapes="_x0000_i1049"> и <img src="/cache/referats/20085/image039.gif" v:shapes="_x0000_i1050"><img src="/cache/referats/20085/image041.gif" v:shapes="_x0000_i1051"><img src="/cache/referats/20085/image043.gif" v:shapes="_x0000_i1052"><img src="/cache/referats/20085/image045.gif" v:shapes="_x0000_i1053"> индуктивным образом спомощью соотношений:

<img src="/cache/referats/20085/image047.gif" v:shapes="_x0000_i1054">;

Ясно, что данные соотношенияоднозначно определяют функцию <img src="/cache/referats/20085/image045.gif" v:shapes="_x0000_i1056"><img src="/cache/referats/20085/image051.gif" v:shapes="_x0000_i1057"> считается определённой в том и тольков том случае, когда определены <img src="/cache/referats/20085/image053.gif" v:shapes="_x0000_i1058"> и <img src="/cache/referats/20085/image055.gif" v:shapes="_x0000_i1059"> при <img src="/cache/referats/20085/image057.gif" v:shapes="_x0000_i1060"><img src="/cache/referats/20085/image059.gif" v:shapes="_x0000_i1061"> неопределено, то и <img src="/cache/referats/20085/image061.gif" v:shapes="_x0000_i1062"> неопределено при <img src="/cache/referats/20085/image063.gif" v:shapes="_x0000_i1063">Про функцию <img src="/cache/referats/20085/image045.gif" v:shapes="_x0000_i1064"> говорят, чтоона получена рекурсией из функций <img src="/cache/referats/20085/image018.gif" v:shapes="_x0000_i1065"> и <img src="/cache/referats/20085/image028.gif" v:shapes="_x0000_i1066"><img src="/cache/referats/20085/image066.gif" v:shapes="_x0000_i1067">

Операция минимизации. Пусть задана <img src="/cache/referats/20085/image002.gif" v:shapes="_x0000_i1068"><img src="/cache/referats/20085/image037.gif" v:shapes="_x0000_i1069"><img src="/cache/referats/20085/image069.gif" v:shapes="_x0000_i1070"> и рассмотрим уравнениеотносительно <img src="/cache/referats/20085/image071.gif" v:shapes="_x0000_i1071">

<img src="/cache/referats/20085/image073.gif" v:shapes="_x0000_i1072">.

Будем решать данное уравнение, вычисляяпоследовательно <img src="/cache/referats/20085/image075.gif" v:shapes="_x0000_i1073"><img src="/cache/referats/20085/image077.gif" v:shapes="_x0000_i1074"><img src="/cache/referats/20085/image079.gif" v:shapes="_x0000_i1075"> и т.д. и сравниваяс <img src="/cache/referats/20085/image081.gif" v:shapes="_x0000_i1076">Наименьшее<img src="/cache/referats/20085/image071.gif" v:shapes="_x0000_i1077">длякоторого выполнено уравнение обозначим <img src="/cache/referats/20085/image084.gif" v:shapes="_x0000_i1078"><img src="/cache/referats/20085/image071.gif" v:shapes="_x0000_i1079"> определено, если <img src="/cache/referats/20085/image086.gif" v:shapes="_x0000_i1080"> определено при всех <img src="/cache/referats/20085/image088.gif" v:shapes="_x0000_i1081"><img src="/cache/referats/20085/image071.gif" v:shapes="_x0000_i1082"> неопределено. Значение<img src="/cache/referats/20085/image071.gif" v:shapes="_x0000_i1083"> есть функция <img src="/cache/referats/20085/image045.gif" v:shapes="_x0000_i1084"> от переменных <img src="/cache/referats/20085/image090.gif" v:shapes="_x0000_i1085">, про которуюговорят, что она получена из <img src="/cache/referats/20085/image018.gif" v:shapes="_x0000_i1086"> минимизацией и обозначают: <img src="/cache/referats/20085/image093.gif" v:shapes="_x0000_i1087">.

Функция называется частично-рекурсивной,если она может быть получена из базисных функций <img src="/cache/referats/20085/image095.gif" v:shapes="_x0000_i1088">,<img src="/cache/referats/20085/image097.gif" v:shapes="_x0000_i1089">,<img src="/cache/referats/20085/image099.gif" v:shapes="_x0000_i1090"> применением конечногочисла раз операций суперпозиции, рекурсии и минимизации.

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

Определение [9].Функция называется алгоритмически вычислимой, если существует алгоритмнахождения значения функции при любом допустимом значении аргумента.

Очевидно, что функции<img src="/cache/referats/20085/image095.gif" v:shapes="_x0000_i1091">,<img src="/cache/referats/20085/image097.gif" v:shapes="_x0000_i1092"> и <img src="/cache/referats/20085/image099.gif" v:shapes="_x0000_i1093"> алгоритмически вычислимы.Можно доказать, что операции суперпозиции, рекурсии и минимизации сохраняют свойствовычислимости [10].Значит, все частично рекурсивные функции вычислимы. Тезис Чёрча утверждает, чтокласс алгоритмически вычислимых функций совпадает с классом всех частичнорекурсивных функций. То есть выполняется и обратное включение: все вычислимые функциичастично рекурсивны. Принятие данного тезиса позволяет истолковыватьдоказательство, что некоторая функция не является частично рекурсивной, какдоказательство отсутствия алгоритма вычисления ее значений.

Аппарат частичнорекурсивных функций позволяет исследовать общие алгоритмические проблемы. Дляэтого используется метод характеристик. Он заключается в следующем. Поконкретной задаче строится соответствующая характеристическая функция, которая затемизучается на вычислимость. Вычислимость её позволяет утверждать разрешимостьисходной проблемы. Пусть, например, стоит проблема разрешения предиката [11].То есть если задан <img src="/cache/referats/20085/image002.gif" v:shapes="_x0000_i1094"><img src="/cache/referats/20085/image101.gif" v:shapes="_x0000_i1095">

<img src="/cache/referats/20085/image103.gif" v:shapes="_x0000_i1096"> или доказать, что такого алгоритма нет. Составляем характеристическую функцию:

Теперь если функция <img src="/cache/referats/20085/image107.gif" v:shapes="_x0000_i1098"> не частичнорекурсивна, то искомого алгоритма не существует. А доказательство частичнойрекурсивности сразу даёт рекурсивный алгоритм разрешения предиката.

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

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

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

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

1.Умножение <img src="/cache/referats/20085/image002.gif" v:shapes="_x0000_i1099"><img src="/cache/referats/20085/image002.gif" v:shapes="_x0000_i1100"><img src="/cache/referats/20085/image110.gif" v:shapes="_x0000_i1101"> битовых операций.Предложим рекурсивный алгоритм для данной задачи. Пусть <img src="/cache/referats/20085/image112.gif" v:shapes="_x0000_i1102"> и <img src="/cache/referats/20085/image071.gif" v:shapes="_x0000_i1103"> — два <img src="/cache/referats/20085/image002.gif" v:shapes="_x0000_i1104"><img src="/cache/referats/20085/image114.gif" v:shapes="_x0000_i1105"><img src="/cache/referats/20085/image112.gif" v:shapes="_x0000_i1106"> и <img src="/cache/referats/20085/image071.gif" v:shapes="_x0000_i1107"> на две равные части ввиде <img src="/cache/referats/20085/image116.gif" v:shapes="_x0000_i1108"><img src="/cache/referats/20085/image118.gif" v:shapes="_x0000_i1109"> и будем рассматриватькаждую часть как <img src="/cache/referats/20085/image120.gif" v:shapes="_x0000_i1110"><img src="/cache/referats/20085/image122.gif" v:shapes="_x0000_i1111"> можно представить ввиде

Равенство дает способ вычисления произведения <img src="/cache/referats/20085/image122.gif" v:shapes="_x0000_i1113"> с помощью четырех умножении<img src="/cache/referats/20085/image120.gif" v:shapes="_x0000_i1114">

<img src="/cache/referats/20085/image127.gif" v:shapes="_x0000_i1115">,

где <img src="/cache/referats/20085/image129.gif" v:shapes="_x0000_i1116"><img src="/cache/referats/20085/image131.gif" v:shapes="_x0000_i1117"><img src="/cache/referats/20085/image133.gif" v:shapes="_x0000_i1118">Ясно, что операции сложения исдвига имеют сложность <img src="/cache/referats/20085/image110.gif" v:shapes="_x0000_i1119">.

Заметим, что <img src="/cache/referats/20085/image135.gif" v:shapes="_x0000_i1120"> и <img src="/cache/referats/20085/image137.gif" v:shapes="_x0000_i1121"> имеют, вообще говоря, <img src="/cache/referats/20085/image139.gif" v:shapes="_x0000_i1122"> разрядов. Тогда

запишем равенства <img src="/cache/referats/20085/image141.gif" v:shapes="_x0000_i1123"><img src="/cache/referats/20085/image143.gif" v:shapes="_x0000_i1124"> и, следовательно, <img src="/cache/referats/20085/image145.gif" v:shapes="_x0000_i1125"><img src="/cache/referats/20085/image147.gif" v:shapes="_x0000_i1126"> находится с помощьюрекурсивного алгоритма на задачах размера <img src="/cache/referats/20085/image120.gif" v:shapes="_x0000_i1127"><img src="/cache/referats/20085/image110.gif" v:shapes="_x0000_i1128"><img src="/cache/referats/20085/image149.gif" v:shapes="_x0000_i1129"> или <img src="/cache/referats/20085/image151.gif" v:shapes="_x0000_i1130">либостепень числа 2.

Таким образом, числоиспользуемых операций <img src="/cache/referats/20085/image153.gif" v:shapes="_x0000_i1131"> ограничено сверху

где <img src="/cache/referats/20085/image157.gif" v:shapes="_x0000_i1133"> — постоянная, отражающая число сложений и сдвигов валгоритме. Докажем по индукции, что отсюда следует формула <img src="/cache/referats/20085/image159.gif" v:shapes="_x0000_i1134"><img src="/cache/referats/20085/image161.gif" v:shapes="_x0000_i1135"> начальные условиявыполнены. Пусть для <img src="/cache/referats/20085/image002.gif" v:shapes="_x0000_i1136"> формула есть решение рекурсивногосоотношения. Тогда имеем <img src="/cache/referats/20085/image163.gif" v:shapes="_x0000_i1137"> (здесь использованоравенство <img src="/cache/referats/20085/image165.gif" v:shapes="_x0000_i1138">.).Таким образом явная формула справедлива для <img src="/cache/referats/20085/image167.gif" v:shapes="_x0000_i1139">

Ясно, что <img src="/cache/referats/20085/image169.gif" v:shapes="_x0000_i1140"> и данный алгоритмлучше по порядку исходного «наивного» алгоритма. Заметим, что для данной задачиизвестны и более лучшие алгоритмы [12].

2.Умножение матриц. Даны две квадратные матрицы порядка <img src="/cache/referats/20085/image002.gif" v:shapes="_x0000_i1141"> с элементами из некоторогокольца <img src="/cache/referats/20085/image171.gif" v:shapes="_x0000_i1142"> и требуетсянайти их произведение. Стандартный алгоритмтребует <img src="/cache/referats/20085/image173.gif" v:shapes="_x0000_i1143"> умножений и <img src="/cache/referats/20085/image175.gif" v:shapes="_x0000_i1144">К. На первый взгляд, кажется, чтоневозможно сколько-нибудь существенно уменьшить данное число операций, Однако, В.Штрассеном [13] былпредложен следующий алгоритм.

Пусть <img src="/cache/referats/20085/image161.gif" v:shapes="_x0000_i1145">

Пусть <img src="/cache/referats/20085/image178.gif" v:shapes="_x0000_i1146"> и даны матрицы <img src="/cache/referats/20085/image180.gif" v:shapes="_x0000_i1147"><img src="/cache/referats/20085/image182.gif" v:shapes="_x0000_i1148"><img src="/cache/referats/20085/image184.gif" v:shapes="_x0000_i1149"><img src="/cache/referats/20085/image186.gif" v:shapes="_x0000_i1150"> может быть вычисленатак. Пусть <img src="/cache/referats/20085/image188.gif" v:shapes="_x0000_i1151"><img src="/cache/referats/20085/image190.gif" v:shapes="_x0000_i1152"><img src="/cache/referats/20085/image192.gif" v:shapes="_x0000_i1153"><img src="/cache/referats/20085/image194.gif" v:shapes="_x0000_i1154"><img src="/cache/referats/20085/image196.gif" v:shapes="_x0000_i1155"><img src="/cache/referats/20085/image198.gif" v:shapes="_x0000_i1156"><img src="/cache/referats/20085/image200.gif" v:shapes="_x0000_i1157"><img src="/cache/referats/20085/image202.gif" v:shapes="_x0000_i1158"><img src="/cache/referats/20085/image204.gif" v:shapes="_x0000_i1159"><img src="/cache/referats/20085/image206.gif" v:shapes="_x0000_i1160">, <img src="/cache/referats/20085/image208.gif" v:shapes="_x0000_i1161">.

Заметим, в данномалгоритме использовано 7 умножений и 18 сложений и не использованакоммутативность умножения.

Пусть теперь <img src="/cache/referats/20085/image210.gif" v:shapes="_x0000_i1162"><img src="/cache/referats/20085/image212.gif" v:shapes="_x0000_i1163"> и <img src="/cache/referats/20085/image214.gif" v:shapes="_x0000_i1164"> порядка <img src="/cache/referats/20085/image216.gif" v:shapes="_x0000_i1165"> представляются как <img src="/cache/referats/20085/image218.gif" v:shapes="_x0000_i1166"><img src="/cache/referats/20085/image220.gif" v:shapes="_x0000_i1167"> и применяетсяизложенный выше алгоритм умножения <img src="/cache/referats/20085/image218.gif" v:shapes="_x0000_i1168"><img src="/cache/referats/20085/image222.gif" v:shapes="_x0000_i1169"><img src="/cache/referats/20085/image157.gif" v:shapes="_x0000_i1170">, что <img src="/cache/referats/20085/image225.gif" v:shapes="_x0000_i1171"> и к матрицамдобавляется нужное число нулевых строк и столбцов.

Пусть <img src="/cache/referats/20085/image227.gif" v:shapes="_x0000_i1172"> — число арифметическихопераций, используемых в алгоритме на матрицах размера <img src="/cache/referats/20085/image220.gif" v:shapes="_x0000_i1173"><img src="/cache/referats/20085/image229.gif" v:shapes="_x0000_i1174"> и <img src="/cache/referats/20085/image231.gif" v:shapes="_x0000_i1175"><img src="/cache/referats/20085/image233.gif" v:shapes="_x0000_i1176"><img src="/cache/referats/20085/image235.gif" v:shapes="_x0000_i1177"> и <img src="/cache/referats/20085/image237.gif" v:shapes="_x0000_i1178"> формула справедлива.Пусть для <img src="/cache/referats/20085/image157.gif" v:shapes="_x0000_i1179"> формула действительноследует из соотношений. Имеем при <img src="/cache/referats/20085/image239.gif" v:shapes="_x0000_i1180"><img src="/cache/referats/20085/image241.gif" v:shapes="_x0000_i1181"> т.е. наша формула справедливаи для <img src="/cache/referats/20085/image239.gif" v:shapes="_x0000_i1182"><img src="/cache/referats/20085/image243.gif" v:shapes="_x0000_i1183"><img src="/cache/referats/20085/image245.gif" v:shapes="_x0000_i1184">

Рассмотрим теперь в общемвиде вопрос о сложности алгоритмов, использующих рекурсию. Из приведенных вышепримеров, ясно, что сложность рекурсивных алгоритмов выражается рекуррентнымисоотношениями. Если в рекурсивном алгоритме используется одна процедура, тозначение сложности <img src="/cache/referats/20085/image247.gif" v:shapes="_x0000_i1185"><img src="/cache/referats/20085/image249.gif" v:shapes="_x0000_i1186"><img src="/cache/referats/20085/image251.gif" v:shapes="_x0000_i1187"> для аргументов <img src="/cache/referats/20085/image253.gif" v:shapes="_x0000_i1188"> где <img src="/cache/referats/20085/image255.gif" v:shapes="_x0000_i1189"><img src="/cache/referats/20085/image249.gif" v:shapes="_x0000_i1190"> разбивается на <img src="/cache/referats/20085/image157.gif" v:shapes="_x0000_i1191"> подзадач размера <img src="/cache/referats/20085/image257.gif" v:shapes="_x0000_i1192"><img src="/cache/referats/20085/image157.gif" v:shapes="_x0000_i1193"> — некотораяфиксированная константа в рекурсивном алгоритме, при этом функция сложности <img src="/cache/referats/20085/image247.gif" v:shapes="_x0000_i1194"> определяетсярекуррентным соотношением вида:

где <img src="/cache/referats/20085/image261.gif" v:shapes="_x0000_i1196"> — константа, <img src="/cache/referats/20085/image263.gif" v:shapes="_x0000_i1197"><img src="/cache/referats/20085/image265.gif" v:shapes="_x0000_i1198"> — неотрицательные, целочисленные, монотонныефункции, характеризующие сложность получения решения исходной задачи размера <img src="/cache/referats/20085/image249.gif" v:shapes="_x0000_i1199"> из <img src="/cache/referats/20085/image157.gif" v:shapes="_x0000_i1200"> решений подзадачразмера <img src="/cache/referats/20085/image257.gif" v:shapes="_x0000_i1201"><img src="/cache/referats/20085/image247.gif" v:shapes="_x0000_i1202"> только при значенияхаргументов <img src="/cache/referats/20085/image249.gif" v:shapes="_x0000_i1203"> вида <img src="/cache/referats/20085/image267.gif" v:shapes="_x0000_i1204"><img src="/cache/referats/20085/image269.gif" v:shapes="_x0000_i1205"> Для практическихприложений представляет интерес выделение случаев, когда решение <img src="/cache/referats/20085/image247.gif" v:shapes="_x0000_i1206"> ограничено сверхуполиномом от <img src="/cache/referats/20085/image249.gif" v:shapes="_x0000_i1207">

Легко доказывается, что еслифункция <img src="/cache/referats/20085/image263.gif" v:shapes="_x0000_i1208"> удовлетворяет условию:существует <img src="/cache/referats/20085/image271.gif" v:shapes="_x0000_i1209"><img src="/cache/referats/20085/image273.gif" v:shapes="_x0000_i1210"> для всех натуральных <img src="/cache/referats/20085/image249.gif" v:shapes="_x0000_i1211"><img src="/cache/referats/20085/image247.gif" v:shapes="_x0000_i1212"> не мажорируется сверхуникаким полиномом от <img src="/cache/referats/20085/image249.gif" v:shapes="_x0000_i1213"> [14].Таким образом, в дальнейшем ограничимся случаем <img src="/cache/referats/20085/image275.gif" v:shapes="_x0000_i1214">

<img src="/cache/referats/20085/image277.gif" v:shapes="_x0000_i1215">где<img src="/cache/referats/20085/image279.gif" v:shapes="_x0000_i1216"><img src="/cache/referats/20085/image281.gif" v:shapes="_x0000_i1217"><img src="/cache/referats/20085/image283.gif" v:shapes="_x0000_i1218"> — фиксированные целыечисла.

Теперь можно доказать,что справедливо следующее утверждение [15].Пусть дано рекуррентное соотношение

где <img src="/cache/referats/20085/image279.gif" v:shapes="_x0000_i1220"><img src="/cache/referats/20085/image281.gif" v:shapes="_x0000_i1221"><img src="/cache/referats/20085/image261.gif" v:shapes="_x0000_i1222"><img src="/cache/referats/20085/image157.gif" v:shapes="_x0000_i1223"><img src="/cache/referats/20085/image283.gif" v:shapes="_x0000_i1224"> — фиксированныеконстанты. Тогда при <img src="/cache/referats/20085/image288.gif" v:shapes="_x0000_i1225"><img src="/cache/referats/20085/image269.gif" v:shapes="_x0000_i1226">

Далее вытекаетследствие [16],что в предположениях предыдущего утверждения справедливы соотношения

В некоторых случаяхрекурсию для задачи размера <img src="/cache/referats/20085/image249.gif" v:shapes="_x0000_i1229"> удаётся организоватьтолько путем аддитивного уменьшения исходного размера задачи <img src="/cache/referats/20085/image249.gif" v:shapes="_x0000_i1230"> на некоторую константу<img src="/cache/referats/20085/image157.gif" v:shapes="_x0000_i1231"><img src="/cache/referats/20085/image247.gif" v:shapes="_x0000_i1232"> такого типарекурсивных алгоритмов определяется рекуррентным соотношением вида

где <img src="/cache/referats/20085/image279.gif" v:shapes="_x0000_i1234"><img src="/cache/referats/20085/image281.gif" v:shapes="_x0000_i1235"><img src="/cache/referats/20085/image261.gif" v:shapes="_x0000_i1236"><img src="/cache/referats/20085/image157.gif" v:shapes="_x0000_i1237"><img src="/cache/referats/20085/image283.gif" v:shapes="_x0000_i1238"> — фиксированныеконстанты. Например, такая ситуация возникает при решении графических задач.Для такого соотношения при <img src="/cache/referats/20085/image296.gif" v:shapes="_x0000_i1239"><img src="/cache/referats/20085/image269.gif" v:shapes="_x0000_i1240">[17]

В некоторых случаях дляорганизации рекурсии используется «квадратичное» разбиение, при которомисходная задача размера <img src="/cache/referats/20085/image249.gif" v:shapes="_x0000_i1242"> разбивается на <img src="/cache/referats/20085/image300.gif" v:shapes="_x0000_i1243"> подзадач размера <img src="/cache/referats/20085/image300.gif" v:shapes="_x0000_i1244"><img src="/cache/referats/20085/image247.gif" v:shapes="_x0000_i1245"> рекурсивного алгоритмавозникает следующее рекуррентное уравнение

где <img src="/cache/referats/20085/image279.gif" v:shapes="_x0000_i1247"><img src="/cache/referats/20085/image281.gif" v:shapes="_x0000_i1248"><img src="/cache/referats/20085/image261.gif" v:shapes="_x0000_i1249"> — фиксированныеконстанты. Оно определяет однозначно функцию <img src="/cache/referats/20085/image247.gif" v:shapes="_x0000_i1250"> при <img src="/cache/referats/20085/image305.gif" v:shapes="_x0000_i1251"> таким выражением [18]

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

Для задачи умноженияматриц использование базового алгоритма умножения <img src="/cache/referats/20085/image309.gif" v:shapes="_x0000_i1253"><img src="/cache/referats/20085/image279.gif" v:shapes="_x0000_i1254"> умножениями дляпостроения рекурсивного алгоритма, сводящего умножение <img src="/cache/referats/20085/image311.gif" v:shapes="_x0000_i1255"><img src="/cache/referats/20085/image313.gif" v:shapes="_x0000_i1256"><img src="/cache/referats/20085/image247.gif" v:shapes="_x0000_i1257">

(в алгоритме Штрассена <img src="/cache/referats/20085/image317.gif" v:shapes="_x0000_i1259"><img src="/cache/referats/20085/image319.gif" v:shapes="_x0000_i1260"><img src="/cache/referats/20085/image321.gif" v:shapes="_x0000_i1261"> и <img src="/cache/referats/20085/image323.gif" v:shapes="_x0000_i1262"> и получил <img src="/cache/referats/20085/image325.gif" v:shapes="_x0000_i1263"><img src="/cache/referats/20085/image327.gif" v:shapes="_x0000_i1264"><img src="/cache/referats/20085/image329.gif" v:shapes="_x0000_i1265"><img src="/cache/referats/20085/image331.gif" v:shapes="_x0000_i1266"><img src="/cache/referats/20085/image333.gif" v:shapes="_x0000_i1267"><img src="/cache/referats/20085/image335.gif" v:shapes="_x0000_i1268"><img src="/cache/referats/20085/image337.gif" v:shapes="_x0000_i1269"><img src="/cache/referats/20085/image339.gif" v:shapes="_x0000_i1270"> еще не решена [19].

Рассмотрим еще один примерприменения полученных результатов. Вернемся к задаче умножения чисел в двоичнойзаписи. Зафиксируем натуральное число <img src="/cache/referats/20085/image341.gif" v:shapes="_x0000_i1271"> и рассмотрим два <img src="/cache/referats/20085/image343.gif" v:shapes="_x0000_i1272"><img src="/cache/referats/20085/image345.gif" v:shapes="_x0000_i1273"> и <img src="/cache/referats/20085/image347.gif" v:shapes="_x0000_i1274">

Разобьем эти числа на <img src="/cache/referats/20085/image353.gif" v:shapes="_x0000_i1277"> частей

<img src="/cache/referats/20085/image357.gif" v:shapes="_x0000_i1279">.

Здесь каждое <img src="/cache/referats/20085/image359.gif" v:shapes="_x0000_i1280"> и <img src="/cache/referats/20085/image361.gif" v:shapes="_x0000_i1281"><img src="/cache/referats/20085/image002.gif" v:shapes="_x0000_i1282"><i

еще рефераты

Еще работы по компьютерам. программированию

Реферат по компьютерам. программированию

Замечательные имена в информатике

29 Августа 2013

Реферат по компьютерам. программированию

Безопасность информационных технологий

29 Августа 2013

Реферат по компьютерам. программированию

Квантование сигналов по времени

29 Августа 2013

Реферат по компьютерам. программированию

Эмуляция командного процессора ОС UNIX в среде Windows 9x

29 Августа 2013