Алгоритмдер теориясына кіріспе

Кіріспе

Алгоритм ұғымы - математикада вектор, жиын секілді негізгі ұғымдардың бірі. Негізгі ұғымдардың дәл анықтамасы болмайды. Оларды тек интуициямен қабылдаймыз. Дегенімен, осы параграфта алгоритм ұғымын мағыналық тұрғыдан анықтауға тырысамыз.
Көбінесе алгоритм ұғымын берілген элементке сәйкес элементті берілген нұсқаулар арқылы табу деп түсінеміз.
Бірақ бұл анықтама - математикалық тұрғыдан алғанда дәл анықтама емес. Себебі, есептеу, нұсқау ұғымдарының да анықтамасы берілмеген.
Алгоритм ұғымын анықтаудың алдында бірнеше мысалдар келтірейік.
1. (х) = х-ші жай сан. Бұл функцияны есептеуге алгоритм ретінде Эратосфен елегін пайдалануға болады.
2. (х,у) = х пен у-тің ең үлкен ортақ бөлгіші. Бұл жерде Евклид алгоритмі жұмыс істейді.
3. () = , бұл жерде  - көпмүше. Көпмүшелердің туындысы алу алгоритмі мектептен белгілі.
Біз көбінесе тек қана натурал сандарға қолданылатын алгоритмтерді қарастырамыз.
Алгоритмдер төмендегі ортақ қасиеттерімен сипатталады:
1. Алгоритм ақыpлы өлшемді нұсқаулар жиыны ретінде беріледі.
2. Нұсқауларды түсініп, есептеулерді жүргізетін есептегіш (көбінесе адам) болады.
3. Есептеулердің кез келген бөлігін бөліп алуға, жаттауға және кейбір қадамдарын қайталауға мүмкіндіктер бар.
4. Есптегіш нұсқаулар бойынша әр берілген санға сәйкес есептеу кезінде қадамдары дискретті түрде кездейсоқ әдістерсіз жұмыс істейді.
Бұл қасиеттер электронды есептеу машиналарға ұқсастықты көрсетеді. Шынында да
1) машинаның программасы,
2) есептеу құрылысы,
3) жаттау қабілеті,
4) табиғи құрлысы.
Әрине көрсетілген төрт қасиет алгоритмді дәл анықтайды деп айта алмаймыз. Бұл жерде көптеген сұрақтар пайда болады. Солардың бірнешесін қарастырайық.
1) Берілген санның өлшемін шектеу қажет пе?
Егер біз "иә" деп жауап берсек, онда, мысалы, (х) = функциясын есептеудің алгоритмі жоқ болады. Себебі, берілетін сан кез келген ақырлы сан болуы мүмкін. Сондықтан, біз "жоқ" деп жауап береміз және олар тек ақырлы болуы керек дейміз.
2) Нұсқаулардың өлшемін шектеу қажет пе?
Күрделі есептерді шығару үшін біздің нұсқауларымызды шекті деп аламыз, бірақ нұсқаулардың да ақырлы болу керектігін ұмытпаймыз.
3) Жаттау қабілетін шектеу қажет пе?
Алдыңғы екі сұраққа жоқ деп жауап берген соң, бұл сұраққа да "жоқ" деуіміз қажет. Бірақ бір қызығы, кез келген машинаның жаттау қабілеті шектеулі. Дегенмен ол қазіргі керекті есептеулерге жеткілікті.

Пән: Информатика, Программалау, Мәліметтер қоры
Жұмыс түрі: Материал
Тегін: Антиплагиат
Көлемі: 11 бет
Таңдаулыға:

АЛГОРИТМДЕР ТЕОРИЯСЫНА КІРІСПЕ

1 Алгоритм ұғымы

