Алгоритм абстрактілі машина іспеттес

Алгоритм абстрактілі машина іспеттес.

Тьюринг машинасымен ж±мыс істеу Їшін объектілер туралы ±“ымдар“а то›талу ›ажет.

Шлемдегі барлы› объектілерді ЩртЇрлі алфавиттегі сйздер тЇрінде ›арастыру“а болады. Сонды›тан алгоритмніЈ ж±мыс істеу объектілері сйздер болып табылады.

Шрбір Тьюринг машинасында 2 бйлік бар:

1. 
   °яшы›тар“а бйлінген екі жа“ынан да шексіз лента
   
2. 
   Автомат - жазу/о›у инесі
   

Тьюринг машинасы мен тезисі болаша›та да ›олданылады, себебі кез келген проблема шешілмейді деп айту“а болмайды, шешілмейтін есеп болмауы керек, оны ›андай да бір шешілетін тЇрге келтіру керек, со“ан орайластырыл“ан алгоритм ›±растыру керек.

МашинаныЈ белгілі бір процесті орындауыныЈ йзі алгоритмдік процесс болып табылады. Сонды›тан алгоритмге ›ойылатын талаптар мен ›асиеттер оны орындайтын машина“а да ›ойылады:

1. 
   МашинаныЈ ж±мысы дискретті, бірінен кейін бірі орындалатын жеке – жеке командалармен орындалуы керек.
   
2. 
   Шрекеттер детерминделген , я“ни ›адамдар ›атаЈ реттелген , ал олардыЈ нЩтижесі алдыЈ“ы ›адамда алын“ан нЩтижелермен тікелей байланысты болуы керек.
   
3. 
   Ж±мыс алдында ал“аш›ы берілгендер алгоритмніЈ аны›талу облысынан алынуы керек.
   
4. 
   Саны санаулы ›адамдарды орындаудан соЈ нЩтиже алынуы керек.
   
5. 
   Машина универсалды , жан – жа›ты болуы керек, оныЈ кймегімен кез – келген алгоритмді орындайтын болуы керек.
   

МашинаныЈ орындайтын ›адамдары элементарлы болуы Їшін белгілі бір алфавит ар›ылы а›паратты алмастыру керек. Сонды›тан алгоритм – кез– келген а›ырлы алфавиттен берілгендерді немесе а›паратты алмастыру

ЕрежелерініЈ а›ырлы кез келген жЇйесі.

АлгоритмніЈ аны›талу облысынан алын“ан бастап›ы берілгендер А аофавиті жЩне а›ырлы {}таЈбалар тізбегін ›±расын, м±ндай тізбекті сйз дейді. Алгоритмді орындау барысында жаЈа сйз ›±рылады {}, олар В алфавитін ›±райды. Б±л алмастыруды жЇргізу Їшін келесі ›адамдар орындалады:

1. 
   Бастап›ы сйзініЈ бір сйзін В алфавитінен таЈбасымен алмастыру.
   
2. 
   Бастап›ы сйздіЈ таЈбасын йшіру.
   
3. 
   В алфавитінен бір таЈбаны бастап›ы сйзге ›осу.
   

Б±л машина туралы теорияны Алан Тьюринг (1936-1937), Эмиль Пост сия›ты “алымдар ±сын“ан. Осы принципке сЩйкестелген есептеу машиналары 8-9 жылдан кейін пайда бол“ан.

Б±л машинаныЈ Тьюрингтен айырмашылы“ы – ол йзініЈ теориясында «машина» емес «алгоритмдік жЇйе» деген терминді ›олдан“ан.

ОныЈ абстрактылы машинасы бірнеше бірдей секциялар“а бйлінген, о›у-жазу инесі бар шексіз лентадан т±рады. Шр секция бос немесе толтырыл“ан болуы мЇмкін. Лента“а тЇк жазылмаса секция бос, лента“а жазылып белгі тЇссе секция толы› деп есептеледі.

Лента жа“дайы процесс уа›ытында йзгермелі болды. Осы лента жа“дайы мен о›у-жазу инесініЈ орны туралы а›парат Пост машинасыныЈ жа“дайын ай›ындайды.

Инені «», метка-белгі М болсын. Секция бос болса, ешбір белгі тЇспейді. Бір ›адам жаса“анда ине оЈ“а немесе сол“а 1 ›адам жылжып белгіні салады немесе йшіреді. Программада“ы командалар“а сЩйкес машина 1 жа“дайдан келесі жа“дай“а кйшіп отырады.

Шрбір команданыЈ структурасы ХКУ болсын,

Х – орындалатын команда нймірі,

К – орындалатын Щрекет туралы н±с›ау,

У – келесі команда нймірі.
№командаКомандалардыЈ жазылуыМашина ЩрекетініЈ сипаттамасы1ОЈ“а ›адамХУИнені оЈ“а ›арай 1 секция“а жылжыту2Сол“а ›адамХУИнені сол“а ›арай 1 секция“а жылжыту3Белгі салуХ V УСекция“а белгі ›ойылады4Белгіні йшіруХ x УСекциядан белгі йшіріледі5Бас›аруды ауыстыруХ У₁

У₂Секцияда белгі жо› болса бас›ару у₁ командасына, Щйтпесе у₂ командасына беріледі6то›татуХ стоп !Машина ж±мысын то›татады7Тарма›ты ±йымдастыру? a; b°яшы›ты ›арау, егер ±яшы›та 0 т±рса, онда а номерлі команда“а кйші, Щйтпесе b нймірлі команда“а кйшу.

Б±л Щрекеттерге ›ойылатын ›осымша шарттар:

1. 
   ХМУ командасы бос секцияда орындалмайды
   
2. 
   ХсУ командасы толы› секцияда орындалады
   
3. 
   У командасыныЈ нймірі программада“ы бар команда нймірімен сЩйкес болуы керек.
   

Пост машинасы оЈ бЇтін сандарды жазуды ›арастырады, себебі кез келген сйз цифр тЇрінде кодталады.

Лентада К бЇтін саны К+1 келесі белгіленген секцияларда, унарлы санау жЇйесі ›олданылып жазылады.

0,2,3 сандарыныіЈ жазылуы:

ММММММММ
изін тексеру с±ра›тары

1. Алгоритмдік машиналардыЈ шы“уына не себеп болды?

2. Пост жЩне Тьринг машиналарыныЈ айырмашылы›тары?
°сынылатын Щдебиеттер

1. 
   Е. Бидайбеков, Е. Медеуов, А. Ниязбаев. Информатика бастамалары (алгоритмдеу). Алматы, 1990ж.
   
2. 
   Вирт Н. Алгоритмы + структуры данных. Программы. – СПб, 2001ж.
   
3. 
   Симонович С., Евсеев Г.Практическая информатика: Инфорком- Пресс, 1998г.
   
4. 
   Острейковский В.А. Информатика, Москва, 2000 г.
   
5. 
   Петров А.В., Алексеев В.Е., Ваулин А.С., Петрова М.А., Титов М.А., Шкатов П.Н. Вычислительная техника и программирование, Москва, 1990.
   

1. 
   есептелетін функция ±“ымы
   
2. 
   Рекурсия ±“ымы, рекурсивті функция
   
3. 
   Компьютер кймегімен есептелетін функциялар теориясы.
   
4. 
   Черч тезисі
   

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

Іс жЇзінде алгоритм – функцияны беру Щдісі. Ал функция таблица, схема, формула тЇрінде берілуі мЇмкін. Біра› кейбір процестерде бастап›ы енгізілген немесе берілген деректер мен алын“ан нЩтижедегі деректер арасында“ы байланысты ±йымдастыратын функцияны ›±ру ›иын, кЇрделі.

1 – ба“ыт Рекурсивті функциялар – есептелетін функцияла𠱓ымымен байланысты.

X жЩне Y жиындары бар болсын. X жиыныныЈ кейбір элементтеріне Y жиыныныЈ элементтері сЩйкес келсе, онда Y – те X – тен бйлшекті функция берілген дейді.

Y жиынында сЩйкес элементтері бар жЩне X элементтерден ›±рал“ан жиынныЈ элементтер жиыны функцияныЈ аны›талу облысы деп аталады.

X жиынында сЩйкес элеметтері бар Y жиыныныЈ элементтер жиыны функцияныЈ мЩндер облысы деп аталады.

Егер X –тен Y-тегі функцияныЈ аны›талу облысы X жиынымен беттессе, онда ол функцияны барынша аны›тал“ан деп атайды.

Осы ±“ым“а жЩне рекурсивті функция“а негізделіп алгоритмніЈ дЩл аны›тамасын ›±ру“а болады.

