Допомога у написанні освітніх робіт...
Допоможемо швидко та з гарантією якості!

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

РефератДопомога в написанніДізнатися вартістьмоєї роботи

Ми розглянемо цю проблему стосовно МТ. Проте всі сформульовані нами твердження будуть справедливі і для НАМ і для інших еквівалентних уточнень поняття алгоритму. Еквівалентність уточнень поняття алгоритму ми розглянемо пізніше. Слідство 3.2 Ми отримали щось подібне до мови, на якій можна описувати нову Машину Тюрінга, використовуючи описи вже існуючих, а потім, використовуючи теореми 3.1 — 3.4… Читати ще >

Алгоритмі Маркова (реферат, курсова, диплом, контрольна)

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

Зміст

  • Вступ 3
    • 1. Побудова алгоритмів з алгоритмів 4
    • Висновки 8
    • 2. Нормальні Алгоритми Маркова. Побудова алгоритмів з алгоритмів 9
    • Список літератури 13

Вступ

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

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

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

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

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

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

Дії:

Дії мають вигляд або, або, де, P*, де

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

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 () =B (A ()).

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

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

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

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

Доказ.

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

DC=DADВ, QC= QAQB

В програмі для, А всі правила p!, де, DA* {Л, П, Н} замінимо на pqoB, де qoB QB — початковий стан для В. Это забезпечить включення У в той момент, коли, А свою роботу закінчила і не раніше, оскільки QAQB=.

Що і т.д.

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

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

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

DC=DADB

QC=QAQB

C (||) =A (||) B=B (||) A=A () ||B ().

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

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

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

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

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

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

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

Доказ.

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

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

де ||S.

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

1qo1р1П

||р1||р1П

0qo0роП

||ро||роП

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Висновки

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

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

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

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

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

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

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

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

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

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

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

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

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

Розглянемо приклад 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

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

|

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

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

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

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

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

|010

0|1

|0|

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

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

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

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

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

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

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

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

Показати весь текст
Заповнити форму поточною роботою