Схожі визначення алгоритму, контент-платформа

Схожі визначення алгоритму

Алгоритм - це точно певна (однозначна) послідовність простих (елементарних) дій, які забезпечують вирішення будь-якої задачі з деякого класу.

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

Поняття можна уточнити, вказавши перелік загальних властивостей. які харакутерни для алгоритмів. До них відносяться:

1. Дискретність - алгоритм розділений на окремі кроки, причому виконання чергового кроку можливо тільки після завершення всіх операцій на попередньому кроці;

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

3. Елементарність кроків # 8209; закон отримання подальшої системи величин з попередньої повинен бути простим і локальним;

4. Спрямованість # 8209; якщо спосіб отримання наступних величин з будь-яких вихідних не призводить до результату, то повинно бути вказано, що слід вважати результатом алгоритму;

5. Масовість - початкова система величин може вибиратися з деякої множини.

Поняття алгоритму, яке визначається перерахуванням властивостей 1 - 5, також не можна вважати суворим, оскільки в формулюваннях властивостей використані терміни «величина», «спосіб», «простий», «локльний» точний зміст яких не встановлено. Тому його називають нестрогим (інтуїтивним) поняттям алгоритму.

Уточнення поняття алгоритм проводиться в рамках алгоритмічних моделей.

Один з напрямків побудови строгого визначення поняття алгоритму пов'язано з розглядом алгоритмів, що дозволяють обчислювати значення числових функцій, що залежать від цілочисельних значень аргументів - такі функції отримали назву обчислюваних. Поняття обчислюваної функції не є строгим, як і поняття алгоритму. Однак в роботах А. Черча. К. Геделя. С. Кліні була обгрунтована тотожність класу всюди певних обчислюваних функцій з класом частково рекурсивних функцій. який визначається строго. Це дозволило звести проблему алгоритмічної можливості розв'язання до доказу можливості (або неможливості) побудови рекурсивної функції, вирішує завдання.

Нехай є два безлічі Х і Y.

Якщо деяким елементам безлічі Х поставлені у відповідність однозначно визначені елементи множини Y, то кажуть, що задана часткова функція з Х в Y.

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

Якщо область визначення функції з Х в Y збігається з безліччю Х, то функція називається всюди визначеною.

Ідея побудови точного визначення алгоритму, що спирається на поняття рекурсивної функції

Будь-які дискретні дані можна закодувати натуральними числами в деякій системі числення.

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

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

Нехай є клас функцій типу y (x1, x2. ..., xn). особливостями яких є те, що всі аргументи функції x1, x2. ..., xn цілочисельних, і значення функції y також виражається цілим числом.

Функціяy (x1, x2. ..., xn) називається ефективно обчислюваною. якщо існує алгоритм, що дозволяє обчислити її значення за відомими значеннями аргументів.

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

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

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

У рекурсивної моделі «елементарними кроками» є найпростіші числові функції:

· S 1 (x) = x + 1 це одномісна функція безпосереднього проходження;

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

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

Суперпозиція часткових функцій

Нехай m- місцеві функції

підставляються в n-місні функцію g (x1, ..., xn). В результаті виходить n - місцева функція

Кажуть, що функція h отримана з функцій g. f1, ..., fnсуперпозіціей (підстановкою).

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

Якщо вміємо обчислювати функції g, f 1, ......, f n, то функція h також може бути обчислена.

Якщо функції g, f 1, ......, f n, усюди визначені, то функція h також усюди визначена.

Нехай задані будь-які числові часткові функції: n - місцева g (x1, ..., xn) і (n + 2) - місцева. h (x1, ..., xn, y, k). Кажуть, що (n + 1) -місна часткова функція f утворюється з функцій g і h за допомогою примітивної рекурсії, якщо для всіх натуральних значень x1, ..., xn, y справедливо:

Оскільки областю визначення функцій є безліч всіх натуральних чисел, часткова функція f. що задовольняє умовам (1), існує для всіх часткових функцій g і h і функція ця буде єдиною.

Умови (1) задають також послідовність визначення значень f на різних етапах рекурсії:

Для примітивної рекурсії використовується позначення

У цьому записі R розглядається як символ двомісній часткової операції, визначеної на множині всіх часткових функцій. Якщо g і h є всюди певними, то і f є всюди визначеною. Важливим є те, що якщо вміємо знаходити значення функцій g і h. то значення функції f (a1, ..., an, m +1) можна обчислити «механічно» використовуючи співвідношення (2).

Часткова функціяf (x1, ..., xn) називається примітивно рекурсивної, якщо її можна отримати кінцевим числом операцій суперпозиції і примітивної рекурсії, виходячи лише з найпростіших функційS1. 0nіInm.

Все примітивно рекурсивні функції всюди визначені.

Довести, що двомісна функція f (x, y) = x + y є примітивно-рекурсивної

Знайти значення функції f (3,2). якщо вона задана наступними співвідношеннями:

Нехай задана деяка функція f (x, y). Зафіксуємо значення x і з'ясуємо, при якому y значення f (x, y) = 0. Складнішою виявляється задача відшукання найменшого з тих значень y. при яких f (x, y) = 0.

Оскільки результат вирішення такого завдання залежить від x. то і найменше y є функцією x.

Подібним же чином визначається функція багатьох змінних

Для обчислення функції j можна використовувати наступну процедуру:

Функція f (x, y) = x-y може бути отримана за допомогою оператора мінімізації:

Часткова функціяf (x1, ..., xn) називається частково рекурсивної. якщо її можна отримати кінцевим числом операцій суперпозиції, примітивної рекурсії і мінімізації, виходячи лише з найпростіших функційS1. 0nіInm.

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

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

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

З іншого боку, які б класи точно окреслених алгоритмів не будувалися, у всіх випадках незмінно виявлялося, що обчислюваних за допомогою них числові функції були частково рекурсивними.

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

Клас алгоритмічно (або машинно) обчислюваних часткових числових функцій збігається з класом всіх частково рекурсивних функцій.