А. Ж. Асамбаев информатиканың теориялық негіздері. Практикум

 

38 

1) бірінші орында нөмір 1 команда, екінші орында 2 нөмірі және т.с.с  

2) кез келген командадан жөнелту бағдарлама командасы алынады.  

Лентаны  солға  немесе  оңға  жылжытқаннан  кейін  бастиек  ұяшықтың 

қалып күйін оқиды (бос немесе белгі жазылған). Бос секциялар немесе белгіленген 

секциялар  туралы  ақпарат  лентаның  қалып  күйін  немесе  автоматтың  қалып 

күйін  құрады.  Автоматтың  бағдарламасы  деп  командалардың  бос  емес 

шектелген тізімін айтамыз.  

Абстрактілі  автоматтың  жұмыс  істеуі  үшін  бағдарлама  және  бастапқы 

күйін  беру  керек,  яғни  бастиектің  орны  мен  лента  ұяшықтарының  күйін  беру 

керек.  Әрбір  команда  бір  қадамда  орындалады,  одан  кейін  жөнелтуде 

көрсетілген  нөмірлі  команданың  орындалуы  басталады.  Егер  команда  екі 

жөнелтуден  тұрса,  егер  бүркеншік  бос  ұяшықта  тұрса,  онда  жоғарғы  жөнелту 

орындалады. Егер бүркеншік белгісі бар ұяшықта тұрса, онда төменгі жөнелту 

орындалады.  Басқаруды  беру  командасының  орындалуы  автоматтың  күйін 

өзгертпейді  (белгілердің  бірде  біреуі    жойылмайды,  қойылмайды  және  лента 

қозғалыссыз қалады). Автоматты іске қосқанда төмендегі жағдайлардың біреуі 

болуы мүмкін:  

1)  автомат  орындалмайтын  командаға  жетті  (белгіні  бос  емес  ұяшыққа 

жазу,  бос  ұяшықтағы  белгіні  өшіру);  бұл  жағдайда  орындалу  аяқталады,  автомат 

тоқтайды, нәтижесіз тоқтату болады.  

2)  автомат  тоқта  командасына  жетті,  бағдарлама  орындалды  деп 

есептеледі, нәтижелі тоқтату болады.  

3) автомат нәтижелі тоқтатуға да, нәтижесіз тоқтатуға да жетпейді, шексіз 

жұмыс істеледі. 

Пост  машинасының  типтік  бағдарламасын  орындау  кезіндегі  автомат 

жұмысын  қарастырамыз.  Бастиектің  бастапқы  күйі  берілген  және  бос  лентаға 

екі белгі жазу керек.  

 

Бастапқы күйі 

 

M 2 

 



 3 

 

M 3 

 

Тоқта (Стоп) 3 

 

 

Пост машинасында қолданылатын сандар позициялық емес. 

 

4.3  Тьюринг  және  Пост  машинасы  көмегімен  «алгоритм»  ұғымын 

анықтау 

Тьюринг және Пост машиналар толығымен детерминделген универсалды 

орындаушылар  болып  табылады.  Олардың  көмегімен  алғашқы  деректер 

енгізілгеннен кейін нәтижені «оқуғаң болады. Тьюринг және Пост машиналарында 

орындалатын  есептеулерге  шектеулер  бар  ма  деген  сұраққа  Пост  былайша 

 

39 

жауап  берген:  «егер  кез  келген  бойынша  нәтижеге  әкелетін  жалпы  әдіс  болса 

ғана программа құруға берілген есептердің шешімі болады». 

Постың  анықтамасы  алгоритм  ұғымына  және  осы  алгоритмді  цифрлы 

автомат көмегімен шешуге болатындығына әкеледі.  

 

4.4 Марковтың нормальды алгоритмдері 

Алгоритм  ұғымын  тұрпаттандыру  үшін  Россия  математигі  А.А.  Марков 

ассоциативтік қисапты пайдалануды ұсынды. 

Ассоциативтік  қисаптың  кейбір  ұғымдарын  қарастырайық.  Әріппе 

(әртүрлі  таңбалардың  ақырлы  жиынтығы)  бар  болсын.  Оны  құраушы 

