Студопедия
Обратная связь


Авиадвигателестроения Административное право Административное право Беларусии Алгебра Архитектура Безопасность жизнедеятельности Введение в профессию «психолог» Введение в экономику культуры Высшая математика Геология Геоморфология Гидрология и гидрометрии Гидросистемы и гидромашины История Украины Культурология Культурология Логика Маркетинг Машиностроение Медицинская психология Менеджмент Металлы и сварка Методы и средства измерений электрических величин Мировая экономика Начертательная геометрия Основы экономической теории Охрана труда Пожарная тактика Процессы и структуры мышления Профессиональная психология Психология Психология менеджмента Современные фундаментальные и прикладные исследования в приборостроении Социальная психология Социально-философская проблематика Социология Статистика Теоретические основы информатики Теория автоматического регулирования Теория вероятности Транспортное право Туроператор Уголовное право Уголовный процесс Управление современным производством Физика Физические явления Философия Холодильные установки Экология Экономика История экономики Основы экономики Экономика предприятия Экономическая история Экономическая теория Экономический анализ Развитие экономики ЕС Чрезвычайные ситуации ВКонтакте Одноклассники Мой Мир Фейсбук LiveJournal Instagram 500-летие Реформации


Рекурсивные функции

Для дальнейшего рассмотрения нам понадобится ряд определений. Пусть имеются два множества X и Y.

Если некоторым элементам множества X поставлены в соответствие однозначно определенные элементы множества Y, то говорят, что задана частичная функцияиз X в Y.

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

Если область определения функции из X в Y совпадает с множеством X, то функция называется всюду определенной.

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

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

Функция у(x1, х2, ..., хп) называется эффективно вычислимой, если существует алгоритм, позволяющий вычислить ее значение по известным значениям аргументов.

Поскольку понятие алгоритма в этом определении берется в интуитивном смысле, то и понятие эффективно вычислимой функции оказывается интуитивным. Тем не менее, при переходе от алгоритмов к вычислимым функциям возникает одно очень существенное обстоятельство. Совокупность процессов, удовлетворяющих условиям 1 - 5 из п. 7.1 и, следовательно, подпадающих под интуитивное понятие алгоритма, весьма обширна и мало обозрима. Напротив, совокупность вычислимых функций для самых разных пониманий процессов, удовлетворяющих перечисленным условиям, оказалась одной и той же и притом легко описываемой в обычных математических терминах. Эта точно описанная совокупность числовых функций, совпадающая с совокупностью всех вычислимых функций при самом широком до сих пор известном понимании алгоритма, носит название совокупности рекурсивных функций.

Любая алгоритмическая модель и, в том числе, рекурсивные функции, должна предусматривать определение элементарных шагов алгоритма и способов построения из них какой-то последовательности преобразований, обеспечивающих необходимую последовательность обработки данных. В рекурсивной модели такими «элементарными шагами» являются так называемые простейшие числовые функции S1, 0n и Imn комбинацией которых строятся все более сложные и которые определяются следующим образом:

· S1(x) = х + 1 - это одноместная (т.е. имеет один аргумент) функция непосредственного следования;

· 0n (х1, х2.....xn) = 0 - это n-местная функция, тождественного равенства нулю;

· Imn (x1,.....xn) = xm (1 ≤ т ≤ n; n = 1, 2, ...) - п-местная функция тождественного повторения значения одного из своих аргументов.

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

Переходим к рассмотрению операторов, обеспечивающих преобразование простейших функций.

Суперпозиция частичных функций

Пусть m-местные функции

подставляются в n-местную функцию g(x1,..., xn). В результате получается n-местная функция

Говорят, что функция h получена из функций g, f1, ..., fn суперпозицией (или подстановкой). Символически такая подстановка обозначается следующим образом: Sn+1(g, f1, ..., fn), где индекс сверху обозначает количество функций, подставляемых в качестве аргументов.

Если умеем вычислять функции g, f1, ..., fn, то функция h также может быть вычислена. Ясно также, что если все функции g, f1, ..., fn всюду определены, то и функция h также всюду определена. Таким образом, если функции g, f1, ..., fn интуитивно вычислимы, то будет интуитивно вычислимой и функция h.





 

Читайте также:

Список литературы

Пример 4.17

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

Энтропия сложного опыта, состоящего из нескольких независимых, равна сумме энтропии отдельных опытов.

Определение системы

Вернуться в оглавление: Теоретические основы информатики

Просмотров: 1552

 
 

© studopedia.ru Не является автором материалов, которые размещены. Но предоставляет возможность бесплатного использования. Есть нарушение авторского права? Напишите нам. Ваш ip: 54.196.91.84