Дәріс жоспары:
есептелетін функция ұғымы
Рекурсия ұғымы, рекурсивті функция
Компьютер көмегімен есептелетін функциялар теориясы.
Черч тезисі
21-ші ғасырдың ортасына дейін алгоритм ұғымы есептеу әдістері ұғымымен теңестірілді. Есептеу әдістерінде қолданылатын арифметикалық, анализдік, тригонометриялық операциялардың орындалу алгоритм іспеттес болып жүрді. Ондай проблемаларды шешу үшін қосымша арнаулы дәлелдеулердің қажеті болмады. Ал 21-ші ғасырдың 2-ші жартысынан бастап сандық емес объектілерге қолданылатын алгоритмдерге қатаң формулировка берудің болмайтындығы белгілі болды. Лейбництің тұжырымдамасы бойынша алгоритмдік шешілмейтін есептер бар, сондықтан кез келген математикалық тұжырымдамалардың дұрыстығын дәлелдейтін алгоритм құрастыру қажеттігі туындады. Ол барлық теоремалардың дұрыстығын дәлелдейтін болуы керек.
Анықтама. Әлдебір алгоритм көмегімен есептелетін функцияны есептелетін функция дейді.
Іс жүзінде алгоритм – функцияны беру әдісі. Ал функция таблица, схема, формула түрінде берілуі мүмкін. Бірақ кейбір процестерде бастапқы енгізілген немесе берілген деректер мен алынған нәтижедегі деректер арасындағы байланысты ұйымдастыратын функцияны құру қиын, күрделі.
1 – бағыт Рекурсивті функциялар – есептелетін функциялар ұғымымен байланысты.
X және Y жиындары бар болсын. X жиынының кейбір элементтеріне Y жиынының элементтері сәйкес келсе, онда Y – те X – тен бөлшекті функция берілген дейді.
Y жиынында сәйкес элементтері бар және X элементтерден құралған жиынның элементтер жиыны функцияның анықталу облысы деп аталады.
X жиынында сәйкес элеметтері бар Y жиынының элементтер жиыны функцияның мәндер облысы деп аталады.
Егер X –тен Y-тегі функцияның анықталу облысы X жиынымен беттессе, онда ол функцияны барынша анықталған деп атайды.
Осы ұғымға және рекурсивті функцияға негізделіп алгоритмнің дәл анықтамасын құруға болады.
Кез – келген берілген деректерді (үзілісті, дискретті) әлдебір санау жүйесінде натурал сандармен кодтауға болады, онда
Олардың барлық алмастыруы есептеу операцияларының тізбегіне келтіріледі, ал өңдеу нәтижесі солайынша бүтін сан болып қалады. Кез келген алгоритм берілген сандық функция үшін бірдей, оның мәнін есептейді, ал оның элементарлы қадамдары қарапайым арифметикалық және логикалық операциялар болады. Мұндай функциялар есептелетін функциялар деп аталады.
Y(x,,,, x) функция класы бар болсын. Аргументтер бүтін, нәтижеде бүтін сан немесе аргументі де нәтижесі де дискретті болсын.
Y(x,,,, x) функциясы тимді есептелетін функция деп аталады, егер белгілі аргументтер мәндері бойынша оның мәнін есептейтін алгоритм бар болса.
Әр түрлі түсінілетін процесстер үшін есептелетін функциялар тізімі (алгоритмнің барлық қасиеттерін қанағаттандыратын) кәдімгі математикалық терминмен жеңіл сипатталатын функциялар болса, рекурсивті деп аталады.
Кез келген алгоритмдік модель, рекурсивті функция алгоритмнің элементарлы қадамын анықтауы керек, деректерді өңдеуге қажетті алмастыру тізбектерін қанағаттандыруы керек. Рекурсивті модельде мұндай элементарлы қадамдар қарапайым сандық функциялар деп аталады. S
Бұл сандар комбинациясынан күрделі функциялар құрылады:
S(x)=x+1 (бір аргументті бір орынды функция)
O(x,,,, x) =0 –n орынды нөлге теңбе теңдік функциясы.
I(x,,,, x)=X (1) n орынды өз аргументтерінен 1 мәні теңбе теңді қайталану функциясы.
Бұл функциялар барынша анықталған және интуитивті есептелетін функциялар. Бұл функцияларға қолданылатын қасиеттері бірдей барлық операциялар / операторлар қолданылады. Функцияларға осындай операторларды қолдану арқылы алынған бөлшек функцияларда бөлшекті рекурсивті функциялар деп аталады. Бөлшекті рекурсивті функциялар класы арифметикалық есептеулерді жүргізуге болатын функция кластарымен беттеседі.
Бөлшекті функцияның суперпозициясы
m – орынды f функциялар n – орынды g (x,,,, x)
фу нкциясына қойылатын болсын. Нәтижеснде n – орынды функциясы алынады.
Мұны h функциясы g функциясынан суперпозиция арқылы алынды деп айтады.
Мұндай қою - деп берілгенді n- функция саны, олар келесі бір функцияның g-дің аргументтері ретінде қойылып тұр.
Егер функциялары есептелетін болса, n- функциясы да есептеледі. Онда функциялары интуитивті есептелетін болса, n- функциясы да интуитивті есептеледі.
Мысалы:
1) -ді табу керек.
, -ні табу үшін -ді -ге қою керек, ал =0 сонда .
2) -ді табу керек.
N=3-1=2 – нәтиже 2-орынды функция болады:
.
Достарыңызбен бөлісу: |
