Реферат: Нормальные Алгоритмы Маркова. Построение алгоритмов из алгоритмов.

НормальныеАлгоритмы Маркова.Построение алгоритмов из алгоритмов.

В 1956 году отечественным математикомА.А. Марковым было предложено новое уточнение понятия алгоритма, которое позднеебыло названо его именем.

В этом уточнении выделенные нами 7параметров были определены следующим образом:

Совокупность исходных данных — слова валфавите S;

Совокупность возможных результатов — слова в алфавите W;

Совокупность возможных промежуточныхрезультатов — слова в алфавите

Р=S/>W/>V,где V — алфавит служебных вспомогательных символов.

Действия:

Действия имеют вид либо a®g,либо a a g,где a, g ÎP*, где

P* — множество слов над алфавитом Р, и называется правилом подстановки. Смысл этогоправила состоит в том, что обрабатываемое слово w просматривается слеванаправо и ищется вхождение в него слова a.

Определение.3.1. Слово aназывается вхождением в слово w, если существуют такие слова b и n надтем же алфавитом, что и a и w, для которых верно: w=ban.

Если вхождение a в wнайдено, то слово a заменяется на слово g.

Все правила постановки упорядочиваются.Сначала ищется вхождение для первого правила подстановки. Если оно найдено, топроисходит подстановка и преобразуемое слово опять просматривается слеванаправо в поисках вхождения. Если вхождение для первого правила не найдено, тоищется вхождение для второго правила и т.д. Если вхождение найдено для i-го правила подстановки, то происходит подстановка, и просмотрправил начинается с первого, а слово просматривается сначала и слева направо.

Вся совокупность правил подстановкиназывается схемой алгоритма.

Правило начала — просмотр правил всегданачинается с первого.

Правило окончания — выполнение алгоритмазаканчивается, если:

было применено правило подстановки вида a a g,

не применимо ни одно правило подстановкииз схемы алгоритма.

7. Правило размещения результата — слово, полученное после окончания выполнения алгоритма.

Рассмотрим пример 1 из лекции 2:

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

U(n)=n+1;

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

Cхемаэтого НАМ показана на рисунке 3.1.

Перегоняем служебный символ * в конец слова n, чтобы отметить последнюю цифру младших разрядов.

Увеличиваем на единицу, начиная с цифр младших разрядов.

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

Рис.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

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дает такой же результат, как последовательное применение к этому же словусначала А, а потом к результату применения А — В.

Последовательную композицию МТАи МТВ будем обозначать АoВ.

Теорема 3.1. Пусть даны МТ А и В, такие,что В применима к результатам работы А и QA/>QB=Æ.

Тогда можно эффективно построить МТ Стакую, что С= АoВ.

Доказательство.

В качестве алфавита данных и множествасостояний для МТС возьмем объединение алфавитов данных и множествсостояний для А и В, т.е.

DC=DA/>DВ, QC= QA/>QB

В программе для А все правила ap®b!w, где a,bÎDA*, wÎ{Л,П, Н} заменим на ap®bqoBw, где qoBÎ QB — начальное состояние для В. Этообеспечит включение В в тот момент, когда А свою работу закончила и не раньше,т.к. QA/>QB=Æ.

Что и т.д.

Табличная запись программы для Споказана на рисунке 3.3.

Рис 3.3 Структура табличной записипрограмм для Машины С.

Определение3.4. Параллельнойкомпозицией Машин Тьюринга А и В назовем такую МашинуС, для которой:

DC=DA/>DB

QC=QA/>QB

C(a||b)=A(a||b)°B=B(a||b)°A=A(a)||B(b).

Из этого определения видно, что порядокприменения МТА и МТВ не влияет на результат. Он будет такой же как если бы мынезависимо применили А к слову a, а В к слову b.

Теорема 3.2 Для любых МТ А и МТ Вможно эффективно построить МТ С такую, что С=А||В

Обоснование. Мы не будем давать здесьстрого доказательства в виду его технической сложности. Покажем лишьобоснование правильности утверждения теоремы. Обозначим DC=DA/>DB; QC=QA/>QB.

