Будь-який алгоритм може бути реалізований відповідною машиною

Тьюринґа.

Це основна гіпотеза теорії алгоритмів у формі Тьюринґа. Одночасно ця теза є формальним визначенням алгоритму. Завдяки їй можна доводити існування або неіснування алгоритмів, створюючи відповідні машини Тьюринґа або доводячи неможливість їхньої побудови. Завдяки цьому з'являється загальний підхід до пошуку алгоритмічних розв'язків.

Якщо пошук розв'язку наштовхується на перешкоду, то можна використовувати цю перешкоду для доведення неможливості розв'язування, спираючись на основну гіпотезу теорії алгоритмів. Якщо ж при доказі неможливості виникає своя перешкода, то вона може допомогти просунутися в пошуку розв'язку; хоча б частково усунувши стару перешкоду. Так, по черзі намагаючись довести то існування, то відсутність розв'язку, можна поступово наблизитися до розуміння суті поставленної задачі.

Довести тезу Тьюринґа не можна, тому що в його формулюванні не визначене поняття будь-який алгоритм, тобто ліва частина тотожністі. Його можна тільки обґрунтувати, подаючи різноманітні відомі алгоритми у вигляді машин Тьюринґа. Додаткове обґрунтування цієї тези полягає в тому, що пізніше було запропоновано ще декілька загальних визначень поняття алгоритму і щораз вдавалося довести, що, хоча нові алгоритмічні схеми і виглядають інакше, вони насправді еквівалентні машинам Тьгоринґа:

Усе, що реалізовано в одній з цих конструкцій, можна зробити і в інших.

Ці твердження доводяться строго, тому що в них мова йде вже про тотожність формальних схем.

Рекурсія та її використання

Означення називається рекурсивним, якщо воно задас елементи множини за допомогою інших елементів цієї ж множини. Об'єкти, задані рекурсивним означенням, також називаються рекурсивними. Нарешті, рекурсія — це використання в алгоритмі рекурсивних означень.

Рекурсивною функцією називається функція, яка може бути отримана з базових функцій за допомогою скінченної кількості застосувань підстановок, та примітивних рекурсій.

До базових примітивних рекурсивних функцій відносяться три функції:

1) нуль-функція Z (x)=0 при будь-якому х;

2) додавання одиниці: N (x) = х +1;

3) проектуючі функції: U_i(x_l,...,x_n)=x_i для всіх х₁,...,х_n. (визначає натуральне число з цієї множини).

Функція f(х₁,…,х_n) отримана з функцій g, h₁,...,h_m, за допомогою підстановки, якщо f(х₁,…,х_n) = g(h₁(х₁,…,х_n),...,h_m(х₁,…,х_n)).

Функція f(х₁,…,х_n,y) отримана за допомогою рекурсії, якщо:

f(х₁,…,х_n,y+1)=h(х₁,…,х_n,y, f(х₁,…,х_n,y));

f(х₁,…,х_n,0)=g(х₁,…,х_n) при n≠0;

f(y+1)=h(y,f(y)); f(0)=k, k – ціле невід'ємне число при n = 0.

Функція f(х₁,…,х_n) отримана за допомогою µ -оператора, якщо її значення дорівнює мінімальному значенню у, при якому g(х₁,…,х_n,y)=0.

Частково рекурсивною називається функція, яка конструюється за допомогою скінченного числа підстановок, рекурсій та µ -операторів, але визначена не при всіх значеннях аргументів.

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

Приклад 1.10. Визначення функції ≪факторіал≫ задаються виразом: 0!=1, n!=nх (n-1)!. Вони утворюють множину {1,2,6,...}: 0!=1, 1!=1, 2!=2, 3!=6,.... Усі її елементи, крім першого, визначаються рекурсивно.

Отже, функція ≪факторіал≫ задається рекурентним співвідношенням порядку 1 і початковим відрізком 0!=1. Загалом, будь-яке рекурентне співвідношення порядку k разом із завданням перших k елементів послідовності є прикладом рекурсивного означення.

Приклад 1.11. Арифметичні вирази зі сталими та знаком операції ‘+’ у повному дужковому записі (ПДЗ) задаються таким означенням:

1) стала є виразом у ПДЗ;

2) якщо Е і F є виразами у ПДЗ, то (E)+(F) також є виразом у ПДЗ.

Такими виразами є, наприклад, 1, 2, (1)+(2), ((1)+(2))+(1). Всі вони, крім сталих, означаються рекурсивно.

Для коректного виходу з рекурсії повинні виконуватися умови:

ü множина означуваних об'єктів є частково упорядкованою;

ü кожна спадна за цим впорядкуванням послідовність елементів закінчується деяким мінімальним елементом;