таңбаларды әріптер деп атаймыз. Әріппе әріптерінің кез келген ақырлы тізбегі 

(олардың  сызықты  қатары)  осы  әріппедегі  сөз  деп  аталады.  Әлдебір  А 

әріппесіндегі N және M екі сөзін қарастырайық. Егер N M-нің бөлігі болса, онда 

N M-ге енеді дейді. 

Әлдебір әріппеде алмастырулардың ақырлы жүйесі берілсін: N-M, S-Т, ..., 

мұндағы N, M, S, T,... – осы әріппедегі сөздер.  Кез келген N-M алмастыруын 

әлдебір  К  сөзіне  былай  қолдануға  болады:  егер  К-да  N-сөзінің  бір  немесе 

бірнеше кірістері болса, онда олардың кез келгенін М-мен алмастыруға болады 

және керісінше, егер М-нің кірісі бар болса, онда оны N-мен алмастыруға болады. 

Р1 және Р2 сөздері әлдебір ассоциативтік қисапта сыбайлас аталады, егер 

олардың  біреуі  екіншісінен  мүмкін  алмастыруды  бір  ғана  қолданғанда 

түрлендірілетін болса. 

Р,  Р1,  Р2,...,  М  cөздерінің  тізбегі  Р  сөзінен  М  сөзіне  әкелетін дедуктивті 

тізбек аталады, егер осы тізбектің қатар тұрған екі сөзінің әрқайсысы сыбайлас 

болса.  

Егер Р-дан М-ге тізбек және кері тізбек бар болса, онда Р және М сөздері 

эквивалентті аталады. 

 

Мысал: 

Әріппе 

 

 

 

Алмастырулар 

{а,в,с,d,e}      

 

 

ac-ca; abac-abace 

аd-da;  

 

 

 

eca-ae 

bc-cb;  

 

 

 

eda-be 

bd-db; 

 

 

 

edb-be 

 

abcde  және  acbde  сөздері-сыбайлас  (bc-cb  алмастыру)  abcde-cadbe  сөздері 

эквивалентті. 

Алмастырулары  бағытталған  болып  келетін: 

M

N



  (жебеше  алмастыруды 

солдан  оңға  қарай  жүргізуге  рұқсат  етілетіндігін  білдіреді)  ассоциативтік 

қисаптың  арнайы  түрін  қарастыруға  болады.  Әрбір  ассоциативтік  қисап  үшін 

мынадай  есеп  бар:  кезкелген  екі  сөз  үшін  олардың  эквивалентті  немесе  емес 

екендігін анықтау керек. 

Формулаларды  шығарудың кез  келген үрдісі,  математикалық  есептеулер 

мен  түрлендірулер  де  әлдебір  ассоциативтік  қисапта  дедуктивті  тізбектер 

болып  табылады.  Ассоциативтік  қисапты  құру  ақпаратты  анықталған  қайта 

 

40 

өңдеудің  әмбебап  әдісі  болып  табылады  және  алгоритм  ұғымын  тұрпаттандыруға 

мүмкіндік береді. 

Ассоциативтік қисап негізінде алгоритм ұғымын енгізейік: А әріппесінде 

Алгоритм  деп,  А-дағы  сөздерге  үрдіс  анықтайтын  және  бастапқы  сөз  ретінде 

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

мақұл  алмастыруларды  қай  тәртіппен  қолдануға  болатындығы  және  қашан 

тоқтайтындығы  туралы  дәл  ұйғарыммен  толықтырылған  мақұл  алмастырулар 

жүйесі түрінде беріледі. 

 

Мысал: 

Әріппе 

 

 

 

В алмастырулар жүйесі 

А={a,b,c}   

 

 

cb-cc 

 

 

 

 

 

cca-ab 

 

 

 

 

 

 

 

 

 

 

 

ab-bca 

 

Алмастыруларды  қолдану  туралы  ұйғарым:  кез  келген  Р  сөзінде 

алмастырулардың  сол  жағын  оң  жағына  ауыстырып,  мүмкін  алмастырулар 

жасау керек; жаңа алынған сөзбен үрдісті қайталау керек. Осылай, қарастырылған 

