Негізгі есептегіш алгоритмдер: ақырғы автоматтар; Тьюринг және Пост машиналары, оңай және қиын шешілетін есептер.

Алгоритм[1], алгорифм (ағылшынша: algorіthm, algorіsmus — Әл-Хорезмидің атынан шыққан) — бастапқы берілген мәліметтермен бір мәнде анықталатын нәтиже алу үшін қай амалды (жұмысты) қандай ретпен орындау қажеттігін белгілейтін есептерді (мәселелерді) шешу (математикалық есеп-қисаптар орындау, техникалықобъектілерді жобалау, ғылыми-зерттеу жұмысын жүргізу т.б.) тәсілдерінің дәл сипаттамасы. Алгоритм — математика мен кибернетиканың негізгі ұғымдарының бірі. Агоритмді орындау алгоритмдік процесс деп аталады.

Жалпы Алгоритм деп алдын ала не істеу керек екені дәл көрсетілген есептеу процесін айтады. Есептеу процесі қандай болса да алғашқы мәндерден бастап, сол арқылы толық анықталған қорытынды шыққанша жүргізіледі. Алгоритм ұғымының алғышартына алгоритмдік процеспен қатар мүмкін болатын алғашқы деректер жиынтығының нұсқауы және қорытынды алуға байланысты жүргізілген процестің аяқталғандығын көрсететін ереже енеді. Белгілі бір бастапқы деректердің жиынына қолданылған Алгоритм тиянақты қорытындыға келмеуі немесе есептеу барысы аяқталмай тоқталуы мүмкін. Егер есептеу процесі белгілі бір қорытынды алумен аяқталса (не аяқталмай қалса), онда Алгоритм мүмкін болатын бастапқы деректерге қолданылады (не қолдануға болмайды) деп ұйғарылады.

Алгоритм — қазіргі математикада, оның ішінде электронды есептеуіш машинада қолданылатын негізгі ұғымдардың бірі. Белгілі бір теңдеу түбірінің жуық мәнін кез келген дәлдікпен табу оған арналған Алгоритммен есептеледі. Компьютердің кең қолданылуына байланысты Алгоритм жаңа мағынаға ие болды. Берілген есепті шешу барысында орындаушыға біртіндеп қандай әрекеттер жасау керектігін түсінікті әрі дәл көрсететін нұсқау да Алгоритм деп аталады. Алогритмді орындаушы — адам, ЭЕМнемесе робот. Әрбір нұсқау — бұйрық. Ал орындаушының жүзеге асыра алатын бұйрықтар жиыны бұйрықтар жүйесі деп аталады. Мысалы, у = (ax + b) (cx - d) функциясын есептеу ЭЕМ-да мынадай әрекеттерден құралады:

1. а-ны x-ке көбейту R1 деп,

2. оған b-ны қосу нәтижесі R2 деп,

3. с-ны х-ке көбейту R3 деп,

4. сх-тан d-ны алу R4 деп,

5. R2-ні R4-ке көбейту у деп белгіленеді.

Алгоритмнің бұйрықтары бірінен кейін бірі кезекпен орындалады. Бағдарлама Алгоритм тілінде жазу, бейнелеу мағынасын береді. Компьютерде Алгоритмнің сызықты, тармақты, циклді, логикалық, модельдік, параллельдік, тізбекті т.б. түрлері қолданылады.[2]

Алгоритм қасиеттері

Алгоритм ұғымның мәнін аша түсетін оның мынадай қасиеттері бар:

1. Алгоритм дискретті информациялармен жасалатын әрекеттерді тағайындайды және өрнектейді. Алгоритмге қатысты әрекеттердің бәрі дискретті болады. Алгоритмнің жұмысына қажетті материалдар ретінде символдық мәтіндер және сандар пайдаланылады.

