«Информатиканың теориялық негіздері»
Функцияның ассимптотикалық анализі
жүктеу/скачать 0.6 Mb.
|
Функцияның ассимптотикалық анализіАлгоритмнің еңбеккөлемділігі функциясының мінез-құлқын талдау кезінде математикада қабылданған функцияның нақты коэффициенттерді бетперделеп, өсу жылдамдығын көрсететін асимптотикалық бейнелеуді жиі қолданады. Алгоритмнің еңбеккөлемділігін осылайша бағалау алгоритм күрделілігі деп аталады және бастапқы берілгендердің үлкен көлемдері үшін қай алгоритмді қолдану керектігін анықтауға мүмкіндік береді. В асимптотическом анализе приняты следующие обозначения: 1. (тетта) бағасы. Айталық, f(n) және g(n) – оң аргументті оң функциялар, n >= 1 (кірістегі объектілер саны және амалдар саны – оң сандар), сонда:
Әдетте мұнда g(n) функциясы f(n)функциясының асимптотикалық нақты бағасы деп айтылады, себебі, f(n)функциясы анықтамасы бойынша g(n) функциясынан тұрақты көбейткіш дәлдігімен айырмашылығы жоқ. Ескерту: f(n) = (g(n)) теңдігінен g(n) = (f(n)) екені шығады. Мысалдар: 1) f(n)=4 +nlnN+174 – f(n)= ( ); 2) f(n)= (1) – жазбасы f(n) немесе нольге тең емес константаға тең, немесе f(n) тұрақтысымен шектелген: f(n) = 7+1/n = (1) дегенді білдіреді. 11-ДӘРІС. Рекурсивті алгоритмдер. Қарастырылатын сұрақтар: "Билеп төсте" түріндегі алгоритм. Рекурсивтік алгоритмнің тиімділігі. Турнирлер әдісі. Рекурсивті функциялар Ары қарай қарастыру үшін бізге бірқатар анықтамалар қажет болады. Айталық, Х және Ү екі жиыны бар болсын. Егер Х жиынының кейбір элементтеріне Ү жиының бірмәнді анықталған элементтері сәйкестендірілген болса, онда Х-тан Ү-ке жекелеме функция (частичная функия) берілген деп аталады. Ү-те сәйкес элементтері бар Х-тің элементтерінің жиынтығы функияның анықталу облысы деп аталады, ал Х-тің элементтеріне сәйкес келетін Ү-тің элементтерінің жиынтығы функия мәндерінің жиынтығы деп аталады. Егер функцияның Х-тен Ү-ке анықталу облысы Х жиынымен сәйкес келсе, онда функция барлық жерде анықталған деп аталады. Рекурсивті функия ұғымына сүйеніп алгоритм ұғымын нақты анықтамасын құрудың бастапқы идеясы мынада жатыр: кез-келген берілгендерді (әрине дискретті) қандай-да бір санау жүйесінде натурал сандармен кодтауға болады, және сонда оларды кез-келген жолмен түрлендіру - есептеу операцияларының тізбегіне келтіріледі, ал өңдеу нәтижесі де сол сияқты бүтін санды Бұл жағдайда осы сандық функцияға бірдей кез-келген алгоритм оның мәнін есептейді, ал оның элементар қадамдары кәдімгі арифметикалық және логикалық амалдар болып табылады. Мұндай функциялар есептелінетін функциялар деп аталады. Айталық Пусть 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 барлық натурал мәндері үшін келесі теңдіктер тура болса:
Функцияның анықталу облысы барлық натурал сандар жиыны болғандықтан, (7.1) шартын қанағаттандыратын f функциясы g және h әрбір бөлікті функция үшін бар болады және бұл функция жалғыз болады. (7.1) шарты рекурсияның әртүрлі қадамдарында f мәнін анықтау тізбегін береді:
Симводы түрде примитивті рекурсия f = R(g,h) түрінде белгіленеді; бұл жазбада R барлық бөлікті функциялар жиынтығында анықталған екіорныды бөлікті амал ретінде қарастырылады. (7.2) қатынасынан, егер g және h барлық жерде анықталған болса, онда f функциясы да барлық жерде анықталғандығы шығады. Сол сияқты (7.2) қатынасынан мындадай маңызды жағдай көрінеді: егер g және h функцияларының мәнін таба алсақ, онда f(a1,…, an,m+1) функциясының мәнін алдыңғы қадамдарда мәнін тізбектей табу арқылы «механикалық» түрде есептеуге болады. Анықтама енгізейік. f(x1,…, xn) бөлікті функциясы примитивті рекурсиялы деп аталады, егер оны суперпозиция және примитивті рекурсия амалдарының аяқталған санымен, тек S1, 0n и Imn қарапайым функциялары арасынан алуға болса. Егер суперпозиция және примитивті рекурсия амалдарын барлық жерде анықталған функцияларға қолданатын болса, нәтижесінде сол сияқты барлық жерде анықталған функция алынады. Жекелей алғанда барлық примитивті рекурсиялы функциялар барлық жерде анықталған. Мысал 7.3 f(x,y)=x+y екіорынды функциясы примитивті-рекурсиялы болып табылатынын дәлелдеу керек. Бұл функция (7.1) түрде көрсетіле алады:
Бұдан, f(x,y) функциясы примитивті рекурсиялы функциялардан примитивті рекурсия амалымен жасалынады, және бұдан оның өзінің примитивті рекурсиялы екені шығады. Мысал 7.4 f(3,2) функциясының мәнін табу керек, егер ол келесі қатынастармен берілсе:
Бұл жағдайда g(x) = 0, h(x,y,z) = y + z. Себебі f(0,x) = g(x) = 0, кез-келген x үшін, онда f(0,2) = 0 болады, ал басқа мәндерді тәзбектей есептеуге болады:
Осы мысалда f(x,y)=x · y болатынын дәлелдеу қиын емес. Минимизация амалы Айталық, қандай-да бір f(x,y) функциясы берілсін. Х-тің мәнін бекітіп алып, у-тің қай мәнінде f(x,y)=0 болатынын анықтаймыз. f(x,y)=0 болатындай у-тің мәндерінің ең кішісін іздеу есебі күрделірек болады. Мұндай есепті шешу нәтижесі х-ке тәуелді болғандықтан, у-тің кішісі же х-тің функциясы болып табылады. Белгілеу қолданайық: (былай оқылады: «f(x,y)=0 болатындай у-тің кіші мәні», ал -ті -оператор немесе минимизация амалы деп аталады). Осылайша көп айнымалысы бар функциялар да анықталады: функциясын есептеу үшін келесі процедураны ұсынуға болады: f(x1,…xn,0)-ді есептейміз; егер мән нольге тең болса, (x1,…xn)=0. деп есептейміз. Егер f(x1, …xn,0) 0 болса, онда келесі қадамға өтеміз. f(x1,…xn,1) есептейміз; егер мән нольге тең болса, онда (x1,…xn)=1 деп есептейміз. Егер f(x1,… xn,0) 0 болса, онда келесі қадамға өтеміз. Және т.с.с. Егер барлық у үшін f(x1,…xn,0) 0 болса, онда (x1,…xn) функциясы анықталмаған деп есептелінеді. Мысал 7.5 Минимизацияның көмегімен алына алатын f(x,y)=x – y функциясын қарастырамыз:
Мысалы f(7,2) есептейік, яғни y = 2 және x = 7 болғандағы функция мәні. y = 2 деп алып, ал x-ке тізбекті мән беріп отырамыз:
Осылайша, f(7,2) = 5 функцияның табылған мәні. Анықтама енгізейік: f(x1,…, xn) бөлікті функциясы бөлікті рекурсиялы деп аталады, егер оны тек S1, 0n және Imn қарапайым функциялар арасынан суперпозиция, примитивті рекурсия және минимизация амалдарының аяқталған санымен алуға болса. Бөлікті рекурсиялы функциялар класы примитивті рекурсиялы функциялар класынан кең, себебі, барлық примитивті рекурсиялы функциялар барлық жерде анықталған болып табылады, ал бөлікті рекурсиялы функциялар арасында барлық жерде анықталмаған, сол сияқты еш жерде анықталмаған функциялар кездеседі. Бөлікті рекурсиялы функциялар түсінігі алгоритмдер теориясының негізгі түсініктерінің бірі. Оның маңызы келесіден тұрады: бір жағынан, стандартты түрде берілген әрбір бөлікті рекурсиялы функция алгоритмдерді интуитивті көрсетуге жауап беретін қандай-да бір механикалық сипаттағы процедура жолымен есептеліне алады. Екінші жағынан, тура сызылған қандай алгоритмдер класы құрылмаса да, барлық жағдайда олардың көмегімен есептелінетін сандық функциялар бөлікті рекурсиялы болып табылған. Сондықтан Черч тезисі деп аталатын ғылыми гипотеза жалпықабылданған болып табылады: Алгоритмдік (немесе машиналық) есептелінетін бөлікті сандық функциялар класы барлық бөлікті рекурсиялы функциялар класымен беттеседі. Бұл тезис бөлікті рекурсиялы функция ұғымының алгоритмдік түсіндірілуін береді. Оны дәлелдеуге болмайды, себебі ол математикалық қатаң емес интуитивті есептелінетін функция ұғымын қатаң математикалық бөлікті рекурсиялы функциялар ұғымымен байланыстырады. Бірақ бірнеше онжылдықтар көлемінде көптеген математиктердің жүргізген зерттеулері нәтижесінде бөлікті рекурсиялы функция түсінігін есептелінетін бөлікті функциялардың интуитивті ұғымының эквиваленті деп есептеудің толық мақсатқа лайықты екенін анықтады. Черч тезисі алгоритмдік мәселелердің формулировкасына қажетті нақтылық беру үшін және кей жағдайларда олардың шешілмейтіндігін дәлелдеудің мүмкіндігін жасауға жеткілікті болып табылды. Себебі әдеттегі математиканың алгоритмдік мәселерінде алгоритм туралы емес, арнайы үлгімен құрылған функциялардың есептелетіндігі туралы айтылады. Черч тезисіне сүйенсек, функцияның есептелетіндігі туралы сұрақ, оның рекурсивтілігі туралы сұраққа тепе-тең. Функция рекурсивтілігі туралы ұғым қатаң. Сондықтан кәдімгі математикалық техника кейде есепті шешетін функция рекурсивті бола алмайтынын тікелей дәлелдеуге мүмкіндік береді. Тура осы жолмен Черчтің өзіне предикаттар логикасының негізгі алгоритмдік мәселесі – бірінші баспалдақтағы есептеу формулаларының ұқсас ақиқаттығы мәселесінінің шешілмейтіндігін дәлелдеу мүмкін болды. жүктеу/скачать 0.6 Mb. Достарыңызбен бөлісу:
|