мысалдағы  алмастырулар  жүйесін  ваваас  және  всасавс  сөздеріне  қолданып, 

мынаны аламыз: 

babaac  



   bbcaaac  



 тоқтау 

bcacabc 



 bcacbcac 



 bcacccac 



 bcacabc 



ақырсыз үрдіс (тоқтау жоқ), 

осымен біз бастапқы сөзді алдық. 

А.А.Марков ұсынған алгоритм ұғымын анықтау тәсілі мына төмендегідей 

анықталатын қалыпты алгоритм ұғымына негізделген.  

А әріппесі және В алмастырулар жүйесі берілсін. Кез келген Р сөзі үшін 

В-дағы  алмастырулар  сол  В-дағы өз  ретімен  алынады.  Егер  келісті  алмастыру 

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

біріншісі  алынып,  оның  Р-дағы  солжақ  бөлігінің  бірінші  кірісі  оның  оңжақ 

бөлігімен ауыстырылады.  Сонаң  соң барлық  әрекет  жаңадан алынған Р1 үшін 

қайталанады.  Егер В  жүйесінің  соңғы алмастыруы  қолданылатын болса, үрдіс 

тоқтатылады. Мұндай ұйғарымдар жиыны А әріппесімен және В алмастырулар 

жиынымен қалыпты алгоритмді анықтайды. Үрдіс екі жағдайда ғана тоқтайды: 

1)  тиімді  алмастыру  табылмаған  жағдайда;  2)  олардың  жиынындағы  соңғы 

алмастыру пайдалынылған жағдайда. Әртүрлі қалыпты алгоритмдер бір-бірінен 

әріппелері және алмастырулар жүйесі арқылы ерекшеленеді. 

Натурал  сандарды  (бірлер  жиынымен  берілген)  қосуды  сипаттайтын 

қалыпты алгоритмге мысал келтірейік.  

 

Мысал: 

Әріппе              Алмастырулар жүйесі 

 

1

,





A

 

 

 

1

1







 

 

 

 

 

1

1





 

 

 

 

 

 

 

1

1



  

P сөзі: 11+11=111 

 

41 

Р  сөзін  Марковтың  қалыпты  алгоритмі  арқылы  біртіндеп  қайта  өңдеу  

мына кезеңдер арқылы өтеді: 

                Р=11+11+111                         P5=+1+111111 

                P1=1+11+111                         Р6=++1111111 

                P2=+1111+111                        P7=+1111111 

                P3= +111+1111                       Р8=1111111 

                P4=+11+11111                        P9=1111111 

Марковтың қалыпты алгоритмін кез келген алгоритм берілуінің әмбебап 

түрі  ретінде  қарастыруға  болады.  Қалыпты  алгоритмдер  әмбебаптығы 

қалыптастыру  принципі  арқылы  жарияланады:  кез  келген  ақырлы  А  әріппесінде 

кез келген алгоритм үшін оған пара-пар А әріппесі бойынша қалыпты алгоритм 

құруға болады. 

Соңғы тұжырымды түсіндірейік. Кейбір жағдайларда алмастыруларында 

тек  А  әріппесінің  әріптерін  пайдаланатын  болсақ,  А  әріппесінде  берілген 

алгоритмге  эквивалент  қалыпты  алгоритм  құрылмайды.  Дегенмен  А  әріппесін 

кеңейту арқылы (оған жаңа әріптерді қосу арқылы) қажетті, қалыпты алгоритм 

құруға болады. Бұл жағдайда, бастапқы А әріппесіндегі сөздерге ғана қолданы-

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

Егер N алгоритмі А әріппесінің кейбір кеңейімінде  берілген болса, онда 

N А әріппесі бойынша қалыпты алгоритм дейді.  

 

4.5 Бақылау тест тапсырмалары 

1 Тьюринг машинасын қандай түрде көрсетуге болады?  

A) ақырлы автомат  

B) КБ-тіл  

C) грамматика  

D) жүйе  

E) алгоритмдік тіл  

 

2 Жүйе түрінде қандай машинаны көрсетуге болады?  

A) ақырлы автомат  

