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

    Дисциплина: Программирование
    Тип работы: Курсовая
    Тема: Рекурсивные алгоритмы

    Министерство образования Российской Федерации
    Ставропольский Государственный университет
    Кафедра математического анализа
    Курсовая работа на тему:
    «Рекурсивные алгоритмы»
    Выполнил: студент
    го курса ФМФ специальности ПМИ группы «Б»
    Симонян Сергей Олегович
    Проверил: Ионисян А. Д.
    Ставрополь, 2004 г.
    Содержание
    TOC o \"1-2\" f h z u
    Введение.
    PAGEREF _Toc105389907 h
    Теория рекурсивных алгоритмов.
    PAGEREF _Toc105389918 h
    Дескриптивная теория.
    PAGEREF _Toc105389919 h
    Метрическая теория.
    PAGEREF _Toc105389927 h
    Программная реализация рекурсии.
    PAGEREF _Toc105389930 h
    Общие принципы реализации.
    PAGEREF _Toc105389931 h
    Пример: компилятор
    Turbo
    Pascal 7.0.
    PAGEREF _Toc105389964 h
    Заключение.
    PAGEREF _Toc105389971 h
    Список использованной литературы.
    PAGEREF _Toc105389977 h
    Введение
    Не так давно человечество вступило в новый
    век – век информации и компьютеров. Благодаря бурному развитию научных, технических и технологических исследований стало возможным хранить огромные объёмы данных и
    преобразовывать их со скоростями, которые ещё несколько десятилетий назад могли только сниться. При создании сложных информационных систем перед проектировщиками стали нетривиальные
    задачи, требующие разработки новых концепций программирования.
    Для решения проблем такого рода, особенно при учёте человеческого фактора, возникает необходимость обеспечения понятности алгоритма, так называемой «читабельности» исходного
    кода программы, и как следствие модифицируемости и относительной лёгкости сопровождения конечного программного продукта. Часто этого можно достигнуть включением в
    реализацию приложения рекурсивных подпрограмм, механизмы использования которых предоставляются практически всеми современными компиляторами и средами
    разработки.
    Объект называется рекурсивным, если для своего определения или функционирования он прямо или косвенно обращается к объекту в некотором смысле такого же типа. Так, например, в
    теле рекурсивных подпрограмм, которые будут подробно рассмотрены ниже, в простейшем случае содержится вызов самих себя, но с другими параметрами.
    Рекурсия является одним из наиболее мощных и, наверно, самым общим методом научного познания. Она эффективно применяется во многих прикладных и теоретических
    естественнонаучных дисциплинах, и стала неотъемлемой их частью.
    Этому нетрудно найти множество подтверждений, однако один и тот же по сути метод, применительно к различным областям носит различные названия, такие как индукция, рекурсия или
    рекуррентные соотношения.
    Различия касаются особенностей использования.
    Под индукцией понимается метод доказательства утверждений с формулировкой зависящей от натурального переменного
    или
    и проводится доказательство для
    Термин рекуррентное соотношение связан с американским научным стилем и определяет математическое задание функции с помощью рекурсии.
    Важную роль в теории алгоритмов сыграл аппарат рекурсивных функций, разработанный Алонзо Чёрчем и позволивший ему формализовать понятие алгоритма.
    Последние двадцать лет получили бурное развитие созданная и глубоко развитая Бенуа Мандельбротом фрактальная геометрия, теория мультифракталов и их приложения. Нужно заметить,
    что в теориях понятие рекурсии одно из основных. Так, например, многие фрактальные геометрические фигуры, такие как совершенное канторово множество или салфетка Серпинского,
    определяются рекурсивно
    Как видим, понятие рекурсии очень широко и многогранно. В настоящей работе будет освещён лишь один аспект этого понятия, а именно рекурсивные алгоритмы. Они рассмотрены как с
    позиций теории алгоритмов и теории сложности, так и с точки зрения практического программирования. Читатель сможет узнать, как применять на практике алгоритмы, содержащие рекурсию,
    а главное когда стоит это делать. Важно сохранять баланс между изящностью и простотой восприятия, присущие рекурсивным алгоритмам, и сложностью его реализации на конкретной
    вычислительной системе.
    Теория рекурсивных алгоритмов.
    Дескриптивная теория.
    Задача точного определения понятия алгоритма была полностью решена в 30-х годах
    века в двух формах: на основе описания алгоритмического процесса и на основе понятия рекурсивной функции.
    Первый подход заключался в том, что был сконструирован формальный автомат, способный осуществлять ограниченный набор строго определённых элементарных операций (машина Тьюринга).
    Алгоритмом стали называть конечную последовательность таких операций и постулировали предложение, что любой интуитивный алгоритм является алгоритмом и в сформулированном выше смысле.
    То есть для каждого алгоритма можно подобрать реализующую его машину Тьюринга
    Развитие теории конечных автоматов позволило строго доказать алгоритмическую неразрешимость ряда важных математических проблем (10-й проблемы Гильберта
    , проблемы представимости матриц
    и др.). Однако её существенным недостатком является невозможность реализации такой полезной конструкции как рекурсия.
    Этого недостатка лишён другой подход к формализации понятия алгоритма, развитый Гёделем и Чёрчем. Здесь теория построена на основе широкого класса так называемых частично
    рекурсивных функций
    Замечателен тот факт, что оба данных подхода, а также другие подходы (Марков, Пост) приводят к одному и тому же классу алгоритмически вычислимых функций
    . Поэтому для дальнейшего изложения мы выберем именно теорию частично рекурсивных функций Чёрча, так как она позволяет доказать не только алгоритмическую разрешимость задач, но
    и существование для неё рекурсивного алгоритма.
    Сначала определим и исследуем сам класс частично рекурсивных функций
    . Данный класс определяется путем указания конкретных исходных функций и фиксированного множества операций получения новых функций из заданных.
    В качестве базисных функций обычно берутся следующие:
    1. Нуль- функция:
    2. Функция следования:
    3. Функция выбора аргументов:
    Допустимыми операциями над функциями являются операции суперпозиции (подстановки), рекурсии и минимизации.
    Операция суперпозиции
    . Пусть даны
    функций
    зависят от одних и тех же переменных
    .Это можно сделать путем введения фиктивных переменных. Суперпозицией (подстановкой) функций
    называется функция
    Функция
    на наборе переменных
    определена тогда и только тогда, когда определены все функции
    функция
    определена на наборе
    Операцию суперпозиции обозначают:
    Операция рекурсии
    (точнее: примитивной рекурсии). Пусть заданы
    индуктивным образом с помощью соотношений:
    Ясно, что данные
    соотношения однозначно определяют функцию
    считается определённой в том и только в том случае, когда определены
    при
    неопределено, то и
    неопределено при
    Про функцию
    говорят, что она получена рекурсией из функций
    Операция минимизации
    . Пусть задана
    и рассмотрим уравнение относительно
    Будем решать данное уравнение, вычисляя последовательно
    и т.д. и
    сравнивая с
    Наименьшее
    для которого выполнено уравнение обозначим
    определено, если
    определено при всех
    неопределено. Значение
    есть функция
    от переменных
    , про которую говорят, что она получена и...

    Забрать файл

    Похожие материалы:


ПИШЕМ УНИКАЛЬНЫЕ РАБОТЫ
Заказывайте напрямую у исполнителя!


© 2006-2016 Все права защищены