Алгоритм ұғымы - математикада вектор, жиын секілді негізгі ұғымдардың
бірі. Негізгі ұғымдардың дәл анықтамасы болмайды. Оларды тек интуициямен
қабылдаймыз. Дегенімен, осы параграфта алгоритм ұғымын мағыналық тұрғыдан
анықтауға тырысамыз.
Көбінесе алгоритм ұғымын берілген элементке сәйкес элементті берілген
нұсқаулар арқылы табу деп түсінеміз.
Бірақ бұл анықтама - математикалық тұрғыдан алғанда дәл анықтама емес.
Себебі, есептеу, нұсқау ұғымдарының да анықтамасы берілмеген.
Алгоритм ұғымын анықтаудың алдында бірнеше мысалдар келтірейік.
1. ((х) = х-ші жай сан. Бұл функцияны есептеуге алгоритм ретінде Эратосфен
елегін пайдалануға болады.
2. ((х,у) = х пен у-тің ең үлкен ортақ бөлгіші. Бұл жерде Евклид алгоритмі
жұмыс істейді.
3. ((() = , бұл жерде ( - көпмүше. Көпмүшелердің туындысы алу
алгоритмі мектептен белгілі.
Біз көбінесе тек қана натурал сандарға қолданылатын алгоритмтерді
қарастырамыз.
Алгоритмдер төмендегі ортақ қасиеттерімен сипатталады:
1. Алгоритм ақыpлы өлшемді нұсқаулар жиыны ретінде беріледі.
2. Нұсқауларды түсініп, есептеулерді жүргізетін есептегіш (көбінесе
адам) болады.
3. Есептеулердің кез келген бөлігін бөліп алуға, жаттауға және
кейбір қадамдарын қайталауға мүмкіндіктер бар.
4. Есптегіш нұсқаулар бойынша әр берілген санға сәйкес есептеу
кезінде қадамдары дискретті түрде кездейсоқ әдістерсіз жұмыс
істейді.
Бұл қасиеттер электронды есептеу машиналарға ұқсастықты көрсетеді.
Шынында да
1) машинаның программасы,
2) есептеу құрылысы,
3) жаттау қабілеті,
4) табиғи құрлысы.
Әрине көрсетілген төрт қасиет алгоритмді дәл анықтайды деп айта
алмаймыз. Бұл жерде көптеген сұрақтар пайда болады. Солардың бірнешесін
қарастырайық.
1) Берілген санның өлшемін шектеу қажет пе?
Егер біз "иә" деп жауап берсек, онда, мысалы, ((х) = функциясын
есептеудің алгоритмі жоқ болады. Себебі, берілетін сан кез келген ақырлы
сан болуы мүмкін. Сондықтан, біз "жоқ" деп жауап береміз және олар тек
ақырлы болуы керек дейміз.
2) Нұсқаулардың өлшемін шектеу қажет пе?
Күрделі есептерді шығару үшін біздің нұсқауларымызды шекті деп аламыз,
бірақ нұсқаулардың да ақырлы болу керектігін ұмытпаймыз.
3) Жаттау қабілетін шектеу қажет пе?
Алдыңғы екі сұраққа жоқ деп жауап берген соң, бұл сұраққа да "жоқ"
деуіміз қажет. Бірақ бір қызығы, кез келген машинаның жаттау қабілеті
шектеулі. Дегенмен ол қазіргі керекті есептеулерге жеткілікті.

Жаттығулар

Келесі ережелерді алгоритм деп есептеуге болады ма?
1. Бізге n саны берілсін. ((n) мәнін есептеу үшін монетаны лақтырамыз. Егер
елтаңба бар жағы жоғары қараса, онда ((n) = 1; ал егер елтаңба бар жағы
төмен қараса, онда ((n) = 0.
2. Егер ( санының ондық бөлшек түрде жазуында қатар тұрған дәл 2n бірлік
болса, онда ((n) = 1; кері жағдайда ((n) = 0.
3. Егер ( санының ондық бөлшек түрде жазуында қатар тұрған дәл 2n бірлік
болса, онда ((n) = 1; кері жағдайда ((n) анықталмаған.
4. Бізге n саны берілсін. Егер ((n) мәнін бұрын есептелмеген болсақ, онда
біз отырған бөлмеде адам саны тақ болса, ((n) = 1 дейміз; кері жағдайда
((n) = 1 және ((n) мәнін бұрын есептелген деп санаймыз. Ал егер ((n)
бұрын есептелген болса, онда бұрынғы мәнін береміз.
5. Егер ( санының ондық бөлшек түрде жазуында қатар тұрған кем дегенде n
бірлік болса, онда ((n) = 0; кері жағдайда ((n)=1.

6.2 Тьюринг машинасы

Әрине өткен параграфта қойылған сұрақтардың жауаптарын алгоритмнің дәл
анықтамасы ретінде ала алмаймыз. 1936 жылы Тюринг кез келген есептеуді
орындай алады деген жорамалмен теориялық машиналар класын енгізді. Олардың
сипаттамасын берейік.
Көз алдымызға квадратттарға бөлінген ақырлы лентаны елестетейік.
Машинаның алфавиті болып аталатын символдары беріледі. Әр кезде әр
квадратқа бір символ жазылады. Әр кезде квадратта бір символдан артық
болмайды. Машинаның іùкі жағдайлары болып табылатын жиыны болады. Әр
кезде машина сол ішкі жағдайлардың біреуінде ғана болады. Сонымен бірге кез
келген уақытта квадраттардың біреуін ғана қарастыратын оқу тетігі бар.
Машина бір мезетте бір ғана қимыл істейді. Егер машинаның оқу тетігі
қарастырылып тұрған квадратта символы тұрса, ал машинаның ішкі
жағдайы болса, онда ол келесі қимылдардың біреуін істейді:
1. Осы квадраттағы символын өшіріп, символын осы
квадратқа жазады;
2. Оң жақтағы көрші квадратқа көшеді;
3. Сол жақтағы көрші квадратқа көшеді;
4. Тоқтайды.
Алдыңғы үш жағдайда машина басқа ішкі жағдайға көшіп, келесі
қимылға дайын. Екінші немесе үшінші қимыл кезінде көрші квадрат жоқ болса,
онда керек квадрат пайда болады деп есептейміз.
Бос клеткада символы бар деп есептейік. Онда кез келген уақытта
кез келген клеткада символ бар. Алдыңғы үш қимылды болашақта бұйрық деп
атайтын келесі реттелген төрттіктермен белгілеуге болады:
(1) , (2) , (3) .
Бұл жерде алдыңғы екі символ - машинаның ішкі жағдайы мен қарастырылып
отырған квадраттағы символ, үшіншісі - қандай символ жазылатындығының
немесе оқу тетігінің не солға не оңға жылжуының белгісі, ал төртіншісі
қандай ішкі жағдайға көшетінін көрсетеді.
Сонымен енді біз кез келген Тьюринг машинасы мен осы машинаның
алфавитінде құрылған алгоритмді байланыстыра аламыз. Осы алфавиттегі кез
келген сөзді солдан оңға қарай жазамыз. Оқу тетігі ең сол шеткі квадратты
қарастырып тұрған кезде машина ішкі жағдайында жұмысты бастайды. Әр
қадамда не символ өшіріп, басқа символ жазады, не көрші квадраттардың
біріне көшеді. Егер машина жұмысын тоқтатса, онда лентадағы сөз алгоритмнің
нәтижесі болып есептеледі. Енді Тьюpинг машинасының дәл анықтамасын
берейік. Келесі екі шартты қанағаттандыратын ақырлы төрттіктер жиынын
Тьюринг машинасы деп атаймыз:
1. Төрттіктердің кез келгені не , не не түрінде
болады.
2. Алдыңғы екі символдары бірдей болатын төрттіктер жоқ.
Әр төрттік бұйрық деп аталады. Бұйрықтарға енетін символдары
сытрқы жағдайлар деп аталады. Бұйрықтардағы символдары ішкі
жағдайлар деп аталады. кез келген машинаның ішкі жағдайы болып
табылады.
Егер Р - бос болуы мүмкін, ал Q бос емес сөз болса және - машинаның
ішкі жағдайы болса, онда машинаның конфигурациясы деп аталады. Егер
келесі шарттардың біреуі орындалса, онда машина ( конфигурациясын (
конфигурациясына көшіреді дейміз:
1) ( конфигурациясы түрінде, ( конфигурациясы түрінде, ал -
машинаның бұйрықтарының біреуі;
2) ( - түрінде, ( - түрінде, ал - машинаның бұйрықтарының
біреуі;
3) ( - түрінде, ( - түрінде және - машинаның бұйрықтарының
біреуі;
4) ( - түрінде, ( - түрінде және - машинаның бұйрықтарының
біреуі;
5) ( - түрінде, ( - түрінде және - машинаның бұйрықтарының
біреуі.
Егер -ден басталатын бұйрық болмаса, онда машина
конфигурациясында тоқтайды деп атаймыз.
Егер конфигурациясына енетін ішкі жағдай болса, кез келген 0 (
і ( m-1 шартын қанағаттандыратын і үшін машина конфигурациясын
конфигурациясына көшірсе, ал конфигурациясында тоқтаса, онда ақырлы
конфигурациялар тізбегі машинаның есептеуі деп аталады. Және
есептеуі -ден басталып, -мен аяқталады дейміз. Т машинаның
алгоритмін келесі түрде анықтаймыз:
(Р) = Q орындалуы үшін конфигурациясынан басталып, =Q
теңдігі орындалатын конфигурациясымен аяқталуы керек.
Ескерту. сөздеріндегі символдарын ескермейміз. Себебі барлық
уақытта бұл символ бос квадратты білдіреді.
Енді натурал сандарға қолданылатын алгоритмдерге көшейік. Кез келген
натурал m санына m+1 - бірліктен тұратын тізбекті сәйкес қоямыз және оны
деп белгілейміз. Мысалы, 2-ге 111, 5-ке 111111. Егер кез келген
сандары үшін = теңдігі орындалса, онда Тьюринг машинасы
жартылай анықталған арифметикалық (() функциясын есептейді дейміз.
Берілген функцияны есептейтін Тьюринг машинасы табылса, ол функция
Тьюринг бойынша есептеледі деп аталады.
Кез келген Тьюринг машинасын кез келген n саннан тұратын тізбекке
пайдалануға болады. Берілген ((х) функциясын есептейтін Тьюринг машинасына
екі сан берсек, ол машина басқа функцияны есептейді.
Есептер
1. ((х, у) = х +у функциясын есептейтін Тьюринг машинасын құрыңыздар.
2. ((х) = 2х функциясын есептейтін Тьюринг машинасын құрыңыздар.
3. ((х) = 5х функциясын есептейтін Тьюринг машинасын құрыңыздар.
4. Екінші есептегі құрылған Тьюринг машинасына екі саннан тұратын тізбек
берсек, қандай функцияны есептейді?
5. Бірінші есептегі құрылған Тьюринг машинасына бір сан берсек, қандай
функцияны есептейді?

6.3 Черч тезисі, геделдік нөмірлеу

Әрине, алгоритмнің кез келген формализациясын алгоритмнің дәл анықтамасы
екенін дәлелдеу мүмкін емес. Оны не қабылдауға, не қабылдамауға болады.
Тьюрингтен бөлек математиктер де есептеуге болатын функциялардың
анықтамаларын берді. Дегенімен, олардың барлығы Тьюринг анықтамасымен
эквивалент болып шықты. Есімізге Клини, Пост, Марковтардың анықтауларын
алсақ та жеткілікті. Сондықтан, осы формализациялардың кез келгенін
алгоритмнің дәл анықтамасы ретінде алуға болады деп есептелінеді. Бұл ойды
Черч айтқан болатын. Сонымен, өзара эквивалент екі сөйлемді келтірейін.
Черч тезисі. Есептеуге болатын функциялар жиыны Тьюринг машинасында
есептелінетін функциялар жиынына тең.
Черч тезисі. Алгоритмі бар функцияны есептейтін Тьюринг машинасы бар.
Бұл эквивалент екі тезистің ешқайсысын дәлелдеу мүмкін емес. Себебі, ол
үшін алгоритмнің дәл анықтамасы карек. Бұл тезиске келіспеген
математиктердің Тьюринг машинасы есептемейтін алгоритм табуға тырысқан
еңбектерінен ештеңе шықпады. Сондықтан, қазіргі заманда Черч тезисімен
келіспеген математиктер қалмады деуге болады.
Кейбір Тьюринг машиналары кейбір мәндерінде тоқтамауын байқау қиын емес.
Сондықтан, Тьюринг машинасымен есептелетін функцияларды кейде жартылай
рекурсивті функция деп атайды, кейде рекурсивті функция деп атайды.
Eнді біз рекурсивті функцияларды қалай нөмірлейтінімізді көрсетейік.
Лемма 6.1. Тьюринг машинасының бұйрықтар жиынын нөмірлеп шығуға болады.
Дәлелдеуі. Біз , , төрттіктеріне j, і, r+2,z, j, і,
o, z және j, і, 1, z төрттіктерін сәйкес қояйық. Бұл сәйкестік өзара бір
мәнді және кері сәйкестік табылатынын көру қиын емес. Сонымен, біз j, і,
k, r төрттіктерін нөмірлеп шығайық. Координаталарының қосындысы 0-ге тең
бір-ақ 0, 0, 0, 0 төрттігі бар. Оған 0 cанын сәйкес қоямыз.
Координаталардың қосындысы бірге тең төрт төрттік бар. Оларға қандай да
тәртіппен 1-ден 4-ке дейінгі сандарды береміз. Тура осылай,
координаталарының қосындысы e-ге тең төрттіктер саны ақырлы екенін еске
түсірсек, онда осы әдіспен барлық төрттіктерді нөмірлеп шығуға болады.
Лемма дәлелденді.
Лемма 6.2. Бұйрықтар саны берілген e-ге тең Тьюринг машиналарын нөмірлеп
шығуға болады.
Дәлелдеуі. Бірінші лемма бойынша бұйрықтың орнына оның нөмірін алуға
болады. Сонымен, біз e координатасы бар сандар жиынының ішкі жиынын
нөмірлеуіміз керек. Біз тағы да координаталарының қосындысы k-ға тең e-
ліктердің ақырлы екенін пайдаланамыз және k-ны өсіре отырып барлық e
бұйрығы бар жиындарды нөмірлейміз. Берілген k үшін жұмыс алгоритмін
көрсетейік. Координаталарының қосындысы k-ға тең барлық e-ліктер жиыны
{, ,..., } болсын. Осы уақытқа дейінгі ең үлкен нөмір t
болсын. Егер қандай да екі үшін болса, онда бірінші e-лік нөмір
алмайды. Егер мен -лерге сәйкес бұйрықтар бірдей екі символдан
басталса, онда да нөмір берілмейді. Бұл екі шарт орындалмаған жағдайда
бірінші e-ліктің нөмірі ретінде t+1 санын аламыз. Келесі e-лікке көшеміз.
Лемма дәлелденді.
Теорема 6.1. Ақырлы бұйрықтар жиындарының жиынын нөмірлеуге болады.
Дәлелдеуі. Бұйрықтар саны мен сол санға сәйкес екінші лемма бойынша
алынған нөмірдің қосындысы берілген санға тең болатын бұйрықтар жиындарының
ақырлы екені түсінікті. Леммалардың дәлелдеуіндегі идеямен теореманың
дәлелдеуін аяқтауға болады.
Салдар 6.1. Тьюринг машиналарын нөмірлеп шығуға болады.
Дәлелдеуі. Кез келген машина өзінің бұйрықтар жиынымен бір мәнді
анықталады.
Бірінші рет рекурсивті функциялар жиынын нөмірлеп шыққан Гедель болатын.
Сондықтан, біз жоғарыда көрсеткен нөмірлеуімізді гедельдік нөмірлеу деп
атаймыз.
Сонымен арқылы k айнымалысы бар рекурсивті функциялар жиынын
белгілейік.

Жаттығулар.

бұйрығының нөмірін табыңыздар.
12 - қандай бұйрықтың нөмірі?
Тьюринг машинасы {, } командалар арқылы берілсін. Oсы
машинаның бұйрықтар саны екіге тең Тьюринг машиналарының жиынындағы нөмірін
табыңыз.
Үшінші есептегі Тьюринг машинасының гедельдік нөмірі неге тең?

6. 4 Черч тезисінің салдарлары

Енді Черч тезисінен шығатын бірнеше теоремаларға тоқтай кетейік.
Теорема 6.2 Жартылай рекурсивті функциялар жиыны саналымды.
Дәлелдеуі. Черч тезисі бойынша ((х) = k функциясы кез келген k үшін
рекурсивті. Сондықтан, жартылай рекурсивті функциялар кем дегенде
саналымды. Екінші жағынан төртінші салдар бойынша олар саналымдыдан артық
емес.
Анықтама. Кез келген мәнінде анықталған жартылай рекурсивті функция
жалпы рекурсивті функция деп аталады.
Салдар 6.2 Жалпы ... жалғасы

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