B) Пост машинасы  

C) автомат  

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

E) Пост-Тьюринг машинасы  

 

3 



m  командасын орындағаннан кейін Пост машинасының лентасының күйі 

қандай болады?  

         бастапқы             командадан кейін  

 

 

42 

4 



m  командасын  орындағаннан  кейін  Пост  машинасының  лентасының  күйі 

қандай болады?  

     бастапқы                     командадан кейін 

 

 

5  M  m  командасын  орындағаннан  кейін  Пост  машинасының  лентасының  күйі 

қандай болады?  

         бастапқы              командадан кейін  

 

 

6  C  m  командасын  орындағаннан  кейін  Пост  машинасының  лентасының  күйі 

қандай болады?  

             бастапқы           командадан кейін 

 

 

7  Тоқта    n    командасын  орындағаннан  кейін  Пост  машинасының  лентасының 

күйі  қандай болады? 

 

                 бастапқы          командадан кейін 

 

 

43 

8 Пост машинасының автоматын іске қосқанда төмендегі жағдайдың қайсысы 

туындамайды  

A) автомат орындалмайтын командаға дейін орындап жетті (бос емес ұяшыққа 

белгіні жазу, бос ұяшықта белгіні өшіру); программаның орындалуы тоқтатылады, 

автомат тоқтайды, нәтижесіз тоқтату болады  

B)  автомат  тоқта  командасына  дейін  жетті,  программа  орындалды  деп 

есептеледі, нәтижесі бар тоқтату болады 

C)  автомат  нәтижелі  де,  нәтижесіз  де  тоқтатуға  жетпеді,  шексіз  жұмыс  істеу 

болады (автомат «тұрып қалады»)  

D)  автомат  лента  аяғына  дейін  жетті;  программа  жұмысы  тоқтайды,  автомат  

тоқтайды, нәтижесіз тоқтау болады  

E)  автомат  лентада  белгіні  жазуды  жүзеге  асырды  және  келесі  команданы 

орындауға көшеді  

 

9 Тьюринг машинасының қай жерінде жазу орындалады?  

A) жады;  

B) лента;  

C)  процессор  

D) қатар.  

E) бастиекте  

 

10 Тьюринг машинасының жұмыс істеу процесінде не байқалады?  

A) жұмысты басынан бастау;  

B) жұмысты тоқтату;  

C) кіріс жолын сырғыту;  

D) жолдан шығу.  

E) жұмысты екінші жолдан сырғыту  

 

11  Тьюринг  машинасының  келтірілген  функционалды  схемасы  қандай  есепті 

шешеді   

a 

0 

1 

2 

3 

4 

5 



 

q 

z1S   

z2S   

z3S   

z4S   

z5S   

q0L   

z1S 

 

A) бестік санау жүйесіндегі екі санды қосу  

B) бестік санау жүйесіндегі екі санды азайту   

C) бестік санау жүйесіндегі санға бірді қосу  

D) бестік санау жүйесіндегі саннан бірді азайту  

E) ондық санау жүйесіндегі санды бестік санау жүйесіне ауыстыру  

 

12  Тьюринг  машинасының  келтірілген  функционалды  схемасы  қандай  есепті 

шешеді   

A 

q 



 

z 



 S 

a 

qbR 

b 

qaR 

 

44 

A) бірінші таңбаны сөз соңына ауыстыру  

B) соңғы таңбаны сөз басына ауыстыру  

C) a символын b символымен ауыстыру  

D) b символын a символымен ауыстыру  

E)  a  символын  b  символымен  ауыстыру  және  b  символын  a  символымен 

ауыстыру  

 

13 Пост машинасы үшін келтірілген программа көмегімен қандай есеп шешіледі  

1. М 2  

2. 



 3  

3. М 4  

4. тоқта  

  

A) бос лентаға екі белгі жазу  

B) бастиекті солға бірінші бос позицияға дейін қозғалту  

C) бірнеше санның біреуіне бірді қосу  

D) екі көрші ұяшыққа анализ жасау (кіріс ұяшықтары) және үшінші ұяшықты 

