Пост алгоритмдік машинасы алгоритм ұғымын дәлелдеуші
Бұл машинаның Тьюрингтен айырмашылығы – ол өзінің теориясында «машина» емес «алгоритмдік жүйе» деген терминді қолданған.
Оның абстрактылы машинасы бірнеше бірдей секцияларға бөлінген, оқу-жазу инесі бар шексіз лентадан тұрады. Әр секция бос немесе толтырылған болуы мүмкін. Лентаға түк жазылмаса секция бос, лентаға жазылып белгі түссе секция толық деп есептеледі.
Лента жағдайы процесс уақытында өзгермелі болды. Осы лента жағдайы мен оқу-жазу инесінің орны туралы ақпарат Пост машинасының жағдайын айқындайды.
Инені « », метка-белгі М болсын. Секция бос болса, ешбір белгі түспейді. Бір қадам жасағанда ине оңға немесе солға 1 қадам жылжып белгіні салады немесе өшіреді. Программадағы командаларға сәйкес машина 1 жағдайдан келесі жағдайға көшіп отырады.
Әрбір команданың структурасы ХКУ болсын,
Х – орындалатын команда нөмірі,
К – орындалатын әрекет туралы нұсқау,
У – келесі команда нөмірі.
№
|
команда
|
Командалардың жазылуы
|
Машина әрекетінің сипаттамасы
|
1
|
Оңға қадам
|
ХУ
|
Инені оңға қарай 1 секцияға жылжыту
|
2
|
Солға қадам
|
ХУ
|
Инені солға қарай 1 секцияға жылжыту
|
3
|
Белгі салу
|
Х V У
|
Секцияға белгі қойылады
|
4
|
Белгіні өшіру
|
Х x У
|
Секциядан белгі өшіріледі
|
5
|
Басқаруды ауыстыру
|
Х У1
У2
|
Секцияда белгі жоқ болса басқару у1 командасына, әйтпесе у2 командасына беріледі
|
6
|
тоқтату
|
Х стоп !
|
Машина жұмысын тоқтатады
|
7
|
Тармақты ұйымдастыру
|
? a; b
|
Ұяшықты қарау, егер ұяшықта 0 тұрса, онда а номерлі командаға көші, әйтпесе b нөмірлі командаға көшу.
|
Бұл әрекеттерге қойылатын қосымша шарттар:
ХМУ командасы бос секцияда орындалмайды
ХсУ командасы толық секцияда орындалады
У командасының нөмірі программадағы бар команда нөмірімен сәйкес болуы керек.
Егер келтірілген шарттар сақталмаса, онда машина нәтижесіз жұмысын аяқтайды. Х стоп командасы нәтижелі орындалады. Себебі, ол өзінің алдындағы әрекеттер орындалып барып солардың нәтижесінде орындалады. Кейде машина тоқтамауы мүмкін, егер командалардың ешқайсысында тоқтау командасына көшу нөмірі болмаса.
Пост машинасы оң бүтін сандарды жазуды қарастырады, себебі кез келген сөз цифр түрінде кодталады.
Лентада К бүтін саны К+1 келесі белгіленген секцияларда, унарлы санау жүйесі қолданылып жазылады.
0,2,3 сандарыныің жазылуы:
Өзін тексеру сұрақтары
1. Алгоритмдік машиналардың шығуына не себеп болды?
2. Пост және Тьринг машиналарының айырмашылықтары?
Ұсынылатын әдебиеттер
Е. Бидайбеков, Е. Медеуов, А. Ниязбаев. Информатика бастамалары (алгоритмдеу). Алматы, 1990ж.
Вирт Н. Алгоритмы + структуры данных. Программы. – СПб, 2001ж.
Симонович С., Евсеев Г.Практическая информатика: Инфорком- Пресс, 1998г.
Острейковский В.А. Информатика, Москва, 2000 г.
Петров А.В., Алексеев В.Е., Ваулин А.С., Петрова М.А., Титов М.А., Шкатов П.Н. Вычислительная техника и программирование, Москва, 1990.
3-тақырып: «Алгоритмдік шығарылмайтын есептер. Есептелетін функциялар»
Дәріс жоспары:
есептелетін функция ұғымы
Рекурсия ұғымы, рекурсивті функция
Компьютер көмегімен есептелетін функциялар теориясы.
Черч тезисі
21-ші ғасырдың ортасына дейін алгоритм ұғымы есептеу әдістері ұғымымен теңестірілді. Есептеу әдістерінде қолданылатын арифметикалық, анализдік, тригонометриялық операциялардың орындалу алгоритм іспеттес болып жүрді. Ондай проблемаларды шешу үшін қосымша арнаулы дәлелдеулердің қажеті болмады. Ал 21-ші ғасырдың 2-ші жартысынан бастап сандық емес объектілерге қолданылатын алгоритмдерге қатаң формулировка берудің болмайтындығы белгілі болды. Лейбництің тұжырымдамасы бойынша алгоритмдік шешілмейтін есептер бар, сондықтан кез келген математикалық тұжырымдамалардың дұрыстығын дәлелдейтін алгоритм құрастыру қажеттігі туындады. Ол барлық теоремалардың дұрыстығын дәлелдейтін болуы керек.
Анықтама. Әлдебір алгоритм көмегімен есептелетін функцияны есептелетін функция дейді.
Іс жүзінде алгоритм – функцияны беру әдісі. Ал функция таблица, схема, формула түрінде берілуі мүмкін. Бірақ кейбір процестерде бастапқы енгізілген немесе берілген деректер мен алынған нәтижедегі деректер арасындағы байланысты ұйымдастыратын функцияны құру қиын, күрделі.
1 – бағыт Рекурсивті функциялар – есептелетін функциялар ұғымымен байланысты.
X және Y жиындары бар болсын. X жиынының кейбір элементтеріне Y жиынының элементтері сәйкес келсе, онда Y – те X – тен бөлшекті функция берілген дейді.
Y жиынында сәйкес элементтері бар және X элементтерден құралған жиынның элементтер жиыны функцияның анықталу облысы деп аталады.
X жиынында сәйкес элеметтері бар Y жиынының элементтер жиыны функцияның мәндер облысы деп аталады.
Егер X –тен Y-тегі функцияның анықталу облысы X жиынымен беттессе, онда ол функцияны барынша анықталған деп атайды.
Осы ұғымға және рекурсивті функцияға негізделіп алгоритмнің дәл анықтамасын құруға болады.
Кез – келген берілген деректерді (үзілісті, дискретті) әлдебір санау жүйесінде натурал сандармен кодтауға болады, онда
Олардың барлық алмастыруы есептеу операцияларының тізбегіне келтіріледі, ал өңдеу нәтижесі солайынша бүтін сан болып қалады. Кез келген алгоритм берілген сандық функция үшін бірдей, оның мәнін есептейді, ал оның элементарлы қадамдары қарапайым арифметикалық және логикалық операциялар болады. Мұндай функциялар есептелетін функциялар деп аталады.
Y(x ,,,, x ) функция класы бар болсын. Аргументтер бүтін, нәтижеде бүтін сан немесе аргументі де нәтижесі де дискретті болсын.
Достарыңызбен бөлісу: |