2. Алгоритм біздің қалауымызға қарай өзгертуге болмайтын нақты нұсқау алгоритмде не істеу керектігі алдын-ала айқын береді. Мысалы, бір есепті шешудің алгоритмі берілсе онда ойланбай-ақ алгоритмде қандай нұсқаулар берілсе, сол нұсқауларды берілу ретімен орындасақ, есеп шығады. Алгоритмнің осы қасиетін оның анықталғандық қасиеті дейміз. Бұл жағдай адам сияқты емес ойлау қабілеті жоқ құрылғылардың мысалы, компьютердің көмегімен есептерді шешу мүмкіндігіне кепілдік берді. Мұндай құрылғылар алгоритмнің жарлықтарын ойланбастан формальды орындайды. Сондықтан алгоритмді есепті шығаруға қажеттінің бәрі бір мәнді анықталу және атқарушыға түсінікті әрі нақты болуы тиіс.

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

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

Алгоритмді талдау

Алгоритмдерді талдаудың негізгі әдістері:

1. Сөздік-формулалық (табиғи тілдерде);

2. Құрылымды немесе блок-схемалар;

3. Арнайы алгоритмдік тілдерді қолдану;

4. Граф-схемалар көмегімен (граф – әр сызық екі нүктені қосатын, нүктелер мен сызықтар жиынтығы). Нүктелер шыңдар деп аталады, сызықтар – қабырғалар;

5. Петри торының көмегімен.

Бағдарламаны жасау алдында көбінесе сөздік-формулалық және блок-схемалық әдістер қолданылады. Кейде ассемблер сияқты төменгі деңгейдегі тілдерде бағдарламаны жасау алдында, бағдарлама алгоритмін кейбір жоғарғы деңгейдегі бағдарламалау тілінің конструкцияларын қолдана отырып жазады. Күрделі бағдарламалық жүйелер алгоритмдерінің бағдарламалық сипаттамаларын қолдану ыңғайлы. Мысалы, ОЖ жұмыс істеу принциптерін сипаттау үшін Алголға ұқсас жоғарғы деңгейдегі бағдарламалау тілі қолданылды

Сөздік-формулалық әдісте алгоритм әрекеттер тізбегін анықтайтын, құрамында формулалары бар мәтіндік түрде жазылады. Мысалы, келесі өрнектің мәнін анықтау қажет болсын: у=2а-(х+6).Сөздік-формулалық әдістпен бұл есептің алгоритмі келесі түрде жазылуы мүмкін:

1. а және х мәндерін енгізіңіз.

2. х және 6-ны қосу.

3. а на 2-ге көбейту.

4. 2а –дан (х+6) қосындысын азайту.

5. Өрнектің есептелген нәтижесі ретінде у-ті шығару.

Блок-схемада бағдарламадағы барлық тармақтар, циклдар және ішкі бағдарламалар болуы қажет.

Маши́на По́ста (МП) — абстрактная вычислительная машина, предложенная Эмилем Леоном Постом (англ. Emil Leon Post), которая отличается от машины Тьюрингабольшей простотой. Обе машины алгоритмически «эквивалентны» и были придуманы для уточнения понятия «алгоритм». В 1936 г. американский математик Эмиль Пост в статье описал систему, обладающую алгоритмической простотой и способную определять, является ли та или иная задача алгоритмически разрешимой. Если задача имеет алгоритмическое решение, то она представима также в форме последовательности команд для машины Поста.

Содержание

[скрыть]

• 1Принцип работы

• 2Примеры: сложение и вычитание натуральных чисел P, Q

• 3См. также

o 3.1Другие абстрактные исполнители и формальные системы вычислений

• 4Литература

Принцип работы[править | править вики-текст]

Машина Поста состоит из каретки (или считывающей и записывающей головки) и разбитой на ячейки бесконечной в обе стороны ленты (см. пример ниже). Каждая ячейка ленты может находиться в 2 состояниях — быть либо пустой — 0, либо помеченной меткой 1. За такт работы машины каретка может сдвинуться на одну позицию влево или вправо, считать, изменить символ в своей текущей позиции.

