Логика. логіка. Математична логіка та теорія алгоритмів
 Скачать 1.6 Mb.
|
|
Приклад 3. Нехай натуральні числа записуються в алфавіті {I}. Вхідне слово має вигляд m n=III IIII, тобто записане в розширеному алфавіті {I, }. Нормальний алгоритм 3 U заданий схемою: I I Знайти 3 U (ІІІ ІІІІ) Застосовуючи чотири рази першу підстановку, одержимо слово ІІІІІІІ , до якого перша підстановка уже не застосовна. Після цього спрацьовує один раз друга підстановка, яка стирає букву і робота алгоритму на цьому закінчується, тобто 3 U (ІІІ ІІІІ)=ІІІІІІІ. Досить простий аналіз роботи цього алгоритму свідчить, що будь-яке вхідне слово виду n m (де m і n- довільні натуральні числа) він перетворює у суму m+n, тобто наведений нормальний алгоритм реалізує суму двох натуральних чисел. Задачі, що розглянуті в прикладах 1-3 досить прості. Задається вхідне слово і нормальний алгоритм U , потрібно знайти ) ( U . Для цього чисто формально виконуємо оператори нормального алгоритму у відповідності з процедурою його функціонування. Значно складнішими є задачі, в яких ставиться вимога розробити нормальний алгоритм, який розв'язує певний клас задач. Для цього потрібно на змістовному рівні досить глибоко аналізувати розв'язок поставленої задачі, пропонувати різні варіанти підстановок, що ведуть до розв'язку, і для остаточно побудованого нормального алгоритму необхідно перевірити правильність його роботи на всіх можливих варіантах вхідних даних (тобто тут виникає ще і проблема налагодження розробленого алгоритму шляхом тестування). Приклад 4. Побудувати нормальний алгоритм 4 U , який перетворює будь- яке слово в алфавіті } , , { c b a A в слово abc , тобто abc U ) ( 4 Нехай вхідним словом буде bacb . Проведемо такі змістовні міркування: на першому етапі перетворення кожну букву вхідного слова (зліва направо) зітремо, тобто замінимо на пусте слово , а в кінці слово замінимо на abc і процес перетворення вхідного слова на цьому завершимо. А тому шуканий алгоритм можна задати схемою: 101 abc c b a Очевидно, що на будь-якому слові abc U ) ( 4 Приклад 5. Побудувати нормальний алгоритм 5 U , що перетворює будь-яке слово Q P , де P, Q – слова в алфавіті } , { b a A , в слово P, тобто P Q P U ) ( 5 Змістовно очевидно, що на початку роботи треба знищити всі букви вхідного слова, що стоять після букви . Це досягається підстановками: b a Після того, як усі букви слова Q будуть усунені з даного вхідного слова, залишається знищити букву , що реалізується підстановкою: . А тому шуканий алгоритм задається схемою: b a Приклад 6. Скласти нормальний алгоритм 6 U який перетворює будь-яке натуральне число n, записане в алфавіті A={I}, в частку від ділення цього числа на три. Нехай n=IIIIIIII. Замінюючи кожні три палички в цьому слові на одну палочку, ми одержимо результат. Але в переробленому слові за часткою залишиться ще і остача, яку потрібно в кінці роботи знищити. Для відокремлення в слові одиниць частки від одиниць остачі введемо допоміжну букву , яку треба записати на початку слова. Тоді, як легко переконатися, шуканий алгоритм задається схемою: I I III На першому кроці роботи цього алгоритму застосовною до вхідного слова IIIIIIII n буде тільки остання підстановка, в результаті застосування якої на початку вхідного слова буде записана буква і одержимо нове слово IIIIIIII n 1 До цього слова два рази буде застосовною перша підстановка, в результаті чого одержимо слова IIIII I n 2 і II II n 3 . До останнього слова два рази застосуємо другу підстановку, одержимо слова I II n 4 і II n 5 . Використавши третю підстановку одержимо результат II IIIIIIII U ) ( 6 102 Приклад 7. Побудувати нормальний алгоритм 7 U множення двох натуральних чисел nі m, записаних в алфавіті {I}. Вхідним є слово m n в розширеному алфавіті {I, } (буква відіграє роль операції множення). Використавши дистрибутивний закон множення натуральних чисел, маємо: IIIIII II I II I II I II I I I II III ) ( Виходячи з цього, потрібно ввести такі підстановки, які кожну одиницю першого числа n заміняють m одиницями. Ці нові одиниці потрібно якось позначити, щоб вони не змішувалися з одиницями числа m. Введемо підстановку a I , яка замість одиниці числа вводить букву а. Далі, користуючись буквою a , утворимо m позначених одиниць (наприклад, букв b ), не знищуючи одиниць числа m, ввівши підстановку Iba aI . Після дії цієї підстановки одиниці слова т будуть змішані з буквами b . Щоб знову виділити слово m і позначене слово m , що складається з букв b , введемо підстановку Ib bI . Введені три підстановки майже розв'язують поставлене завдання. Наприклад, слово II III алгоритмом a I Iba aI Ib bI перетворюється в слово a IIbbabbabb , в якому вже є шуканий добуток (шість букв b ). Щоб завершити розробку нормального алгоритму множення двох натуральних чисел, залишається ввести підстановки, що знищують одиниці слова m, букви a і знак , та підстановку, що замінює букви b на одиницю. Тобто введемо ще такі підстановки: I b a I Тепер треба ще правильно розташувати введені підстановки. Остаточно нормальний алгоритм множення двох натуральних чисел в розширеному алфавіті {I, , a , b } задається схемою, яку запишемо впорядкованою послідовністю підстановок, розділених комою: I b I a a I Iba aI Ib bI , , , , , , Запитання для самоконтролю 1. Що розуміють під алгоритмом на змістовному рівні(інтуїтивне розуміння)? 103 2. Назвіть характеристичні властивості алгоритмів. 3. Які оператори використовуються в нормальних алгоритмах? 4. Що таке схема нормального алгоритму? 5. Дайте визначення нормального алгоритму Маркова. 6. Як визначається обробка слова нормальним алгоритмом? 7. Чим відрізняються заключні підстановки від звичайних підстановок в нормальному алгоритмі? 8. Як визначається обчислювальність функції : n f N N за допомогою НА? 9. Що таке НА-обчислювальна функція? 10. В чому суть принципу нормалізації? ВПРАВИ 4.1. Натуральні числа записуються в алфавіті } {I A , а схема нормального алгоритму містить одну підстановку: I . Яку функцію реалізує цей алгоритм? 4.2. Нормальний алгоритм заданий в алфавіті } , { b a A схемою: b b a , Вияснити, до яких слів цей алгоритм застосовний, а до яких незастосовний. 4.3. Побудувати нормальний алгоритм, який до будь-якого слова дописує зліва дві букви a 4.4. Задати НА, що знаходить модуль різниці двох натуральних чисел m i n записаних в алфавіті } {I A 4.5. Побудувати НА U для знаходження найбільшого спільного дільника двох натуральних чисел (алгоритм Евкліда), заданих в алфавіті } {I A 4.6. Нехай задано два алфавіти } , { b a A і } , { B , між буквами яких встановлена бієктивна відповідність: b a , . Скласти НА (так званий алгоритм перекладу), який будь-яке слово Р в алфавіті А переводить в слово P P , де P - слово у відповідному алфавіті В. 4.7. В алфавіті } , { b a A задане слово . Побудувати НА в розширеному алфавіті } {I A , який би знаходив довжину слова 4.8. Знайти НА U , який для будь-якого натурального числа п, записаного в двійковій системі числення, тобто в алфавіті } 1 , 0 { A знаходить наступне число в цій же системі числення, тобто 1 ) ( n n U . 104 4.9. Побудувати НА U , що перетворює будь-яке слово Q P , де Q P, -слова в алфавіті } , , { c b a A , в слово Q , тобто Q Q P U ) ( 4.10. Скласти НА, який слово P Q R перетворює в слово Р, де P, Q, R - слова в алфавіті } , { b a A 4.11. Знайти НА U , який перетворює будь-яке натуральне число, записане в алфавіті } {I A , в остачу від ділення цього числа на 3. 4.12. Побудувати НА, що будь-яке натуральне число, записане в алфавіті } {I A перетворює в те ж саме натуральне число, записане в двійковій системі числення в алфавіті B={0, 1}. 4.13. Побудувати НА, що перетворює всяке натуральне число n, записане в алфавіті } {I A , в натуральне число kn, де k - фіксоване натуральне число в тому ж алфавіті А. 4.14. Побудувати НА U , що реалізує функцію натурального аргументу 1 2 ) ( n n f 4.15. Побудувати НА, який всяке слово в алфавіті } {I A перетворює в частку від ділення цього числа на два, записану в тому ж алфавіті А. 4.16. Скласти НА, що перетворює кожне натуральне число n в алфавіті } {I A в цілу частину числа 3 2n , тобто перетворює число n в 3 2n 4.17. Побудувати НА, який слово m n(m i n слова в алфавіті } {I A ) перетворює в слово 3 n m , записане в тому ж алфавіті А. 4.18. Знайти НА U подвоєння слів, тобто алгоритм, який всяке слово Р в алфавіті } , { b a A перетворює в слово РР, тобто PP P U ) ( 4.3. РЕКУРСИВНІ ФУНКЦІЇ Історично першою алгоритмічною системою є система, запропонована в 1936 році американським математиком А. Черчем, яка базується на використанні конструктивно означених арифметичних (цілозначних) функцій, які одержали назву рекурсивних функцій. Застосування подібних функцій в теорії алгоритмів ґрунтується на ідеї нумерації слів в довільному скінченному алфавіті послідовними натуральними числами. Найбільш просто таку нумерацію можна здійснити, розташовуючи слова в будь-якому алфавіті у порядку зростання їх довжини, а слова, які мають однакову довжину, впорядкувати довільно, 105 наприклад, в лексикографічному (алфавітному) порядку. Тоді кожному слову буде відповідати його номер, тобто між сукупністю слів та множиною натуральних чисел встановлюється бієктивна відповідність. При цьому кожному з алфавітних операторів відповідатиме певна функція ) (x f y , аргумент якої, як і сама функція, приймає цілі додатні значення, а сама функція називається арифметичною. Арифметична функція називається загально арифметичною, якщо її область визначення співпадає з усією множиною натуральних чисел, в протилежному випадку функцію називають частково арифметичною. Наприклад, функція ) 7 ( y x z є загально арифметичною, а функція 2 x y - частково арифметична. Функція, для якої існує алгоритм обчислення її значень, називають обчислювальною функцією. Оскільки загальне поняття алгоритму не є математично точним, то таким же є і поняття обчислювальної функції, яке потрібно уточнити. Серед обчислювальних функцій виділимо найбільш прості функції, які називають елементарними арифметичними функціями або базовими. 1). 0 ) ,..., , ( 2 1 n n x x x O - константа нуль або нуль-функція. 2). k n n k x x x x I ) ,..., , ( 2 1 ( n k ) - функція-проектор або функція вибору k-го аргументу. 3). 1 ) ( x x S - функція слідування. Аргументи у всіх цих функцій - натуральні числа. Число 0 також вважаємо натуральним числом. Із базових арифметичних функцій за допомогою трьох операцій - суперпозиції (підстановки), примітивної рекурсії та операції найменшого кореня (операція мінімізації) будуються більш складні обчислювальні функції. При цьому в обчислювальних функціях можна використовувати додаткові, так звані фіктивні аргументи, від яких функція фактично не залежить. Наприклад, функцію слідування можна розглядати як функцію двох (і більше) аргументів: ) ( 1 ) , ( x S x y x 1). Операція суперпозиції (підстановки) дає можливість із відомих функцій ) ,..., ( 1 1 n x x , ) ,..., ( 1 2 n x x ,…, ) ,..., ( 1 n k x x , ) ,..., ( 1 k x x f побудувати нову функцію: )) ,..., ( ),..., ,..., ( ), ,..., ( ( ) ,..., , ( 1 1 2 1 1 2 1 n k n n n x x x x x x f x x x F 106 Приклад 1. З нуль-функції 0 ) ( x O і функції слідування 1 ) ( x x S підстановкою одержується функція 1 )) ( ( x O S - константа одиниця, або константна функція 1 )) ( ( 1 x O S c . Аналогічно можна одержати всі інші константи (натуральні числа): ))...) ,..., , ( ( ( ) ,..., , ( 2 1 2 1 n n раз k n n k x x x O S S S x x x c k Приклад 2. Окремими випадками операції суперпозиції є операції перестановки аргументів та ідентифікації аргументів. Так, функція ) , ( ) , ( x y y x f утворюється з функції ) , ( y x підстановкою: )) , ( ), , ( ( ) , ( 2 1 2 2 y x I y x I y x f , де x y x I y y x I ) , ( , ) , ( 2 1 2 2 - функції-проектори на другу та першу змінні у та х відповідно. Функція ) , ( ) ( x x x f утворюється з функції ) , ( y x підстановками: )) , ( ), , ( ( ) ( 2 1 2 1 y x I y x I x f 2). Операція примітивної рекурсії дає можливість будувати n-місну арифметичну функцію (функцію від n аргументів) за двома заданими функціями, одна з яких (n-1)-місна, а друга – (n+1)-місна. Ця операція визначається такими двома співвідношеннями: )). ,..., , ( , , ,..., , ( ) 1 , ,..., , ( ), ,..., , ( ) 0 , ,..., , ( 2 1 1 2 1 1 2 1 1 2 1 1 2 1 n n n n n n n x x x f x x x x h x x x x f x x x g x x x f де функції ) ,..., , ( 1 2 1 n x x x g і ) ,..., , ( 1 2 1 n x x x h задані, а функція ) , ,..., , ( 1 2 1 n n x x x x f визначається цими співвідношеннями, які називають схемою примітивної рекурсії. Кажуть, що ) , ,..., , ( 1 2 1 n n x x x x f одержана за схемою примітивної рекурсії з функцій ) ,..., , ( 1 2 1 n x x x g і ) ,..., , ( 1 2 1 n x x x h |