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

Кіріспе

1. Алгоритмдердің өзі емес, тек олардың бар жоқтығы туралы факті ғана қызықтыратын ғалымдарға алгоритмдерді оқудың мүлде қажеті жоқ. Алгоритм іспеттес бар не жоқ объектілерді тапсақ жеткілікті.
Мұндай объектілер рекурсивті функция делінеді. Мұндай алгоритмдер мен қалай байланысыатынын көрсетелік. W шамасын функция деп, х1, х2, х3 шамаларын аргументтер не тәуелсіз айнымалылар деп атаймыз. Егер х1, х2, х3 шамаларының нақты мәніне W шамасының анықталған мәні берілетін заң белгілі болса.
Дербес жағдайда функция тек бір ғана аргументке ие болуы мүмкін. Егер функцияның мәнін алуға болатын болса, ондай функцияларды есептелінетін функция деп атайды.
Рекурсивті функция деп – есептелінетін функцияның жеке бір класын айтады. Олардың тапсырмаларының заңы болып табылатын алгоритмдерді біз рекурсивті функцияға сапарлас алгоритмдер деп атаймыз.
Функцияның үш жағын ажырата білу керек:
1) Функцияның аты (W )
2) Функциональды жазуы W =f(x1, x2,… xn)
3) Функцияның мәні.
Мұнда f - функциональды белгі (таңба) .

1. Базалық функциялардың үш типі:

1) Тәуелсіз айнымалылардың кез келген мәнінде 0-ге тепе-тең
болатын функциялар. Бұларды -деп белгілейді. Мұндағы n-аргументтер саны. Мысалы: мұндай функциялардың қатарына функциялары іспеттес функцияларды алуға болады.

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

2) Тәуелсіз айнымалылардың кез келген мәнінде тепе-тең функциялар.
Оларды деп белгілейміз. Мұндағы n-аргументтер саны; і-аргументтердің бірінің нөмірі, яғни 1 .

Пән: Физика
Жұмыс түрі: Реферат
Тегін: Антиплагиат
Көлемі: 8 бет
Таңдаулыға:

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

Жоспар

1. Рекурсивті функциялар
2. Базалық функцияның типтері
3. алғашқы 0-бойынша тұрғызу, Суперпозиция немесе орнына қою, Рекурсия
операторлары.

1. Алгоритмдердің өзі емес, тек олардың бар жоқтығы туралы факті ғана
қызықтыратын ғалымдарға алгоритмдерді оқудың мүлде қажеті жоқ. Алгоритм
іспеттес бар не жоқ объектілерді тапсақ жеткілікті.
Мұндай объектілер рекурсивті функция делінеді. Мұндай алгоритмдер мен
қалай байланысыатынын көрсетелік. W шамасын функция деп, х1, х2, х3
шамаларын аргументтер не тәуелсіз айнымалылар деп атаймыз. Егер х1, х2, х3
шамаларының нақты мәніне W шамасының анықталған мәні берілетін заң белгілі
болса.
Дербес жағдайда функция тек бір ғана аргументке ие болуы мүмкін. Егер
функцияның мәнін алуға болатын болса, ондай функцияларды есептелінетін
функция деп атайды.
Рекурсивті функция деп – есептелінетін функцияның жеке бір класын
айтады. Олардың тапсырмаларының заңы болып табылатын алгоритмдерді біз
рекурсивті функцияға сапарлас алгоритмдер деп атаймыз.
Функцияның үш жағын ажырата білу керек:
1) Функцияның аты (W )
2) Функциональды жазуы W =f(x1, x2,... xn)
3) Функцияның мәні.
Мұнда f - функциональды белгі (таңба) .

1. Базалық функциялардың үш типі:

1) Тәуелсіз айнымалылардың кез келген мәнінде 0-ге тепе-тең
болатын функциялар. Бұларды -деп белгілейді. Мұндағы n-аргументтер
саны. Мысалы: мұндай функциялардың қатарына функциялары іспеттес
функцияларды алуға болады.

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

2) Тәуелсіз айнымалылардың кез келген мәнінде тепе-тең функциялар.
Оларды деп белгілейміз. Мұндағы n-аргументтер саны; і-
аргументтердің бірінің нөмірі, яғни 1.

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

3)Бір тәуелсіз айнымалының ілесу (келесіні алу) функциясы.
Оларды функциональды белгісі арқылы белгілейді. Мысалы:

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

3.Суперпозиция немесе орнына қою операторы.

Бұл берілген жағдайда екі сөз бір мағынаны береді. Бұл оператор n –
аргументі бар F-функциясынан және f1, f2... fn функцияларынан жаңа Ф-
функциясын тұрғызады. Ол үшін төменде берілген тепе-теңдік ақиқат болу
керек.

Бұл функцияға байланысты алгоритм былай дейді:
f1, f2... fn функцияларының мәнін Ғ-функциясының аргументтерінің мәні деп
қабылдап, Ғ-тің мәнін есептеңіздер. Төмендегі: ::= белгісі анықтама
бойынша былай оқылады: Ф функциясын және fі функциясынан суперпозицияны
төмендегідей түрде жазамыз:Ф::=S[F,f1, f2,...,fn]. Мұндағы S-суперпозиция
белгісі.

Рекурсия операторы

Бұл функция 1-in-1 тәуелсіз айнымалылары бар, 2-сі аталған
айнымалыларға қосымша тағы 2-айнымалысы бар (яғни n+1) екі функция
көмегімен n тәуелсіз айнымалылары бар жаңа функция тұрғызады. Рекурсия
операторын R әріпімен белгілейміз. Оның қолданылуын төмендегідей түрде
жазамыз:
.
Мұндағы -жаңадан алынатын функция f1 n-1; f2 n+1 – тәуелсіз
айнымалысы бар функцияны білдіреді. Х-қосымша аргументтің ішіндегі
негізгісі, у-көмекшісі.
Бұл функцияға байланысты алгоритм былай дейді:
Алынатын жаңа функцияның 0-дік мәндері ретінде n-1 айнымалысы бар
функцияның келесі мәндері ретінде f2 функциясының мәндерін қарастырамыз

Алғашқы 0-бойынша тұрғызу операторы.

Кейбір кітаптарда бұл операторды – ең кіші мәнге ұмтылу операторы деп
те айтады. Бұл оператор берілген функция бойынша (n+1 аргументі бар) жаңа n-
аргументі бар функция тұрғызады. Мұндағы жоғалатын аргумент көмекші
аргумент болып табылады. Бұл операторды әрпімен белгілейміз. Оның
қолданылуын төмендегідей түрде жазамыз.

Мұнда х-жоғалатын аргумент.
Бұл операторға байланысты алгоритм былай дейді:
Көмекші аргументке келесі мәндерді бере отырып (0-ден бастап, берілген
функция мәні 0-ге айналғанша) функцияны 0-ге айналдыру. Көмекші алгоритмнің
алынған мәнін анықталатын функцияның мәні деп қабылдаймыз.
Рекурсивті функциялар деп – базалық функциялар және алғашқы 0-бойынша
тұрғызу, рекурсия және суперпозиция операторының көмегімен алынған кез-
келген функцияны айтамыз. Егер жоғарыдағы аталғандардың ішінде функциялар
алғашқы 0-бойынша тұрғызу операторынсыз алынатын болса, онда ол операторлар
– примитивті рекурсивті функциялар деп аталады.
Егер берілген мәндердің кейбірінде шарттар орындалатын болса, онда
олар – жалпы рекурсивті функциялар деп аталады.
Черч тезисі.
Теріс емес бүтін мәнді функциялардан алынатын кез-келген есептелетін
теріс емес бүтін мәнді функция үшін оған тепе-тең рекурсивті функция бар
болып табылады.
Негізгі тезисі.
Бүтін, теріс емес мәндерді өңдейтін (бүтін, теріс емес мәндерге ) кез-
келген алгоритм үшін рекурсивті функцияларға сапарлас, берілген
алгоритмдерге эквивалентті алгоритм бар болып табылады. Бұл айтылған ойды
орыс ғалымдары – Калмагоров пен Успенский толықтырды.

Көп мүшеліктер теориясы
Жоспар:
1. Көпмүшеліктер теориясы
2. Кардинал сандар

1. Арифметикаландыру арқасында көптеген математикалық ұғымдар әртүрлі
натурал сандар жүйесі арқылы өрнектеледі. Мысалы: кездейсоқ нақты санды
шекті натурал сандар жүйесі ретінде қарастыруға болмайды.Оған көз жеткізу
үшін П-санын алсақ жетікілкті.
Неміс математигі Г.Кантор ұсынған (1874-1897) көпмүшеліктер теориясы
шекті және шексіз заттар жүйесін оқып үйренетін негізгі пән болып табылады.
Бұл теорияның негізгі объектісі – жиын. Жиындар құрамына енетін заттар сол
жиынның элементтері деп аталады. Жиындар теориясы жиынның элементтеріне
қатысты емес қасиеттерін оқып үйретеді. Халық о заманнан әр түрлі нақты
және абстракты заттар жиынымен кездесіп келеді. Мысалы: падашшы сиырлармен,
құрылысшы үйме құммен, математиктер натурал сандардың қатарларымен жұмыс
жасайды.
Заттарды белгілі бір абстракциялау актісі мен байланыстыру біздің
сана сезімімізде өздігінен жүреді. Бұл абстракциялаудың екі жағы бар:
2. Заттар бөлігінің әлсіз әсері (басқа заттарға)не білінеді, не
білінбейді және есептелінбейді.
3. заттар бөлігінің күшті әсері. Заттың толық әсері ретінде қабылданады,
сонымен заттар не қосылады,и не орта мәнге келтіріледі. Бұл
айтылғандарды анайы мысалмен түсіндіруге болады. Мысалы: Мен кездескен
адамды зат ретінде қабылдайтын болсам, онда ол менімен амандасуы
мүмкін, не байқамай соғып кетуі мүмкін. Екі боксерді алатын болсақ,
олар бір-біріне күш жұмсайды.
Әлсіз әсерге мысал: Кездескен адамнан тұмау жұғуы мүмкін.
Әлемнің кейбір бөлігі біз үшін абстракция арқасында бір зат болып
қабылдануы заттың абстракциялануы деп аталады. жазуы а элементінің
А жиынында жататындығын білдіреді.
Жиын идеясында Канторға дейін де еңбектер болды. Жиындарды өзара
салыстыру әдісін – Кантор ойлап тапты. Оның әдісі бойынша жиындар өзара
бір мәнді сәйкестендіру арқылы жүзеге асырылады.
Егер А және В жиындарының арасында өзара бір мәнді сәйкестік орнатуға
болатын болса, онда анықтама бойынша мұндай жиындар тең қуатты жиындар
деп ... жалғасы

Сіз бұл жұмысты біздің қосымшамыз арқылы толығымен тегін көре аласыз.