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

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

Күйлер ауысуының диаграммасының қызметі басқару кезіндегі оның реакцияларын немесе поведениелерін (спецификацияны анықтау кезіндегі) кӛрсету болып табылады. Мұнда басқарушы сигнал немесе қолданушының командасы болуы мүмкін. Бұл команданы алғаннан кейін, жүйе оған жауап ретінде бір әрекет жасайды, яғни сол күйін сақтап қалады, не болмаса басқа күйге ауысады. Автоматтар теориясына сәйкес, мұнда диаграмма тұрғызу үшін, анықталады: бастапқы күй (терминальное состояние); әсер етуші басқарушы сигнал (немесе кӛшу шарты); орындалатын әрекет немесе бірнеше варианттар.

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

Түбіртектің оңға қозғалуы Түбіртектің солға қозғалуы М енін жазу m С енін өшіру m Басқаруды беру Тоқтау стоп n Пост машинасында ақпарат сызық бойынша орналасады да, бірінен соң бірі оқыла береді, ал ЭЕМ-де ақпаратты адресі бойынша оқуға болады; ЭЕМ командаларының жиынтығы әлде- қайда кең әрі Пост машинасы командаларына қарағанда айқын, т.с.с. Қазіргі уақытта мектептерде компьютерлердің кеңінен қолданылуына байланысты тек есептеу техникасының көмегімен ғана шығарылатын есептерді шығару мүмкіндігі пайда болды. Яғни аналитикалық жолмен шешуге болмайтын есептердің жуық теңдеулері сандық әдіспен алынып одан кейін компьютердің көмегімен оңай шығарылады [3,4]. Ондай есептерге келесілер жатады:

Бір формуланың көмегімен бірнеше рет есептеуді қажет ететін есептер. Әсіресе график салатын есептер.Шешу барысында жоғары дәрежелі теңдеулер немесе трансценденттік теңдеулер кездесетін сандық әдіспен оңай шешілетін есептер.Функциялардың экстремумдарын табу ұсынылып, ал оны аналитикалық жолмен табуға болмайтын есептер.Тек сандық әдістермен шешуге болатын анықталған интегралды табуға арналған есептер.Дифференциалдық теңдеулерге келтірілген есептер. Шешімі сандық әдісті қолдану арқылы табылады.Теңдеулер жүйесін шешуге арналған есептер.