lab03_Markov_16_11_2009_print

МIНIСТЕРСТВО ОСВIТИ І НАУКИ УКРАЇНИ Національний університет "Львівська полiтехнiка"

Нормальні алгоритми Маркова

МЕТОДИЧНІ ВКАЗІВКИ

до лабораторної роботи № 3 з курсу "Алгоритми і структури даних"

для студентiв базового напрямку 6.050101 "Комп'ютернi науки"

Затверджено на засiданнi кафедриСистеми автоматизованого проектування"

Протокол N 2 вiд 4.09.2009р.

Львiв – 2009

Нормальні алгоритми Маркова: Методичні вказівки до лабораторної роботи N3 з курсу «Алгоритми і структури даних» для студентiв базового напрямку 6.050101 «Комп’ютернi науки» / Укл.: А.Б.Керницький, П.Ю.Денисюк, М.Р.Мельник. - Львiв: Національний університет «Львівська політехніка», 2009.- 20 с.

Відповідальний за випуск Лобур М.В., д-р техн.наук, проф.

2

1. МЕТА РОБОТИ

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

2.КОРОТКІ ТЕОРЕТИЧНI ВIДОМОСТI

Улабораторній роботі розглядається підхід до уточнення поняття алгоритму, запропонований у 1956р. радянським математиком А.А. Марковим. Даний підхід пов’язує неформальне поняття ефективності з переробкою слів у деякому кінцевому алфавіті відповідно з певними правилами. У вигляді елементарного перетворення використовується підстановка одного слова замість іншого. Множина таких підстановок визначає схему алгоритму. Правила, які визначають порядок застосування підстановок, а також правила зупинки є загальними для всіх нормальних алгоритмів.

Алгоритмічна система, заснована на відповідності між словами в абстрактному алфавіті, включає об’єкти подвійної природи: елементарні оператори і елементарні розпізнавачі.

Елементарні оператори − алфавітні оператори за допомогою послідовного виконання яких реалізується будь-який алгоритм у даній алгоритмічній системі.

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

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

2.1 Підстановки

Цікавою особливістю НАМ є те, що у них використовується лише одна елементарна дія - так звана підстановка, яка визначається наступним чином: оператором підстановки називається запис вигляду α→β (читається «α замінити на β»), де α і β − будь-які слова (можливо, і порожні). При цьому α називається лівою частиною оператора, а β - правою частиною.

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

3

підстановки слово q називають результатом підстановки. Умовно це можна відобразити наступним чином:

Необхідні уточнення:

1.Якщо ліва частина оператора підстановки входить у слово p, тоді говорять, що цей оператор є застосовний до p. Але якщо α не входить у p, тоді оператор вважається незастосовним до p, і підстановка не виконується.

2.Якщо ліва частина α входить у p декілька раз, тоді на праву частину β, за визначенням, замінюється лише перше входження α в р:

3.Якщо права частина оператора підстановки є порожнім словом, тоді підстановка α→ зводиться до викреслювання підслова α з р (в операторах підстановки не прийнято позначати порожнє слово):

4.Якщо у лівій частині оператора підстановки вказано порожнє слово, тоді підстановка →β зводиться, за визначенням, до приписування β зліва до слова р:

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

2.2 Визначення НАМ

Нормальним алгоритмом Маркова (НАМ) називається непорожній скінчений впорядкований набір операторів підстановки:

1 1

У цих операторах можуть використовуватися два види стрілок: звичайна стрілка (→) і стрілка «з хвостиком» ( ). Оператор із звичайною стрілкою називається звичайним оператором, а оператор із стрілкою «з хвостиком» − завершальний оператором. Записати алгоритм у вигляді НАМ − означає представити такий набір операторів.

4

2.3 Правила виконання НАМ

Перш за все, задається деяке вхідне слово р. Де саме записане це слово - не важливо, у НАМ це питання не обумовлюється. Робота НАМ зводиться до виконання послідовності кроків. На кожному кроці переглядаються зверху вниз оператори підстановки, що входять в НАМ і вибирається перший з операторів, який можна застосувати до вхідного слова р, тобто самий верхній з тих, ліва частина яких входить у р. Далі виконується підстановка відповідно до знайденого оператора. Отримуємо нове слово р1. На наступному кроці це слово р1 береться за початкове і до нього застосовується аналогічна процедура, тобто знову переглядаються зверху вниз оператори починаючи з самого верхнього і шукається перший оператор, який можна застосувати до слова р1, після чого виконується відповідна підстановка і отримується нове слово р2. І так далі:

р → р1→ р2 → … → рn

Послідовність слів р, р1, р2, …, рn, що отримуються у процесі реалізації алгоритму, називається дедуктивним ланцюжком, який веде від слова p до слова рn.

Слід звернути увагу на те, що на кожному кроці оператори в НАМ завжди є видимими починаючи з найпершого.

Необхідні уточнення:

1.Якщо на черговому кроці було застосовано звичайний оператор (α→β), тоді робота НАМ продовжується.

2.Якщо на черговому кроці було застосовано завершальний оператор

(α β), тоді після його застосування робота НАМ припиняється. Те слово, яке вийшло у цей момент, і є вихідним словом, тобто результатом застосування НАМ до вхідного слова.

Як видно, різниця між звичайним і завершальним операторами підстановки виявляється лише у тому, що після застосування звичайного оператора робота НАМ продовжується, а після завершального оператора − припиняється.

3. Якщо на черговому кроці до біжучого слова не застосовано жодний оператор, то і в цьому випадку робота НАМ припиняється, а вихідним словом вважається біжуче слово.

Таким чином, НАМ зупиняється з двох причин: було застосовано завершальний оператор, або жодний з операторів не підійшов. Перше і друге вважається «хорошим» завершенням роботи НАМ. В цих випадках кажуть, що НАМ є застосовний до вхідного слова.

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

5

2.4 Граф-схеми нормальних алгоритмів Маркова

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

Граф-схема алгоритму є скінченою множиною з’єднаних між собою вершин які називаються вузлами граф-схеми. Кожному вузлу, крім особливих вузлів, які називаються входом і виходом, ставиться у відповідність певний елементарний оператор або розпізнавач. З кожного вузла, якому поставлено у відповідність оператор, а також із вхідного вузла виходить точно по одній дузі. З кожного вузла, якому поставлено у відповідність розпізнавач, виходить точно по дві дуги. З вихідного вузла не виходить жодної дуги. Кількість дуг, які входять у вузол граф-схеми, може бути довільна.

Розглянемо на прикладі загальний вигляд такої граф-схеми (рис. 2.1). У даному випадку для вершини, яка відповідає входу, маємо P (x) 0,

P (x) 2, P (x) 2; для вершини, яка відповідає виходу, P (x) 1, P (x) 0. У загальному випадку кількість дуг, які входять у вершини-

розпізнавачі, може бути довільна.

Рис.2.1. Загальний вигляд граф-схеми НАМ

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

6

− до наступного розпізнавач (іноді ці стрілки відповідно позначають знаками

« + » і «−»).

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

Наприклад, для слова abcabca застосування підстановки bc → cb через два кроки приводить до слова acbacba:

abcabc → acbabca → acbacba.

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

Таким чином, для вершин, які відповідають операторам підстановки

P (x) 1.

Розглянемо приклад УНА, який заданий підстановками ba→ab, bc→ba, bb→ac. Роботу алгоритму, заданого графом рис.2.2., розглянемо для вхідного слова bcbaab.

bcbaab →bcabab→bcaabb→baaabb→baaaac

Рис. 2.2. Приклад граф-схеми УНА,

який заданий підстановками ba→ab, bc→ba, bb→ac.

Розглянувши УНА, перейдемо до характеристики власне нормальних алгоритмів.

7

Нормальними алгоритмами називаються такі УНА, граф-схеми яких задовольняють наступним умовам:

1.Всі вузли, які відповідають розпізнавачам, впорядковуються за допомогою їх нумерації від 1 до n.

2.Дуги, які виходять з вузлів, що відповідають операторам підстановки, під’єднуються або до вузла, що відповідає першому розпізнавачу, або до вихідного вузла. У першому випадку підстановка називається звичайною, у другому − завершальною.

3.Вхідний вузол під’єднується дугою до першого розпізнавача.

Граф-схема нормального алгоритму у загальному вигляді представлена на рис. 2.3.

Як приклад розглянемо роботу НАМ, заданого алфавітом А ={+, 1} і системою підстановок ”1+1”→”1”, ”1” ”1”.

Нехай на вході задана стрічка ”11+11+1”. Вона перетворюється алгоритмом у стрічку ”11+11+1”→”1111+1”→”11111”→”11111”. Алгоритм реалізує додавання одиниць.

Рис.2.3 Граф-схема нормального алгоритму у загальному вигляді

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

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

8

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

Якщо алгоритм N заданий у деякому розширенні алфавіту А, тоді говорять, що N є нормальний алгоритм над алфавітом А.

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

Домовимося називати той або інший алгоритм таким, що нормалізується, якщо можна побудувати еквівалентний йому нормальний алгоритм, і ненормалізованим – у іншому випадку. Принцип нормалізації тепер може бути висловлений в наступній видозміненій формі: всі алгоритми можна нормалізувати.

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

2.5 Приклади складання НАМ

Розглянемо приклади, в яких демонструються типові прийоми складання НАМ.

Для скорочення формулювання завдань будемо використовувати наступні позначення:

−літерою р будемо позначати вхідне слово;

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

Крім того, в прикладах праворуч від операторів підстановки будемо вказувати їхні номери. Ці номери не входять в оператори, а потрібні для посилань на оператори при представленні покрокового виконання НАМ.

Приклад 1 (вставляння і видалення символів)

А={а, b, c, d}. У слові р необхідно замінити перше входження підслова bb на ddd і видалити всі входження символу с.

Наприклад: abbcabbca → adddabba

Розв’язок. Перш за все зауважимо, що в НАМ вставлення нових символів у слово - це заміна деякого підслова на підслово з більшою кількістю символів; наприклад, за допомогою оператора bb→ddd два символи будуть замінені на три символи. При цьому непотрібно створювати

9

вільне місце для додаткових символів (в НАМ слово розсувається автоматично). Видалення символів − це заміна деякого підслова на підслово з меншою кількістю символів; наприклад, видалення символу с реалізується оператором c→ (з порожньою правою частиною). При цьому жодних порожніх позицій усередині слова не з’являється, стискування слова в НАМ відбувається автоматично.

З врахуванням вищесказаного наше завдання повинне вирішуватися таким НАМ:

Перевіримо алгоритм на вхідному слові abbcabbca (над стрілками вказані номери застосованих операторів, а в словах зліва від стрілок підкреслені для наочності ті підслова, до яких були застосовані ці оператори):

abbcabbca abbabbca abbabba adddabba

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

Перевіримо розроблений НАМ на вхідному слові, в яке не входить bb:

1 1

dcacb dacb dab

До останнього слова (dab) незастосовний жодний оператор, тому, згідно з визначенням НАМ, алгоритм зупиняється і це слово оголошується вихідним.

Приклад 2 (перестановка символів)

А={а, b}. Перетворити слово р таким чином, щоб на його початку опинилися всі символи а, а в кінці − всі символи b.

Наприклад: babba → aabbb

Розв’язок. Завдання вирішується з допомогою НАМ, який містить лише одну формулу:

ba ab

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

babba abbba abbab ababb aabbb

10