3. Формальные преобразования алгоритмов

3.1. Основные понятия. Эквивалентность алгоритмов

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

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

Можно определить сильную и слабую эквивалентность алгоритмов.

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

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

На формальном уровне понятие эквивалентности двух алгоритмов U1 и U2 будем определять следующим образом:

• для каждого алгоритма вводится понятие «входа» и «выхода»;

• для каждого входа, который имеет смысл для данного алгоритма, выполнение алгоритма может приводить к некоторому выходу.

Пусть Х1 и Х2 - входы алгоритмов U1 и U2 соответственно.

Алгоритмы U1 и U2 считаются эквивалентными, если из условия Х1=Х2 следует, что если алгоритм U1 имеет выход У1, то и другой алгоритм U2 имеет выход У2=У1.

На практике большое значение имеет определение эквивалентности с точностью до изоморфизма.

Слово «изоморфизм» происходит от греческих слов: «изо» - равный, одинаковый и «морфо» - форма.

Изоморфизм – это взаимно однозначное соответствие между двумя множествами каких-либо объектов.

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

В этом случае между некоторыми входами Х1 алгоритма U1 и входами X2 алгоритма U2 конструктивно задается некоторый изоморфизм i (в данном случае понимаемый как однозначное соответствие).

Аналогично задается некоторый изоморфизм j между выходами Y1 и Y2 алгоритма U1 и U2 соответственно.

Эквивалентность теперь будет определяться стандартным образом:

-алгоритмы U1 и U2 считаются эквивалентными, если из условия Х1ⁱ~ Х2 следует, что если хотя бы один алгоритм имеет выход Y1, то другой алгоритм имеет выход Y2, причем Y1^j~ Y2.

Разные виды эквивалентности отличаются тем, как определяются «входы» и «выходы» алгоритма, а также тем, как выбираются изоморфизмы i и j. Между различными видами эквивалентности можно ввести частичное отношение порядка, выражающиеся словами «сильнее» и «слабее».

Будем считать, что отношение эквивалентности Э1 слабее отношения эквивалентности Э2, если любые алгоритмы U1 и U2, эквивалентные в смысле Э2, эквивалентны и в смысле Э1, и в то же время есть хотя бы одна пара алгоритмов U1 и U2, таких, что U1 и U2 эквивалентны в смысле Э1 и не эквивалентны в смысле Э2.

Очевидно, чем слабее отношение эквивалентности, тем шире класс алгоритмов, эквивалентных согласно этому отношению.

С одной стороны такое расширение классов рассматриваемых алгоритмов – хорошо, однако, при слишком слабом определении эквивалентности алгоритмов проблема распознавания эквивалентности алгоритмов может оказаться неразрешимой.

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

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

На степень широты понятия эквивалентности наиболее существенно влияет выбор определения «выхода» алгоритма.

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

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

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

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

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

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

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

S-представления тех переменных, значения которых нас интересуют в качестве результатов выполнения алгоритма.

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

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

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

Такие приемы программирования, как: разбиение задачи на подзадачи;-расчленение формул; выделение промежуточных результатов; преобразование логических операторов и т.п. приводят к таким преобразованиям алгоритмов, которые сохраняют S-представления результативных переменных.

Для определения эквивалентности операторных алгоритмов рассмотрим два алгоритма - U1 и U2 из некоторого класса операторных алгоритмов.

Для каждого из алгоритмов выделим те переменные, которые нас интересуют в качестве результатов выполнения этих алгоритмов. Выделенные переменные могут быть различными у алгоритма U1 и алгоритма U2 , но число их должно быть одинаковым и между ними должно быть установлено взаимно однозначное соответствие. То же самое относится к функциональным переменным алгоритмов U1 и U2 и к параметрам этих алгоритмов, которые могут входить в S – представление.

Обозначим функциональные переменные, параметры и выделенные в качестве результатов переменные алгоритма U1 как:

X1,……,Xs , P1,…Pr,Y1,…Yn соответственно.

Соответствующие им переменные, играющие аналогичную роль в U2:

1,…s, 1,…r, 1,…n

Алгоритмы U1 и U2 эквивалентны по отношению к выделенным переменным Y1,…Yn и 1,…n, если для любого набора исходных данных 1,…s, имеет место следующее утверждение:

если какой-либо из этих алгоритмов, например, U1 имеет значение для исходных данных 1,…s и S – представления выделенных переменных имеет вид: T1(Xi11,…Xi1m1,Pj11,…Pj1l1)àY1;

T2(Xi21,…Xi2m2,Pj21,…Pj2l2)àY2;

……………………………………

Tn(Xin1,…Xinmn,Pjn1,…Pj1ln)àYn;

то другой алгоритм U2 также имеет значение для исходных данных 1,…s и S-представления выделенных переменных имеют вид:

T1(i11,… i1m1, j11,… j1l1)à 1;

T2(i21,… i2m2, j21,… j2l2)à 2;

…………………………….

Tn(in1,… inmn, jn1,… jnln)à n;

Можно также определить эквивалентность между двумя алгоритмами U1 и U2 из разных классов U1(j1,j1) и U2(j2,j2) .

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

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

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

Предлагаю ознакомиться с аналогичными статьями: