«Алгоритм жЩне оныЈ кЇрделілігі» пшнін ољыту-шдістемелік кешен


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



бет2/8
Дата17.06.2016
өлшемі0.89 Mb.
#143176
1   2   3   4   5   6   7   8

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


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

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



Анытама. Шлдебір алфавиттен алын“ан ЩріптердіЈ кез келген тізбегі осы алфавитте сйз деп аталады.

Анытама. Сйздегі ЩріптердіЈ саны сйз ±зынды“ы деп аталады. Шріптері жо› сйзді бос сйз дейді. Олар «» немесе деп белгіленеді.

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



Анытама. Алгоритм ›олданылатын сйзді енгізілетін сйз дейді. АлгоритмніЈ нЩтижесі шы“арылатын сйз деп аталады. Алгоритм ›олданылатын сйздердіЈ жиыны алгоритмніЈ ›олданылу облысы деп аталады.

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



  1. °яшы›тар“а бйлінген екі жа“ынан да шексіз лента

  2. Автомат - жазу/о›у инесі

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

Анытама. Тьюринг машинасы деп жЇйесін айтады. М±нда“ы: А – шекті –жиын, Тьюринг машинасыныЈ алфавиті, - А алфавитініЈ бос сйзі, Q –Тьюринг машинасыныЈ жа“дайын білдіретін шекті жиынныЈ элементі, q1- ТМ-ныЈ бастап›ы жа“дайы, q0- МТ-ныЈ то›тау жа“дайы, пассивті жа“дай, Т-МТ-ныЈ жылжу жиыны, - МТ-ныЈ программасы.

Анытама. Алгоритм (Тьюринг бойынша) – ›ойыл“ан есепті шешуге келтірілетін Тьюринг машинасына ›±рыл“ан программа.

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

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


  1. МашинаныЈ ж±мысы дискретті, бірінен кейін бірі орындалатын жеке – жеке командалармен орындалуы керек.

  2. Шрекеттер детерминделген , я“ни ›адамдар ›атаЈ реттелген , ал олардыЈ нЩтижесі алдыЈ“ы ›адамда алын“ан нЩтижелермен тікелей байланысты болуы керек.

  3. Ж±мыс алдында ал“аш›ы берілгендер алгоритмніЈ аны›талу облысынан алынуы керек.

  4. Саны санаулы ›адамдарды орындаудан соЈ нЩтиже алынуы керек.

  5. Машина универсалды , жан – жа›ты болуы керек, оныЈ кймегімен кез – келген алгоритмді орындайтын болуы керек.

Сипаттал“ан машинаныЈ ›±рыл“ылары немесе структурасы ›арапайым болса жЩне орындалатын ›адамдар элементарлы болса, алгоритмніЈ орындалуы машинаныЈ ж±мыс істеуі деп есептеуге болады .

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

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

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



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

  2. Бастап›ы сйздіЈ таЈбасын йшіру.

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

Егер алфавитке «бос таЈба» деп аталатын таЈба ›осылса, оны сйзге оЈ жа“ынан да сол жа“ынан да ›осса› та сйз йзгермейді, я“ни 1) операция бос таЈбаны алмастыру болады. Сонда 2) – 3) – операцияларды орындаса› та, бЩрібір 1) – ›адамда та“ы сол алдыЈ“ы ›адам ›алады. Сонды›тан абстрактылы машина Щр символды зерттейді, сосын шексіз лента“а – жады“а са›тайды, егер символ бос болмаса оны бас›а таЈбамен алмастырады да жаЈа ›алыпта т±рады.

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


Пост алгоритмдік машинасы алгоритм ±“ымын дЩлелдеуші

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

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

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

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

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

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

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

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

У2Секцияда белгі жо› болса бас›ару у1 командасына, Щйтпесе у2 командасына беріледі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.


3-та›ырып: «Алгоритмдік шы“арылмайтын есептер. Есептелетін функциялар»

ДЩріс жоспары:

  1. есептелетін функция ±“ымы

  2. Рекурсия ±“ымы, рекурсивті функция

  3. Компьютер кймегімен есептелетін функциялар теориясы.

  4. Черч тезисі

21-ші “асырдыЈ ортасына дейін алгоритм ±“ымы есептеу Щдістері ±“ымымен теЈестірілді. Есептеу Щдістерінде ›олданылатын арифметикалы›, анализдік, тригонометриялы› операциялардыЈ орындалу алгоритм іспеттес болып жЇрді. Ондай проблемаларды шешу Їшін ›осымша арнаулы дЩлелдеулердіЈ ›ажеті болмады. Ал 21-ші “асырдыЈ 2-ші жартысынан бастап санды› емес объектілерге ›олданылатын алгоритмдерге ›атаЈ формулировка берудіЈ болмайтынды“ы белгілі болды. ЛейбництіЈ т±жырымдамасы бойынша алгоритмдік шешілмейтін есептер бар, сонды›тан кез келген математикалы› т±жырымдамалардыЈ д±рысты“ын дЩлелдейтін алгоритм ›±растыру ›ажеттігі туындады. Ол барлы› теоремалардыЈ д±рысты“ын дЩлелдейтін болуы керек.

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

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

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) -ді табу керек.



, -ні табу Їшін -ді -ге ›ою керек, ал =0 сонда .

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

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

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

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

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



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

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

(2)

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


Примитивті рекурсия f=R(g, h) деп белгіленеді. R- бйлшек функциялар жиынында аны›тал“ан 2-орынды бйлшек операция символы деп ›арастырылады.

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

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

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

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



примитивті


Аны›тама:

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


1   2   3   4   5   6   7   8




©dereksiz.org 2024
әкімшілігінің қараңыз

    Басты бет