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

Згідно теоремам 3.1 і 3.2., ми можемо побудувати машину, знаючи Е, Ф і СМІТТЮ. Тепер, маючи, BRNCH, А і В, можна побудувати машину З таким чином:

Машина 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 - універсальний набір дій по управлінню обчислювальним процесом.

2. Нормальні Алгоритми Маркова. Побудова алгоритмів з алгоритмів

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

Якщо входження a в w знайдено, те слово a замінюється на слово g.

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

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

Правило початку - проглядання правил завжди починається з першого.

Правило закінчення - виконання алгоритму закінчується, якщо:

було застосовано правило підстановки вигляду aag,

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

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

Розглянемо приклад 1 з лекції 2:

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

U(n) =n+1;

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