Claw.ru | Рефераты по математике | Нормальные Алгоритмы Маркова. Построение алгоритмов из алгоритмов. Нормальные Алгоритмы Маркова. Построение алгоритмов из алгоритмов. | Категория реферата: Рефераты по математике | Теги реферата: реферат по информатике, мцыри сочинение | Добавил(а) на сайт: Баранов. Предыдущая страница реферата | 1  2  3  4  5  6 | Следующая страница реферата Увеличиваем на единицу, начиная с цифр младших разрядов.

Вводим служебный символ * в слово, чтобы им отметить последнюю цифру в слове.

Рис.3.1. Схема НАМ для вычисления U1(n)=n+1

 Нетрудно сообразить, что сложность этого алгоритма, выраженная в количестве выполненных правил подстановки, будет равна:

(k+1)+(l+1),

где k - количество цифр в n, l - количество 9, которые были увеличены на 1.

Но в любом случае сложность НАМ для U1(n) больше сложности Машины Тьюринга для этой же функции, которая равнялась k+1.

 Обратите внимание, что у НАМ порядок следования правил подстановки в схеме алгоритма существенно влияет на результат, в то время как для МТ он не существеннен.

 Построим НАМ для примера 2 из лекции 2:

построить алгоритм для вычисления

U2((n)1)=(n-1)1

Итак, S=; W=S; V=Æ, т.е. пусто.

| a

Cложность этого алгоритма равна 1, в то время как сложность алгоритма для Машины Тьюринга равнялась n.

Теперь построим НАМ для примера 3 из лекции 2:

построить алгоритм для вычисления

U3((n)1)=(n)10

S=;  W={0,1,2,3,4,5,6,7,8,9};  V=Æ

Схема этого алгоритма приведена на рисунке 3.2.