Основная проблема: какгарантировать чтобы А не затронула слово b, а В — слово a. Для этого введем в алфавит DС символ||. Добавим для всех состояний qiÎQC<sub/>таких,что qiÎQA<sub/> правила вида ||qi®||qiЛ, т.е. каретка машины Абудет, натыкаясь на символ ||, уходить влево.Соответственно для всех qjÎQC таких,что qjÎQB добавим правила вида ||qj®||qjП, т.е. каретка машины В будет уходитьвправо. Тем самым мы как бы ограничиваем ленту для Асправа, а для В слева.

Существенным здесь является вопрос: неокажутся ли вычислительные возможности Машины Тьюринга с полулентой слабее, чемвычислительные возможности Машины Тьюринга с полной лентой?

Оказывается справедливо следующееутверждение: множество алгоритмов, реализуемых МТ с полулентой, эквивалентномножеству алгоритмов, реализуемых МТ с полной лентой.Обозначим Ф(Р) Машину Тьюринга, реализующую распознающий алгоритм:

Теорема 3.3. Для любых МашинТьюринга А, В и Ф, имеющих один и тот же алфавит S,может быть эффективно построена машина С над тем же алфавитом S, такая что

Доказательство.

Обозначим: E(Р)тождественную машину, т.е. Е(Р)=Р

СOPY(Р)копирующую машину, т.е. СOPY(Р)=Р||Р,

где ||ÏS.

BRANCH(P) — эта машина переходит либо в состояние р1, либо всостоянии ро. Ее программа состоит из 4-х команд:

1qo®1р1П

||р1®||р1П

0qo®0роП

||ро®||роП

Построим машину

Эта машина строится по следующейформуле:

Согласно теоремам 3.1 и 3.2., мы можемпостроить машину />, зная Е, Ф и COPY. Теперь, имея />, BRNCH, A и В, можно построить машину С следующим образом:

Машина />o BRANCH заканчивает свою работу либо в состоянии р1, если слово P обладает нужным свойством, либо в состоянии ро,находясь в начале слова P.Поэтому, если принять у машины А состояние р1, как начальное, а умашины В состояние ро, как начальное, то машина А будет включена приусловии, что Ф(Р)=1, а машина В будет включена, если Ф(Р)=0.

Правило композиции, определяемое этойтеоремой будем записывать, если Ф то А иначе В.

Теорема 3.4. Для любых машин А и Фможно эффективно построить машину Lтакую, что

L(P)={ Пока Ф(Р)=1, применяй А }

Доказательство: Заменим в доказательстветеоремы 3.3. машину В машиной Е, а заключительное состояние в машине В заменимна начальное состояние в машине />. В итоге получим нужный результат.

Теорема 3.5. (Бомм, Джакопини, 1962)

Любая Машина Тьюринга может бытьпостроена с помощью операции композиций o, ||, если Ф, то А иначе В,пока Ф применяй А.

Эту теорему мы даем здесь бездоказательства.

Следствие 3.1. В силу Тезиса Тьюринга,любая интуитивно вычислимая функция может быть запрограммирована в терминахэтих операций.

Следствие 3.2 Мы получили что-то вродеязыка, на котором можно описывать новую Машину Тьюринга, используя описания ужесуществующих, а затем, используя теоремы 3.1 — 3.4, построить её функциональнуюсхему.

Следствие 3.3 Алгоритм — этоконструктивный объект. В случае Машины Тьюринга атомарными объектами являютсякоманды, а теорема 3.5 определяет правила композиции.

Выводы:

Алгоритм — конструктивный объект;

Алгоритм можно строить из другихалгоритмов;

o, ||, if_then_else, while_do — универсальный набор действий поуправлению вычислительным процессом.

Вопросы :

Что такое правило подстановки?

Зависит ли результат от порядкаследования правил в НАМ?

Что происходит когда не применимо ни одно правило подстановки?

Что утверждает тезис Маркова?

Можно ли доказать тезис Маркова?

Семантика операции o?

Семантика операции ||?