Алгоритмы и программы

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

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

3. Метод сужающих преобразований дает алгоритмы, являющиеся частными случаями решения задач, для которых имеются исходные алгоритмы.
4. Применение формального метода к нематематической проблеме, существующей в какой-либо предметной области.

Запись  проблемы на математическом языке позволяет:

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

    Комментарии:

1. Корректность алгоритмов, полученных первым методом, не вызывает сомнений, если исходные алгоритмы дают точный результат. Если же они дают приближенный результат (алгоритмы численных методов), то обоснование корректности таких алгоритмов может потребовать сложных исследований.
2. Доказательством корректности алгоритмов, полученных с помощью эквивалентных преобразований, является правильность этих преобразований.
3. Корректность алгоритмов, полученных посредством сужающих преобразований, обеспечивается проверкой того, что каждый результат, полученный таким алгоритмом, тождественен результату исходного алгоритма.
4. Корректность алгоритма, полученного в результате формализации проблемы, выясняется либо теми же способами, что и для эмпирических алгоритмов, либо:
1. оценкой адекватности полученной математической модели, т. е. возможностью получения при ее решении результата, достаточно близкого к искомому результату;
2. доказательством корректности алгоритма решения математической задачи.
5. Эвристические алгоритмы тоже требуют обоснования. Их корректность доказывается так же, как для эмпирических алгоритмов, либо согласно формальному методу.

 

    1.8 Традиционные подходы в теории алгоритмов.

    1.8.1 Рекурсивные функции.

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

    Пусть задана некоторая функция w = f(x₁, x₂, …, x _n).

    Здесь f (или знак функционала) – это правило, задающее связь функции и аргумента. Функционал f может быть любым, в том числе и алгоритмом.

    Тогда рекурсивными функциями называют частный случай вычислимых функций. Алгоритмы, являющиеся правилами задания функций, называют алгоритмами, сопутствующими рекурсивным функциям (АСФ).

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

    Базовые рекурсивные функции могут быть трех типов:

    1) Функции любого  числа независимых  переменных, тождественно равные нулю j_n()=0,где  n – число аргументов функции (n может быть равным нулю).

    Например:

    

    АСФ в данном случае гласит: если задана функция j_n ,то для любой совокупности значений аргументов значение функции равно нулю. Например,

    2) Тождественные функции  любого числа независимых  переменных Y_n,i, где n – число аргументов функции, i – номер одного из аргументов.

    АСФ гласит: если задана функция Y_n,i, то значение функции равно значению i-го  аргумента (слева направо).

    Например:

    Y_3,2(5, 8, 0)=8

    Y_1,1(6)=6

    Для тождественных функций:

    

    3) Функции следования  одного независимого  переменного l(х).

    АСФ гласит: если задана функция l(х), то значением функции нужно считать число, непосредственно следующее за числом, являющимся значением аргумента.

    При этом l(х)=х’ – последователь аргумента.

    Например:  l(5)=5’=6

    Знак  апострофа показывает на получение  последователя для x. 

    Операторы.

    1. Оператор суперпозиции (подстановки)  S. Этот оператор по заданной функции F(f₁,f₂,…,f_n) строит новую функцию Ф, такую, что для нее справедливо тождество:

    Ф= F(f₁,f₂,…,f_n), где f_i – значение некоторых функций.

    Формальная  запись оператора суперпозиции выглядит следующим образом:

    Ф::=S[ F, f₁, f₂,, …, f_n],

    где  знак ::= обозначает «равно по определению».

    Например, если функция F=l(f₁) задана как функция следования, а функция l(y)=f₁, то, согласно оператору суперпозиции, получаем некоторую функцию

    t(y)::=S[l(f₁); l(y)]

    Ее  числовое значение определяется:

    t(y)= l(l(y))= l(y’)=y’’

    t(5)=7

    2. Оператор рекурсии R. Этот оператор строит по двум функциям f1_n-1 и f2_n+1 новую функцию f_n.

    Формальная  запись:

    f::=R[f1, f2, x, (y)],

    где переменная х – главный дополнительный аргумент;

    у – вспомогательный аргумент.

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

    

    Здесь f1 ~ f1(x₁, x₂,…, x_n-1, 0 ), x=0

          i’ – последователь текущего аргумента.

    АСФ в данном случае гласит: значением получаемой функции для х=0 (главный дополнительный элемент) считать значение исходной функции f1(x₁, x₂,…, x_n ).

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

      Например, пусть f1=j₀=0 (n=0),  f2=Y_2,1(x, y)=X  (n=2), тогда некоторая новая функция Z(x)::=R[j₀,, Y_2,1(x, y); X, (y)]  удовлетворяет следующим условиям:

    

    Т. о. Z(1)=0,  Z(2)=1,  Z(3)=2 и т. д.

    3. Оператор минимизации m (оператор построения по первому нулю). Этот оператор по заданной функции, зависящей от n+1 аргументов, строит новую функцию, зависящую от n аргументов. При этом исключаемый аргумент является вспомогательным.

    Формальная  запись:   f::=m [f1; (x)] 
 
 
 
 
 
 
 

    АСФ гласит: придавать вспомогательному аргументу (х) последовательные значения, начиная с 0 до тех пор, пока не окажется, что функция f₁ становится равной нулю в первый раз, полученное значение вспомогательного аргумента х^* считать значением искомой функции f.

    Замечание: Базовые функции и функции, получаемые при помощи операторов S и R определены для любых значений аргументов, чего не следует для функций, полученных через оператор m, поскольку для многих комбинаций аргументов функции f₁ они могут быть не определены, т.к. исходная функция не обращается в ноль.

    Например:

    f₁=Y_2,1(x, y)

    r(x)::= m[Y_2,1(x, y); (y)]

    r(0)=0,  r(i)  не существует при i ¹ 0

    Пусть i=2.

    Y_2,1(2, 0)=2

    Y_2,1(2, 1)=2

    Т. о. при любых значениях у эта функция возвращает один и тот же результат.

    Вывод: Рекурсивными называются базовые функции и любые функции, полученные из них с помощью конечного числа операторов суперпозиции S,рекурсии R, минимизации m. При этом, функции, получаемые без использования оператора минимизации называются примитивно рекурсивными. Рекурсивные функции, которые определены не для всех возможных значений аргументов называют частично рекурсивными. Функции полученные с использованием операторов S, R, m называют общерекурсивными.

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

    1) y = x+1 = l(x) = x’.

    2) Y_3,3(x, y, z)=z

    Если  z^*:z®(z+1), то  f^*(x, y, z^*)::=S[Y_3,3; z+1]=z+1

    С помощью введенной функции f^* и базовой функции Y_1,1(x)=x можно определить новую функцию F(x, y) как рекурсивную функцию