О формализации понятия алгоритма.

Термин «алгоритм» впервые был использован средневековыми учеными, переводившими на латынь сочинения Аль Хорезми. Алгоритмами они называли правила арифметических действий на многоразрядными числами.

В XVII веке В.Лейбниц выдвинул идею формализации математики – т.е. построения универсального метода решения математических задач в виде системы правил манипулирования символами, с помощью которых эти задачи формулируются. В.Лейбниц ввел в употребление современную символику дифференциального и интеграль­ного исчисления, в большой степени решившую задачу вычислений произ­водных и интегралов при помощи формальных правил мани­пу­лирования символами.

Формальное понятие алгоритма было сформулировано как одно из понятий математической логики в 30-х годах XX века. В работах Э. Поста, А. Тьюринга, С. Клини, А. Черча и др. логиков. Несколько позже А.А. Марков ввел еще один формализм описания алгоритмов – т.н. нормальные алгорифмы Маркова.

Фор­маль­ные аспекты понятия «алгоритм» изучаются в теории алгоритмов

Определение алгоритма как частично-рекурсивной функции

(С. Клини, А.Черч)

Понятие вычислимости. Вычислимые функции

Альтернативный (императивному) т.н. декларативный (описа­тель­ный) подход к описанию алгоритмов состоит в описании алгоритма как функции преобразования Вход à Выход.

Алгоритм: Вход à Выход

Или, в более привычных «школьных» обозначениях

y = A(x),

Где A – алгоритмическая функция

x ÎХ – входные данные (аргументы) из области определения X

y ÎY – выходные данные (значения) из области значений Y.

Изучение понятия алгоритма, следовательно, можно определить как изучение свойств функции A.

Точная постановка задачи формального определения алгоритма заключается в формализации понятия вычислимой функции.

Под вычислимыми функциями понимают натуральные функции натуральных аргументов, значения которых можно вычислить, исходя из значений аргументов, выполнив конечное число элементарных, точно определенных вычислительных действий.

В качестве областей определения аргументов и области значения функции выступают натуральные числа. Почему именно они?

Натуральные числа можно задавать конструктивным и конечным способом, например в десятичной системе счисления.

2. Требование конструктив­нос­ти и конечности элементов областей определения и значения алгоритми­чес­ких функций приводит к тому, что эти элементы можно перенумеровать и использовать таким образом в рассуждениях об алгоритмических функциях номера элементов вместо самих элементов.

Примеры вычислимых функций:

Z = x+y, z = min(x, y), z = x div y

Более сложные примеры прямо апеллируют к интуитивному понятию алгоритма:

Y = {наименьшее простое число, большее x и такое, что y+2 - также простое}

Y = {максимальный показатель степени в разложении числа x в произведение степеней простых сомножителей }

Примитивно-рекурсивные функции

0. Базисные примитивно-рекурсивные функции:

a) s(x) =df= x + 1 примитивно рекурсивна (по определению)

b) o(x) =df= 0 примитивно рекурсивна (по определению)

c) pi(x1,…,xi,…,xn) =df= xi примитивно рекурсивна (по определению)

Правила построения примитивно-рекурсивных функций

Правило суперпозиции

Если F(y₁, …, y_n) примитивно рекурсивна и g₁(x₁,…,x_k), g₂(x₁,…,x_k),... g_n(x₁,…,x_k) примитивно рекурсивны,то

H(x1, …, xk) =df= F(g1(x1,…,xk), g2(x1,…,xk),... gn(x1,…,xk)) также примитивно рекурсивна

Правило примитивной рекурсии

Если F(x1,…,xn-1), G(x1,…,xn, xn+1) – примитивно-рекурсивные функции, то функция H(x1,…, xn), определяемая соотношениями

а) H(x1, …, xn-1, 0) =df= F(x1,…,xn-1)

b) H(x1, …, xn-1, s(y)) =df= G(x1,…,xn-1, y, H(x1, …, xn-1, y))

также примитивно рекурсивна.

Функция называется примитивно-рекурсивной, если она определена с помощью конечного числа правил 1, 2 из функций, определенных правилом 0 (из базисных примитивно-рекурсивных функций).

Суть рекуррентных (рекурсивных) определений:

· Определяются базисные (элементарные) объекты определяемого класса.

· Определяются правила построения объектов – такие правила, применения которых к (уже определенным) объектам приводит к построению новых объектов определяемого класса.

