«Дәлелдеу», «Алгоритм», «Анықталғандық» және «Тиімді есептеу» ұғымдары

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

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

Есептелетін функциялар классын келесідей көрсетуге болады. Алдымен қарапайым функциялар алынады:

- l(x) = x + 1 (жылжыту операторы),

- O(x) = 0 (нөлге айналдыру операторы),

- I_n^m(x₁, x₂,…, x_n) = x_m (жобалау операторы).

Барлық үш қарапайым функция барлық жерде анықталған және

интуитивты түрде есептеледі.

Тьюринг машинасының жұмысы.

Машинаның жұмысы ең алдымен төмендегілерді анықтау арқылы (бастапқы) жүзеге асырылыады:

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

- басының орналасуы;

- машинаның ішкі күйі.

Осы үш шарттың жиынтығы (аталмыш жағдайда) конфигурация деп аталады. Әдетте бастапқы уақытта машинаның ішкі күйі q₁ жағдайында болады, ал машинаның басы лентаның оң немесе сол жағының бірінші клеткасында орналасы.

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

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

Рекурсия – программаның өзін-өзі шақыруы. Рекурсиялық процедураны қолданған программалар өзінің қарапайымдылығымен, көрнектілігімен және шағын мәтінімен ерекшеленеді. Рекурсиялы алгоритмдердің мұндай қасиеті рекурсиялы процедураның не істеу керек екендігін көрсетеді, ал рекурсиялы емес алгоритм қалай істеу керек екендігін көрсетеді.

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

Осылайша, белгілі бір локальдды А айнымалысына рекурсияның әрбір деңгейінде жадының әр түрлі ұяшықтары сәйкес келеді және де әр түрлі мәнге ие болады.

Рекурсияның тереңдігі деп рекурсиялы шақырулардың максимал санын айтады.

Кез-келген Rec рекурсиялы процедурасы белгілі бір S операторлар жиынтығынан және бір немесе бірнеше рекурсиялы операторлардан тұрады.

Шартсыз рекурсиялы процедуралар шексіз үрдіске әкеліп соғады, бұл мәселеге аса назар аударған жөн, себебі, процедураны шексіз өзін-өзі шақыру мүмкін емес.

Осылайша, рекурсиялы процедураларға келесідей талап қойылуы қажет – рекурсиялы процедураны шақыру белгілі бір шартқа негізделуі керек және де ол рекурсияның белгілі бір деңгейінде жалған болуы керек.

Егер шарт ақиқат болса, онда рекурсия жалғасады. Жалған болған жағдайда рекурсия тоқтатылады және шақырылған процедуралық үрдістер рет-ретімен қайтарылады. Рекурсиялы процедура үш түрлі формада болуы мүмкін:

1. 
   рекурсия шақырылмас бұрын әрекеттердің орындалу формасы (рекурсиялық ағында);
   

S;

if шарт then Rec; end;

2. 
   рекурсия шақырылғаннан кейінгі әрекеттердің орындалу формасы (рекурсиялы қайтарым);
   

3. 
   рекурсия шақырылғанына дейінгі және кейінгі әрекеттердің орындалу формасы;
   

S1;

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

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

Бағдарламалаудың модульді (объектіге-бағытталған және «жоғарыдан – төмен») әдісін жақсы меңгеру үшін математиканың негізін білуді қажет етеді. Бағдарламалаудың модульді әдісінің математикалық негізін анықтау мақсатында, оқылатын пәндер мен логика-алгебралық ұғымдарының, терминдерінің арасында тезаурус түрінде салыстыру жүргіздік (9.1 кесте).