Реферати українською » Математика » Алгоритми Маркова


Реферат Алгоритми Маркова

>Алгоритми Маркова


>Зміст

>Вступ. 3

1.Побудоваалгоритмів ізалгоритмів. 4

>Висновки. 8

2.НормальніАлгоритми Маркова.Побудоваалгоритмів ізалгоритмів. 9

Списоклітератури. 13


>Вступ

У 1956роцівітчизняним математиком А.А.Марковим було бзапропонованоновеуточненняпоняття алгоритму, якупізніше назв йогоім'ям.

У цьомууточненнівиділені нами 7параметрів буливизначено таким чином:

>Сукупністьпочатковихданих - слова валфавіті P.S;

>Сукупністьможливихрезультатів - слова валфавіті W;

>Сукупністьможливихпроміжнихрезультатів - слова валфавіті

>Р=SWV, де V -алфавітслужбовихдопоміжнихсимволів.

>Дії:

>Діїмаютьвигляд чиa®g, чи a a g, де a, gP*, де

>P* -безлічслів надалфавітом Р, йназивається правиломпідстановки.Значення цого правилаполягає до того, щооброблюване слово wєвидимимзліва направо йшукаєтьсявходження внього слова a.


1.Побудоваалгоритмів ізалгоритмів

>Дотепер,будуючи тієї чиінший МТ, чи НАМ ми шкірного разу усіробили наново.Природнозадати запитання, а чи не можна припобудові,наприклад,нової МТкористуватися ужепобудованоюраніше МТ.

>Наприклад,МТ3 із приклада 3

>U3((n) 1) =(n) 10

посутієналежним чиномз'єднані МТ дляU1(n) =n+1 йU2((n) 1) =(>n-1) 1.

>Аналогічне запитання можнасформулювати для НАМ.Іншими словами чи можнаакумулюватизнання уформіалгоритмів так,щоб із них можна було б будуватиіншіалгоритми.

Мирозглянемоцю проблемустосовно МТ.Проте усісформульовані намитвердження будутьсправедливі й для НАМ й дляіншихеквівалентнихуточненьпоняття алгоритму.Еквівалентністьуточненьпоняття алгоритму мирозглянемопізніше.

>Визначення 3.2.Говоритимемо, щоМТ1 можнаефективнопобудувати ізМТ2 йМТ3якщоіснує алгоритм,якийдозволяє,маючипрограму дляМТ2 йМТ3,побудуватипрограму дляМТ3.

>Визначення 3.3.Послідовноюкомпозицією МТ А й Уназивається така МТ З, що

областьзастосовності МТ А й Зспівпадають;

>C(a) =>B(A(a)).

>Іншими словами,застосування З до слова aдаєтакий ж результат, якпослідовнезастосування до цого ж словаспочатку А, апотім до результатузастосування А - У.

>ПослідовнукомпозиціюМТА йМТВпозначатимемоАoВ.

Теорему 3.1. Хайдані МТ А й У,такі, що Узастосовна дорезультатів роботи А йQAQB=.

>Тоді можнаефективнопобудувати МТ Зтаку, що З=АoВ.

>Доказ.

якалфавітданих йбезлічістанів для МТСвізьмемооб'єднанняалфавітівданих йбезлічістанів для А й У,тобто

>DC=DADВ,QC=QAQB

Упрограмі для А усі правилаap®b! w, деa,bDA*w{Л, П, М}замінимо наap®bqoBw, деqoBQB -початковий стан для У. Цезабезпечитьвключення У у тому момент, коли А свою роботузакінчила й нераніше,оскількиQAQB=.

Коли й т.д.


>Табличнийзаписпрограми для З показано намалюнку 3.3

>Рис 3.3. Структура табличногозаписупрограм дляМашини З.

>Означення.Паралельноюкомпозицією МашинТюрінга А й Уназвемотаку Машину З, дляякої:

>DC=DADB

>QC=QAQB

>C(a||b) =>A(a||b) °>B=B(a||b) °>A=A(a) ||>B(b).

З цоговизначення видно, що порядокзастосуванняМТА йМТВ не так на результат.Він якщо настільки жненачебто минезалежнозастосували До слова a, а У до слова b.

Теорему 3.2 Длябудь-яких МТ А й МТ У можнаефективнопобудувати МТ Зтаку, щоС=А||В

