Головна

 Квантификация багатомісної висказивательной форми. |  Заперечення пропозицій кванторами. |  чисельні квантори |  Символічна запис визначень і теорем. |  Інтуїтивне поняття алгоритму. |  алгоритм Евкліда |  властивості алгоритмів |  машина Поста |  Приклади виконання програм. |  Уточнення поняття алгоритму |

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

  1.  алгоритми
  2.  Алгоритми виконання операцій з множинами, проекції, зовнішнього з'єднання.
  3.  Алгоритми виконання селекції з однією умовою порівняння: розмір селекції, використання первинного індексу, використання вторинної індексу.
  4.  Алгоритми виконання з'єднання: по блоках з'єднання, удосконалення алгоритму поблочного з'єднання, з'єднання за індексом.
  5.  Алгоритми геополітики і стратегії таємних воєн світової закуліси
  6.  Алгоритми і процеси роботи в ISDN 1
  7.  АЛГОРИТМИ на графі ТА ЇХ ПРОЛОГ ПРОГРАМИ

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

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

Нехай Х - деякий кінцевий алфавіт, F (X) - слова алфавіту,  - Пусте слово. якщо  , То вирази и  називаються формулами підстановки в алфавіті Х:

 - Проста підстановка;

 - Остаточна підстановка.

Символи > і. не належать Х.

Слова p і q можуть бути порожніми.

Рядок R входить в рядок L, якщо L має вигляд L1RL2. Підстановка застосовна до слова, якщо рядок відповідна лівій частині підстановки входить в слово. Застосування полягає в заміні в перетворюючої слові лівої рядки - правої:

11.3 Механізм роботи НАМ:

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

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

2) Робота алгоритму закінчується якщо:

· Жодна з підстановок не може бути застосована,

· Використана заключна підстановка.

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

Приклад.

Х = {x, y, z};

Нормальна схема підстановок:

xx ® y

xy ® x

yzy ® x

zz ®. z

yy ® x

Конвертувати слово:

xxxyyyzzz > yxyyyzzz > yxyyzzz > yxyzzz > yxzzz > yxzz

Приклад.

X = {А, Б, В, Г, ..., Я};

Нормальна схема підстановок:

Х®К

М®Р

КА®ЛОН

РУ®. З

Конвертувати слово:

МУХА®МУКА®РУКА®РУЛОН®СЛОН

Приклад 9:

X = {a, b};

Нормальна схема підстановок:

a > .e

b > b

Конвертувати слово:

bbbbbb - схема не може бути застосована.

Конвертувати слово:

abab > bab

Приклад.

Х = {х, у, х-1, у-1};

Нормальна схема підстановок:

х х-1> е

х-1х > е

у у-1> е

у-1у > е

Конвертувати слово:

ххухуу-1х-1ух > ХХУхх-1ух > ххуух

Приклад 10:

Х = {x1, ..., Xn};

Нормальна схема підстановок:

x1> e

x2> e

...

xn> e

Конвертувати слово переписується в порожнє.

Нехай R і Q нормальні алгорифм над алфавітом Х і pIF (x). запис  означає, що або обидва алгорифм R і Q не застосовні до слова p, або обидва застосовні і .

Два алгорифм R і Q називають еквівалентними щодо алфавіту Х, якщо  кожен раз, коли pIF (x) і хоча б одне зі слів R (p) або Q (p) визначено і теж належить F (x).

Якщо для всіх pIF (x)  , То R і Q називаються повністю еквівалентними.

Нехай X = {1}, а  . Тоді будь-яке натуральне число n можна записати у вигляді слова в алфавіті :

Поставимо у відповідність вектору (n1, n2, ... Nk), Де n1, n2, ... Nk - Натуральні числа, слово в алфавіті  виду  , Яке позначимо  . Наприклад, вектору  відповідає слово 11111 * 1 * 111.

Нехай f: Nk> N - деяка часткова функція і Rf позначає алгорифм в алфавіті  такий, що

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

Функція f називається частково визначної по Маркову, якщо існує нормальний алгорифм Q над  повністю еквівалентний Rf над  . Якщо функція визначена повністю, то її називають просто обчислюваною по Маркову.

теорема: Найпростіші функції O (x) = 0, S (x) = x + 1 і Im(x1, x2, ..., Xn) = Xm обчислюваних по Маркову.

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

1. Функцію O (x) = 0 реалізує наступний алгорифм R0:

 = {1, *}, ;

Нормальна схема підстановок:

 * > * (1)

?11 > ?1 (2)

?1 > .1 (3)

е > ? (4)

Конвертувати слово:

р = 111 ... 11.

Тоді за формулою (4) отримуємо р = ? 11 ... 11.

Застосуємо формулу (2) і отримаємо: р = ? 11... 11 > ? 1... 11 > ? 1.

Застосовуємо формулу (3) і отримуємо ? 1> 1.

Так як 1 - це  в алфавіті Х, то R0 і є шуканим алгоритмом.

2. Функцію S (x) = x + 1 реалізує наступний алгорифм Rs:

 = {1, *}, ;

Нормальна схема підстановок:

 * > * (1)

?1 > .11 (2)

е > ? (3)

Конвертувати слово:

р = 111 ... 11.

Тоді за формулою (3) отримуємо р = ? 11 ... 11 (n одиниць).

Застосуємо формулу (2) і отримаємо: р = 111... 11 (n + 1 одиниця). Так як будь-яке натуральне число n можна записати у вигляді слова в алфавіті :

 , То ми реалізували алгоритм RS(N) = n + 1.

Цей алгоритм застосовується лише до тих слів, які є натуральними числами.

Питання для контролю:

1. Визначення і принципи роботи машини Тьюринга.

2. Теза Тьюринга.

3. обчислюваної функції.

4. Вербальні алгоритми.

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

6. Нормальні функції.

 



 Машина Тьюринга (МТ) |  СМ-13-8к1,2 тобина тест с?ра?тари 1 сторінка
© um.co.ua - учбові матеріали та реферати