Тізімдер. Циклдік тізімдер. Ортогоналды тізімдер 11 страница
СОҢҒЫ АВТОМАТ ТЬЮРИНГ МАШИНАСЫ
Енгізу лентасы
Басыныңың
Басының қозғалысы қозғалысы
Шығару лентасы MT = ( S, X, Y,
А = (S,X, Y, O) Г = ( L, R, H)
&: S*X S*Y &: S*X S*Y*Г
Программа: Программа
1. (s, a) (p, y) 1. ( s, a) (p, y, l )
2. (q, b) (s, z) 2. (q, b ) (s, z, R )
Тьюрингөзініңқұрылғысыненгізудееңэлементароперациялықпроцесстердімодельдеді. Адамныңсоңғыесіндеқалыптыңеңсоңғыжүйесінкөрсетугеболады. Ақпараттышығаружәнеоныалгоритмгеқосусимволдартізбегіарқылыберіледі.
Бұлинформациясөздіктесөзтүріндеберілгеналгоритмдіорындаудаадамесептеуішқосымшажадынықолданады, алақпараттардыжазудасимволдардықолданады. Адамесептегендебұрынжазылғанақпаратқақайтыпкелүімүмкінжәнекейбірақпараттыөшіріптастауынаболады. Осығанорайэлементароперациялықалгоритмдердіорындаудасимволдардыжазуғажәнеөшіругеболады.
Тьюрингтіңайтуыбойыншаформальдықмодельдіңсоңғыавтоматтанайырмашылығыол – 2 аспектбойыншаорындалады.
1.Олшексізжұмыслентасынқамтамасызетеді, оныменолсимволдардықайдажазудыжәнеоқудыбіледі.
2.Жазудыңбасыоныменолжұмыслентасындакез – келгенжаққақозғалуымүмкін.
Тьюрингмашинасытактбойыншажұмысатқарады. Әрбіртактаолсимволдардыоқидыжәнежұмыслентасындаұяшықтардықұрады. Функционалдаубейнесін, оныңпрограммасыретіндесанауғаблоады. Олбестікжиынменберіледі. <S, A, P, Y, D>ұндағы: S,A,P жәнеУ – солмағынаныбереді, олДжұмыслентасыныңбасынқозғалтудықамтамасызетеді. Ол 3 мағынадаайтылады. L – солға, R- оңға, жәнеН – орындақалу. Екіншісөзбенайтқандабұлпрограммасоңғыбестіңтізбегі. ТьюрингмашинасыбіріншісоңғыжұмыстықХалфавитінемденеді, ондаенгізужәнешығарусимволыоллентадатеріледі, машинакелесітактбойыншаоқиды. ЫңғайынақарайХэлементібоссимволдардықұрайды.
|
|
|
Қарастырайық: ТЬЮРИНГмашинасықалайжұмысістеитінін.
Тьюрингмашинасыныңконфигурациясыноныңөткенқалпыдепатайды. Программаныатқарудатакттаконфигурацияөзгереді.
Тьюрингмашинасыныңтоқтағанкезіндеенгізутізбегіндеөңдеунәтижесішығады. Осығанорайпрограммаавтомвттысимволдықтізбекболыптабылады. Тьюрингмашинасыкөптегентізбектердітүсіндіруідемүмкін. Бұлпрограммадаарнаиықалыптарберіледінемесе «!» жәнепрограмматүсіндірушіретіндеберілсеенгізулентасыбосболады.
Тьюрингмашинасытоқтағанкездеқалыпөзгередіжәнеақпаратжұмыслентасындаенгізуақпаратыменөңделеді.
|
|
|
Тьюрингмашиналарыныңқасиеттері.
Тьюрингмашиналарыныңбірнешеқасиеттерінқарастырайық.
Теорема. Әрбір Тьюринг машиналарына эквиваленция орындалу керек.
Дәлелдеуі: Тьюринг машинасының шығаруында эквиваленттік ережелер орындалады.
Теорема. Әрбір Тьюринг машинасына орта шексіз лента эквиваленциясы орындалады.
Дәлелдеуі: Бұл теорема конструктивтік, біз оған алгоритм берейік . Ол Тьюринг машинасы бойынша құрылады. 1-ден жұмыс летентасында ұяшықтарды нөмірлейік
Содан кейін ұяшыққа «*» символын берейік
Тьюринг машинасын қарастыру
Тьюринг машинасын қарастырудың сұрақтарын қарастырайық. Қазіргі кездегі копьютерлерде шексіз аналогтар берілген. Олар Тьюринг машинасының жұмыс лентасында орналасқан. Ол бес команда арқылы орындалады.
| Команда | Түсіндірмесі |
| Қозғалу (солға, оңға) | Басын 1 – жақ лентаға оңға немесе солға қозғалту. |
| Көшу, Р | Сөзсіз р нөмерімен с командасына өту |
| Егер s, p, | Шартты өту Р нөмерімен С командасына , егер ұяшықта S символы блоса. |
| Басу, S | S символының ұяшықта басылуы. |
| тоқтау | Тоқтату |
Егер Тьюринг машинасы шексіз лентада жұмыс атқарса, онда универсалды Тьюринг машинсы оның жұмысын көшіріп алуы мүмкін.
|
|
|
Универсалды Тьюринг машинасын қарастыру оқырманға жаттығулар арқылы беріледі.
№ 12 БИЛЕТ
Тізімдер. Циклдік тізімдер. Ортогоналды тізімдер
Тізімдегеніміз – сандары өзгеруі мүмкін элементтердің жиынтығы. Ол шынжырдағы шығыршық іспеттес. Тізімнің ұзындығы жаңа шығыршықтар қосу арқылы көбеюі мүмкін. Жаңа элементтер тізімге тізімнің бір жерін үзіп, соған жаңа элемент қосып, қайтандан жалғау арқылы кіргізуі мүмкін. Элементтер тізіміне сол сияқты тізімді үзіп, бір шығыршықты алып қайта жалғап қойған сияқты алынып тасталады. Тізімдер үш түрлі болады:
1. Бір байланысты.
2. Циклық
3. Екі байланысты
|
|
|
1. Бір байланысты сызықтық тізім.
Бір байланысты сызықтық тізім екі әдіспен жүзеге асуы мүмкін:
1-массивтер негізінде
2-көрсеткіштер көмегімен
Тізімді массив негізінде жүзеге асыруда тізім элементтері массивінің қатарлас ұяшықтарында орналасады. Бұлай берілуі тізімнің мазмұнын жеңіл қарап, оның аяғына жаңа элементтер қосуға мүмкіндік береді. Бірақ жаңа элементті тізімнің ортасына қосу қажет болғанда оған арнап кейінгі элементтердің барлығын массивтің аяғына қарай бір позиция жылжытып, бір орын ашу керек. Сол сияқты массив элементін алып тастау үшін де босаған ұяшықты жою үшін элементтің барлығын солға қарай жылжыту керек болады. Бірақ бұлай істеудің бірнеше кемшіліктері бар:
1. Тізімді массив негізінде жүзеге асыру орындалмас бұрын тізімнің максималды өлшемін көрсетуді талап етеді.
2. Массив негізіндегі тізімдерді жүзеге асыру компьютер жадысының үлкен көлемін қажет етеді. Тізімді жүзеге асыру үшін тізімнің ең үлкен мүмкін мөлшеріне жететіндей етіп жады көлемін бөлу қажет.
Циклдық тізімдер
Осы уақытқа дейін біз тізімнің соңғы элементін көрсеткіш мәнін 0 деген сызықтық
тізімді қарастырдық. Егер тізімнің соңғы элементінің көрсеткіш мәні тізімнің басының адресіне ауыстыратын болсақ, циклдық тізім аламыз. Көптеген кәсіби програмистер байланған тізімдерді жүзеге асыру үшін келесі циклдік модельді қолданады:
head
| Dann1 |
| next |
| Dann2 |
| next |
| dannN |
| next |
Циклдық тізімнің бір жетістігі бұл элементтерге кез келген жерде элементтерге кіруге болатындығында. Ал кемшілігі тізіммен жүрген кезде байқамаса ақырсыз циклге кіріп кетуге болады. Циклдық тізім сызықтық тізімге қарағанда құрылымы неғұрлым иілгіш болып келеді. Ол тізімде жүруді кез келген жағдайда бастауға мүмкіндік береді және оны бастапқы позицияға дейін жалғастыруға болады.
Ортогоналды тізім (немесе көп тізімді)- әрбір элемент бір мезгілде бірнеше тізімге енгізілген және тізімдер санына сәйкес келетін байланыс өрістерінің саны бар құрылым. Тізімдегі әрбір реализациялану бір немесе бірнеше циклдің орындалуы мүмкін. Мультисктерді өңдеу технологиясы қарапайым тізімдерді өңдеуден ерекшеленбейді, алайда көп мәжбүрлі тізімде бірнеше тізімдер болғандықтан, әрбір операция әр тізім үшін бөлек орындалуы керек.
Ортогоналды тізім ақпаратқа ие бірдей атрибуттар жиынтығын ұйымдастыруға мүмкіндік береді, әртүрлі сипаттамалармен реттелген әртүрлі тізімдерді ұйымдастырады. Тұжырымдаманың әрқайсысында мынадай ақпарат көздері бар оқушылардың тізімін қарастырыңыз: тегі, аты-жөні, орташа балы, туған күні, мекен-жайы, студенттік жазба кітапшасының нөмірі және т.б. Студенттердің тізімін екі негізде ұйымдастыру керек: алфавиттік тәртіп бойынша аты-жөні бойынша және орташа баллға сәйкес. Бұған екі түрлі тізімді құру арқылы қол жеткізуге болады, бірақ бұл жағдайда ақпараттық өрістерді сақтау элементтері қайталанады, бұл оперативті жадыны тиімсіз пайдаланылуына әкеледі, әсіресе ақпараттық өрістердің саны үлкен болған жағдайда. Мақсаты - екі тізімді қамтитын көп мәжбүрлеуді қолдану, оның әрқайсысы, мысалы, екі еселенген байланыстырылған циклдік тізім түрінде: алфавит бойынша, тізім элементтері fnext және fprev сілтеме атрибуттары арқылы реттеледі және орташа балл бойынша сол элементтер сілтеме атрибуттары bnext және bprev. Өңдеуге ыңғайлы болу үшін, бірнеше тізімде меңзер орнатылатын бас элементі бар.
Дата добавления: 2018-08-06; просмотров: 587; Мы поможем в написании вашей работы! |
Мы поможем в написании ваших работ!