Алгоритмнің тиімділігі мен күрделілігі. Тьюринг, Пост абстрактілі машиналарымен жұмыс

МАЗМҰНЫ

Кіріспе

Ақпарат пен ақпараттық жүйелер − Информатика ғылымының зерттеу нысандары болып табылады. Информатика ғылым ретінде ХХ ғасырдың ортасына пайда болғанымен ақпаратқа деген ғылыми қызығушылықтар мен осы саладағы зерттеулер одан ілгерірек кезеңде жүргізіле бастаған. Бұл ғылым 1940 жылдардың аяғында қалыптасып, бағдарламалық басқару принциптерін зерттеуді қамтитын “Кибернетика” ғылымынан бастау алады. Өткен ғасырдың басында телефон, телеграф, радио сияқты байланыс құралдарының өмірге келуіне орай “Байланыстар теориясы” атты ғылыми бағыт қалыптасты. Ол өз кезегінде кодтау теориясы мен ақпараттар теориясының пайда болуына негіз болды. Ақпараттар теориясы байланыс каналдары арқылы берілетін ақпаратты өлшеуге ықпал етті.

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

Алгоритмдер теориясын толыққанды игермей сапалы білімді бағдарламашыны, информатика пәнінің мұғалімін даярлау мүмкін емес. Қазіргі "ақпарат ғасырында" ақпарат қорына иелік етіп, оны сақтау, өңдеу және тұтынушыларға жеткізу технологиясын игерудің үлкен мәні бар. "Қазақстан Республикасында білім беруді дамытудың 2011-2020 жылдарға арналған мемлекеттік бағдарламасына" сай орта білім беру ұйымдарында электрондық оқыту жүйесінің қолданылу санын 2015 жылы 50%-ға, 2020 жылы 90%-ға арттыру жоспарланған. Осыған орай оқу үрдісінде компьютерлік техникалар мен оқыту жүйелерін пайдаланудың маңызы күн өткен сайын артуда. Болашақ информатика пәні мұғалімінің есептеу техникасының теориялық негіздерін игеруі міндетті шарт.

Курстық жұмыста абстрактілі автоматтар, алгоритмдер теориясының негізгі ұғымдары, алгоритмдер тиімділігі мен күрделіліктерін талдау сияқты Информатиканың іргелі ұғымдары жайлы теориялық мәліметтер берілген.

1 Алгоритм ұғымы. Алгоритмдер теориясының негізгі ұғымдары

1. 1 Алгоритм түсінігі және оның негізгі қасиеттері. Алгоритм орындаушысы. Алгоритмді ұсыну тәсілдері

Алгоритм ұғымы көптеген жылдар бойы интуитивтi ұғым болып келдi. Тек ХХ-ғасырдың 30-жылдарында көрнектi математиктер Д. Гильберт, А. Черч, Э. Пост және А. Тьюрингтың еңбектерiнде рекурсивтi функция ұғымына және алгоритмдiк үрдісті сипаттауға негiзделген алгоритмнiң формальды анықтамасы берiлдi. Соңынан математиканың жаңа саласы - Алгоритмдер теориясы қалыптасты. Ал ол есептеуiш техникасының дамуының теориялық негiзiн құрайды.

Алгоритм сөзi арифметикалық амалдарды орындау ережесiн тұжырымдаған ұлы математик Әл-Хорезмидiң (“Арифметикалық трактат” еңбегi, IX ғасыр) аты-жөнiнiң латынша algoritmi болып бұрмалауынан шыққан.

Алға қойған мақсатқа жетуде немесе берiлген есептi шешуде арнайы ережелер бойынша атқарушыға (адам‚ компьютер‚ робот‚ станок‚ программалау тiлдерi т. б. ) жинақты түрде берiлген нұсқаулар тiзбегi алгоритм делiнедi.

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

1. (дискреттiлiгi) . Ақпаратты өңдеу үрдісі ретiмен жазылған жеке-жеке нұсқаулар тiзбегiнен тұруы тиiс.
2. . Кез келген атқарушы (орындаушы) алгортмдi түсiндiрiп, орындай алатын болуы керек. Сондай-ақ әртүрлi мағыналы нұсқаулар енгiзiлмеуi тиiс.
3. Алгоритмнiң қарастырып отырған ақпараттың кез келген алғашқы .
4. Алгоритмнiңнәтижелiгi. Нұсқаулар шексiз көп болмай, қорытындыда оның нәтижесi болуы тиiс.

