Тізімдер. Циклдік тізімдер. Ортогоналды тізімдер 10 страница

Реляциялық есептеулер.

Нақты реляциялық МҚБЖ-да шындығында қазір реляциялық алгебра да реляциялық есептеулер де таза күйінде қолданылмайды. Реляциялық деректер қорымен жиынына стандартты қатынау SQL(Structured Query Language). SQL тілі реляциялық алгебраның операторлар қоспасынан және синтаксис қолданатын, ағылшын тілінің фразасына жақын реляциялық алгебра мен реляциялық есептеуде кездеспейтін реляциялық есептеу өрнектерінен тұрады.

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

Есептер - мәліметтер ұсынудың ерекше формасы. Әдетте, есепті қалыптастыру үшін есептелетін ерістер, топтастырулар, іріктеу шарттарымен бірге әр түрлі кестелерден мәліметтер жинайтыи сұрау салулар жасалады.

Содан кейін MS Access-тің жалпы ережелері бойынша осындай сұрау салулар негізінде есеп жобаланады, ол мыналарға жол ашады:

- оку ментандауға қолайлы формалармен мәліметтер ұсынуға;

- қорытынды және орта мәндерді есептеп, жазбаларды топтастыру (бірнеше деңгей бойынша);

- графикалық объектілерді есепке кіргізу мен басып шығару (мысалы, диаграмма).

Автоматтардың классификациясы: ақырлы, дүкен жадылы, екі жақты автоматтар. Тьюринг машинасы, фон Нейман автоматтары. Детерминантты және детерминантты емес автоматтар.

Ақырлы автоматтар (АА) – құрамында жұмыс жады жоқ автоматтар;

Стектік автоматтар (СА) – жұмыс жады стек принципінде ұйымдастырылған автоматрт: соңғы енген, бірінші шығады - Last Input First Output (LIFO);

Тьюрингамашиналары (ТМ) – жұмыс жады екі жағынан да (солдан да, оңнан да) шенеуленбеген автоматтар;

Екі жақты автомат, егер ол өзінің бастиегін солға да, оңға да жылжытса.

Тьюринг машинасы

Тьюринг машиналары.Сыртқы және ішкі альфавиттер, командалар, бағдарламалар. Тьюринг машинасының жұмысының сипаттамасы.

Егер алгоритм түзу құрылымын қарастырса, онда оларды түзудің үш негізгі типін: сызықтық, тармақталатын, циклдік-ерекшелеуге болады.

Орындаушы командалардың орналасу ретіне қарай бірінен кейін бірін орындайтын алгоритм сызықтық деп аталады.

Орындаушының әрекеті қандай да бір шарттардың орындалу нәтижесімен анықталатын алгоритм тармақталатын деп аталады.

Кейбір жеке командаларды немесе командалар тобын орындағанда бірнеше рет қайталанатын алгоритм циклдік деп аталады.

Көптеген алгоритмдер осы құрылымдардың бәрін өзіне біріктіреді.

Жоғарыда сипатталған алгоритм анықтамалары интуитивті деп аталады, себебі олар адам түсінігіне есепке алады. Бірақ математиканың өзінің есептерін шешу үшін алгоритм ұғымын анықтап алу қажеттігі пайда болды. Алгоритмнің математикалық анықтамасы ХХ ғасырдың отызыншы жылдарының ортасында үш типті модельдерде алынды:

Есептелгіш (рекурсивті) функциялар теориясы;

Ақырлы, ақырсыз автоматтар теориясы;

Марковтың нормалы алгоритмдері.

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

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

фон Нейман автоматтары

3. Автоматтардың сыныпталуы: ақырлы, дүкен жадылы, екі жақты автоматтар. Тьюринг машинасы, фон Нейман автоматтары,детерминантты және детерминантты емес автоматтар

Пост машинасы лентадан және кареткадан (оқушы және жазушы) тұрады. Лента шексіз және көлемдері бірдей секцияларға бөлінген.

Лентаның әр секциясына өңделетін екілік информацияның бір символын жазуға болады. Екілік алфавиттің бір символы лентада "V" белгісімен көрсетіледі, келесісі – бос орын.