Работа машины Поста определяется программой, состоящей из конечного числа строк. Для работы машины нужно задать программу и её начальное состояние (то есть состояние ленты и позицию каретки). Кареткой управляет программа, состоящая из пронумерованных не обязательно упорядоченных строк команд, если в каждой команде указана строка, на которую нужно перейти. Обычно принимается, что если в команде переход не указан, то переход происходит на следующую строку. Каждая команда имеет следующий синтаксис:

i K j

где i — номер команды, K — действие каретки, j — номер следующей команды (отсылка).

Всего для машины Поста существует шесть типов команд:

V j - поставить метку, перейти к j-й строке программы.

X j - стереть метку, перейти к j-й строке программы.

← j - сдвинуться влево, перейти к j-й строке программы.

→ j - сдвинуться вправо, перейти к j-й строке программы.

? j1; j2 - если в ячейке нет метки, то перейти к j1-й строке программы, иначе перейти к j2-й строке программы.

! – конец программы (стоп).

В команде «стоп» переход на следующую строку не указывается.

После программы запуска возможны варианты:

• работа может закончиться невыполнимой командой (стирание несуществующей метки или запись в помеченное поле);

• работа может закончиться командой Stop;

• работа никогда не закончится.

Тьюринг машинасы- –бұл абстрактты орындаушы (абстрактты есептеу машинасы), 1936 жылы алгоритм ұғымын формальдау үшін Алан Тьюринг ұсынды. абстрактты орындаушы (абстрактты есептеу машинасы). Тьюринг машинасы –ақырлы автоматтың кеңейтілген түрі, басқа орындаушыларды қадамдап есептеу процесін жүзеге асырып имитациялай алады (өту ережелерін беру арқылы қарапайым), қадамдар аса қарапайым.

Тьюринг машинасының құрамы:  екі жағы шексіз лентадан (олар ұяшыққа бөлінген)  басқару құралы,осы күйлердің біреуінде болады  күйлер жиыны. Күйлердің саны шектеулі және нақты беріледі

Басқару құралы лентада солға, оңға жылжи алады, лентаға қандай да бір ақырлы алфавиттің символдарын жазады не оқиды. Бос символ болады, ол лентаның кірістік деректер жазылмаған,қалған ұяшықтарына жазылады. Басқару құралы өту ережесі бойынша жұмыс істейді. Өту ережесі Тьюринг машинасында жүзеге асатын алгоритм. Өтудің әрбір ережесі Тьюринг машинасына ағымдағы күймен ағымдағы ұяшықтағы символға байланысты, осы клеткаға жаңа символ жазуды, жаңа күйге өтуге немесе бір клеткаға оңға немесе солға жылжуға бұйрық береді.

Тьюринг машинасын анықтау үшін мыналар көрсетіледі: Сыртқы алфавит A= {} - ұяшықтың бос символы Ішкі күйлердің алфавиті немесе оны ішкі алфавит деп атаймыз. Q = { } , мұндағы - тоқтаудың күйі. Осыған келгенде машина жұмысын тоқтатады. - бастапқы күй, машина жұмысын бастайды. Программа (функционалды схема), ол –команда деп аталатын өрнектердің жиынтығы. Мынандай әрбір жұп үшін () тек бір ғана команда болады. Ереженің жалпы түрі: - жаңа күй, ол кейде қалуы мүмкін. -ның орнына жазылатын жаңа символ Тьюринг машинасын сипаттау үшін бастапқы және соңғы күйді (), лентадағы бастапқы орналасуды және басқару құрылғысының бас тиегінің орнын көрсету керек.

