Реферат: Алгоритми Маркова

Перегонимо службовий символ * в кінець слова 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=Æ, тобто порожньо.

| a

Складність цього алгоритму рівна 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