>Обгрунтовування. Ми недаватимемо тут сувородоказу із заподій йоготехнічноїскладності.Покажемолишеобгрунтовуванняправильностізатвердженнятеореми.ПозначимоDC=DADB;QC=QAQB.

>Основна проблема: якгарантуватищоб Аторкнулася слова b, а У - слово a. Для цоговведемо валфавітDС символ ||.Додамо для всіхстанівqiQC таких, щоqiQA правилавигляду ||>qi®||qiЛ,тобто кареткамашини А якщо,натикаючись на символ ||,йтивліво.Відповідно для всіхqjQC таких, щоqjQBдодамо правилавигляду ||>qj®||qjП,тобто кареткамашини Уйтимеуправо. Тім самим ми як біобмежуємострічку для А справа, а Узліва.

>Істотним тутє запитання: чи невиявлятьсяобчислювальніможливостіМашиниТюрінга ізнапівстрічкоюслабіше, ніжобчислювальніможливостіМашиниТюрінга ізповноюстрічкою?

>Виявляється справедливонаступнетвердження:безлічалгоритмів,реалізовуваних МТ ізнапівстрічкою,еквівалентнобезлічіалгоритмів,реалізовуваних МТ ізповноюстрічкою.ПозначимоФ(Р) МашинуТюрінга, щореалізовує алгоритм, щорозпізнає:

Теорему 3.3 Длябудь-яких МашинТюрінга А, У й Ф,мають один й тієї жалфавіт P.S,може бутиефективнопобудований машина З над тім жалфавітом P.S, така що

>Доказ.

>Позначимо:E(Р)тотожну машину,тобтоЕ(Р) =Р

>СМІТТЮ(Р)копіюючу машину,тобтоСМІТТЮ(Р) =>Р||Р

де ||>S.

>BRANCH(P) -ця машина переходити чи до лавр1, чи взмозіро.Їїпрограмаскладається із 4-х команд:

>1qo®1р1П

||>р1®||р1П

>0qo®0роП

||>ро®||роП

>Побудуємо машину

>Ця машинабудується понаступнійформулі:

>Згідно теоремам 3.1 й 3.2., миможемопобудувати машину, знаючи Є, Ф йСМІТТЮ.Тепер,маючи,BRNCH, А й У, можнапобудувати машину З таким чином:

МашинаoBRANCHзакінчує свою роботу чи встанір1,якщо словоPволодієпотрібноювластивістю, чи взмозіро,знаходячись на свої словаP. Тому,якщоприйняти умашини А станр1, якпочаткове, а й умашини У станро, якпочаткове, то машина А якщо включень заумови, щоФ(Р) =1, а машина У якщо включень,якщоФ(Р) =0.

Правилокомпозиції,визначуванецієютеоремоюзаписуватимемо,якщо Ф то Аінакше У.

Теорему 3.4 Длябудь-яких машин А й Ф можнаефективнопобудувати машину Lтаку, що

>L(P) ={ПокиФ(Р) =1,застосовуй А }

>Доказ:Замінимо вдоведеннітеореми 3.3 машину Умашиною Є, азаключний стан вмашині Узамінимо напочатковий стан вмашині . Урезультатіотримаємо потрібен результат.

Теорему 3.5 (>Бомм,Джакопіні, 1962)

>Будь-яка МашинаТюрінгаможе бутипобудований задопомогоюопераціїкомпозиційo ||,якщо Ф, то Аінакше У,поки Фзастосовуй А.

>Цю теорему мидаємо тут бездоказу.

>Слідство 3.1 ЧерезТезуТюрінга,будь-якаінтуїтивнообчислюванафункціяможе бутизапрограмований втермінахцихоперацій.

>Слідство 3.2 Миотримали щосьподібне домови, наякій можнаописуватинову МашинуТюрінга,використовуючи опису ужеіснуючих, апотім,використовуючитеореми 3.1 - 3.4,побудуватиїїфункціональну схему.

>Слідство 3.3 Алгоритм -цеконструктивнийоб'єкт. УразіМашиниТюрінгаатомарнимиоб'єктамиєкоманди, а теорема 3.5визначає правилакомпозиції.

>Висновки

Алгоритм -конструктивнийоб'єкт;

Алгоритм можна будувати ізіншихалгоритмів;

>o ||,if_then_else,while_do -універсальнийнабірдій поуправліннюобчислювальнимпроцесом.

 


2.НормальніАлгоритми Маркова.Побудоваалгоритмів ізалгоритмів

>Означення 3.1. Слово aназиваєтьсявходженням в слово w,якщоіснуютьтакі слова b й n над тім жалфавітом, що й a й w, для яківірно:w=ban.

>Якщовходження a в wзнайдено, ті слово aзамінюється слову g.

>Всі правила постановкиупорядковуються.Спочаткушукаєтьсявходження для Першого правилапідстановки.Якщо воно тазнайдено, товідбуваєтьсяпідстановка йперетворюване словозновуєвидимимзліва направо упошукахвходження.Якщовходження для Першого правила незнайдено, тошукаєтьсявходження іншому правила й т.д.Якщовходженнязнайдено дляi-го правилапідстановки, товідбуваєтьсяпідстановка, йпроглядання правилпочинається із Першого, а словоєвидимимспочатку йзліва направо.

Усясукупність правилпідстановкиназиваєтьсясхемою алгоритму.

Правило початку -проглядання правилзавждипочинається із Першого.

Правилозакінчення -виконання алгоритмузакінчується,якщо:

було бзастосовано правилопідстановкивигляду a a g,

незастосовножодне правилопідстановки ізсхеми алгоритму.

Правилорозміщення результату - слово,отримане послезакінченнявиконання алгоритму.

>Розглянемо приклад 1 ізлекції 2:

>побудувати алгоритм дляобчислення

>U(n) =n+1;

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

Схема цого НАМ показано намалюнку 1.1

>Перегонимослужбовий символ * вкінець слова n,щобвідзначитиостанню цифрумолодшихрозрядів.

>Збільшуємо наодиницю,починаючи із цифрамимолодшихрозрядів.

 

 

>Вводимослужбовий символ * в слово,щобїмвідзначитиостанню цифру вслові.

>Рис.1.1 Схема НАМ дляобчисленняU1(n) =n+1

>Неважкозміркувати, щоскладність цого алгоритму,виражена вкількостівиконаних правилпідстановки, якщорівна:

(>k+1) +(>l+1)

де до -кількість цифр в n, l -кількість 9, котрі булизбільшені на 1.

Алі убудь-якомувипадкускладність НАМ дляU1(n) понадскладностіМашиниТюрінга дляцієї жфункції, Якадорівнювалаk+1.

>Звернітьувагу, що у НАМ порядокпроходження правилпідстановки всхемі алгоритмуістотновпливає на результат, тоді як для МТвін не істотний.

>Побудуємо НАМ для приклада 2 ізлекції 2:

>побудувати алгоритм дляобчислення

>U2((n) 1) =(>n-1) 1

Отже, P.S={|};W=S;V=,тобтопорожньо.

| a

>Складність цого алгоритмурівна 1, тоді якскладність алгоритму дляМашиниТюрінгадорівнювала n.

>Теперпобудуємо НАМ:

>побудувати алгоритм дляобчислення

>U3((n) 1) =(n) 10

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

Схема цого алгоритму приведено намалюнку 3.2

1|®2

2|®3

3|®4

4|®5

5|®6

6|®7

7|®8

8|®9

9|®|0

|0®10

0|®1

|®0|

>Мал.1.2 Схема НАМ дляобчисленняU3((n) 1) =(n) 10.

>Складність цого НАМ якщо n+ [>log10n], щоістотно менше заскладність дляМашиниТюрінга, щообчислюєцюфункцію, котрадорівнювалаn2+ [>log10n(log10n+1)].

>РеалізаціюфункціїU4порівняння двохцілих чиселзалишаємочитачу яквправа.

>Зауваження:початкове словотребазадати уформі *

Длянормальнихалгоритмів Маркова справедлива теза,аналогічнатезіТюрінга.

>Теза Маркова: Длябудь-якоїінтуїтивнообчислюваноїфункціїіснує алгоритм, щоїїобчислює.


Списоклітератури

1. ДжонХопкрофт,РаджівМотані,Джеффрі УльманРОЗДІЛ 8.Введення втеорію машинТюрінга //Введення втеоріюавтоматів,мов йобчислень. – М., 2002. –С528.


Схожі реферати:

Навігація