ü мінімальні елементи означаються нерекурсивно;

ü неміпімшіьні елементи означаються за допомогою менших від них елементів.

Глибина рекурсії – кількість викликів підпрограми, що реалізують рекурсію.

Вживання рекурсивних підпрограм вимагає обережності та вміння оцінити можливу глибину рекурсії та загальну кількість викликів. Не завжди треба писати рекурсивні підпрограми безпосередньо за рекурсивним означенням. Справа в тому, що виконання кожного виклику підпрограми потребує додаткових дій комп'ютера. Тому ≪циклічний≫ варіант описання обчислень виконується, як правило, швидше від рекурсивного. Також нетреба вживати рекурсію для обчислення елементів рекурентних послідовностей. За великої глибини рекурсії це взагалі може призвести до вичерпання автоматичної пам'яті та аварійного завершення програми.

Наведемо приклад нерекурсивного та рекурсивного визначення значення функції.

Приклад. 1.12. Маємо функцію, що розкладається у ряд:

.

#include <stdio.h>

#include<math.h>

double func1 (int n); // прототип нерекурсивної функції ряду

double func2(int n); // прототип рекурсивної функції ряду

void main()

{

int n; // n - кількість елементів ряду

double s=1; // значення функції

scanf("%n", &n); // ввели кількість елементів ряду

printf("Nonrecursiv result is %6.2f", func1(n));

printf("Recursiv result is %6.2f", func2(n));

}

double func1 (int n)

{

double s=1;

int x; // x - поточний член ряду

for(x=1;x<=n;x++)

s*=x/(exp(x) - x*x)

return (s);

}

double func2(int n)

{

double s=1;

if (n<1) // умова виходу з рекурсії

return (s);

else

s*=n/(exp(n) - n*n)*func2(n-1);// виклик рекурсивної функції з

n-1

}

Найкраще рекурсію використовувати тоді, коли розв'язання задачі з допомогою рекурсії загалом зводиться до розв'язання подібної задачі, але меншої розмірності, а, отже, легшої для розв'язання.

Найяскравіший приклад задачі такого плану- задача про ханойські вежі.

Легенда свідчить, що десь в Ханої знаходиться храм, в якому розміщена така конструкція: на підставці знаходяться З діамантових стержня, на яких при створенні світу Брахма нанизав 64 золотих диска із отвором посередині, причому внизу опинився найбільший диск, на ньому трохи менший і так далі, поки на верхівці піраміди не опинився найменший диск. Жерці храму зобов'язані перекладати диски за такими правилами:

1) за один хід можна перенести лише один диск,

2) не можна класти більший диск на менший.

Керуючись цими правилами, жерці повинні перенести початкову піраміду з 1-го стержня на 3-й. Як тільки вони впораються з цим завданням, настане| кінець світу.

Для розв'язання задачі спочатку спробуємо побудувати абстрактну модель процесу перенесення частини піраміди.

Отже, вирішуємо узагальнену задачу: як перенести піраміду з n кілець із стержня i на стержень j, користуючись стержнем k як допоміжним? Ця задача розв'язується таким чином.

1. Перенести (n-1) кільце i на k.

2. Перенести 1 кільце з i на j.

3.Перенести (n-1) кільце на j.

Отже, задача перенесення n кілець розв'язується через перенесення (n-1) кільця. Залишилося лише додати тривіальну граничну умову для виродженого випадку перенесення порожньої піраміди з 0 кілець, щоб наш алгоритм завершився.

Реалізація алгоритму на мові С:

void Hanoj (int n, short і, short j, short k)

// перенесення піраміди з n дисків з стержня i

// на стержень j, використовуючи стержень k як допоміжний

{

//перевірка граничної умови - порожню піраміду не переміщувати

if (!n) return;

Hanoj (n-1, і, k,j);

// переносимо одне кільцо - фактично це Hanoj (1, і, j, k);

printf(≪%2d-%2d\n≫,i,j);

Hanoj (n-1, k, j, i);

}

Конфликты в семейной жизни. Как это изменить? Редкий брак и взаимоотношения существуют без конфликтов и напряженности. Через это проходят все...

ЧТО И КАК ПИСАЛИ О МОДЕ В ЖУРНАЛАХ НАЧАЛА XX ВЕКА Первый номер журнала «Аполлон» за 1909 г. начинался, по сути, с программного заявления редакции журнала...

Что делать, если нет взаимности? А теперь спустимся с небес на землю. Приземлились? Продолжаем разговор...

ЧТО ПРОИСХОДИТ, КОГДА МЫ ССОРИМСЯ Не понимая различий, существующих между мужчинами и женщинами, очень легко довести дело до ссоры...

Не нашли то, что искали? Воспользуйтесь поиском гугл на сайте: