Мәліметтер типтері

Жұмыс түрі: Материал
Тегін: Антиплагиат
Көлемі: 12 бет
Таңдаулыға:

№4 Билет

1. Тьюринг машинасы және Марковтың нормальды алгоритмдері.

2. «Деректер қорын басқару жүйесі» атты сабақты оқыту әдістемесі.

1. Тьюринг машинасы және Марковтың нормальды алгоритмдері.

Тьюрингтың абстрактілі машинасы

Екі жағыда шексіз лентадан және автоматтан тұратын құралғыны қарастырамыз. Ленталар ұяшықтарға бөлінген, оған сыртқы алфавиттың символдары { , a ₀ , a ₁ , . . . , a _N } , жазылады, мүндағы " " символ бос символды белгілейді. автомат мына {q ₁ , . . . , q _r } жағдайлардың бірінде болуы мүмкін, және әрбір уақыт аралығында {R, L, S} үш жағдайдың бірімен қозғалыс жасайды: R - оңға бір ұяға жылжиды, L- солға бір ұяға жылжиды, S- орнында қалады. Мұндай құрылғының (машинаның) жұмысын бағдарлама деп аталатын арнайы кестемен беруге болады.

q ₁

q _j

q _r

: a ₀

q1:

qj:

qr:

: a ₁

q1:

qj:

qr:

: .

q1:

qj:

qr:

: .

q1:

qj:

qr:

: .

q1:

qj:

qr:

: a _i

q1:

qj: cDq

qr:

: .

q1:

qj:

qr:

: .

q1:

qj:

qr:

: .

q1:

qj:

qr:

: a _N

q1:

qj:

qr:

Сол жақ ең шеткі бағанға алфавит символдары (машинаның сыртқы алфавиті) орналасады. Жиыны машинаның ішкі алфавиты. Бұл кестенің кейбір ұялары бос болу мүмкін. Бұл кестенің ұяларына машина командалары жазылады яғни cDq символдарының үштігі, мұндағы с - машинаның сыртқы алфавитінің символы, q - машинаның ішкі алфавитінің символы және D - машинаның қозғалысын сипаттайтын алфавиттердің символы яғни {R, L, S} жиынынан. Уақыттың бір моментінде автоматтың бас тиегі лентадағы а _і символын көрсе, және автомат q _j жағдайында болса, онда машина а _і жолымен q _j бағанының қиылысындағы команданы орындауға тиісті. Егер cDq командасын көрсе, онда машина ағымдағы осы ұяға с символын жазып, q жағдайына өтіп, D қозғалысын жүзеге асыруы керек. Егер байқалған ұя бос болса, онда машина тоқтайды. Тьюринг машинасының конфигурациясы деп αqaβ түріндегі тізбекті айтады, мұндағы αaβ - лентадағы жазулар, - бас тиектің ағымдағы жағдайы, ал оның орны α мен β арасындағы көрінген ұяшық (суретті қара) . . сөзін қысқарту үшін а ^х деп жазамыз. Бастапқы конфигурация әруақытта q ₀ aβ түрінде болады деп есептелінеді де, мұндай конфигурацияда бас тиек лентаның сол жақ шетіне ығыструлы болады. Бағдарламаны қолдану нәтижесінде 2 жағдай болуы мұмкін:

1) Кей уақытта бос команда кездессе (бос ұяшық) онда машина тоқтайды.

2) Бос ұяшяқ ешуақытта пайда болмайды, онда машина тоқтамайды.

3-мысал . Тьюринг машинасының көмегімен унарлық санға 1 санын қосу керек.

Сыртқы алфавит A ={ , 1}, жинымен берілуі мүмкін, мұндағы 1 толтырылған секцияға, ал - бос белгіге сәйкес келеді, және толтырылған секциялар бірінен кейін бірі қатар келеді. Ішкі алфавит Q ={ q , z } жиынымен беріледі, мұндағы q - құрылғының жұмыс жағдайына сәйкес келеді, ал z - тоқтау. Барлық түрлендіру ережелері (логикалық функциясы) функциянальды схема түрінде берілуы мүмкін.

Equation. 3

q: z 1 S

z: z

Equation. 3 S

A: 1

q: q 1 R

z: z 1 S

Функциянальды схема кесте түрінде былай құрылады, бағандар мен жолдардағы белгілер логикалық құрылғының кіру параметрін анықтайды, ал қиылысындағы ұяшықта шығу параметрі тұрады. Кей жағдайда машинаның бас тиегі лента секциясындағы 1 санының белгісін көрсе және машинаның (ЛҚ) логикалық құрылғысы ( q) жағдайында болса, онда осы тактідегі оның жұмыс нәтижесі осы секциядағы 1 санын қайталап, оңға R бір секцияға жылжиды, бұл команда былай жазылады q 1 R .

Егер машинаның бас тиегі лента секцисындағы белгісін көрсе және машинаның ЛҚ ( q) жағдайында болса, онда белгісі 1 санымен аустырылады, лентаның жылжуы болмайды, машина тоқтайды - z1S.

Алғашқы конфигурация мынадай 1q болсын. Логикалық функцияның сипаттамасына сәйкес машинаның жұмысы былай жүреді:

1-такт. 1 көрінеді, ЛҚ жағдайы q. Шығыс командасы q 1 R, бұл лентаға қатысты бас тиектің оңға 1 қадам жасауымен эквивалентті. Бұған сәйкес аралық конфигурация мынадай 11q111 болады.

2-такт. Машина осындай қадам жасап 111q11 конфигурацияға өтеді.

3-такт. q1 конфигурацияға өтеді.

4-такт. q конфигурацияға өтеді.

5-такт . көрінді, ЛҚ жағдайы q. Шығыс командасы z1S - ұяшықтағы орнына 1-ді жазады, жылжу жоқ, жұмыс тоқтайды.

Соңғы конфигурация z.

4-мысал. Ондық санау жұйесінен көп разрядты n саны берілген. n+1 мәнін есептеуді қамтемесіз ететін Тьюринг машинасын құруымыз керек.

Сыртқы алфавитты А ={0, 1, …, 9, 0, } пайдаланамыз, символ бос белгіге сәйкес келеді. Ішкі алфавиттың өткен мысалдағы сияқты екі жағдайы болады - ( q ) жұмыс жағдайы және тоқтауы( z ) ( Q ={ q , z }) . Берілген сан n, нәтиже n+1ондық жүйеде жазылады, және цифрлар көршілес ұяшықтарға арасынан бос орын қалдырмай орналасады. Функционалдық схеманы кесте түрінде береміз:

Equation. 3

a: q

0: z 1 S

1: z 2 S

2: z 3 S

3: z 4 S

4: z 5 S

5: z 6 S

6: z 7 S

7: z 8 S

8: z 9 S

9: q 0 L

Equation. 3: z 1 S

21 q 9 алғашқы конфигурация болсын.

1-такт. q9→q0L, 9 саны 0-ге ауыстырылады, бас тиек ондық разрядтың - 2q10 аралық конфигурациясына жылжиды.

2- такт. q1→z2S, 1 саны 2-ге ауыстырылады да, соңғы кофигурацияға 2z20 ауысып тоқтайды, яғни 219+1 қосу нәтижесі алынды.

99 q 9 алғашқы конфигурация болсын.

1-такт. q9 → q0L, 9 q 90 аралық конфигурациясы қалыптасады.

2-такт. q9 → q0L, q 900 конфигурациясы туады.

3-такт. q9 → q0L, q 000 туады.

4-такт. q → z1S, z1000 туады және жұмыс тоқтайды.

Марковтың нормальды алгоритмдері. 1956 жылы математик А. А. Марков алгоритм ұғымының жаңа анықтамасын ұсынған, кейін ол Марковтың құрметіне Марковтың тармақталатын, цифрлы алгоритмі деген атпен аталған болатын. Төменде алгоритмнің 7 негізгі параметрі көрсетілген:

Бастапқы берілгендердің жиынтығы - S сөздер;
мүмкін нәтижелердің жиынтығы - W алфавитіндегі;
мүмкін аралық нәтижелердің жиынтығы - Р=SWV алфавитіндегі сөздер; Мұндағы V- көмекші қызметші символдарға арналған алфавит

Әрекеттер:

Әрекеттер мына түрде болады: α→γ немесе α γ. Мұндағы α, γ ∈P ^* және

P* - Р алфавитіндегі сөздердің жиыны және ол ауыстыру ережесі деп аталады. Бұл ереженің мәнісі мынада - өңделетін сөз ω солдан оңға қарай қаралады және α сөзінің оған кіруі ізделінеді.

Егер β және ν сияқты сөздері бар болса, және ω=βαν теңдігі орындалса, α сөзі ω сөзіне кіруі деп аталады.

Егер α сөзі ω сөзіне кіруі анықталмаса, онда α сөзі γ сөзіне алмастырылады.

Барлық орнату ережелері реттеледі. Алдымен бірінші ережесіне арналған кіріс ізделінеді. Егер ол табылса, онда кіру іздеулерінде сол жағынан оңға қарай ауыстыру және алмастырылған сөз тағы да қаралады . Егер бірінші ережеге арналған кіру табылмаса, онда екінші ережеге арналған кіру және т. с. с. ізделінеді. Егер кіру ауыстыру ережелері i - ші үшін табылса, онда ауыстыру болады және ережелердің қарауы біріншісінен басталады, ал сөз басынан және солдан оңға қарай қаралады.

Ауыстыру ережелерінің барлық жиынтығы алгоритм схемасы деп аталады .

Басталуының ережесі - ережелерді қарау әрқашан біріншісінен басталады.

Аяқталуының ережесі - алгоритмнің орындалуы мына жағдайларда ғана тоқтайды, егер:

α γ түріндегі ауыстыру ережесі қолданылған болса,
Алгоритм схемасынан ешбір ережесін қолдануға болмайтын болса.

Нәтижені орналастыру ережесі - алгоритм орындалғаннан кейін алынған сөз.

Есептеуге арналған алгоритм құру

U(n) =n+1;

S={0, 1, 2, 3, 4, 5, 6, 7, 8, 9}; S=W; V={*, +}.

Бұл алгоритмнің схемасы төменде келтірліген:

Кіші разрядтың соңғы цифрын белгілеу үшін көмекші белгісін n сөзінің соңына апарамызКіші разрядтың цифрларынан бастап, бір бірлікке асырамыз:

Кіші разрядтың соңғы цифрын белгілеу үшін көмекші белгісін n сөзінің соңына апарамыз

Кіші разрядтың цифрларынан бастап, бір бірлікке асырамыз

Кіші разрядтың соңғы цифрын белгілеу үшін көмекші белгісін n сөзінің соңына апарамызКіші разрядтың цифрларынан бастап, бір бірлікке асырамыз: Сөздегі соңғы цифрды белгілеу үшін * көмекші белгісін сөзге енгіземіз.

Мына алгоритм қиындығы - айтылған ауыстыру орындалған ережелерінің саны мынаған тең болады

(k+1) +(l+1),

мұндағы k - n-дағы цифрлар саны, l - саны 9, 1-ге өсіп отырады.

2 ДЕРЕКТЕР ҚОРЫН БАСҚАРУ

Мәліметтер базасымен жұмыс істеу

Мәліметтербазасын басқару жүйелері (МББЖ МББЖ) ;
AccessМББЖ-сының сервистік мүмкіндіктері;
Мәліметтер базасы (МБ) ;
MS Accessобъектілері;
Мәліметтер базасын жобалау кезеңдері;
MS Access-тің екі жұмыс режимі;
Мәліметтертиптері;
Жаңа мәліметтер базасы файлын ашу

Жоспары:

3 . Access программасы - бұл мәліметтер базасын басқару жүйесі (BD-СУБД - МББЖ) . Басқару жүйесі дегеніміз - көлемді мәліметтер жиынын тұтынушыларға ыңғайлы түрде бейнелеп, белгілі бір форматта сақтап қана қоймай, оны ары қарай өңдеуге арналған программалар кешені.

Мәліметтер базасын басқару жүйелері(МББЖ)

Access жиі қайталанып отыратын операцияларды автоматтандыруға мүмкіндік береді (мыс., жалақы есептеу, құнды материалдарды есепке алып отыру, т. с. с. ) .

Access көмегімен мәліметтерді енгізу мен оларды көруге арналған ыңғайлы форматтар жасауға және оларды қағазға басып шығаратын күрделі басылымдар (отчеты) құрастыруға да болады.

... жалғасы

Сіз бұл жұмысты біздің қосымшамыз арқылы толығымен тегін көре аласыз.