Алгоритмнің қолданбалы теориясы пәнінен емтихан сұрақтары 25 сұрақ деңгей
жүктеу/скачать 0,9 Mb.
|
Алгоритм 001
| 2 деңгей
Ағаштар, сұрыптау және іздеу ұғымындарына сипаттама беріңіз? Екілік ағашты сұрыптау (екілік ағашты сұрыптау, ағашты сұрыптау, ағашты сұрыптау, екілік ағашты сұрыптау, ағылш. tree sort) - массив (тізім) кілттері бойынша екілік іздеу ағашын құрудан тұратын әмбебап сұрыптау алгоритмі, содан кейін салынған ағаштың түйіндерін қажетті кілттер ретімен айналып өту арқылы алынған массивті құрастыру. Бұл сұрыптау деректерді ағыннан (мысалы, файл, Розетка немесе консоль) тікелей оқу арқылы алу кезінде оңтайлы болып табылады. Жіктеудің тағы бір маңызды белгісі-ағаштарды қолдану (бірақ ағаштың атауы әрдайым дәл осы мақсатта қолданылатындығын білдірмейді). Мысал ретінде іздеу немесе сұрыптау ағаштарын көрсетуге болады, бірақ "іздеу ағашы" атауынан ол тек іздеу үшін қолданылады Бағытталған және бағытталмаған графтар ұғымын түсіндіріңіз? Графтың төбелерінің қандай сызықтарымен қосылатындығы (түзу әлде қисық), сызықтардың ұзындығы туралы ақпараттар маңызды емес.Төбелердің арасында байланыс бар екендігі және ол байланыс туралы ақпарат R доғалар жиынында екендігі болса болды.Төбелерді қосатын сызықтардың бағыты көрсетілген болуы мүмкін (мысалдағы сияқты). Мұндай граф бағытталған граф деп аталады (оргграф). Оған математикалық түрде мынандай анықтама беруге болады. Егер R қатынасы симметриялы болмаса, яғни (a,b)R,(b,а)R онда G= Граф төбелерін айналып өту алгоритмдеріне анықтама беріңіз. Шекті байланысты графта әрбір қабырғасынан бір рет өтуші ориентирленген циклді салуға болады (әрбір бағыт бойынша). Мұндай циклді графтың барлық қабырғаларын айналып өту әдісі деп атайды. Бұл әдіс графтармен байланысты болған көп есептерді шешуде қолданылады. Ориентирленбеген графтың әрбір төбесінен бір рет өтетін шынжырды гамильтон шынжыры деп атайды. Ориентирленбеген графтың әрбір төбесінен тек бір рет өтетін циклді гамильтон циклі деп атайды. Пост машиналары мысалында автоматтар теориясындағы алгоритм ұғымын формализациялау. Тарихи тұрғыдан бір-біріне тәуелсіз туындаған осы тәсілдердің барлығы кейіннен баламалы болып шықты. Алгоритм ұғымын ресімдеудің негізгі мақсаты: әртүрлі математикалық есептердің алгоритмдік шешілу мәселесін шешуге жақындау, яғни.есепті шешуге әкелетін алгоритм құрылуы мүмкін бе деген сұраққа жауап беру. Біз осы мәселенің тұжырымын және есептердің алгоритмдік шешілу теориясының кейбір нәтижелерін қарастырамыз, бірақ алдымен автоматтар теориясындағы алгоритм ұғымын Пост машиналарының мысалында формализациялауды талқылаймыз Абстрактілі (яғни, бар емес, тек қиялда) ораза және Тьюринг машиналары, олар үшін бағдарламалардың қасиеттері туралы әр түрлі пікірлерді дәлелдеуге арналған, 1936 жылы американдық математик Эмиль пост пен ағылшын математигі Аллан Тьюринг дербес (және іс жүзінде бір уақытта) ұсынды. Бұл машиналар бастапқы деректерді "енгізуге" мүмкіндік беретін және нәтижені "оқу" бағдарламаларын орындағаннан кейін толық детерминирленген әмбебап орындаушылар болып табылады. Пост машинасы онша танымал емес, бірақ ол Тьюринг машинасынан әлдеқайда жеңіл. Оның көмегімен компьютерлерге арналған бағдарламаларды құрудың алғашқы дағдыларын үйретуге болады. Абстрактілі пост машинасы-бұл бірдей ұяшықтарға бөлінген шексіз таспа, олардың әрқайсысы бос немесе "V" белгісімен толтырылған болуы мүмкін және таспа бойымен бір ұяшыққа оңға немесе солға жылжи алатын бастар, таспа ұяшығына белгі қойыңыз, егер бұл белгі бұрын болмаған болса,белгіні өшіріңіз, егер ол болса немесе ұяшықта жапсырманың бар-жоғын тексеріңіз. Жапсырмамен толтырылған таспа жасушалары туралы ақпарат машинаның жұмысы кезінде өзгеруі мүмкін таспаның күйін сипаттайды. Уақыттың әр сәтінде бас ( " – " ) таспа жасушаларының бірінің үстінде болады және оны қарап шығады дейді. Нормальды алгоритмге түсінік беріңіз. Марковтың қалыпты алгоритмін кез келген алгоритм берілуінің әмбебап түрі ретінде қарастыруға болады. Қалыпты алгоритмдер әмбебаптығы қалыптастыру принципі арқылы жарияланады: кез келген ақырлы А әріппесінде кез келген алгоритм үшін оған пара-пар А әріппесі бойынша қалыпты алгоритм құруға болады. Соңғы тұжырымды түсіндірейік. Кейбір жағдайларда алмастыруларында тек А әріппесінің әріптерін пайдаланатын болсақ, А әріппесінде берілген алгоритмге эквивалент қалыпты алгоритм құрылмайды. Дегенмен А әріппесін кеңейту арқылы (оған жаңа әріптерді қосу арқылы) қажетті, қалыпты алгоритм құруға болады. Бұл жағдайда, бастапқы А әріппесіндегі сөздерге ғана қолданылатын болса да құрылған алгоритмді А әріппесі бойынша алгоритм дейді. Егер N алгоритмі А әріппесінің кейбір кеңейімінде берілген болса, онда N А әріппесі бойынша қалыпты алгоритм дейді. Нормальды алгоритмдер композициясының тәсілдерін атаңыз. Марковтың қалыпты алгоритмін кез келген алгоритм берілуінің әмбебап түрі ретінде қарастыруға болады. Қалыпты алгоритмдер әмбебаптығы қалыптастыру принципі арқылы жарияланады: кез келген ақырлы А әріппесінде кез келген алгоритм үшін оған пара-пар А әріппесі бойынша қалыпты алгоритм құруға болады. Соңғы тұжырымды түсіндірейік. Кейбір жағдайларда алмастыруларында тек А әріппесінің әріптерін пайдаланатын болсақ, А әріппесінде берілген алгоритмге эквивалент қалыпты алгоритм құрылмайды. Дегенмен А әріппесін кеңейту арқылы (оған жаңа әріптерді қосу арқылы) қажетті, қалыпты алгоритм құруға болады. Бұл жағдайда, бастапқы А әріппесіндегі сөздерге ғана қолданылатын болса да құрылған алгоритмді А әріппесі бойынша алгоритм дейді. Егер N алгоритмі А әріппесінің кейбір кеңейімінде берілген болса, онда N А әріппесі бойынша қалыпты алгоритм дейді. Нормальды алгоритмдерге мысалдар келтіріңіз. Марковтың нормальды алгоритмдерін құруңыз. Қосу және орындау үшін (қалыпты алгоритм) құрыңыз сындарлы натурал сандарды көбейту. Шешім: Конструктивті табиғи қосуды орындау алгоритмі сандар. Алфавитте{0,1,+} қарастырайық. Натурал сандар жұбын қосу үшін біз оларды келесідей орнатамыз сөз түрі 011...1+0111 1 1. Қосу үшін берілген сөзден " + " әрпін тастау жеткілікті "0" әрпі. Сондықтан схема қосудың бір формуласы бар: +0 → ⋅ Біз жұмысты мысалда қанағаттандыратын 0111+011111 сөзін көрсетеміз тапсырма шарттарына: 0111+011111 ├ 0111⋅11111 Егер 1-ші немесе 2-ші термин нөлге тең болса, онда алгоритм де жұмыс істейді: 011...1+0 ├ 011...1⋅ 0+ 011...1├ 0⋅11...1 Егер екі термин де нөлге тең болса: 0+0├ 0⋅ Марковтың қалыпты алгоритмдері және жасанды интеллект бойынша зерттеулердегі ассоциативті есептеулер тәсілдерін атаңыз. Алгоритм ұғымын жетілдірудің (нақтыландырудың) үшінші қырын қысқаша талдайық. Мағынасы бойынша ол Тьюринг машинасына жақын, бірақ онда қандай-да бір машиналар туралы ойлар қолданылмайды. Алгоритм ауыстарулар жүйесімен беріледі, онда қандай символдар ауыстыруын жасау қажеттігі және бұл ауыстырулар қандай ретпен орындалатыны туралы көрсетіледі. Мұндай қырды А.А.Марковым ұсынған. 50 ж. басында қалыпты алгоритмдер ұғымы енгізілді (Марковтың өзі оларды алгорифмдер деп атаған). Үштік санау жүйесінде қосу амалын орындауды қамтамасыз ететін қалыпты алгоритм құрастыр. Алфавит келесі символдардан тұрады: A ={0,1,2,+}; орнына қоюлар жүйесі: 0+1, 1+1, 2+1+10, +1. әртүрлі бастапқы сөздерге алгоритмді қолданамыз:
Әртүрлі қалыпты алгоритмдер бір-бірінен алфавиттерімен және мүмкін орнына қоюлар жүйесімен еренкшеленеді. Марковтың қалыпты алгоритмін кез-келген алгоритмді берудің стандартты формасы ретінде қарастыруға болады. Алгортмді көрсетудің осы түрі алгоритмдер теориясында зерттеулер жүргізу тұрғысынан ғана маңызды емес, Данная форма представления алгоритма важна не только с точки зрения проведения исследований в теории алгоритмов, сол сияқты ол жасанды интеллект жүйелеріндегі мамандандырылған символдық түрлендірулер тіліне негіз болды. Нормальды алгоритмдерді қолдану тәсілдеріне мысал келтіріңіз. Үштік санау жүйесінде қосу амалын орындауды қамтамасыз ететін қалыпты алгоритм құрастыр. Алфавит келесі символдардан тұрады: A ={0,1,2,+}; орнына қоюлар жүйесі: 0+1, 1+1, 2+1+10, +1. әртүрлі бастапқы сөздерге алгоритмді қолданамыз:
Рекурсивті функциялар теориясының негізінде алгоритм ұғымын формализациялауды атаңыз. Қандай да бір меншікті түрде анықталған функция рекурсивті деп аталады. Олардың анықталу облысы – 0 және натурал сандар жиыны. Бір рекурсивті функцияларды екінші рекурсивті функциялар аргументтерінің орнымен алмастыру суперпозиция операциясы деп аталады. Функция примитивті – рекурсивті деп аталады, егер оны элементар рекурсивті функциялардың, саны шектеулі суперпозиция және примитивті – рекурсия операцияларының көмегімен өрнектеуге болса. Функция дербес деп аталады, егер ол аргументтердің барлық мәндерінде анықталмаса. жүктеу/скачать 0,9 Mb. Достарыңызбен бөлісу:
|