Алгорифм Маркова. Еквівалентність алгорифму Маркова з іншими алгоритмічними системами

Размещено на http://www.allbest.ru/

Міністерство освіти і науки України

Державний вищий навчальний заклад

«Київський національний економічний університет імені Вадима Гетьмана»

Кафедра інформаційного менеджменту

Реферат

з дисципліни: «Теорія алгоритмів»

на тему: «Алгорифм Маркова. Еквівалентність алгорифму Маркова з іншими алгоритмічними системами»

Виконали: студенти

1 курсу, 2 групи

Факультету ІСІТ

Спеціальності 6101

Черниш Віталій Віталійович

Лаврінчук Сергій Володимирович

Перевірив: викладач

Дем'яненко В. В.

Київ 2014

1. Алгорифм Маркова

Алгоритмічними моделями третього типу є перетворення слів у довільному алфавіті за допомогою операцій підстановки, тобто заміни однієї частини слова на іншу. Основною теоретичною моделлю даного типу є нормальні алгоритми Маркова. Вони є строгими означеннями алгоритму, який уточнює інтуїтивне уявлення на основі алфавітно-словарного підходу.

Слід зазначити, що наведені алгоритмічні моделі, які були запропоновані для формалізації поняття алгоритму, математично еквівалентні. Але на практиці вони суттєво різняться з точки зору складності, що виникає при їх реалізації.

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

Основні положення та означення теорії нормальних алгоритмів

Теорія нормальних алгоритмів була розроблена радянським математиком А.А. Марковим (1903 р. - 1979 р.) наприкінці 40-х - на початку 50-х років ХХ ст. і є ще однією алгоритмічною моделлю для уточнення поняття алгоритму.

Алгорифмом (запропоноване Марковим поняття для позначення алгоритму) в теорії нормальних алгорифмів є правила по перетворенню слів в довільному алфавіті. Нормальні алгорифми оперують словами скінченої довжини, перетворюючи їх одне в одне за допомогою підстановок, тобто змін однієї частини слова на іншу.

Поняття алфавіту нормального алгорифму

Алфавітом (як і випадку будь-якої формальної системи) називається будь-яка скінчена множина деяких символів.

Будь-яка скінчена послідовність N літер деякого алфавіту - це слова завдовжки N у цьому алфавіті. Наприклад, в алфавіті А з трьох літер {a,b,c} словами є послідовності a,b,c,ab,bac,aacbaccc.

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

Якщо слово б є частиною слова в, то кажуть, що слово б входить у слово в.

Наприклад, у слові d = abcbcbabaa є 4 підслова а, 2 підслова bcb, одне слово cba.

Поняття про підстановку

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

Отримане слово називають результатом підстановки застосування підстановки (б, в) до слова S.

Якщо ж першого входження б в слово в немає (і відповідно немає ні одного входження б в S), то вважається, що підстановка (б, в) не застосована до слова S.

Для позначення підстановки (б, в) надалі будемо використовувати запис б > в, який називається формулою підстановки (б, в).

Деякі підстановки будемо вважати заключними (б > . в )

Означення нормального алгорифму Маркова

Нехай задано алфавіт А і зафіксовано впорядковану (задану в певному порядку) систему орієнтованих підстановок Р. Виходячи з довільного слова б в алфавіті А розглядаються підстановки в тому порядку, в якому їх задано.

Перша підстановка, що зустрілася, з лівою частиною, яка є підсловом б, використовується для перетворення б, в яке замість першого входження лівої частини підстановки підставляється її права частина, внаслідок чого утворюється слово б1. Далі, виходячи зі слова б1, процес повторюється, поки він не зупиниться.

Ознаками зупинки процесу перетворення слова б є два випадки:

* коли утворюється таке слово бn, що жодне з лівих частин допустимих підстановок не є його словами;

* коли при утворенні слова бn використано останню підстановку (підстановку із знаком «.»).

Пара (А,Р) визначає нормальний алгорифм Маркова.

Приклад 1:

Даний алгоритм перетворює двійкові числа в " одиничні ", тобто на виході виходить рядок з N одиничок, якщо на вході у нас було N в двійковій системі. Наприклад, 101 перетвориться в 5 одиниць:

Правила:

"| 0" > "0 | |"

"1" > "0 |"

"0" > "" (порожній рядок)

Вихідний рядок:

"101"

Виконання:

"0 | 01"

"00 | | 1"

"00 | | 0 |"

"00 | 0 | | |"

"000 |||||"

"00 |||||"

"0 |||||"

"|||||"

Приклад 2

Нехай задано алфавіт

А={1,+}

і систему орієнтованих підстановок

Р={+>л, 1>1}.

Слово 1+11+1111+1 алгорифм перетворює наступним чином:

1+11+1111+1

111+1111+1

1111111+1

11111111

алгорифм марков еквівалентність алгоритмічний

2. Еквівалентність алгоритмічних моделей

Різноманітні підходи до уточнення (формалізації) поняття алгоритму привели до чітких алгоритмічних моделей.

В 1936 році Алонзо Черч сформулював свою тезу. Незабаром, після формулювання тези Черча, Алан Т'юрінг показав, що клас обчислювальних за Тьюрінгом функцій співпадає з класом частково-рекурсивних функцій та запропонував свій тезис, що формулюється так: “ Класи обчислювальних та обчислювальних за Тьюрінгом функцій збігаються ”. В свою чергу Марков сформулював свій тезис: “ Будь-яка обчислювальна в інтуїтивному сенсі функція обчислювальна за Марковим ”.

Загальні риси всіх алгоритмічних моделей

* обчислювальна функція задається скінченим переліком елементарних інструкцій - програмою (програми машини Т'юрінга, схеми орієнтовних підстановок, схема примітивної рекурсії тощо);

* обчислення значень функції за вказаною програмою проводиться за чітко зафіксованому кінцевому переліку простих правил (опис підстановок нормальних алгорифмів чи кроків машини Т'юрінга);

* визначається єдиний спосіб подання вхідної та вихідної інформації (значення аргументів та функцій).

Висновок

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

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

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

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

Машина Поста й машина Т'юринга еквівалентні по своїх можливостях. Розроблені практично в той самий час (в 1936 р.) незалежно один від одного.

Використана література

1. Навчальний посібник: «Математична логіка і теорія алгоритмів» 2008

2. Марков А. А., Нагорний Н. М. «Теорія алгорифмов» 1984

3. http://znaimo.com.ua/Нормальний_алгоритм

4. http://bookdn.com/book_385_glava_17_Tema_16.Pobudova_kombіnator.html

Размещено на Allbest.ru