Тьюринг машинасының кейбір күйлері терминалды деп белгіленеді, бұл күйге өту жұмыстың аяқталмағанын, яғни алгоритмнің тоқтағанын білдіреді. Бір ғана ережеден тұратын Тьюринг машинасы анықталған (детерминирленген) Тьюринг машинасы деп аталады, ал егер екі немесе одан да көп командасы болатын «лента символы — күй» жұбы бар болса, мұндай Тьюринг машинасы анықталмаған (детерминирленбеген) деп аталады.

Жартылай шексіз лентада жұмыс істейтін Тьюринг машинасы. Мұндай машинаны Тьюринг машинасына өзгерту оңай,

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

* белгісі Тьюринг машинасының сөздігінде

сақталмайды, штрихталған зонада шекараға жеткендігін білдіреді, ал бастапқы күй жартылай шексіз лентада қай жерде тұрса, мұнда да сол жерде тұрады. Машина штрихталмаған зонада жұмыс істейді. Еер жұмыс кезінде ‘*’ символы кезіксе, оқу-жазу бастиегі зона шекарасына жеткені. Лентаның «*» сол жағындағылар бұл машинада қарастырылмайды. Жаңа Тьюринг машинасының бастапқы күйі бастапқы машинадағыдай жақта орналасады.Төменде жартылай шексіз лентада жұмыс істейтін Тьюринг машинасы жұмысының схемасы берілген:

Марков алгоритмдерінің таралуы және бірігуі. Марковтың нормаль алгоритмі (МНА) — алгоритм ұғымының формалді анықтамасын берудің стандарты тәсілдерінің бірі (Тьюринг машинасы сияқты). Бұл ұғымды көрнекті кеңес математигі А.А.Марков(1903-1979жж.) 1940-жылдардың соңында енгізген. Марков алгоритмдері туралы сөз болғанда, "алгорифм" деп атау қабылданған. Марковтың қалыпты алгоритмдері. Марковтың қалыпты алгоритмінің жұмысының сипаттамасы. Марковтың цифрлы алгоритмы Алгоритм ұғымын тұрпаттандыру үшін Россия математигі А.А. Марков ассоциативтік қисапты пайдалануды ұсынды. Ассоциативтік қисаптың кейбір ұғымдарын қарастырайық. Әріппе (әртүрлі таңбалардың ақырлы жиынтығы) бар болсын. Оны құраушы таңбаларды әріптер деп атаймыз. Әріппе әріптерінің кез келген ақырлы тізбегі (олардың сызықты қатары) осы әріппедегі сөз деп аталады. Әлдебір А әріппесіндегі N және M екі сөзін қарастырайық. Егер N M-нің бөлігі болса, онда N M-ге енеді дейді. Әлдебір әріппеде алмастырулардың ақырлы жүйесі берілсін: N–M, S-Т, ..., мұндағы N,M,S,T,... –осы әріппедегі сөздер. Кез келген N-M алмастыруын әлдебір К сөзіне былай қолдануға болады: егер К-да N-сөзінің бір немесе бірнеше кірістері болса, онда олардың кез келгенін М-мен алмастыруға болады және керісінше, егер М-нің кірісі бар болса, онда оны N-мен алмастыруға болады.

Марковтың нормальды алгоритмдері. Бірінен-бірі тәуелсіз тарихи пайда болған бұл тәсілдер, соңыра өзара эквивалентті болып шықты. Алгоритм ұғымын тұрпаттандырудың негізгі мақсаты мынада: әртүрлі математикалық есептердің алгоритмдік шешімділігі мәселесін шешуге жол ашу, яғни есеп шешіміне әкелетін алгоритм құруға бола ма - деген сұраққа жауап беру. Біз осы мәселенің қойылуын және есептердің алгоритмдік шешімділігі теориясының кейбір нәтижелерін қарастырамыз, бірақ алдымен Пост, Тьюринг машиналары және Марковтың нормалы алгоритмдері мысалында автоматтар теориясындағы алгоритм ұғымын тұлғатандыруды, сонан соң рекурсивті функциялар теориясы негіздерін талқылаймыз. Өздеріне арналған программалардың қасиеттері туралы әртүрлі тұжырымдауды дәлелдеуге арналған абстракты ( яғни шын емес, тек қиялда ғана бар) Пост пен Тьюринг машиналарын американдық математик Эмил Пост пен ағылшын математигі Аллан Тьюринг бірінен-бірі тәуелсіз (және іс жүзінде бір уақытта) 1936 ж. ұсынды. Бұл машиналар бастапқы мәліметтерді “енгізіп”, программалар орындалғаннан соң нәтижені оқуға мүмкіндік беретін, толығымен анықталған әмбебап орындаушылар болып табылады. Пост машинасы аса танымал емес, бірақ Тьюринг машинасына қарағанда әлдеқайда қарапайым.

