Алгоритми Маркова
Зміст
Вступ. 3
1. Побудова алгоритмів з алгоритмів. 4
Висновки. 8
2. Нормальні Алгоритми Маркова. Побудова алгоритмів з алгоритмів. 9
Список літератури. 13
Вступ В 1956 році вітчизняним математиком А.А. Марковим було запропоновано нове уточнення поняття алгоритму, яке пізніше названий його ім'ям.
В цьому уточненні виділені нами 7 параметрів були визначено таким чином:
Сукупність початкових даних - слова в алфавіті S;
Сукупність можливих результатів - слова в алфавіті W;
Сукупність можливих проміжних результатів - слова в алфавіті
Р=SWV, де V - алфавіт службових допоміжних символів.
Дії:
Дії мають вигляд або a®g, або a a g, де a, g ÎP*, де
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,bÎDA* wÎ{Л, П, Н} замінимо на ap®bqoBw, де qoBÎ QB - початковий стан для В. Это забезпечить включення У в той момент, коли А свою роботу закінчила і не раніше, оскільки 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 Для будь-яких МТ А і МТ В можна ефективно побудувати МТ З таку, що С=А||В
Обгрунтовування. ............