Рефераты | Рефераты по математике | Нормальные Алгоритмы Маркова. Построение алгоритмов из алгоритмов.
Нормальные Алгоритмы Маркова. Построение алгоритмов из алгоритмов.Категория реферата: Рефераты по математике Теги реферата: реферат по информатике, мцыри сочинение Добавил(а) на сайт: Баранов. Предыдущая страница реферата | 1 2 3 4 5 6 | Следующая страница реферата 6|®7 7|®8 8|®9 9|®|0 |0®10 0|®1 |®0| |
Рис. 3.2. Схема НАМ для вычисления U3((n)1)=(n)10.
Сложность этого НАМ будет n+[log10n], что существенно меньше сложности для Машины Тьюринга, вычисляющей эту функцию, которая равнялась n2+[log10n(log10n+1)].
Реализацию функции U4 сравнения двух целых чисел оставляем читателю в качестве упражнения.
Замечание: исходное слово надо задать в форме 
* 
Для нормальных алгоритмов Маркова справедлив тезис, аналогичный тезису Тьюринга.
Тезис Маркова: Для любой интуитивно вычислимой функции существует алгоритм, ее вычисляющий.
Построение алгоритмов из алгоритмов.
До сих пор, строя ту или иную МТ, или НАМ мы каждый раз все делали заново. Естественно задать вопрос, а нельзя ли при построении, например, новой МТ пользоваться уже построенной ранее МТ.
Например, МТ3 из примера 3
U3((n)1)=(n)10
по существу есть надлежащим образом объединенные МТ для U1(n)=n+1 и U2((n)1)=(n-1)1.
Аналогичный вопрос можно сформулировать для НАМ. Другими словами можно ли аккумулировать знания в форме алгоритмов так, чтобы из них можно было строить другие алгоритмы.
Мы рассмотрим эту проблему применительно к МТ. Однако все сформулированные нами утверждения будут справедливы и для НАМ и для других эквивалентных уточнений понятия алгоритма. Эквивалентость уточнений понятия алгоритма мы рассмотрим позже.
Определение.3.2. Будем говорить, что МТ1 можно эффективно построить из МТ2 и МТ3 если существует алгоритм, который позволяет, имея программу для МТ2 и МТ3, построить программу для МТ3.
Определение.3.3.Последовательной композицией МТ А и В называется такая МТ С, что
область применимости МТ А и С совпадают;
C(a)=B(A(a)).
Другими словами, применение С к слову a дает такой же результат, как последовательное применение к этому же слову сначала А, а потом к результату применения А - В.