Егер секцияға "V" белгісі жазылса, демек секция белгіленген, ал егер секцияда "V" белгісі жоқ болса онда ол белгіленбеген немесе бос деп саналады.

1сурет. Пост машинасының қалып-күйі

Каретка лента бойымен оңға және солға жылжый алады. Каретка қозғалмай тұрғанда ол лента секциясының бірінің қарсысында тұрады. Каретканың қарсысындағы секция ағымдағы секция деп аталады.

Каретка бір қадам жасаған да бір секцияға оңға немесе солға жылжуы мүмкін. Сонымен бірге каретка ағымдағы секцияның белгіненген немесе белгіленбеген екендігін анықтап, бос секцияға белгі қойып, ал белгіленген секцияның белгісін алып тастай алады.

Белгіленген секцияны қайта белгілеп немесе бос секциядан белгіні алып тастау командаларын орындауға болмайды (рұқсат етілмейді).
Пост машинасы командасының форматы:

nKm, мұндағы:
n – ағымдағы команда нөмірі,
K – Пост машинасы командалар жүйесінің командасы,
m - сілтеме немесе келесі қадамда орындалатын команда нөмірі.

Последовательность команд из системы команд - программа, если:
1) на n - ом месте этой программы будет стоять команда с номером n.
2) отсылке m соответствует реальная команда в программе.
Пост машинасының командалар жүйесі:
1). a → b
каретканы оңға жылжыту, лентадағы жазбалар өзгермейді.
2). a ← b
каретканы солға жылжыту, лентадағы жазбалар өзгермейді.

3). a V b
Ағымдағы секцияға "V" белгісін қою немесе белгілеу. Бұл команданы тек қана ағымдағы секция бос болғанда орындауға болады. Егер ағымдағы секция белгіленген болса, онда команданы орындауға болмайды.
4). a ↑ b
Каретка ағымдағы секцияда жазылған белгіні өшіреді. Бұл команданы тек белгіленген секция үшінғана орындауға болады. Егер ағымдағы секция бос болса, онда команданы орындауға болмайды.
5). a ? b1, b2
Көшу командасы. Ағымдағы секцияның мәні тексеріледі, егер секция белгіленбеген болса, онда басқару b1 нөмірдегі командаға беріледі, ал секция белгіленген болса, онда басқару b2 нөмірдегі командаға беріледі. Лентадағы жазбалар өзгермейді.
6). a ! [ b ]
Машинаны тоқтату командасы. Лентадағы жазбалар өзгермейді. Машинаны тоқтату командасыда сілтеме болмайды.

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

Пост машинасының тоқтау жағдайлары:

1) нәтижесіз тоқтау – берілген программаны программаны орындау барысында орындауға болмайтын команда кездессе;

2) нәтижелі тоқтау – берілген программаны орындау барысында тоқтау командасына жетікенде;

3) берілген программаны орындау барысында алдыңғы екі жағдайдың ешқайсысына жетпей машина кешсіз жұмыс жасауы мүмкін.

Пост машинасының программасы.

Алдын ала лентаға жазылған санға бірді қосу (белгі оң жақтан қосылады) программасы:

Алдын ала лентаға жазылған санға бірді қосу (белгі сол жақтан

қосылады) программасы:

Дүкендік жадысы бар автомат түсінігі
Магазиндік жадысы бар автомат (МЖ-автоматы) магазин түрінде ұйымдастырылған жұмыс лентасынан тұрады.

МЖ - автоматы – ол M = (К, Σ, Г, δ, p₀, F, B₀) түріндегі жетілік, мұндағы:

К – күйлердің ақырлы жиыны;

Σ - алфавит;

Г –магазин алфавиті;

δ - өту функциясы;

p₀ – бастапқы күй;

F – қорытынды күйлердің жиыны;

B₀ – Г жиынының символы, магазиннің түбінің маркерін белгілеу.

Жалпы жағдайда осы анықтама детерминерленбеген автоматқа сәйкес келеді. Ақырлы автоматтан айырмашылығы ерікті магазиндік жадысы бар автоматқа эквивалентті детерминерленген автомат құрастыруға болмайды. Тілдердің берілуінің танығыш құралдарын қолданудың негізгі қолданылуы болып грамматикалық бөлшектеудің алгоритмін құру табылады. Сондықтан ерікті КС – грамматика үшін эквивалентті МЖ-автомат құра білу керек.

МЖ-автомат ерікті түрдегі КС – грамматикадағы бөлшектеу құралы ретінде қызығушылықты тудырады. Бұл тұжырым келесі теоремада қалыптасқан.

Теорема. КС – грамматикамен туындайтын тілдер магазиндік жадысы бар автоматармен танылатын тілдерге сәйкес келеді.

Дәлелдеу. Бөлшектеудің екі түрлі стратегиясы бар: төменнен жоғары қарай және жоғарыдан төмен қарай бөлшектеу.

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

Детерминантты шекті автоматтар. Мур диаграммалары

Шекті автоматтың бір жақтылығын терминалды емес шекті автоматты

қарастырайық. Ол үшін автомат жұмысының әр бір тактын білу қажет.

Детермиалданбаған шекті автомат жұмысының такты ағымды құрылымдық қалыппен

және ағымды енгізу символы мен анықтаймыз. Детерминалданбаған шекті

автоматтың әр тактысы бірінші конфигурациядан екінші конфигурацяға өтеді.

Сонда енгізу басында оң жақтағы бір символ өзгереді. Формалдық автоматтың

конфигурацясы деп (q,[pic]) [pic](Qx[pic]) Мына жұптар аталады.

Конфигурация (q[pic],[pic]) бастапқы деп аталады. Ал а(q, [pic]), (q[pic]F)

шекті деп аталады.

Шекті автоматының жұмысының такты бинорлық қатынаспен анықталады.

Егер q[pic][pic][pic](q;а) болса онда (q,а[pic])+(q[pic][pic][pic]) болады.

Егер [pic]- көпшілік конфигурация , сонда :

[pic] *С+[pic]С[pic] мынаны білдіреді С=С[pic].

*С[pic]+кСк ол k>=1 деп аталады.

*С[pic],С[pic]+С[pic] сонда мынау орындалады 0<=i=1, aC+C[pic]

білдіреді.

([pic][pic]) және ([pic][pic]) арақатынастары транзитивтік немесе

рефлексифті –транзитивтік қатыс болып табылады .Шекті автомат k=(Q,[pic]

,[pic],q[pic],F) енгізу тізбегін [pic] анықтайды, егер

(q[pic][pic])+(q,[pic] ) болса, онда q[pic]F.Анықталған тілмен шекті к-

автоматты көптеген енгізу тізбегімен аталады .

L(k)=(w/[pic] және (q[pic],[pic])+[pic](q,[pic]) онда q[pic]F).

4.1.Мысалы: Шекті автомат k-ны мына түрде қарастырайық

k=([pic]q[pic],q[pic],q[pic],q[pic][pic],[pic]a,b[pic],[pic],q[pic],[pic]q[pic]

[pic], функцияда [pic] келесідейорындалды.

1) [pic](q[pic][pic],a)=[pic]q[pic][pic]; 5)

[pic](q[pic][pic],a)=[pic]q[pic][pic];

2) [pic](q[pic][pic],b)=[pic]q[pic][pic]; 6)

[pic](q[pic][pic],b)=[pic]q[pic][pic];

3) [pic](q[pic][pic],a)=[pic]q[pic][pic]; 7)

[pic](q[pic][pic],a)=[pic]q[pic][pic];

4) [pic](q[pic][pic],b)=[pic]q[pic][pic]; 8)

[pic](q[pic][pic],b)=[pic]q[pic][pic][pic];

Бұл шекті автомат тізбек бойынша орындалады. Ол а және b символдарынан

тұрады baababa k- автоматында енгізу тізбегі болып табылады және ол келесі

такт бойынша орындалады .

(q[pic], baababa) +2 (q[pic], aababa) +1

(q[pic] ababa) +3 (q[pic], baba) +4

(q[pic] , aba) +5 (q[pic], ba) +8

(q[pic], a) +7 (q[pic], [pic]) .

Сонымен baababa L(k) тіліндеорындалады.

Мысал: Шектіавтоматтыанықтайық .Ол 0 және 1 тізбегінентұрады.

Тізбекмысалыбойынша , ол 11,011001,10111.

K==([pic]q[pic],q[pic],q[pic][pic],[pic]0,1[pic],[pic],q[pic],[pic]q[pic][pic]

Мұндағы q[pic]- бастапқықалыпоғаненгізуде 1-символыберіледі. Мұндағы

q[pic]- қалып , ал q[pic]- шектіқалыпсонда [pic] функциясымынатүрде

орындалады .

1) [pic](q[pic][pic],0)=[pic]q[pic][pic]; 4)

[pic](q[pic][pic],1)=[pic]q[pic][pic];

2) [pic](q[pic][pic],1)=[pic]q[pic][pic]; 5)

[pic](q[pic][pic],0)=[pic]q[pic][pic];

3) [pic](q[pic][pic],0)=[pic]q[pic][pic]; 6)

[pic](q[pic][pic],1)=[pic]q[pic][pic];

Аленгізутізбегі 10111 k- автоматындакелесітактбойыншаорындалады.

(q[pic] 10111 ) + (q[pic] , 0111 ) +( q[pic], 111 )

(q[pic] , 11 ) + (q[pic], 1 ) +( q[pic],

[pic]).

Тьюринг машиналары (ТМ) тіршілік өмірде тұтынылатын нақтылы машина емес. Ол қиялдан туған – елестік машина. Айқынырақ айтқанда, «Тьюрингмашинасы» дегеніміз алгоритмдер туралы ұғымды дәлді анықтау үшін және оның ерекшеліктері мен қызметін көрнекілеп талдау жәнетүсіндіру мақсатымен алынған дерексіз үлгілеме жүйенің шартты атауы болып табылады.

Алан Матисон Тьюринг (1954-1954) ағылшын инженері әрі математигі. Оның ғылыми еңбектері, көбінесе, математикалық логика мен есептегіш машина жұмысының негіздемелік мәселелерін зерттеуге және уағыздауға арналған. Кибернетика ғылымы мен электронды есептегіш машиналар теориясының негізін алғаш қалаушы Норберт Виннер (1894- 1964) : «Тьюринг расында, ғалымдардың ішіндегі ойша тәжірибе жүргізу арқылы машиналардың логикалық мүмкіндігін тұңғыш зерттнген адам болды.

Тьюринг машинасы дәлді математикалық ұғым болып табылады. Оны ешұқашан кездеспейтін және ұшы қиыақырсыз жады бар механикалық құрылым деп қарастырады.

Анықтама: Тьюринг машинасы (ТМ) деп ұзындықтары бірдей шаршы ұяларға бөлінген ақырсыз таспамен және уақыттың әрбір моментінде таспаның мазмұнын есепке алатын жаңа белгілеменіжазатын және таспаны жылжытатын Д тетіктен жабдықталған А ақырсыз автоматты айтады.

Тьюринг машинасы соңғы автоматтандырудың жай моделі болып табылады.

Қарастырайық, Тьюринг машинасы мен жай модельдік автоматтың айырмашылығын.

Жай автомат ішкі құрлысына қарай күрделі емес және ол екі лента арқылы жұмыс атқарады: енгізу және шығару. Жай автомат такт бойынша жұмыс істейді. Әрбір такт енгізу символдар көмегімен лентаға енгізілген ұяшықтарды санайды, және кейбір символдарды алфавит бойынша тереді.

Функционалдық автоматты бейнелеуді оның программасы ретінде санауға блады: онда 4 – тік санау жүйесі қолданылады < s, a, p, y> - бұл өткен қалып, а – келесі енгізілген сигнал, р – келесі қалып және у – кезекті шығару сигналы. Соңғы автомат программасы аргуметерді санайды, және функцияның нәтижесін шығарады: S*X – S*Y

Дата добавления: 2018-08-06; просмотров: 462; Мы поможем в написании вашей работы!

Поделиться с друзьями:

⇐ Предыдущая 5 6 7 8 91011 12 13 14 Следующая ⇒

Мы поможем в написании ваших работ!