Рефераты | Рефераты по математике | Нормальные Алгоритмы Маркова. Построение алгоритмов из алгоритмов.
Нормальные Алгоритмы Маркова. Построение алгоритмов из алгоритмов.Категория реферата: Рефераты по математике Теги реферата: реферат по информатике, мцыри сочинение Добавил(а) на сайт: Баранов. Предыдущая страница реферата | 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.
|
1|®2 2|®3 3|®4 4|®5 5|®6 Рекомендуем скачать другие рефераты по теме: контрольные работы 9 класс, доклады бесплатно. Предыдущая страница реферата | 1 2 3 4 5 6 | Следующая страница реферата Поделитесь этой записью или добавьте в закладкиКатегории: |