Пост машинасы: i-2,i-1,i,i+1,i+2 Пост абстракты машинасы, жазатын немесе оқитын түбіртек арқылы не ен жазылып, не ен оқылатын жеке секцияларға (ұяшықтарға) бөлінген ақырсыз таспа болып табылады.

Пост абстракты машинасы. Таспа (немесе түбіртек) командаға байланысты бір адым солға немесе оңға ауыс қимыл жасай алады. Таспа әрқашан түбіртектің қарсы алдында секция (ұяшық) тұратындай етіп тоқтайды. Абстракты автомат командалары әдетте келесі әрекеттердің бірінен тұрады: Команда

Түбіртектің оңға қозғалуы Түбіртектің солға қозғалуы М енін жазу m С енін өшіру m Басқаруды беру Тоқтау стоп n Пост машинасында ақпарат сызық бойынша орналасады да, бірінен соң бірі оқыла береді, ал ЭЕМ-де ақпаратты адресі бойынша оқуға болады; ЭЕМ командаларының жиынтығы әлде- қайда кең әрі Пост машинасы командаларына қарағанда айқын, т.с.с.

Таспаның кү йі

командадан кейін

Қорытынды:

Тьюринг машинасы – белгілі бір есептерді шығаруға арналған қатаң математикалық құрылым, математикалық аппарат. Бұл аппарат машина деп аталу себебі оның құрамдас бөлігінің және функцияларының есептеу техникасына ұқсауында. Тьюринг машинасының есептеу техникасынан ерекшелігі оның еске сақтау құрылғысы шексіз лентадан тұруында, ал есептеу техникасының еске сақтау құрылғысы қаншалықты үлкен көлемді болса да шектеулі. Сондықтан Тьюринг машинасын лентасы шексіз болғандықтан есептеу техникасы түрінде қолдануға болмайды. Марковтың нормальды алгоритміне қойылатын талаптар: алгоритм қарапайым орындалатын саны шектеулі ережелерден тұруы тиіс, яғни жазбалардың шектеулі болуы талабын қанағаттандыруы тиіс; алгоритм шектеулі қадамнан соң есепті шешуі тиіс, яғни әрекеттердің шектеулі болу талабын қанағаттандыруы тиіс; алгоритм барлық мүмкін болатын бастапқы деректер үшін біреу ғана болуы керек, яғни әмбебаптық талабын қанағаттандыруы тиіс; алгоритм қойылған есептің дұрыс шешімін табуы керек, яғни дұрыс болу талабын қанағаттандыруы тиіс. Бұл анықтамаларда әрекетті орындаушы көрсетілуі тиіс және ол орындайтын «қарапайым» операцияларға не жататыны нақтылануы тиіс. Алгоритмді әртүрлі формада бейнелеуге , яғни беруге болады.

Жартылай шексіз лентада жұмыс істейтін Тьюринг машинасы. Мұндай машинаны Тьюринг машинасына өзгерту оңай,

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

* белгісі Тьюринг машинасының сөздігінде

Таспаның кү йі

командадан кейін

Қорытынды: