Программалау тілдері туралы ақпарат

Презентация қосу

“ Программалау тілдері. ”

Тақырыбы: “ Тьюринг машинасы
”.
Тексерген: Рысжанова А.C.
Орындаған: Абдолла А. С. Т-313
Тьюрингтің алгоритмдік машинасы

Тьюринг машинасы үш бөліктен тұрады: лентадан, оқитын-жазатын
головкадан және логикалық құрылғыдан ( 7.1 суретті қара).
Лента сырқы жады ретінде болады; ол шектелмеген (шексіз) болып
есептелінеді – бұл Тьюринг машинасының моледьді құрылғы екенін
көрсетеді, себебі ешқандай шынайы құрылғының шексіз көлемді жадысы
болмайды.

7.1 сурет.Тьюринг машинасының схемасы.
Пост машинасындағыдай, лента жеке бөліктерге б өлінген, біра қ,
Тьюринг машинасында головка қозғалмайды, ал лента оған қатысты оңға
және солға қозғалады. Басқа айырмашылығы ол екілік алфавитте емес,
кандай-да бір кез-келген A = { , a1…a n} шекті алфавитте жұмыс істейді –
бұл алфавит сыртқы алфавит деп аталады. Онда бос белгі деп аталатын
арнайы символы ерекшеленіп тұр, оны қандай-да бір ұяшы ққа жіберу
ондағы белгіні өшіріп, ұяшықты бос қалдырады.
Головка әрқашан лента ұяшықтарының бірінің үстінде орналасады.
Жұмыс тактілермен (қадамдармен) жүреді. Головкаларымен орындалатын
командалар жүйесі қарапайым: әр такті сайын ол шолынулы ұяшы қта ғы ai
белгісін aj белгісіне ауыстырады. Мұнда келесі с әйкестіктер болуы м үмкін:
•j = i – бұл шолынулы ұяшықта ештеңе өзгермегенін білдіреді;
•i 0, j = 0 – ұяшықта сақтаулы белгі бос белгіге ауыстырыл ғанын, я ғни
өшірілгенін білдіреді;
•i =0, j 0 - ұяшықта сақтаулы бос белгі бос емес белгіге (алфавиттегі j
белгісіне) ауыстырылғанын білдіреді, яғни белгі қою орындалады;
•i j 0 - бір белгіні екіншісімен ауыстыруды білдіреді.
Осылайша, Тьюринг машинасында ақпараттарды өңдеудің ең қарапайым
командалары жүзеге асырылады. Бұл өңдеуді ң командалар ж үйесі тура сол
сияқты қарапайым лентаның орын ауыстыруының командалар ж үйесімен
толықтырылады: бір ұяшық солға, бір ұяшық оңға және орнында қалу, я ғни
шолынулы ұяшықтың адресі команданы орындау нәтижесінде немесе 1-ге
ауысады, немесе өзгеріссіз қалады. Бірақ, шыныда лента жылжы ғанмен, әдетте
головканың секцияға қатысты жылжуы қарастырылады – сонды қтан лентаны ң
оңға жылжуы командасы R («Right») арқылы, ал солға жылжу командасы L
(«Left») арқылы, жылжудың болмауы - S («Stop») арқылы бейнеленеді. Ары қарай
головканың жылжуы туралы айтамыз да, R, L және S командаларын оның
қозғалысы деп білеміз. Бұл командалардың қарапайымдылығы қандай-да бір
ұяшықтың мазмұнына барғымыз келсе, ол жеке бір ұяшы ққа жылжу
командасының тізбегі арқылы ізделінетінін білдіреді. Әрине б ұл өңдеу процесін
біршама ұзартады, оның есесіне ұяшықтарды нөмірлеу және адрес бойынша өту
командасынан арылуымызға көмектеседі, яғни, шынайы қарапайым қадамдарды ң
санын азайтады, бұл теориялық тұрғыдан өте маңызды.
Тьюринг машинасында ақпаратты өңдеу және таңбаны жазу командасын
беру, сол сияқты лентаны жылжыту логикалық құрылғы (ЛҚ) арқылы
орындалады. ЛҚ шекті жиын құрып, Q ={q1…qm, z} арқылы бейнеленетін
қалыптардың бірінде бола алады, z қалпы жұмыстың аяқталғанына сәйкес
келеді, ал q1 бастапқы қалып болып табылады. Q таңбасы R, L, S таңбаларымен
бірге машинаның ішкі алфавтін құрады. ЛҚ екі кіру каналына (ai, qi) және үш
шығу каналына (ai+1, qi+1, Di+1) (суретке қара) ие:

Схеманы келесі түрде түсіну керек: i тактісінде ЛҚ-ның бір
кірісіне сол мезетте шолынулы (ai,) ұяшығынан белгі беріледі,
басқа кірісіне сол мезеттегі ЛҚ-ның қалпын (qi)-ді бейнелейтін
белгі беріледі. Алынған (ai, qi) белгілерінің үйлесуіне және бар
өңдеу ережелеріне байланысты ЛҚ жаңа (ai+1) белгісін
дайындап, бірінші шығыс каналынан шолынулы ұяшыққа
бағыттайды, головканың орын ауыстыру командасын (R, L және
S-ден Di+1-ді) береді, сол сияқты келесі басқару белгісін (qi+1 )
шақыру командасын береді.
Осылайша, Тьюринг машинасы жұмысыны ң қарапайым қадамы (такт)
келесіден тұрады: головка шолынулы ұяшықтан символды оқиды, ж әне өзіні ң
қалпына және оқылған символға байланысты қандай символ жазу (немесе өшіру)
керектігі және қандай қозғалыс орындау керектігі жазыл ған команданы
орындайды. Мұнда головка да жаңа қалыпқа өтеді. Мұндай машинаны ң
функционалдану схемасы келесі 7.2 суретте көрсетілген.

Сурет 7.2. Тьюринг машинасының функционалдану схемасы.
Осы схемада жадыны сыртқы және ішкі жадыға бөлу бейнеленген. Сыртқы
жады шексіз лента түрінде көрсетілген – ол сыртқы алфавиттті ң символдарымен
кодталған ақпаратты сақтауға арналған. Ішкі жады ағымдағы тактідегі келесі
команданы сақтауға арналған екі ұяшық түрінде көрсетілген: Q-де ЛҚ-дан
келесі қалып (qi+1) беріліп, сақталады, ал D-да – жылжу командасы (Di+1). Q-дан
кері байланыс линиясы бойынша qi+1 ЛҚ-ға түседі, ал D-дан команда қажет
кезінде лентаны бір позиция оңға немесе солға жылжытатын орындаушы
механизмге түседі.
Тьюринг машинасының функционалдануын талдамас бұрын та ғы бір ұғым
енгізейік. Лентаның ұяшықтарының барлық қалыптарының жиынтығы, ЛҚ-
ның қалпы және головканың қалпы машинаның конфигурациясы деп аталады.
Конфигурацияны келесі түрде жазу ға болды: a1qiaj…ak , бұл k символдан
тұратын сөзде j нөмірлі секция шолынуда, және бұл кезде басқарушы құрылғы
qi қалыпта тұр дегенді білдіреді. Машина конфигурациясы сырт қы алфавитті ң
символдарының кез-келген санынан тұратыны және тек бір ғана ішкі алфавит
символынан тұратыны түсінікті. Көбінесе конфигурацияны 1 qi 2 түрде жазады,
мұндағы 1 – лентадағы головканың сол жағында тұрған сөз, 2 – лентадағы
головканың оң жағындағы тұрған сөз, шолынулы таңбаны қоса есептегенде. 1 –
дің сол жағында және 2 –нің оң жағында лента бос. 7.1 суретте бейнеленген
конфигурацияны келесі түрде жазуға болады: a1 a2 qa3a 4ak, ал 7.2 суреттегі –
1q1111.
Жұмысты бастамас бұрын бос лентаға А алфавитінде жазыл ған, шекті
бастапқы сөзі жазылады; головка сөзінің бірінші символыны ң үстіне
орнатылады, ЛҚ қалпына келтіріледі (яғни, бастапқы конфигурация т үрде
болады). Әрбір конфигурацияда тек қана бір түрлендіру ережесі ж үзеге
асатындықтан, бастапқы конфигурация машинаның барлы қ келесі ж ұмысын,
яғни, жұмысты тоқтатқанға дейінгі барлық конфигурациялар тізбегін бірм әнді
анықтайды.
Бастапқы конфигурацияға байланысты оқиғаның өрбуінің екі
нұсқасы бар:
• Тактілердің шекті санынан кейін тоқтау командасы бойынша
машина тоқтайды; бұл кезде лентада шығатын ақпаратқа сәйкес
соңғы конфигурация қалады;
• Тоқтау болмайды.
Бірінші жағдайда, осы машинаның бастапқы ақпаратқа
қолданылатыны туралы айтылады, ал екінші жағдайда – жоқ.
Машина нәтиже алуды қамтамасыз ететін барлық кіру
конфигурацияларының жиынтығы шешілетін есептер класын
құрады. Әрине, Тьюринг машинасын шешілетін классқа кірмейтін
есептерге қолдану мәнсіз болады. Екінші жағынан, көптеген
жағдайларда шешілетін есептер класын басқа Тьюринг
машиналарын құру арқылы кеңейтуге болады.
Мысал 1.
Көпразрядты бүтін сан n–нің ондық санау жүйесіндегі жазылуы бар; n+1 мәнін
есептеуді қамтамасыз ететін Тьюринг машинасын құру керек.
A={0,1,…,9 ,} сыртқы алфавитін қолданамыз, мұнда символы бос белгіге
сәйкес келеді. Ішкі алфавит алдыңғы есептегідей екі қалыптан т ұрады – ж ұмыс
қалпы (q) және тоқтау (z) (Q={q, z}). Бастапқы сөз n, сол сияқты нәтиже – n+1 –
ондық санау жүйесінде жазылады, және де цифрлар к өрші ұяшы қтарда бір-бірден,
бос орынсыз жазылады. Функционалдық схема кесте т үрінде к өрсетіледі
(қолайлылық үшін жол q қалпына, ал бағандар – сыртқы алфавит та ңбаларына
сәйкес келеді):
a 0 1 2 3 4 5 6 7 8 9
q z1S z2S z3S z4S z5S z6S z7S z8S z9S q0L z1S
Айталық, бастапқы конфигурациясы 21q9 болсын.
Такт 1 q9 q0L, яғни 9 таңбасы 0-ге ауысады да, головка ондықтар бірлігіне
жылжиды – аралық конфигурация 2q10.
Такт 2 q1 z2S, яғни 1 таңбасы 2-ге ауысады да соңғы конфигурациямен 2z20
тоқтау болады, яғни, 219+1 қосынды нәтижесі алынды.
Аталық, бастапқы конфигурация 99q9 болсын.
Такт 1 q9 q0L, яғни, 9q90 аралық конфигурациясы құрылады.
Такт 2 q9 q0L – q900 аралық конфигурациясы құрылады.
Такт 3 q9 q0L –q 000 құрылады.
Такт 4 q z1S – z1000 туындайды және жұмыс тоқтатылады.
Осылайша, сипатталған алгоритм кез-келген бүтін сан мен бірлікті қосуды
қамтамасыз етеді. Осылайша бірлікті емес, қандай-да бір б үтін m санын қосу
үшін осы алгоритмді m рет қайталау кажеттігі түсінікті. Б үтін сандарды к өбейту
де санды өзіне-өзін қосуға келтіруге болады. Осыдан, Тьюринг машинасы
маңызды қасиетке ие – қолда бар машиналарды біріктіру арқылы жа ңа машина
құру мүмкіндігі – мұндай амал композиция деп аталады.
Марковтың қалыпты алгоритмдері
Алгоритм ұғымын жетілдірудің (нақтыландырудың) үшінші қырын қыс қаша
талдайық. Мағынасы бойынша ол Тьюринг машинасына жа қын, біра қ онда
қандай-да бір машиналар туралы ойлар қолданылмайды. Алгоритм ауыстарулар
жүйесімен беріледі, онда қандай символдар ауыстыруын жасау қажеттігі ж әне б ұл
ауыстырулар қандай ретпен орындалатыны туралы к өрсетіледі. М ұндай қырды
А.А.Марковым ұсынған. 50 ж. басында қалыпты алгоритмдер ұғымы енгізілді
(Марковтың өзі оларды алгорифмдер деп атаған).
Тағы да қандай-да бір А алфавитін қарастырайық.
Анықтамалар енгізейік:
Сөз – бұл алфавит таңбаларының кез-келген шекті тізбегі.
Сөздегі символдар саны оның ұзындығы деп аталады. Ұзындығы
нольге тең сөз бос деп аталады.
s сөзі q сөзінің ішкі сөзі деп аталады, егер q-ді q=rst түрінде
көрсетуге болса, мұндағы r және t сол алфавиттегі кез-келген
сөздер (соның ішінде бос сөздер де болады).
Енді алгоритм ұғымын анықтауға болады (қатаң емес):
А алфавитіндегі алгоритм деп анықталу облысы А
алфавитіндегі барлық сөздер жиынының қандай-да бір ішкі
жиыны болатын және мәндері сол сияқты А алфавитінің сөздері
болатын тиімді есептелінетін функция аталады.
Марков алгоритмдерінде бір сөзді басқа сөздің орнына қою алгоритмні ң
элементар қадамы ретінде қабылданған. Айталы қ, А алфавитінде Р бастап қы с өзі
құрылған болсын. Ол сөзде Pr ішкі сөзі болсын (жалпы жағдайда мұндай с өздер
бастапқы сөзде бірнеше болуы мүмкін), сол сияқты сол алфавиттегі қандай-да бір
Pk сөзі де болсын.
Орнына кою деп бастапқы Р сөзіндегі реті бойынша бірінші Pr ішкі сөзін Pk
сөзіне ауыстыру аталады. Орнына қою Pr → Pk арқылы бейнеленеді.
Осы түрде көрсету алгоритмі орнына қоюлар тізбегі (тізімі)
болып табылатын орнына қоюлар жүйесімен беріледі. Егер бұл
тізімде Р-ға енетін сол жақ бөлігі бар орнына қоюлар бар болса,
онда алғашқысы Р-ға қолданылады, нәтижесінде ол басқа P1 сөзіне
өтеді. Оған тағы да ауыстырулар схемасы қолданылады, және
т.с.с. процесс екі жағдайда тоқтатылады: немесе тізімде Pn-ге
енетін сол жақ бөлігі бар орнына қою табылған жоқ, немесе Pn-ді
алу кезінде соңғы орнына қою қолданылды.
Мысал 2
Алфавитте орыс тілінің символдары болсын: A ={а,б…я}. Келесі түрлендірулерді
қамтамасыз ететін орнына қоюлар жүйесін табу керек: путь муть, поло мала.
Мұндай алгоритмнің папа, пузо бастапқы сөздеріне қолданылу нәтижесін тап.
Орнына қоюлар жүйесі түсінікті: п м, о а.
Алгоритмді қолдану: папа мапа мама пузо музо муза
Пайдаланылған әдебиеттер тізімі:
1. Камардинов О. Информатика: жоғарғы және орта оқу орындарына арналған оқу
құралы. –Алматы:Қарасай, 2006.-360б.
2. Игошин В.И. Математическая логика и теория алгоритмов. – М:, 1991
3. Информатика: Учебник. - 3-е перераб. изд. /Под. ред. проф. Н.В. Макаровой. - М.:
Финансы и статистика, 2001. - 768 с: ил.
4. Савельев А.Я. Основы информатики: Учеб. для вузов. - М.: Изд-во МГТУ им. Н.Э.
Баумана, 2001 - 328 с, ил. (Сер. Информатика в техническом университете).
5. Бешенков С.А., Ракитина Е.А. Моделирование и формализация. Методическое
пособие. - М.: Лаборатория Базовых Знаний, 2002. - 336 с: ил.
6. Кормен Т., Лейзерсон Ч., Ривест Р. Алгоритмы: построение и анализ, М: Центр
непрер.матем. образ-я, 2000.
7. http://de.uspu.ru/Informatics/Metodes/DPP/F/08/1/glavs/oglav.htm
НАЗАРЛАРЫҢЫЗҒА
РАХМЕТ!

Ұқсас жұмыстар

Web-сайттардың қазіргі заманғы динамикалық мазмұнын жобалаудың құралдары

ДК қолданбалы программалық қамтамасыздандырылу

Алгоритм күрделілігі

JAVA ТІЛІНДЕГІ ОБЪЕКТІЛІ – БАҒЫТТАЛҒАНПРОГРАММАЛАУ

Объектілі бағытталған программалаудың негізгі артықшылығы модульдік программалаумен салыстырғанда модульдер арасында жіберілген ақпарат көлемінің азаюы және модуларалық байланыстар санының қысқаруы

DELPHI және Visual Basik тілдері

Программалық жабдықтар

Аналитикалық машина

Паскаль программалау тілдері

Бағдарламалау тілі

Пәндер