Кез – келген берілген деректерді (Їзілісті, дискретті) Щлдебір санау жЇйесінде натурал сандармен кодтау“а болады, онда

ОлардыЈ барлы› алмастыруы есептеу операцияларыныЈ тізбегіне келтіріледі, ал йЈдеу нЩтижесі солайынша бЇтін сан болып ›алады. Кез келген алгоритм берілген санды› функция Їшін бірдей, оныЈ мЩнін есептейді, ал оныЈ элементарлы ›адамдары ›арапайым арифметикалы› жЩне логикалы› операциялар болады. М±ндай функциялар есептелетін функциялар деп аталады.

Y(x,,,, x) функция класы бар болсын. Аргументтер бЇтін, нЩтижеде бЇтін сан немесе аргументі де нЩтижесі де дискретті болсын.

Y(x,,,, x) функциясы тимді есептелетін функция деп аталады, егер белгілі аргументтер мЩндері бойынша оныЈ мЩнін есептейтін алгоритм бар болса.

Шр тЇрлі тЇсінілетін процесстер Їшін есептелетін функциялар тізімі (алгоритмніЈ барлы› ›асиеттерін ›ана“аттандыратын) кЩдімгі математикалы› терминмен жеЈіл сипатталатын функциялар болса, рекурсивті деп аталады.

Кез келген алгоритмдік модель, рекурсивті функция алгоритмніЈ элементарлы ›адамын аны›тауы керек, деректерді йЈдеуге ›ажетті алмастыру тізбектерін ›ана“аттандыруы керек. Рекурсивті модельде м±ндай элементарлы ›адамдар ›арапайым санды› функциялар деп аталады. S

Б±л сандар комбинациясынан кЇрделі функциялар ›±рылады:

1. 
   S(x)=x+1 (бір аргументті бір орынды функция)
   
2. 
   O(x,,,, x) =0 –n орынды нйлге теЈбе теЈдік функциясы.
   
3. 
   I(x,,,, x)=X (1) n орынды йз аргументтерінен 1 мЩні теЈбе теЈді ›айталану функциясы.
   

m – орынды f функциялар n – орынды g (x,,,, x)

фу нкциясына ›ойылатын болсын. НЩтижеснде n – орынды функциясы алынады.

М±ны h функциясы g функциясынан суперпозиция ар›ылы алынды деп айтады.

М±ндай ›ою - деп берілгенді n- функция саны, олар келесі бір функцияныЈ g-діЈ аргументтері ретінде ›ойылып т±р.

Егер функциялары есептелетін болса, n- функциясы да есептеледі. Онда функциялары интуитивті есептелетін болса, n- функциясы да интуитивті есептеледі.

1) -ді табу керек.

2) -ді табу керек.

N=3-1=2 – нЩтиже 2-орынды функция болады:

.
Примитивті рекурсия

љандай да бір санды› бйлшек функциялар берілсін: n-орынды орынды .

G жЩне h функциясынан (n+1) орынды f функциясы примитивті рекурсия ар›ылы алынады, егер у натурал сандар Їшін

ФункцияныЈ аны›талу облысы натурал сандар жиыны бол“анды›тан, f-бйлшекті функция да (1)-ді ›ана“аттандырады,жЩне ол функция Щрбір g, h бйлшек функция Їшін табылады жЩне жал“ыз болады.

Рекурсия ›адамы йзгерген сайын (1):

(2)

тЇрінде жазылады.

(2)=> дербес жа“дайда g жЩне h барынша аны›тал“ан болады.

(2)-дегі g жЩне h функцияларыныЈ мЩндері табылатын болса функцияныЈ мЩндері де механикалы› есептеледі.

Аны›тама бйлшек функциясы примитивті рекурсия деп аталады, егер оны ›арапайым функциялар“а суперпозиция немесе примитивті рекурсия операцияларын ›олданып, саны санаулы операциялармен алу“а болса.
Мысалы:

1) 2-орынды функция примитивті рекурсивті функция.

примитивті

f(x_1,x_2,...x_n) – бйлшекті функция бйлшекті рекурсивті деп аталады, егер оны ›арапайым - функцияларынан суперпозиция , примитивті рекурсия , минимизация операцияларын санаулы рет ›олданып алу“а болса.

• 
  
  жүктеу/скачать 0.89 Mb.
  
  Достарыңызбен бөлісу: