відповіді алгоритми
Інтуїтивне поняття алгоритму. Властивості алгоритмів.
Алгоритм це-певна послідовність дій для вирішення певної проблеми.
Такими властивостями є:
• Дискретність (переривчастість, роздільність) - алгоритм повинен представляти процес вирішення завдання як послідовне виконання простих (або раніше визначених) кроків. Кожна дія, передбачене алгоритмом, виконується тільки після того, як закінчилося виконання попереднього.
• Визначеність - кожне правило алгоритму має бути чітким, однозначним і не залишати місця для сваволі. Завдяки цій властивості виконання алгоритму носить механічний характер і не вимагає ніяких додаткових вказівок або відомостей про розв'язуваної задачі.
• Результативність (кінцівка) - алгоритм повинен призводити до вирішення завдання за кінцеве число кроків.
• Масовість - алгоритм рішення задачі розробляється в загальному вигляді, тобто, він повинен бути застосовний для деякого класу задач, що розрізняються лише вихідними даними. При цьому вихідні дані можуть вибиратися з деякою області, яка називається областю застосовності алгоритму.
Машина Поста. Опис, приклади задач. Формулювання l.
Машина Поста (МП) - абстрактна обчислювальна машина, запропонована Емілем Леоном Постом (англ. Emil Leon Post), яка відрізняється від машини Тьюринга більшою простотою. Обидві машини алгоритмічно «еквівалентні» і були придумані для уточнення поняття «алгоритм». У 1936 році американський математик Еміль Пост в статті описав систему, що володіє алгоритмічної простотою і здатну визначати, чи є та чи інша задача алгоритмічно розв'язною. Якщо завдання має алгоритмічне рішення, то вона подана також у формі послідовності команд для машини Поста.
Додавання двох чисел тривіально - досить поставити 1 між ними і стерти два крайніх правих «1» у Q. Програма вирахування складається з послідовної зміни крайніх лівих «1» у послідовності «1» в зображенні Q і правих «1» у послідовності «1» в зображенні P. на початку програми каретка встановлена на крайню ліву «1» у Q:
2. 1, 3 - якщо в осередку порожньо, перейти до 1 кроку, якщо ні, до 3
3. 0 - видалити мітку
5. 4, 6 - якщо в осередку порожньо, перейти до 4 кроку, якщо ні, до 6
6. 0 - видалити мітку
8. 9, 1 - якщо в осередку порожньо, перейти до 9 кроку, якщо ні, до 1
Відзначимо, що номер команди переходу не вказується, якщо перехід відбувається на наступну по порядку рядок (для наочності тексту). У 6-му рядку можливо зациклення, якщо Q> P.
Визначення машини Тьюринга. Застосування машин Тьюринга до слів.
Машина Тьюринга (МТ) - aбстрактний виконавець (абстрактна обчислювальна машина). Була запропонована Аланом Тьюрингом в 1936 році для формалізації поняття алгоритму.
Машина Тьюринга є розширенням кінцевого автомата і, згідно з тезою Черча - Тьюринга. здатна імітувати всі виконавці (за допомогою завдання правил переходу), будь-яким чином реалізують процес покрокового обчислення, в якому кожен крок обчислення досить елементарний.
Машина Тьюринга володіє зовнішнім алфавітом А =, символи якого записуються на стрічку машини, і алфавітом внутрішніх станів Q =, де q1 - початковий стан, q0 - заключне. Робота машини визначається програмою (функціональною схемою). Програма складається з команд. Кожна команда T (i, j) (i = 1, 2, ..., m; j = 0, 1, ..., n) є виразом одного з наступних видів:
Конструювання машин Тьюринга. Композиції машин Тьюринга.
Приклад 3. Спробуємо побудувати таку машину Тьюрін-га, яка з п записаних підряд одиниць залишала б на стрічці n-2 одиниці, також записані підряд, якщо п> 2, і працювала б вічно, якщо п = 0 або n = 1. В як зовнішній алфавіту візьмемо двоелементною множе-ство А =. Кількість необхідних внутрішніх станів буде визначено в процесі складання програми. Вважаємо, що машина починає працювати зі стандартного початкового поло-ження, тобто коли в стані q1 оглядається крайня права оди-ка ИЗП записаних на стрічці. Почнемо з того, що зітремо першу одиницю, якщо вона є, перейдемо до огляду наступної лівого вічка і зітремо там одиницю, якщо вона в цьому осередку записана. На кожному такому переході машина повинна переходити в нове внутрішній стан, тому що в протилежному випадку будуть стерті взагалі все одиниці, записані підряд. Ось команди, які здійснюють описані дії: q11 q20Л; q21 q30Л. Машина знаходиться в стані q3 оглядає третю праворуч осередок з тих. в яких записано дане слово (п одиниць). Не змінюючи вмісту оглядається осередку, машина повинна осту-новіться, тобто перейти до заключного стан q0, неза-мо від вмісту осередки. Ось ці команди: q30 q00; q31 q01. Тепер залишається розглянути ситуації, коли на стрічці записи-на всього одна одиниця або не записав жодної. Якщо на стрічці записана одна одиниця, то після першого кроку (виконавши коман-ду q11 q20Л) машина буде перебувати в стані q2 і буде оглядати другу праворуч осередок, в якій записаний 0. По усло-вию, в такому випадку машина повинна працювати вічно . Це можна забезпечити, наприклад, такою командою: q20 q20П, виконуючи яку крок за кроком. машина буде рухатися по льон-ті необмежено вправо (або протягувати стрічку через зчитую-щую головку справа наліво). Нарешті, якщо на стрічці не записано жодної одиниці, то машина, за умовою, також повинна рабо тать вічно. В цьому випадку в початковому стані q1 оглядається осередок з вмістом 0, і вічна робота машини забезпечується за допомогою такої команди: q10 q10П.
Обчислюваних по Тьюрингу функції. Правильна вичіслімость функцій на машині Тьюринга.
Теза Тьюринга (основна гіпотеза теорії алгоритмів). Машини Тьюринга і сучасні ЕОМ.
Теза Тьюринга: Клас функцій, алгоритмічно обчислюваних щодо якої-небудь функції (або класу функцій), збігається з класом часткових функцій, частково рекурсивних щодо (відповідно щодо системи).
З тези Тьюрінга випливає теза Черча.
Походження рекурсивних функцій.
(Від позднелатинского recursio - повернення)
назва, що закріпилася за одним з найбільш поширених варіантів уточнення загального поняття арифметичного алгоритму, тобто такого Алгоритму, допустимі вихідні дані якого є системи натуральних чисел, а можливі результати застосування є натуральними числами. Рекурсивні функції були введені в 30-х рр. 20 в. С. К. Кліні. в свою чергу грунтується на дослідженнях К. Геделя. Ж. Ербрана і ін. Математиків.
Кожна рекурсивна функція задається кінцевою системою рівностей точно охарактеризованого типу в тому сенсі, що її значення обчислюються за допомогою цієї системи рівностей по точно формулируемая правилам, причому таким чином, що в результаті для обчислення значень заданої рекурсивної функції виходить алгоритм певного типу.
Рекурсивні функції є частковими функціями, т. Е. Функціями, не обов'язково всюди визначеними. Щоб підкреслити цю обставину, часто як синонім використовують термін «частково рекурсивні функції». Рекурсивні функції, визначені при будь-яких значеннях аргументів, називають общерекурсівнимі функціями.
Основні поняття теорії рекурсивних функцій і теза Черча.
Теза Черча. клас алгоритмічно (або машинно) обчислюваних часткових числових функцій збігається з класом всіх частково рекурсивних функцій. Іншими словами, арифметична функція, обчислювана в загальному сенсі, є суть рекурсивна функція. Соотв.
часткова арифметична функція, обчислювана в загальному сенсі, є суть частково рекурсивна функція. Це не суворе визначення, це висновок на рівні тези (не доведену, але і не спростоване твердження)
примітивно рекурсивні функції - рекурсивні функції, що виходять з вихідних функцій в результаті кінцевого числа застосувань одних лише операторів суперпозиції і примітивної рекурсії. Вони утворюють власну частину класу общерекурсівних функцій. В силу відомої теореми Кліні про нормальній формі рекурсивної функції можуть бути вказані такі конкретні примітивно рекурсивні функції U від однієї змінної та Tn від n + 2 змінних, що для будь-якої рекурсивної функції φ отn змінних і для будь-яких натуральних чисел x 1. xn має місце рівність φ (x 1. xn) ≅ U (y), гдеу є найменше з чисел z таких, що T n (φ. x 1. xn, z) = 0 (тут φ є т. н. Геделя номер функції φ - число, яке ефективно будується за системою рівностей, яка задає функцію φ). З цієї теореми, зокрема, випливає, що для рекурсивної функції від п змінних може бути побудована універсальна рекурсивна функція від n +1 змінних, т. Е. Така рекурсивна функціяФ n, що для будь-якої рекурсивної функції φ від n змінних і для будь-яких натуральних чисел x 1. xn має місце умовне рівність
Зазначимо на ряд широко відомих арифметичних функцій, які є примітивно рекурсивними.
Функція Додавання двох натуральних чисел () може бути розглянута як примітивно рекурсивної функції двох змінних, одержуваної в результаті застосування оператора примітивної рекурсії до функцій і. друга з яких виходить підстановкою основної функції в основну функцію S:
Вичіслімость по Тьюрингу примітивно-рекурсивних функцій.
Функція Аккермана - простий приклад всюди певної обчислюваної функції. яка не є примітивно рекурсивної. Вона приймає два невід'ємних цілих числа в якості параметрів і повертає натуральне число. позначається. Ця функція зростає дуже швидко, наприклад, число настільки велике, що кількість цифр в порядку цього числа багаторазово перевершує кількість атомів в спостережуваної частини Всесвіту.
Оператор мінімізації Нехай є функція f (x1, ... .xn). що належить безлічі часткових арифметичних функцій (ПАФ). Нехай існує якийсь механізм її обчислення, причому значення функції не визначено тоді і тільки тоді, коли цей механізм працює нескінченно, не виказуючи ніякого певного результату. Фіксуємо якісь значення x1. xn-1 для перших n-1 аргументів функції f і розглянемо рівняння: f (x1. xn-1, y) = xn Щоб знайти рішення y (натуральне) цього рівняння, будемо обчислювати за допомогою вказаного вище "механізму" послідовно значення f ( x1. xn-1, y) для y = 0,1,2. Найменше значення a, для якого вийде f (x1. Xn-1, a) = xn. позначимо через μy (f (x1. xn-1, y) = xn) Описаний процес знаходження виразу μy (f (x1. xn-1, y) = xn) буде тривати нескінченно в наступних випадках:
У всіх цих випадках значення виразу μy (f (x1. Xn-1, y) = xn) вважається невизначеним. В інших випадках описаний процес обривається і дає найменшу рішення y = a рівняння f (x1. Xn-1, y) = xn .. Це рішення, як сказано, і буде значенням вираженіяμy (f (x1. Xn-1, y) = xn). Наприклад, для функції різниці f (x, y) = xy відповідно до зазначеного змістом символу μ, для всіх x, y маємо: f (x, y) = xy = μz (y + z = x) Підрахунок значень функції f ( x, y) = xy в цьому випадку буде відбуватися за двома сценаріями.
Общерекурсівние і частково рекурсивні функції.
Рекурсією називається такий спосіб завдання функції, при якому значення визначається функції для довільних значень аргументів виражаються відомим чином через значення визначається функції для менших значень аргументів. Розглянемо рівність f (х) = g (x), де f (х) і g (x) деякі функції. Коли говорять, що це рівність є рівняння, то це означає, що рівність розглядається як невизначений висловлювання, при одних значеннях х справжнє, при інших помилкове. Визначення. Функція є загально-рекурсивної, якщо вона визначена за допомогою ряду рівнянь деякого типу.
Визначення. Часткова функція f називається частково рекурсивної, якщо вона може бути отримана з найпростіших функцій O, S, Umn кінцевим числом операцій підстановки, примітивної рекурсії і мінімізації. Із зазначеного основного визначення безпосередньо випливають такі властивості щодо рекурсивних функцій.
Кожна часткова функція, примітивно рекурсивна щодо системи функцій σ, є і частково рекурсивної относітеьно σ. Зокрема, все примітивно рекурсивні функції частково рекурсивних.
Клас частково рекурсивних функцій ширше класу примітивно рекурсивних функцій, так як все примітивно рекурсивні функції всюди певні, а серед частково рекурсивних функцій зустрічаються і функції не всюди певні, наприклад ніде не визначена функція
Операції підстановки, примітивної рекурсії і мінімізації, вироблені над функціями, частково рекурсивними щодо системи σ, дають в результаті функції, знову частково рекурсивні щодо σ.
Визначення. Часткова аріфмітіческая функція f називається частково рекурсивної, якщо вона може бути отримана з найпростіших функцій O, S, Umnконечним числом операцій підстановки, примітивної рекурсії імінімізаціі.