Авиационно инженерство Административно право Административно право Беларус Алгебра Архитектура Безопасност на живота Въведение в професията „психолог” Въведение в икономиката на културата Висша математика Геология Геоморфология Хидрология и хидрометрия Хидросистеми и хидравлични машини Културология Медицина Психология икономика дескриптивна геометрия Основи на икономически т Oria професионална безопасност Пожарна тактика процеси и структури на мисълта, Професионална психология Психология Психология на управлението на съвременната фундаментални и приложни изследвания в апаратура социалната психология социални и философски проблеми Социология Статистика теоретичните основи на компютъра автоматично управление теория на вероятностите транспорт Закон Turoperator Наказателно право Наказателно-процесуалния управление модерна производствена Физика Физични феномени Философски хладилни инсталации и екология Икономика История на икономиката Основи на икономиката Икономика на предприятията Икономическа история Икономическа теория Икономически анализ Развитие на икономиката на ЕС Спешни ситуации ВКонтакте Однокласници Моят свят Facebook LiveJournal Instagram
border=0

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

За по-нататъшно разглеждане са ни необходими няколко определения. Да предположим, че има два множества X и Y.

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

Множеството от тези елементи на множеството X, които имат съответни елементи в Y, се нарича област на дефиниране на функцията, а множеството от тези елементи на Y, които съответстват на елементите на X, се нарича набор от стойности на функцията.

Ако домейнът на функция от X до Y съвпада с множеството X, тогава функцията се нарича навсякъде дефинирана.

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

Да предположим, че има клас от функции от тип y ( x 1, x 2 , ..., x n ), чиито характеристики са, че всички аргументи на функцията x 1 , ..., x n са цяло число, а стойността на функцията y също се изразява като цяло число. С други думи, се разглеждат функции, чиито аргументи и стойности са дискретни.

Функция y ( x 1 , x 2 , ..., x n ) се нарича ефективно изчислима, ако има алгоритъм, който позволява неговата стойност да бъде изчислена от известните стойности на аргументите.

Тъй като понятието за алгоритъм в тази дефиниция е взето в интуитивен смисъл, понятието за ефективно изчислима функция се оказва интуитивно. Въпреки това при прехода от алгоритми към изчислими функции възниква едно много съществено обстоятелство. Наборът от процеси, отговарящи на условията от 1 до 5 от параграф 7.1 и следователно, попадащи под интуитивната концепция на алгоритъм, е много обширен и не е много видим. Напротив, множеството изчислими функции за много различни разбирания за процеси, отговарящи на изброените условия, се оказват еднакви и освен това лесно се описват в обикновени математически термини. Това точно описано множество от числени функции, което съвпада с множеството на всички изчислими функции с най-широко разбиране на досега известния алгоритъм, се нарича набор от рекурсивни функции.

Всеки алгоритмичен модел, включващ рекурсивни функции, трябва да осигури определянето на елементарните стъпки на алгоритъма и методите за конструиране от тях на някаква последователност от трансформации, които осигуряват необходимата последователност от обработка на данни. В рекурсивния модел такива "елементарни стъпки" са така наречените най - прости числени функции S 1 , 0 n и I m n, чиято комбинация изгражда все по-сложни и дефинирани както следва:

· S 1 ( x ) = x + 1 - това е единична (т.е. има един аргумент) пряка функция;

· 0 n ( x 1 , x 2 ..... x n ) = 0 е n -функцията на мястото, идентична на нула;

· I m n ( x 1 , ..... x n ) = x m (1 ≤ m ≤ n; n = 1, 2, ...) е n- мястото на идентичното повторение на стойността на един от неговите аргументи.

Изброените най-прости функции са дефинирани навсякъде и интуитивно изчислими. Операциите са дефинирани над тях (наричани по-нататък оператори), притежаващи свойството, че тяхното приложение към функции, изчислими в интуитивен смисъл, генерира нови функции, които също са изчислими в интуитивния смисъл. Частичните функции, които могат да бъдат получени с помощта на тези оператори от най-простите функции, се наричат ​​частично рекурсивни. Хипотезата на Църквата е, че класът на частично рекурсивните функции, конструирани по този начин, съвпада с класа на функциите, който позволява алгоритмично изчисление.

Сега ще се обърнем към разглеждане на операторите, които осигуряват трансформацията на най-простите функции.

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

Нека m са местни функции

се заместват в n -функцията на място g (x 1 , ..., x n ). Резултатът е функция n- place.

Функцията h е получена от функциите g, f 1 , ..., f n чрез суперпозиция (или чрез заместване). Символично, такова заместване се обозначава както следва: S n + 1 (g, f 1 , ..., f n ), където индексът по-горе означава броя на функциите, заместени като аргументи.

Ако можем да изчислим функциите g, f 1 , ..., f n , тогава може да се изчисли и функцията h . Ясно е също, че ако всички функции g, f 1 , ..., f n са дефинирани навсякъде, функцията h също е дефинирана навсякъде. Така, ако функциите g, f 1 , ..., f n са интуитивно изчислими, тогава функцията h ще бъде интуитивно изчислима .





Вижте също:

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

Пример А.7

Преобразуване на нормализирани числа

Компютърно кодиране и обработка на реални числа

Тестови въпроси и задачи

Връщане към съдържанието: Теоретични основи на компютърните науки

2019 @ ailback.ru