Алгоритмнің қолданбалы теориясы пәнінен емтихан сұрақтары 25 сұрақ деңгей
жүктеу/скачать 134.63 Kb.
|
| Рекурсивті функциялар.
Алгоритм ұғымын тұрпаттандыру мәселесіне барар тағы бір жол, ол-рекурсивті функциялар. Тарихи бұл жол ең бірінші пайда болды, сондықтан да алгоритмдерге арналған математикалық зертеулерде ол кең таралған. Анықтама 3: Рекурсия дегеніміз, аргументердің белгілі бір мәнінде функцияның мәні функцияның бұған дейін аргументердің өзге мәндерінде берілген мәндері арқылы өрнектелетін функцияның берілу тәсілі. Алгоритмдер теориясында рекурсивті функцияларды қолдану кез келген әріппедегі сөздерді натурал сандар тізбегі арқылы нөмірлеу идеясына негізделген. Осылайша, кез келген алгоритмді аргументтерінің бүтінсандық мәндеріндегі кейбір бүтінсандық функцияның мәндерін есептеуге келтіруге болады. Қарапайым функциялар туралы негізгі ұғымдарды атаңыз. Кез-келген алгоритмдік модель, оның ішінде рекурсивті функциялар, алгоритмнің қарапайым қадамдарын анықтауды және олардан мәліметтерді өңдеудің қажетті тізбегін қамтамасыз ететін қандай-да бір түрлендірулер тізбегін құру тәсілдерін қарастыруы керек. Рекурсивті модельде мұндай «элементар қадамдар» болып S1, 0n және Imn қарапайым функциялар деп аталатын функциялар табылады. Олардың комбинацияларының көмегімен олардан да күрделірек функциялар құрылады және олар келесідей анықталады: S1(x) = x+1 – тікелей ілесудің бірорынды (яғни, бір аргументі бар) функциясы. 0n(x1,x2,…,xn) = 0 – бұл нольге теңдікке ұқсастық n-орынды функциясы. Imn(x1,…,xn) = xm (1 m n; n=1,2,…) – өзінің аргументтерінің бірінің мәнін ұқсас (тождественного повторения) қайталайтын n-орынды функция. Аталған қарапайым функциялар барлық жерде анықталған және интуитвті есептелінеді. Олардың үстінен амалдар анықталған (ары қарай оларды операторлар деп атаймыз). Бұл амалдарды интуитвті есептелінетін функцияларға қолданатын болсақ, итуитивті есептелінетін жаңа функцияларды туындататын қасиеттерге ие. Осы операторлардың көмегімен қарапайым функциялардан алынатын бөлікті функцияларды бөлікті рекурсивті функциялар деп атаймыз. Черч гипотезасының мағынасы мынадай: осылайша құрылған бөлікті рекурсивті функциялар класы алгоримтдік есептелінуі мүмкін функциялар класымен беттеседі. Ішінара функция, жартылай есептелінетін функция ұғымдарға сипаттама беріңіз Ішінара функция f : A ® B есептелетін деп аталады, егер мұндай детерминирленген алгоритм болса, онда A = I, B, K және f(a) = b егер b осы алгоритмді a кірісімен есептеудің нәтижесі болса (бұл алгоритм a кірісіне тоқталуы керек, онда A = I, B, K және F (a) = b f(A) мәні анықталды). Функцияны есептеу міндетінен басқа, жиынның элементтерін тану міндеті қарастырылады. Бұл жағдайда танылатын жиын кейбір негізгі B жиынының (сандар жиыны, матрицалар, жолдар және т.б.) ішкі жиыны болып саналады. Егер оның сипаттамалық функциясы CA: B ® {0,1}есептелсе, A ® B жиыны шешілетін немесе рекурсивті деп аталады Егер оның "жартылай сипаттамалық" функциясы ha: B ® {1}есептелсе, A ® B жиыны жартылай шешілетін деп аталады Кез-келген шешілетін жиынтық жартылай шешілетіні белгілі, бірақ керісінше емес. Жартылай шешілмейтін санау жиындары да бар. Егер ол барлық n натурал сандар жиынында анықталған кейбір есептелетін F функциясының мәндерінің жиыны болса, яғни f(N) = A. натурал сандарды сұрыптау арқылы осы функция арқылы А жиынының кез келген элементін алуға болады (және басқа ештеңе жоқ). Рекурсивті түрде тізімделген кез-келген жиынтық жартылай шешілетіні белгілі және керісінше. Есептелмейтін функция туралы негізгі ұғымдарға сипаттама беріңіз. Есептелетін функциялар-бұл Тьюринг машинасында жүзеге асырылуы мүмкін түрдің көптеген функциялары. Функцияны есептеу мәселесі функцияны есептейтін алгоритмнің мүмкін екендігіне байланысты алгоритмдік шешілетін немесе алгоритмдік шешілмейтін деп аталады. Жартылай рекурсивті функция, примитивті-рекурсивті функция туралы негізгі ұғымдарға сипаттама беріңіз. жүктеу/скачать 134.63 Kb. Достарыңызбен бөлісу:
|