өзгерту  (шығыс  ұяшығы).  Егер  кіріс  ұяшықтары  белгіленген  болса,  онда 

шығысында белгі өшіріледі; егер кіріс ұяшықтарының ең болмағанда біреуінде 

белгі болмаса, онда шығыс ұяшықта белгі қойылады  

E) лентада кез келген ара қашықтықта жазылған a және b екі санын қосу 

 

 

45 

5 АЛГОРИТМДЕР ТЕОРИЯСЫНЫҢ НЕГІЗГІ ҰҒЫМДАРЫ 

 

Алгоритм  деп  алдын  ала  анықталған  мақсатқа  жету  үшін,  есептің 

шешімін  табу  үшін  орындаушыға  (адамға,  компьютерге  және  т.б.)  берілген 

түсінікті нұсқаулардың тізбегін айтады. 

 

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

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

арқылы ажыратамыз. Олар алгоритмнің түсініктілігі, дискреттігі (жалғыздығы), 

анықтығы,  нәтижелігі,  жалпыға  бірдейлігі.  Берілген  орындаушы  үшін 

алгоритмнің  түсініктілігі  деп,  орындаушының  жарлықтарының  жүйесіне, 

құрамына  енетін  іс-әрекеттерді  орындау,  тексеру  туралы  жазбалар  мазмұнын 

айтады.  Алгоритм  ЭЕМ  қабылдайтын  және  сол  бойынша  қажетті  амалдарды 

орындай алатын нұсқаулар түрінде берілуі керек. 

Дискреттілігі  –  деп  алгоритм  жарлықтарының  тізбектелген  ретпен 

орындалуын  айтады.  Оның  бір  жарлығының  орындалуының  соңы  мен  келесі 

жарлықтың  басына  сілтеме  дәл,  нақты  анықталады.  Алгоритм,  әрқайсысы 

ЭЕМ-ді  белгілі  бір  қадам,  әрекет  жасататын  нұсқаулардың  тізбегінен  тұрады. 

Әрбір  жарлықты  орындағанда  алгоритмнің  орындалуы  аяқталды  ма  не  келесі 

қандай  жарлық  орындалады,  сол  туралы  дәл  мәлімет  болуы  шарт,  яғни 

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

ЭЕМ  үшін  әрбір  нұсқауды  орындағаннан  кейін  келесі  қай  жарлықты  орындау 

(не істеу керектігі) анық көрсетілуі қажет. 

Алгоритм  –  шектеулі  қадамдарды  орындап  болған  соң    нәтижеге  алып 

келеді.  Нәтижеде,  алгоритм  орындалған  соң  есептің  шешуінің  аяқталуы,  не 

қандай  да  бір  себептерге  байланысты  есепті  шешуді  жалғастыру  мүмкін 

еместігі  туралы  мәлімет  болуы  мүмкін.  Алгоритмнің  жалпылығы  деп  оны 

бірдей типтегі (түрдегі) есептерді шешу үшін қолдануға болатындығын айтады. 

 

 

5.2 Алгоритмді жазу тәсілдері 

Алгоритмдегі  жарлықтардың,  нұсқаулардың  берілу  түріне  қарай 

алгоритмді  жазу  әдістерін  ажыратуға  болады.  Орындаушының  өзіне  тән 

біліміне  байланысты  арнайы  таңбалар,  сөздер,  іс-қимылдар,  схемалар  арқылы 

алгоритмдерді жазудың тәсілдерін ұйымдастыруға болады. 

Мысалы, цирктегі құстар мен жануарларға алгоритмдер арнайы дауыстар, 

іс-қимылдар арқылы, автокөлікті жүргізу алгоритмі, телевизор, магнитофонды 

жұмыс істету алгоритмі арнайы пернелерді басу, бұрау арқылы жүзеге асырылады; 

т.с.с. әртүрлі таңбалармен, белгілермен берілген алгоритмдер көп кездеседі. 

Орындаушы  –  адам  болатын  жағдайда  алгоритм  көбінесе  сөзбен 

жазылады.  Сөзбен  жазылған  алгоритмдер,  ретпен  орналасқан  сөйлемдерден 

(нұсқаулардан)  тұрады.  Сонымен  бірге  алгоритмдер  арнайы  таңбалар,  блок-

схемалар,  формулалар,  кесте  түрінде,  ноталар  (сазгерлер  үшін)  арқылы 

жазылады. 

Енді сөзбен жазылған алгоритмге мысалдар қарастырайық. 

 

46 

1-мысал.  Екі  бүтін  санның  ең  үлкен  ортақ  бөлгішін  (ЕYОБ)  табу  керек. 

Бұл  есепті  шешу,  үлкен  санды  кішісінен  бөлу  арқылы,  сонан  соң  кіші  санды 

қалдыққа бөлу, бірінші қалдықты екінші қалдыққа бөлу және т.с.с. қалдық нөл 

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

бөлгіш нәтиже болып табылады. 

Бастапқы  берілген  екі  бүтін  санды  М  және  N  деп  белгілейік.  Бөлуді 

қайталанып  отыратын  азайту  амалымен  алмастырайық.  Онда  алгоритмді  

келесі түрде ұйымдастыруға болады: 

1. Басы 

2.  (M, N) енгізіңдер. 

3. Егер   M ≠ N   болса, онда 4 пунктке, әйтпесе 7 пунктке өтіңдер. 

4. Егер M > N   болса, онда 5 пунктке, әйтпесе 6 пунктке өтіңдер. 

5. M := M − N;  3 пунктке өтіңдер. 

6. N := N − M;   3 пунктке өтіңдер. 

7. EYOБ := M 

8.  EYOБ := M жауапқа шығару. 

9. Соңы. 

2-мысал.  Максимум  мен  минимумды    іздеу  (табу)  алгоритмі.  Ол  үшін 

бізге кез келген n нақты саннан тұратын шекті тізбек  а

1

, а

2

,..., а

і

,…, а

n

  берілсін. 

Сандардың саны аз болған жағдайда максимум мен минимумды оңай көрсетуге 

болады.  Ал,  егер  n  үлкен  болса,  онда  есеп  қиындайды.  Бірнеше  жүздеген 

көпразрядты сандардың ішінен максимум мен минимумын табудың қиындығы 

жоғары болады. Сондықтан, бір анықталған (тәртіпке) жүйеге сүйену қажет. 

Мысалы,  алғашқы  мән  ретінде  максимум  үшін  де,  минимум  үшін  де 

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

мәнімен  салыстырамыз.  Егер  келесі  сан  максимумнан  үлкен  болса,  онда  оны 

максимумның  жаңа  мәні  ретінде  қабылдаймыз  (алғашқы  мән  «ұмытылып» 

отырады), онан соң келесі тұрған санға өтеміз. Егер қарастырылып отырған сан 

максимумнан  үлкен  болмаса,  онда  оны  минимум  ретінде  алынған  санмен 

салыстырамыз.  Егер  осы  сан  минимумнан  кіші  болса,  оны  минимумның  жаңа 

мәні  ретінде  қабылдаймыз;  егер  бұл  сан  минимумнан  кіші  болмаса,  келесі 

санды  таңдауға  өтеміз.  Осындай  әдіспен  сандардың  бәрін  салыстыру  арқылы 

максимум  мен  минимумның  соңғы  мәнін  табамыз.  Осы  айтылған  ережені 

сөзбен жазу тәсілімен былай жазуға болады: 

1. Басы 

2. (a

i

, i = 1, 2,..., n) енгізіңдер. 

3. min := a

1

;     max := a

1

. 

4. i := 2 

5. Егер   a

i 

> max, онда 6 п. өтіңдер, әйтпесе 7 п. өтіңдер. 

6. max := a

i

;  9 пунктке өтіңдер. 

7. Егер   a

i 

< max, онда 8 п. өтіңдер, әтпесе 9 п. өтіңдер 

8. min := a

i

. 

9. i := i +1. 

10. Егер  i < n,   онда 5 пунктке өтіңдер, әйтпесе 11 пунктке өтіңдер. 

11. (max, min)  жауапқа шығарыңдар. 

12. Соңы. 

 

 

47 

жүктеу/скачать 1,43 Mb.

Достарыңызбен бөлісу: