«Информатиканың теориялық негіздері»
жүктеу/скачать 0,6 Mb.
|
«Информатиканы теориялы негіздері»
| Кез-келген алгоритм тьюрингтік функционалдық схема арқылы беріліп, сәйкес Тьюринг машинасында жүзеге асырыла алады.
Бұл гипотеза Тьюринг тезисі деген атауға ие болды. Черч тезисі сияқты оны дәлелдеуге болмайды, себебі ол қатаң емес алгоритм ұғымын Тьюринг машинасының қатаң анықтамасымен байланыстырып тұр. Негізінде егер тьюрингтік функционалдық схема арқылы жүзеге аспайтын алгоритмге мысал келтіру мүмкін болса бұл гипотезаны жоққа шығаруға боолады. Бірақ барлық осы кезге дейін белгілі алгоритмдер тьюрингтік функционалдық схема арқылы беріле алады. Марковтың қалыпты алгоритмдері Алгоритм ұғымын жетілдірудің (нақтыландырудың) үшінші қырын қысқаша талдайық. Мағынасы бойынша ол Тьюринг машинасына жақын, бірақ онда қандай-да бір машиналар туралы ойлар қолданылмайды. Алгоритм ауыстарулар жүйесімен беріледі, онда қандай символдар ауыстыруын жасау қажеттігі және бұл ауыстырулар қандай ретпен орындалатыны туралы көрсетіледі. Мұндай қырды А.А.Марковым ұсынған. 50 ж. басында қалыпты алгоритмдер ұғымы енгізілді (Марковтың өзі оларды алгорифмдер деп атаған). Тағы да қандай-да бір А алфавитін қарастырайық. Анықтамалар енгізейік: Сөз – бұл алфавит таңбаларының кез-келген шекті тізбегі. Сөздегі символдар саны оның ұзындығы деп аталады. Ұзындығы нольге тең сөз бос деп аталады. s сөзі q сөзінің ішкі сөзі деп аталады, егер q-ді q=rst түрінде көрсетуге болса, мұндағы r және t сол алфавиттегі кез-келген сөздер (соның ішінде бос сөздер де болады). Енді алгоритм ұғымын анықтауға болады (қатаң емес): А алфавитіндегі алгоритм деп анықталу облысы А алфавитіндегі барлық сөздер жиынының қандай-да бір ішкі жиыны болатын және мәндері сол сияқты А алфавитінің сөздері болатын тиімді есептелінетін функция аталады. Марков алгоритмдерінде бір сөзді басқа сөздің орнына қою алгоритмнің элементар қадамы ретінде қабылданған. Айталық, А алфавитінде Р бастапқы сөзі құрылған болсын. Ол сөзде Pr ішкі сөзі болсын (жалпы жағдайда мұндай сөздер бастапқы сөзде бірнеше болуы мүмкін), сол сияқты сол алфавиттегі қандай-да бір Pk сөзі де болсын. Орнына кою деп бастапқы Р сөзіндегі реті бойынша бірінші Pr ішкі сөзін Pk сөзіне ауыстыру аталады. Орнына қою Pr Pk арқылы бейнеленеді. Осы түрде көрсету алгоритмі орнына қоюлар тізбегі (тізімі) болып табылатын орнына қоюлар жүйесімен беріледі. Егер бұл тізімде Р-ға енетін сол жақ бөлігі бар орнына қоюлар бар болса, онда алғашқысы Р-ға қолданылады, нәтижесінде ол басқа P1 сөзіне өтеді. Оған тағы да ауыстырулар схемасы қолданылады, және т.с.с. процесс екі жағдайда тоқтатылады: немесе тізімде Pn-ге енетін сол жақ бөлігі бар орнына қою табылған жоқ, немесе Pn-ді алу кезінде соңғы орнына қою қолданылды. Мысал 7.10 Айталық, A ={ *,1} алфавиті және жалғыз *1 орнына қою берілсін. Егер P = 11*111*1 бастапқы сөз болса, өңдеу нәтижесін тап. Қалыпты алгоритмді берілген сөзге көрсетілген орнына қоюды қолдану келесі тізбекті беред (астын сызу арқылы түрленуші комбинация көрсетілген): 11*111*1 *1 , яғни, алгоритм бастапқы сөздегі бірліктер санын табады (унарлық санау жүйесінде сандарды қосады). Мысал 7.11 Алфавитте орыс тілінің символдары болсын: A ={а,б…я}. Келесі түрлендірулерді қамтамасыз ететін орнына қоюлар жүйесін табу керек: путь муть, поло мала. Мұндай алгоритмнің папа, пузо бастапқы сөздеріне қолданылу нәтижесін тап. Орнына қоюлар жүйесі түсінікті: п м, о а. Алгоритмді қолдану: папа мапа мама пузо музо муза Мысал 7.12 Үштік санау жүйесінде қосу амалын орындауды қамтамасыз ететін қалыпты алгоритм құрастыр. Алфавит келесі символдардан тұрады: A ={0,1,2,+}; орнына қоюлар жүйесі: 0+1, 1+1, 2+1+10, +1. әртүрлі бастапқы сөздерге алгоритмді қолданамыз:
Әртүрлі қалыпты алгоритмдер бір-бірінен алфавиттерімен және мүмкін орнына қоюлар жүйесімен еренкшеленеді. Марковтың қалыпты алгоритмін кез-келген алгоритмді берудің стандартты формасы ретінде қарастыруға болады. Алгортмді көрсетудің осы түрі алгоритмдер теориясында зерттеулер жүргізу тұрғысынан ғана маңызды емес, Данная форма представления алгоритма важна не только с точки зрения проведения исследований в теории алгоритмов, сол сияқты ол жасанды интеллект жүйелеріндегі мамандандырылған символдық түрлендірулер тіліне негіз болды. Алгоритмдік модельдерді салыстыру Кейбір теориялық мәселелер (мысалы, алгоритмдік шешілу мәселелері) және практика қажеттіліктері (мысалы, ақпаратты атоматты түрде өңдеуді жүзеге асыратын құрылғылардың жұмыс принциптерін құру қажеттілігі) алгоритмнің қатаң анықтамасын құруды қажет етті. Мәселелерді шешудің әртүрлі варианттары абстрактілі алгоритмдік жүйелер деп аталатын жүйелерді құруға алып келді (оларды сол сияқты алгоритмдік модельдер деп те атайды). Олардың толық тізімі келесі суретте көрсетілген. Жеке модельдердің өзара байланысын анықтайық. Сур. 7.3. абстрактілі алгоритмдік жүйелер (модельдер) класы Барлық алгоритмдік есептерді екі үлкен классқа бөлу қарастырылған: біріншісі – бұл функция мәнін есептеумен байланысты есептер; екіншісі – бұл объектінің берілген жиынға тиістілігін тануға байланысты есептер (бұл келесі сұраққа жауап алумен тең: объекттің берілген қасиеттері бар ма?). Бірінші жағдайда Q алгоритмі бастапқы берілгендермен - А алфавитінің негізінде құрылған P сөзімен жұмыс істей бастайды, және шектеулі қадамдардан (түрлендірулерден) кейін Pk = fQ (P) нәтижесін беруі керек. Нәтиже бастапқы сөзге, сол сияқты өңдеу тізіміне, яғни алгоритмнің өзіне тәуелді (функция болып табылады). Мұнда есептеу кең көлемде – алфавиттік түрлендіру ретінде түсіндіріледі. Екінші классқа жатқызылатын есептерде алгоритмді орындау нәтижесінде келесі сұраққа жауап алынады: «xM» айтылымы ақиқат болып табыла ма?» немесе тура солай xM предикатының ақиқаттығы тексеріледі және екі мүмкін нәтиженің біреуі беріледі: АҚИҚАТ немесе ЖАЛҒАН. Бұл классты біріншінің әртүрлілігі деп санауға болады, себебі, предикат – бұл шартына байланысты екі мән қабылдайтын функция. Дегенмен, бұл есептер класын бөлу пайдалы, себебі алгоритмдер теориясының екі маңызды ұғымына әкеледі – есептелінетін функция және шешілетін жиын. Функция есептелінетін деп аталады, егер оның мәнін есептейтін алгоритм бар болса. Жиын шешілетін деп аталады, егер кез-келген объектінің берілген жиынға тиісті немесе тиісті еместігін анықтайтын алгоритм бар болса. Бұл анықтамалар формальды түрде қатаң емес, себебі қандай-да бір функцияның есептелетін функция болатынын немесе болмайтынын алдын ала анықтауға мүмкіндік бермейді (немесе қалай функция сипаты бойынша оның есептелуіне алгоритм құруға болатынын анықтауға болады?). Осы себеппен алгоритмдер теориясын құру үшін барлық бөлікті рекурсиялы функция есептелінетін функция болып табылатындығы туралы Черч тезисі өте маңызды болды. Басқаша айтқанда, егер функцияны қарапайым функциялардан суперпозиция, рекурсия немесе минимизацияның көмегімен құруға болатын болса, онда оны есептейтін алгоритм бар болады. Осындан ары қарай, барлық есептелінетін функция үшін оны есептейтін Тьюринг машинасын құруға болатыны жөнінде айтылған Тьюринг тезисі болды. Пост алгоритмдері де осылайша бөлікті рекурсиялы функциялар көмегімен жүзеге асатын функцияларға келтірілетінін дәлелдеуге болады. Керісінше тұжырым да әділ болады. Кешірек бір алгоритмдік модельдің екіншісіне келтірілетіндігі туралы теорема дәлелденді, оның салдары келесідей тұжырымдамалар болып табылады: «кез-келген рекурсивті функцияларды сәйкес Тьюринг машинасының көмегімен есептеуге болады» немесе «Тьюринг машинасының көмегімен шешілетін кез-келген есеп үшін оны шешетін Марков алгоритмі бар болады». Осылайша барлық модельдер эквивалентті болады. Бұдан терең мағына көруге болады, яғни, ақпаратты өңдеу нәтижесі функция (алгоритм) сипатымен және енетін берілгендермен анықталады, бірақ алгоритмдік модельге байланысты емес. Алгоритмдік шешілу мәселесі
«Алгоритм» термині математикада бұрыннан пайда болды және ұзақ қолданылды – алгоритм деп белгілі қарапайым қадамдар тізбегін орындау арқылы кімнің орындағанына байланыссыз бірмәнді нәтиже алуға болатын процедураны түсінген. Осылайша, өзіндік шешім қабылдау алгоритмнің бар болуына дәлел ретінде қызмет еткен. Бірақ жалпылама түрде шешу мүмкін емес бірқатар математикалық есептер белгілі болатын. Мысал ретінде, үш көне геометриялық есепті алуға болады: бұрыштың үш секциясы туралы, шеңбердің квадратурасы туралы және кубтың екіленуі туралы – олардың біреуі де циркуль және бөліксіз сызғыштың көмегімен шешудің жалпы тәсіліне ие емес. жүктеу/скачать 0,6 Mb. Достарыңызбен бөлісу:
|