· Объектами определяемого класса объявляются только те, которые могут быть построены из базисных с применения помощью конечного числа правил построения.

Упражнение. Определить класс управляющих структур алгоритмов с помощью рекурсивных определений.

Многие классы функций, используемые в математике, обладают свойствами 0 и 1, т.е. содержат функции s(x), o(x), p_i(x₁, …, x_n) и замкнуты относительно операции суперпозиции.

«Эксклюзивность» и, как следствие, имя классу примитивно-рекурсивных функций дает правило (схема) примитивной рекурсии.

Отметим, что функция проектирования p_i(x₁, …, x_n) используется для решения технической проблемы представления функции одного переменного как функции многих переменных.

Обоснование вычислимости функций, определяемых правилом 2

Вход: x₁,…,x_n-1, y

H:= F(x₁,…,x_n-1),

Для i:= 1 до y выполнить H:= G(x₁,…,x_n-1,i_, H)

Выход: H

Переменные x₁,…,x_n-1 играют роль параметров (не меняют значения в теле цикла). Переменная y - верхнее значение параметра цикла. Вычисление каждого следующего значения H использует предыдущее значение Н.

Пример: П. Р. Функция Add сложения двух натуральных чисел

Add(x, o) = x; {x + 0 = x}

Add(x,s(y)) = s(Add(x, y)) {x + (y + 1) = (x + y) + 1

Мю-оператор

Основной результат о примитивно-рекурсивных функциях и их связи с императивными алгоритмами можно сформулировать так:

Примитивно-рекурсивные функции вычислимы. Вычисление прими­тивно-рекурсивной функции можно реализовать в виде императивного алгоритма, использующего число 0, функцию s, оператор присваивания и оператор повторения с параметром.

Можно построить пример вычислимой функции, не принадлежащей классу примитивно-рекурсивных функций

Функция Аккермана

Функция Аккермана А(x, y) определена на множестве натуральных чисел рекурсивно:

A(0, y) = y + 1,

A(x, 0) = A(x - 1, 1),

A(x, y) = A(x - 1, A(x, y - 1));

Упражнение

a) Опишите функции A(1, y), A(2, y), A(3, y), A(4, y) явным образом;

б) Реализуйте рекурсивную программу вычисления A(x, y);

в) Реализуйте программу вычисления A(x, y) без рекурсии.

Для формализации класса вычислимых функций правила примитивной рекурсии недостаточно. Более того, никакое “разумное” расширение класса ПРФ до формально описанного класса всюду определенных функций, являющихся вычислимыми, невозможно.

Поэтому любой формализм неибежно приводит к частично-определенным функциям (функциям, не определенным при некоторых значениях аргумента). Свойство результативности алгоритма оказывается нетривиальным.

Правило m-операции

Пусть F(x₁,…,x_n,y) – вычислимая функция. Тогда функция G(x₁,…,x_n), определенная правилом

G(x₁,…,x_n) = { Наименьшее y | F(x₁, …, x_n, y) = 0 }

является (по определению) результатом применения m-операции к функции F(x₁,…,x_n, y). Стандартная форма записи m- операции:

G(x₁,…,x_n) = m y (F(x₁, …, x_n, y) = 0 }

Говорят, что функция G – результат применения m-оператора к функции F.

Решение уравне­ния F(x1, …, xn, y) = 0 для любой вычислимой функции F возможно осуществить последовательным пере­бо­ром значений y, однако такой способ решения не дает гарантии того, что перебор когда-нибудь завершится.

Если это уравнение не имеет решения, перебор не завершится, и, следовательно, значение функции G не будет найдено.

Функция G, таким образом, опре­де­­лена частично

Частично-рекурсивные функции как формализация понятия вычислимых функций

Функция называется частично-рекурсивной, если она определена с помощью конечного числа правил суперпозиции, примитивной рекурсии и m-операции из функций, определенных правилом 0 (из базисных примитивно-рекурсивных функций).

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

ЧТО ПРОИСХОДИТ ВО ВЗРОСЛОЙ ЖИЗНИ? Если вы все еще «неправильно» связаны с матерью, вы избегаете отделения и независимого взрослого существования...

ЧТО ТАКОЕ УВЕРЕННОЕ ПОВЕДЕНИЕ В МЕЖЛИЧНОСТНЫХ ОТНОШЕНИЯХ? Исторически существует три основных модели различий, существующих между...

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

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