Алгоритмдер теориясы

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

Алгоритм ұғымы - математикада вектор, жиын секілді негізгі ұғымдардың бірі. Негізгі ұғымдардың дәл анықтамасы болмайды. Оларды тек интуициямен қабылдаймыз. Дегенімен, осы параграфта алгоритм ұғымын мағыналық тұрғыдан анықтауға тырысамыз.

Көбінесе алгоритм ұғымын берілген элементке сәйкес элементті берілген нұсқаулар арқылы табу деп түсінеміз.

Бірақ бұл анықтама - математикалық тұрғыдан алғанда дәл анықтама емес. Себебі, есептеу, нұсқау ұғымдарының да анықтамасы берілмеген.

Алгоритм ұғымын анықтаудың алдында бірнеше мысалдар келтірейік.

1.    ¦(х) = х-ші жай сан. Бұл функцияны есептеуге алгоритм ретінде Эратосфен елегін пайдалануға болады.

2.    ¦(х,у) = х пен у-тің ең үлкен ортақ бөлгіші. Бұл жерде Евклид алгоритмі жұмыс істейді.

3.    m(¦) = ,  бұл жерде ¦- көпмүше. Көпмүшелердің туындысы алу алгоритмі мектептен белгілі.

Біз көбінесе тек қана натурал сандарға қолданылатын алгоритмтерді қарастырамыз.

Алгоритмдер төмендегі  ортақ қасиеттерімен сипатталады:

1.        Алгоритм ақыpлы өлшемді нұсқаулар жиыны ретінде беріледі.

2.        Нұсқауларды түсініп, есептеулерді жүргізетін есептегіш (көбінесе адам) болады.

3.        Есептеулердің кез келген бөлігін бөліп алуға, жаттауға және кейбір қадамдарын қайталауға мүмкіндіктер бар.

4.        Есптегіш нұсқаулар бойынша әр берілген санға сәйкес есептеу кезінде қадамдары дискретті түрде кездейсоқ әдістерсіз жұмыс істейді.

Бұл қасиеттер электронды есептеу машиналарға ұқсастықты көрсетеді. Шынында да

1)        машинаның программасы,

2)        есептеу құрылысы,

3)       жаттау қабілеті,

4)        табиғи құрлысы.

Әрине көрсетілген төрт қасиет алгоритмді дәл анықтайды деп айта алмаймыз. Бұл жерде көптеген сұрақтар пайда болады. Солардың бірнешесін қарастырайық.

1)           Берілген санның өлшемін шектеу қажет пе?

Егер біз "иә"  деп жауап берсек, онда, мысалы, ¦(х) =  функциясын есептеудің алгоритмі жоқ болады. Себебі, берілетін сан кез келген ақырлы сан болуы мүмкін. Сондықтан, біз "жоқ" деп жауап береміз және олар тек ақырлы болуы керек дейміз.

2)           Нұсқаулардың өлшемін шектеу қажет пе?

Күрделі есептерді шығару үшін біздің нұсқауларымызды шекті деп аламыз, бірақ нұсқаулардың да ақырлы болу керектігін ұмытпаймыз.

3)           Жаттау қабілетін шектеу қажет пе?

Алдыңғы екі сұраққа жоқ деп жауап берген соң, бұл сұраққа да "жоқ" деуіміз қажет. Бірақ бір қызығы, кез келген машинаның жаттау қабілеті шектеулі. Дегенмен ол қазіргі керекті есептеулерге жеткілікті.

Жаттығулар

Келесі ережелерді алгоритм деп есептеуге болады ма?

1.    Бізге nсаны берілсін. ¦(n) мәнін есептеу үшін монетаны лақтырамыз. Егер елтаңба бар жағы жоғары қараса, онда ¦(n) = 1; ал егер елтаңба бар жағы төмен қараса, онда ¦(n) = 0.

2.    Егер pсанының ондық бөлшек түрде жазуында қатар тұрған дәл 2nбірлік болса, онда ¦(n) = 1; кері жағдайда ¦(n) = 0.

3.    Егер pсанының ондық бөлшек түрде жазуында қатар тұрған дәл 2nбірлік болса, онда ¦(n) = 1; кері жағдайда ¦(n) анықталмаған.

4.    Бізге nсаны берілсін. Егер ¦(n) мәнін бұрын есептелмеген болсақ, онда біз отырған бөлмеде адам саны тақ болса, ¦(n) = 1 дейміз; кері жағдайда ¦(n) = 1 және ¦(n) мәнін бұрын есептелген деп санаймыз. Ал егер ¦(n) бұрын есептелген болса, онда бұрынғы мәнін береміз.

5.    Егер pсанының ондық бөлшек түрде жазуында қатар тұрған кем дегенде nбірлік болса, онда ¦(n) = 0; кері жағдайда ¦(n)=1.

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

Әрине өткен параграфта қойылған сұрақтардың жауаптарын алгоритмнің дәл анықтамасы ретінде ала алмаймыз. 1936 жылы Тюринг кез келген есептеуді орындай алады деген жорамалмен теориялық машиналар класын енгізді. Олардың сипаттамасын берейік.

Көз алдымызға квадратттарға бөлінген ақырлы лентаны елестетейік. Машинаның алфавиті болып аталатын  символдары беріледі. Әр кезде әр квадратқа бір символ жазылады. Әр кезде квадратта бір символдан артық болмайды. Машинаның іùкі жағдайлары болып табылатын  жиыны болады. Әр кезде машина сол ішкі жағдайлардың біреуінде ғана болады. Сонымен бірге кез келген уақытта квадраттардың біреуін ғана қарастыратын оқу тетігі бар. Машина бір мезетте бір ғана қимыл істейді. Егер машинаның оқу тетігі қарастырылып тұрған квадратта  символы тұрса, ал машинаның ішкі жағдайы  болса, онда ол келесі қимылдардың біреуін істейді:

1.Осы квадраттағы  символын өшіріп,  символын осы квадратқа жазады;

2.Оң жақтағы көрші квадратқа көшеді;

3.Сол жақтағы көрші квадратқа көшеді;

4.Тоқтайды.

Алдыңғы үш жағдайда машина басқа  ішкі жағдайға көшіп, келесі қимылға дайын. Екінші немесе үшінші қимыл кезінде көрші квадрат жоқ болса, онда керек квадрат пайда болады деп есептейміз.

Бос клеткада  символы бар деп есептейік. Онда кез келген уақытта кез келген клеткада символ бар. Алдыңғы үш қимылды болашақта бұйрық деп атайтын келесі реттелген төрттіктермен белгілеуге болады:

 (1) , (2) ,  (3) .

 Бұл жерде алдыңғы екі символ - машинаның ішкі жағдайы мен қарастырылып отырған квадраттағы символ, үшіншісі - қандай символ жазылатындығының немесе оқу тетігінің не солға не оңға жылжуының белгісі, ал төртіншісі қандай ішкі жағдайға көшетінін көрсетеді.

Сонымен енді біз кез келген Тьюринг машинасы мен осы машинаның алфавитінде құрылған алгоритмді байланыстыра аламыз. Осы алфавиттегі кез келген сөзді солдан оңға қарай жазамыз. Оқу тетігі ең сол шеткі квадратты қарастырып тұрған кезде машина  ішкі жағдайында жұмысты бастайды. Әр қадамда не символ өшіріп, басқа символ жазады, не көрші квадраттардың біріне көшеді. Егер машина жұмысын тоқтатса, онда лентадағы сөз алгоритмнің нәтижесі болып есептеледі. Енді Тьюpинг машинасының дәл анықтамасын берейік. Келесі екі шартты қанағаттандыратын ақырлы төрттіктер жиынын Тьюринг машинасы деп атаймыз:

1. Төрттіктердің кез келгені не , не  не  түрінде болады.

2. Алдыңғы екі символдары бірдей болатын төрттіктер жоқ.

Әр төрттік бұйрық деп аталады. Бұйрықтарға енетін  символдары сытрқы  жағдайлар деп аталады. Бұйрықтардағы  символдары ішкі жағдайлар деп аталады.