Лекция 2. О понятии алгоритма. Декларативный подход о формализации понятия алгоритма.

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

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

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

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

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

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

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

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

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

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

y = A(x),

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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