-ДӘРІС. Рекурсивті алгоритмдер

Рекурсивті функциялар

Ары қарай қарастыру үшін бізге бірқатар анықтамалар қажет болады. Айталық, Х және Ү екі жиыны бар болсын.

Егер Х жиынының кейбір элементтеріне Ү жиының бірмәнді анықталған элементтері сәйкестендірілген болса, онда Х-тан Ү-ке жекелеме функция (частичная функия) берілген деп аталады. Ү-те сәйкес элементтері бар Х-тің элементтерінің жиынтығы функияның анықталу облысы деп аталады, ал Х-тің элементтеріне сәйкес келетін Ү-тің элементтерінің жиынтығы функия мәндерінің жиынтығы деп аталады. Егер функцияның Х-тен Ү-ке анықталу облысы Х жиынымен сәйкес келсе, онда функция барлық жерде анықталған деп аталады.

Рекурсивті функия ұғымына сүйеніп алгоритм ұғымын нақты анықтамасын құрудың бастапқы идеясы мынада жатыр: кез-келген берілгендерді (әрине дискретті) қандай-да бір санау жүйесінде натурал сандармен кодтауға болады, және сонда оларды кез-келген жолмен түрлендіру - есептеу операцияларының тізбегіне келтіріледі, ал өңдеу нәтижесі де сол сияқты бүтін санды

Бұл жағдайда осы сандық функцияға бірдей кез-келген алгоритм оның мәнін есептейді, ал оның элементар қадамдары кәдімгі арифметикалық және логикалық амалдар болып табылады. Мұндай функциялар есептелінетін функциялар деп аталады.

Айталық Пусть y(x1, x2, …, xn), типті функциялар класы берілсін, олардың ерекшеліктері функцияның барлық аргументтерінің x1,…, xn бүтінсандылығы және функция мәні у-те бүтін сан арқылы өрнектеледі. Басқаша айтқанда аргументтері мен мәндері дискретті болып табылатын функциялар қарастырылады.

y(x1, x2, …, xn) функциясы тиімді есептелінетін деп аталады, егер оның мәнін аргументтердің белгілі мәндері бойынша есептеуге мүмкіндік беретін алгоритм бар болса.

Бұл анықтамада алгоритм ұғымы интуитивті түрде алынғандықтан, тиімді есептелінетін функция ұғымы да интуитвті болып табылады. Сонда да алгоритмдерден есептелінетін функцияларға өту барысында да бір мағызды жағдай туындайды. Алдыңғы тақырыптарда қарастырған алгоритмнің интуитивті ұғымына сәйкес келетін, 1-5 шарттарды қанағаттандыратын процесстер жиынтығы барынша кең және анық көрінбейді. Керісінше, келтірілген шарттарды қанағакттандыратын, процесстердің әртүрлі түсініктері үшін есептелінетін функциялар бірдей болып табылды және әдеттегі математикалық терминдермен оңай сипатталады. Барлық есептелінетін функциялар жиынтығымен беттесетін, дәл сипатталған сандық функциялар жиынтығы осы кезге дейін белгілі алгоритмнің кең ұғымында рекурсивті функциялар жиынтығы деп аталады.

Кез-келген алгоритмдік модель, оның ішінде рекурсивті функциялар, алгоритмнің қарапайым қадамдарын анықтауды және олардан мәліметтерді өңдеудің қажетті тізбегін қамтамасыз ететін қандай-да бір түрлендірулер тізбегін құру тәсілдерін қарастыруы керек. Рекурсивті модельде мұндай «элементар қадамдар» болып S1, 0n және Imn қарапайым функциялар деп аталатын функциялар табылады. Олардың комбинацияларының көмегімен олардан да күрделірек функциялар құрылады және олар келесідей анықталады:

• 
  S1(x) = x+1 – тікелей ілесудің бірорынды (яғни, бір аргументі бар) функциясы.
  
• 
  0n(x1,x2,…,xn) = 0 – бұл нольге теңдікке ұқсастық n-орынды функциясы.
  
• 
  Imn(x1,…,xn) = xm (1 m n; n=1,2,…) – өзінің аргументтерінің бірінің мәнін ұқсас (тождественного повторения) қайталайтын n-орынды функция.
  

Қарапайым функциялардың түрленуін қамтамасыз ететін операторларды қарастырамыз: Бөлікті функциялардың суперпозициясы

Айталық, m-орынды функциялар

f1(x1,…, xm), f2 (x1,…, xm),…, fn(x1,…, xm)

n-орынды g(x1,…, xn) функциялардың астына қойылсын. Нәтижесінде n-орынды функция алынады

h(x1,…, xn)=g(f1(x1, …, xm),…, fn(x1,…, xm))

Осы жерде h функциясы g, f1, …, fn функцияларынан суперпозициямен (немесеастына қоюмен) алынды деп айтылады. Символды түрде мұндай астына қою келесідей белгіленеді: Sn+1(g,f1,…,fn), мұндағы жоғарғы индекс аргумент ретінде қойылатын функция санын бейнелейді.

Егер біз g, f1, …, fn функциясын есептей алсақ, онда h функциясы да есептелінеді. Осылайша g, f1, …, fn функциялары барлық жерде анықталған болса, онда h функциясы да барлық жерде анықталған. Осылайша егер g, f1, …, fn функциясы итуитивті есептелінетін болса, онда h функциясы да интуитивті есептелінеді.

Мысал 7.1

S2(S1,01) мәнін табу керек.  

Бұл үшін қарапайым 01 функциясының мәні S1 (x)=x+1 -ге қойылу керек. Бірақ 01(x)=0, бұдан , h(x) = S2(S1, 01) = S1(01) = 0+1= 1.

Мысал 7.2

S3(I22,I1 1,01) мәнін табу керек. Бұл жағдайда соңғы функция екіорынды болады (n = 3–1 =2), бұдан h(x1,x2) = I2 2(I11,01) = I22(x1,0) = 0

Примитивті рекурсия

Айталық, қандай-да бір сандық бөлікті функциялар берілсін: n-орынды g(x1, …, xn) және (n + 2)-орынды h(x1,…, xn, k, y). Бұл жерде (n + 1)-орынды бөлікті f функциясы g и h функцияларынан примитивті рекурсия арқылы жасалынды деп айтылады, егер x1,…, xn, y барлық натурал мәндері үшін келесі теңдіктер тура болса:

Анықтама енгізейік.

f(x1,…, xn) бөлікті функциясы примитивті рекурсиялы деп аталады, егер оны суперпозиция және примитивті рекурсия амалдарының аяқталған санымен, тек S1, 0n и Imn қарапайым функциялары арасынан алуға болса.

Егер суперпозиция және примитивті рекурсия амалдарын барлық жерде анықталған функцияларға қолданатын болса, нәтижесінде сол сияқты барлық жерде анықталған функция алынады. Жекелей алғанда барлық примитивті рекурсиялы функциялар барлық жерде анықталған.

Мысал 7.3

f(x,y)=x+y екіорынды функциясы примитивті-рекурсиялы болып табылатынын дәлелдеу керек.

Бұл функция (7.1) түрде көрсетіле алады:

Мысал 7.4

f(3,2) функциясының мәнін табу керек, егер ол келесі қатынастармен берілсе:

Минимизация амалы

Айталық, қандай-да бір f(x,y) функциясы берілсін. Х-тің мәнін бекітіп алып, у-тің қай мәнінде f(x,y)=0 болатынын анықтаймыз. f(x,y)=0 болатындай у-тің мәндерінің ең кішісін іздеу есебі күрделірек болады. Мұндай есепті шешу нәтижесі х-ке тәуелді болғандықтан, у-тің кішісі же х-тің функциясы болып табылады. Белгілеу қолданайық:

(былай оқылады: «f(x,y)=0 болатындай у-тің кіші мәні», ал -ті -оператор немесе минимизация амалы деп аталады).

1. 
   f(x1,…xn,0)-ді есептейміз; егер мән нольге тең болса, (x1,…xn)=0. деп есептейміз. Егер f(x1, …xn,0)  0 болса, онда келесі қадамға өтеміз.
   
2. 
   f(x1,…xn,1) есептейміз; егер мән нольге тең болса, онда (x1,…xn)=1 деп есептейміз. Егер f(x1,… xn,0)  0 болса, онда келесі қадамға өтеміз. Және т.с.с.
   

Мысал 7.5

Анықтама енгізейік:

f(x1,…, xn) бөлікті функциясы бөлікті рекурсиялы деп аталады, егер оны тек S1, 0n және Imn қарапайым функциялар арасынан суперпозиция, примитивті рекурсия және минимизация амалдарының аяқталған санымен алуға болса.

Бөлікті рекурсиялы функциялар класы примитивті рекурсиялы функциялар класынан кең, себебі, барлық примитивті рекурсиялы функциялар барлық жерде анықталған болып табылады, ал бөлікті рекурсиялы функциялар арасында барлық жерде анықталмаған, сол сияқты еш жерде анықталмаған функциялар кездеседі.

Бөлікті рекурсиялы функциялар түсінігі алгоритмдер теориясының негізгі түсініктерінің бірі. Оның маңызы келесіден тұрады: бір жағынан, стандартты түрде берілген әрбір бөлікті рекурсиялы функция алгоритмдерді интуитивті көрсетуге жауап беретін қандай-да бір механикалық сипаттағы процедура жолымен есептеліне алады. Екінші жағынан, тура сызылған қандай алгоритмдер класы құрылмаса да, барлық жағдайда олардың көмегімен есептелінетін сандық функциялар бөлікті рекурсиялы болып табылған. Сондықтан Черч тезисі деп аталатын ғылыми гипотеза жалпықабылданған болып табылады:

Алгоритмдік (немесе машиналық) есептелінетін бөлікті сандық функциялар класы барлық бөлікті рекурсиялы функциялар класымен беттеседі.

Бұл тезис бөлікті рекурсиялы функция ұғымының алгоритмдік түсіндірілуін береді. Оны дәлелдеуге болмайды, себебі ол математикалық қатаң емес интуитивті есептелінетін функция ұғымын қатаң математикалық бөлікті рекурсиялы функциялар ұғымымен байланыстырады. Бірақ бірнеше онжылдықтар көлемінде көптеген математиктердің жүргізген зерттеулері нәтижесінде бөлікті рекурсиялы функция түсінігін есептелінетін бөлікті функциялардың интуитивті ұғымының эквиваленті деп есептеудің толық мақсатқа лайықты екенін анықтады. Черч тезисі алгоритмдік мәселелердің формулировкасына қажетті нақтылық беру үшін және кей жағдайларда олардың шешілмейтіндігін дәлелдеудің мүмкіндігін жасауға жеткілікті болып табылды. Себебі әдеттегі математиканың алгоритмдік мәселерінде алгоритм туралы емес, арнайы үлгімен құрылған функциялардың есептелетіндігі туралы айтылады. Черч тезисіне сүйенсек, функцияның есептелетіндігі туралы сұрақ, оның рекурсивтілігі туралы сұраққа тепе-тең. Функция рекурсивтілігі туралы ұғым қатаң. Сондықтан кәдімгі математикалық техника кейде есепті шешетін функция рекурсивті бола алмайтынын тікелей дәлелдеуге мүмкіндік береді. Тура осы жолмен Черчтің өзіне предикаттар логикасының негізгі алгоритмдік мәселесі – бірінші баспалдақтағы есептеу формулаларының ұқсас ақиқаттығы мәселесінінің шешілмейтіндігін дәлелдеу мүмкін болды.