Алгоритмнiң маңызды қасиетi мынада: орындаушыдан есептi шешу әдiсi түсiну талап етiлмейдi, тек алдын-ала берiлген iс-әрекеттер тiзбегiн орындаса болғаны. Сондықтан орындаушы (атқарушы) ережедегі бұйрықтарға сүйенiп, алгоритмдi механикалық түрде орындайды. Алгоритм қандай да бiр орындаушыға (атқарушыға) арналып дайындалады. Мысалы, адам, компьютер және т. б. құрылғылар үшiн. Сондықтан алгоритмнiң сипаты орындаушы үшiн түсiнiктi болуы тиiс. Орындаушының түсiнiп, орындайтын барлық командалары оның командалары жүйесiн құрайды. Мысалы, компьютер үшiн командалар жүйесi: сандарды қосу, азайту, көбейту, бөлу және салыстырудан тұрады.

Алгоритмдік тіл - құрылымы нақтыланған, бiрыңғай және дәл жазылатын арнайы таңбалар мен ережелер жүйесiнен тұрады. Мұндағы таңбалар жиыны оның алфавитін , ал алгоритмдi жазу ережелерi оның синтаксисін құрайды.

Ол математикалық символиканы (сандарды, шамаларды, функция белгiлерiн, амал таңбаларын, жақшаларды) қамтиды.

Ақпаратты өңдеу алгоритмi табиғи тілде, блок-схема түрiнде, алгоритмдік тілде құрылуы мүмкiн.

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

Алгоритмнiң блок-схемалық түрiнде мемлекеттiк стандарт бекiткен арнайы символдар, схемалар пайдаланылады.

1. 2 Алгоритмдерге қойылатын негізгі талаптар. Алгоритмдік модельдер

1. Әрбір алгоритм берілгендермен (бастапқы, аралық, нәтижелік) жұмыс істейді.

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

2. Берілгендерді сақтау үшінжадқажет. Жад дискретті, әрқайсысында 1 ғана таңба сақталынатын біртекті ұяшықтар жиынтығынан тұрады. Сондықтан берілгендер мен жад көлемін есептеуге мүмкіндік бар.
3. Алгоритм жекелегенқарапайым қадамдардантұрады. Бірақ алгоритмді құрайтын түрлі қадамдар саны шектеулі болады. Мысалы, ЭЕМ-нің командалары жүйесі.
4. Алгоритм қадамдарының . Әрбір қадамнан кейін қай қадамды орындау қажеттігі не алгоритмді аяқтау қажеттігі көрсетіледі.
5. . Қандай да бір шекті қадамнан кейін нәтиже алынады.
6. Алгоритмжүзеге асыру механизмінсипаттайды. Алгоритм мен оны жүзеге асыру механизмінің қадамдары шектеулі.

1-6 талаптар ЭЕМ-дер үшін келесі түрде беріледі: 1-талап - ЭЕМ-нің сандық табиғаты; 2-талап - ЭЕМ жады; 3-талап - программа; 4-талап - ЭЕМ-нің логикалық құрылымы; 5-6 талаптар - ЭЕМ-нің есептеуіш құрылғылары.

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

1. Бастапқы берілгендердің өлшемдері шекті бола ма?
2. Қарапайым қадамдар санының шекті аралығын анықтауға бола ма?
3. Жад көлемінің шекті аралығын анықтауға бола ма?
4. Есептеу барысында қадам санын шектеуге бола ма?

1-4 сұрақтарға «жоқ» деп жауап беріледі. Себебі ЭЕМ үшін бұл өлшемдер шектеулі. Бірақ алгоритмдік есептеулермен айналысатын теорияда ешқандай шектеу болмайды. Сонымен алгоритм ұғымы берілгендер мен оларды өрнектеуді, жадты және онда берілгендердің орналасуын, алгоритмнің қарапайым қадамдарын, алгоритмді жүзеге асыру механизмін анықтауды талап етеді. Алайда бұл ұғымдарды анықтауда өзге де қосымша ұғымдар қажет етіледі. Сондықтан алгоритмдер теориясында нақты алгоритмдік модель ұғымы қолданылады. Бұл модель белгілі бір іс-әрекеттер шеңберінде әмбебап (универсал) болады. Алгоритмдік модельдің үш түрі қолданылады:

1. Белгілі бір уақыт аралығында саны шектеулі амалдарды орындайтын детерминирленген құрылғы. Мысалы, Тьюринг машинасы.

2. Рекурсивтік функцияларға негізделген модель.

3. Марковтың нормаль алгоритмдеріне негізделген модель. Мұндай модель түрлі сөз бөліктерінен сөздер құрастыруға негізделген.

1. 3 Алгоритмдi талдау және алгоритмді құру схемасы

Қойылған мақсатқа, есептiң бастапқы шарты мен оны шешу жолдарына және орындаушының қызметiн қарай алгоритм келесi түрлерге бөлiнедi.

1. Механикалық алгоритмiзделiндi нәтижеге жету үшiн тек бiр ғана түрде анықталатын қайталамалы iс-әрекеттер тiзбегiнен тұрады. Мысалы, машина двигателiнiң жұмыс iстеу алгоритмi.
2. Ықтималдық (схоластикалық) алгоритмесептi бiрнеше жолмен шешуге мүмкiндiк бередi. Соңынан нәтиженiң ықтимал мәнi алынады. Мысалы, Тьюрингтiң ықтимал машинасына негiзделген алгоритмдер.
3. Эвристикалық алгоритмденәтижеге жету үшiн iс-әрекеттер тiзбегi бiр мәндi анықталмайды. Бұларға ережелер (инструкциялар) жатады.

Эвристика − грекше iздеп табу, анықтау деген сөз. Ол қойылған есептi шешудiң белгiсiз жолдарын анықтайтын арнайы әдiстердi қамтиды. Эвристика − дәл шешiмi белгiсiз есептердi шешудiң тиiмдi бағыттарын анықтайтын әдіс, шығармашылықпен ойлауды зерттейдi.

Алгоритм ұғымы есептi шешу әдiсi ұғымымен тығыз байланысты. Алгоритм − есептi шешу мен оны практикалық қолдану әдiсiн сипаттаудан тұрады. Ол әдiстi зерттеу нәтижесiнде құрылады.

Алгоритмнiң берiлу тәсiлдерi алуан түрлi: формула, кесте, сөз түрiнде, графиктiк түрде, алгоритмдiк және программалау тiлдерiнде берiлу мүмкiн. Мысалы, программалау тiлiнде берiлген алгоритм сипаттамасы программа делiнедi.

Берiлген есептi шешудің алгоритмiн құруда келесi схеманы қолданған жөн:

1. Есептiң қойылымын зерттеу.

2. Алгоритм әмбебап болуы үшiн бастапқы берiлгендердiң типтерiн анықтау.

3. Нәтиженiң типтерiн анықтап, олар үшiн белгiлеулер енгiзу.

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

5. Алгоритмнiң дұрыс құрылғандығын тексеру. Алгоритм сипаттамасында кездескен қателердi жою.

6. Алгоритмдi сынақтаудан (тестiлеуден) өткiзу.

Алгоритм құру − қиын мәселе. Оны дайындау барысында түрлi логикалық қателiктер жiберiлуi мүмкiн. Сондықтан алгоритмнiң дұрыстығына, оның көпшiлiкке арналғандығына көз жеткiзу үшiн нақты есеп алып, оны сынақтау (тестiлеу) қажет. Әдетте осы мақсатта шешiмi белгiлi есептер (тестiк есептер) қолданылады. Мысалы, квадрат теңдеудi шешуге арналған алгоритмдi тексеруде 3 түрлi теңдеудi қарастыру жеткiлiктi. Олар:

1. Әртүрлi нақты түбiрлi теңдеу.

2. Бiрдей нақты түбiрлi теңдеу.

3. Терiс дискриминантты теңдеу. Мұнда комплекстi түбiрлер анықталады не нақты сандар жиынында түбiр табылмайтындығы көрсетіледі.

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

Марковтың нормаль алгоритмі ( МНА ) - алгоритм ұғымының формальды анықтамасын берудің стандартты тәсілдерінің бірі (Тьюринг машинасы сияқты) . Бұл ұғымды көрнекті кеңес математигі А. А. Марков (1903-1979жж. ) 1940 жылдардың соңында енгізген. Марков алгоритмдері туралы сөз болғанда, оны "алгорифм" деп атау қабылданған.

1. 4. 1 Қарапайым операторлар мен танып-білгіштер

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

Қарапайым операторлар деп қарапайым алфавиттік оператор-ларды айтады. Олардың тізбектей орындалуы нәтижесінде алгоритм-дік жүйедегі кез келген алгоритм жүзеге асырылады.

Қарапайым танып-білгіштер арқылы өңделетін ақпараттың қасиеттері анықталады.

Қандай да бір алгоритмнің қарапайым операторының орындау ретін бағдарланған граф арқылы беруге болады (бағдарланған граф - алгоритмнің граф-схемасы) .

Алгоритмнің граф-схемасы бір-бірімен байланыстырылған төбелердің саны шекті жиынынан тұрады. Төбелерді кейде тораптар (узлы) деп те атайды. Әрбір торапқа қандай да бір оператор не танып-білгіш сәйкестендіріледі. Тек кіріс, шығыс тораптары ерекше тораптарға жатқызылады (1. 1-сурет) .

1. 1-сурет

Оператор сәйкестендірілетін кіріс торабынан тек бір доға шығады. Ал танып-білгіш сәйкестендірілген тораптардан 2 доға шығады. Шығыс торабынан ешқандай доға шықпайды. Граф-схема торабына енетін доғалар саны түрліше болуы мүмкін.

Граф-схема арқылы анықталатын алгоритмнің жұмысы келесі түрде жүзеге асырылады: бастапқы сөз кіріс төбесіне енгізіліп, бағыттауыш бойымен жылжиды. Танып-білгіш торапта шарт тексеріледі. Шарт қанағаттандырылған жағдайда сөз операторлық торапқа , керісінше жағдайда танып-білгішке жіберіледі.

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

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

1. 4. 2 Нормаль алгоритмдер

Нормаль алгоримтдерде қарапайым оператор ретінде алмастыру операторы , ал қарапайым танып-білгіш ретінде кіріс танып-білгіші қолданылады.

Кіріс танып-білгіші р ₁ сөзінің қандай да бір q сөзінің құрамына енетіндігі-енбейтіндігі шартын тексереді.

Алмастыру операторы q сөзінің сол жағынан бастап, р ₁ сөзін р ₂ сөзімен алмастырады, яғни р ₁ →р ₂ . Мысалы, abcabca сөзіне қолданылған bc→cb алмастыруы 2 қадамнан кейін acbacba сөзін береді:

abcabca→acbabca→acbacba.

Алгоритмнің орындалуы барысында алынатын р ₁ , р ₂ , …, р _n сөздер тізбегі р ₁ сөзінен р _n сөзіне жеткізетін дедуктивтік тізбек делінеді.

Кіріс танып-білгіші мен алмастыру операторлары арқылы граф түрінде берілген алгоритмдер жалпыланған нормаль алгоритмдер деп аталады. Мұнда әрбір алмастыру операторына сәйкес танып-білгіштен шығатын бір ғана доға сәйкестендіріледі.

ba→ab, bc→ba, bb→aс алмастырулары арқылы берілген жалпыланған нормаль алгоритмді қарастырайық (1. 2-сурет) . Бастапқы сөз bcbaab түрінде берілсін. Нәтижеде bc сөзі алынады:

bcbaab→bcabab→bcaabb→baaabb→bc.

Граф-схемалары келесі шарттарды қанағат-тандыратын жалпы нормаль алгоритмдер нормаль алгоритмдер делінеді:

1. Танып-білгішке сәйкестендірілген барлық тораптар нөмірлері бойынша 1 менnарасында реттелінеді.
2. Алмастыру операторына сай тораптан шығатындоғаларалғашқы танып-білгішке қатысты торапта немесе шығыс торабында түйіседі. Алғашқы жағдайда алмастыруқарапайым алмастырудеп, екінші жағдайданәтижелік алмастырудеп аталады. 1. 2-сурет
3. Кіріс торабыдоға арқылы бірінші танып-білгішке жалғастырылады.

Жалпы, нормаль алгоритмдерде қарапайым алмастырулар р ₁ →р ₂ түрінде, ал нәтижелік алмастырулар р ₁ →. р ₂ түрінде таңбаланады.

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

Алфавиті А={+, 1} және алмастыру жүйесі ‘1+1’→’11’, ‘1’→. ’1’ болатын А. А. Марков нормаль алгоритмі жұмысын қарастырайық. Бастапқы сөз ‘11+11+1’ түрінде берілсін. Алгоритмнің орындалу нәтижесі:

‘11+11+1’→’+1’→’’.

Алгоритм жұмысы барысында бірліктер топтастырылады.

Нормализация принципі. Қандай да бір шекті А алфавиті арқылы құрылған кез келген алгоритмге осы алфавит бойынша эквивалентті нормаль алгоритм құруға болады.

Көптеген жағдайда А алфавиті бойынша құрылған алгоритмге эквивалентті алгоритм құру мүмкін болмайды. Бірақ А алфавитіне жаңа әріптер қосып, кеңейте отырып, қажетті нормаль алгоритм тұрғызуға болады (1. 3-сурет) .

Егер де N алгоритмі А алфавитінің кеңейтілуі арқылы құрылса, онда N алгоритмі А алфавитіне қатысты нормаль алгоритм делінеді.

Егер де А алфавитіндегі әрбір р сөзі үшін F(p) =N(p) орындалатындай N нормаль алго-ритмі табылса, онда А алфавитіне қатысты 1. 3-сурет.

F(p) бір орынды бөлікше сөздік функция нормаль есептелінетін делінеді.

Мысал. {0, 1} алфавитінде F(p) =pa формуласымен берілген сөздік функцияны қарастырайық. {0, 1, 2} кеңейтілген алфавитінде 20 →02, 21→12, 2→. а, Λ→2 схемалы N нормаль алгоритмі берілсін (мұндағы, Λ - бос орын) .

{0, 1} алфавитінің қандай да бір 0110 =p сөзін алайық. Бірінші қадам нәтижесі бойынша − 2 0110. Әрбір келесі қадамда 2 символы бір орынға оңға қарай жылжытылады. Бесінші қадамнан кейін 01102 сөзі алынады, яғни 0110а=ра.

Дербес жағдайда Λ→. Λ схемалы алгоритм F(p) =p функциясын, ал Λ→Λ схемалы алгоритм еш жерде анықталмаған функция мәнін есептейді.

Нормализация принципі математикалық тұрғыдан дәлелденбей-ді.

1. 4. 3 Нормаль алгоритмдердің композициясы

Берілген алгоритмнен жаңа алгоритм құру үрдісі композиция делінеді.

1) Алгоритмнің суперпозициясы. А мен В алгоритмдерінің суперпозициясында А алгоритмінің шығыс сөзі В алгоритмінің кіріс сөзі ретінде қарастырылады. Нәтижені C(p) =B(A(p) ) арқылы өрнектеуге болады. Суперпозиция кез келген саны шекті алгоритмдер үшін орындалады.

2) Х алфавитіндегі А, В алгоритмдерінің бірігуі деп сол алфавитке қатысты С алфавитін айтады. Мұнда А және В алгоритмдерінің анықталу облыстарының қиылысуындағы кез келген р сөзі A(p) және B(p) қатар орналасқан сөздеріне түрлендіріледі. Ал басқа сөздер үшін бұл алгоритм анықталмаған.

Мысалы, X={a, b} алфавиті, A={ab→ba}, B={ba→ab} алгоритмдері және олардың анықталу облыстарының қиылысуында жатқан аba сөзі берілсін. Нәтиже A(aba) =baa, B(aba) =aab, C(aba) =bb түрінде алынады.

3) Алгоритмнің тармақталуы А, В және С алгоритмдерінің композициясын құрайды. Композиция нәтижесі D болсын. D алгоритмінің анықталу облысы А, В және С үш алгоритмінің анықталу облыстарымен беттеседі. Осы қиылысуда жатқан кез келген р сөзі үшін егер де C(p) =e болса, онда D(p) =A(p) және D(p) =B(p) орындалады. Мұндағы е - бос жол.

4) Итерация амалы А, В алгоритмдерінің композициясы арқылы өрнектеледі. Композиция нәтижесі С алгоритмі арқылы беріледі. Қандай да бір р кіріс сөзінен C(p) шығыс сөзі В алгоритміне А алгоритмін бірнеше рет тізбектей қолдану арқылы алынады.

Мысалы, X={a, b} алфавиті, A={ab→ba}, B={bbbaa→ab} алгоритмдері берілсін. Демек, C(ababb) =ab нәтижесі келесі түрде алынады:

ababb→baabb→babab→bbaab→bbaba→bbbaa→ab.

1-4 композицияларды нормаль алгоритмдерге қолдануда нормаль алгоритмдер алынады . Кез келген алгоритмнің жұмысын орындай-тын универсал алгоритм құру есебінің маңызы зор.

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

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

f функциясы есептелетін функция делінеді, егер де осы функцияның анықталу облысындағы кез келген аргумент үшін функция мәнін есептейтін Тьюринг машинасы табылса. Егер де мұндай машина табылмайтын болса, онда f функциясы есептелінбейтін функция делінеді.

f функциясының анықталу облысының ішкі жиынындағы аргументтер үшін функция мәнін есептейтін Тьюринг машинасы бар болса да, f функциясы есептелінбейтін функция делінеді.

Егер f функциясының есептеу нәтижесі “ақиқат” не “жалған” түріндегі логикалық өрнек болса, онда есеп − берілген есептелетін функцияға қатысты шешілетін не шешілмейтін есеп деп аталады. Есеп бастапқы берілгендердің кейбірі үшін шешілетін, ал келесі біреулері үшін шешілмейтін болғандықтан, бастапқы берілгендердің мүмкін мәндерін нақтылап көрсету керек.

Машина жұмысын тоқтату проблемасының (мәселесінің) шешілмейтіндігі дәлелденген есепке жатады. Ол келесі түрде беріледі:

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

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

2 Автомат - ақпараттық жүйенің негізгі Элементі. Абстрактілі автоматтар

2. 1 ЭЕМ - ақпаратты өңдеудің әмбебап құралы

Пайдаланушы тұрғысынан алғанда компьютер қиындығы түрліше есептерді шешуде анағұрлым күрделі амалдарды орындайтын “қара жәшік” ретінде ұғынылады. Ақпаратты түрлендіру, өңдеу үрдісіне талдау жасай отырып, “қара жәшіктің” құрылысын қарастырайық. Мұнда келесі мәселелерге назар аударған жөн:

1. Кез келген есептеуіш машинасы (үлкен немесе кіші ЭЕМ, дербес компьютер, Супер-ЭЕМ) автоматты түрде жұмыс істейді. ЭЕМ-дерді автомат ретінде келесі құрылымдық схемалар түрінде беруге болады (2. 1, 2. 2-суреттер) :

Орындаушы элементті арифме-тикалық-логикалық құрылғы (АЛҚ), жад, енгізу-шығару құрылғылары құрайды.

Автомат

2. 1-сурет

Басқарушы құрылғылар

Орындаушы құрылғылар

Қосымша құрылғылар

Автоматтың басқарушы элементі-нің қызметін автоматты жұмыс режимін қамтамасыз ететін басқару құрылғы-лары атқарады.

Қосымша құрылғыларға автоматтың жұмысын кеңейтіп, жақсартатын қосымша құралдар жатады.

Жад

Арифметикалық-логикалық құрылғы

Басқару құрылғысы

Перифериялық құрылғылар

Ақпарат

... жалғасы

Алгоритмдер теориясының негізгі ұғымдары

Алгоритмдер теориясы. Анықтамасы. Қасиеттері. Түрлері. Алгоритмді жазу әдістері. Алгоритм модельдері

Алгоритмдер және деректер структурасы

АЛГОРИТМНІҢ ПРАКТИКАЛЫҚ АСПЕКТІЛЕРІ. АВТОМАТТАР ТЕОРИЯСЫ

АЛГОРИТМДЕР ТЕОРИЯСЫН ИНТЕЛЛЕКТУАЛДЫ ЖҮЙЕЛЕРДЕ ҚОЛДАНЫЛУЫНА ҚАТЫСТЫ ТЕРМИНДЕРГЕ ШОЛУ

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

Тьюринг машиналары

Алгоритмды оқыту

Информатика пәнінен лекциялық сабақтардың тезистері

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

• Іс жүргізу
• Автоматтандыру, Техника
• Алғашқы әскери дайындық
• Астрономия
• Ауыл шаруашылығы
• Банк ісі
• Бизнесті бағалау
• Биология
• Бухгалтерлік іс
• Валеология
• Ветеринария
• География
• Геология, Геофизика, Геодезия
• Дін
• Ет, сүт, шарап өнімдері
• Жалпы тарих
• Жер кадастрі, Жылжымайтын мүлік
• Журналистика
• Информатика
• Кеден ісі
• Маркетинг
• Математика, Геометрия
• Медицина
• Мемлекеттік басқару
• Менеджмент
• Мұнай, Газ
• Мұрағат ісі
• Мәдениеттану
• ОБЖ (Основы безопасности жизнедеятельности)
• Педагогика
• Полиграфия
• Психология
• Салық
• Саясаттану
• Сақтандыру
• Сертификаттау, стандарттау
• Социология, Демография
• Спорт
• Статистика
• Тілтану, Филология
• Тарихи тұлғалар
• Тау-кен ісі
• Транспорт
• Туризм
• Физика
• Философия
• Халықаралық қатынастар
• Химия
• Экология, Қоршаған ортаны қорғау
• Экономика
• Экономикалық география
• Электротехника
• Қазақстан тарихы
• Қаржы
• Құрылыс
• Құқық, Криминалистика
• Әдебиет
• Өнер, музыка
• Өнеркәсіп, Өндіріс