АЛГОРИТМОВ РАВНОСИЛЬНЫЕ ПРЕОБРАЗОВАНИЯ

— формальные преобразования, позволяющие преобразовать заданный алгоритм в алгоритм, эквивалентный в расширенном смысле заданному. При этом под эквивалентностью в расширенном смысле понимают свойство алгоритмов перерабатывать эквивалентные исходные данные в эквивалентные реаультаты. Сущность эквивалентности исходных данных и, соответственно, результатов определяется конкретно для каждого класса алгоритмов. Обычно исходные данные (результаты) двух алгоритмов считаются эквивалентными, если с помощью некоторого достаточно простого приема эти данные можно преобразовать друг в друга. Графическое тождество исходных данных является частным случаем их эквивалентности, а алгоритмов вквивалентность — частным случаем равносильности алгоритмов. При А. р. п. каждый преобразуемый алгоритм рассматривают в совокупности с областью его задания, которая может составлять лишь часть области его применимости (т. е. в совокупности с допустимыми исходными данными задачи). Это приводит к тому, что равносильные алгоритмы (эквивалентные в расширенном смысле), исходные данные и результаты которых соответственно совпадают, могут все же не быть эквивалентными (напр., в случае несовпадения области их применимости).

А. р. п. являются наиболее важным приемом, используемым при программировании и осуществляемым, как правило, на содержательном уровне, а не формальным путем. Существуют три этапа в работе по программированию: описание, получение и преобразование алгоритма. Этап описания задачи на входном языке программирования не формализован и производится составителем программы на основе его опыта и интуиции. Следующим этапом является внесение улучшений в полученный алгоритм в рамках избранного входного языка (на практике эти этапы обычно перемежаются). Третьим, последним, этапом являются равносильные преобразования полученного алгоритма в программу (т. е. в алгоритм на языке машинном), что осуществляется формально самой ЭВМ с помощью спец. программы, наз. транслятором. Таким образом, при программировании используются А. р. п., связанные с изменением языков и производимые без изменения языков (в дальнейшем, говоря об А. р. п., имеют в виду только преобразования, производимые без изменения языков).

Первые исследования в области А. р. п. производились применительно к алгоритмам, заданным на языке логических схем (ЯЛС), который, собственно, и возник как язык описания дискретных процессов (в частности, как входной язык программирования), удобный для А. р. п. Затем изучались А. р. п. при использовании адресного языка программирования. Отдельные вопросы А. р. п. разрабатывались при создании трансляторов. При создании программ информационно-поисковых систем были разработаны некоторые приемы А. р. п., позволившие предусматривать автоматические равносильные преобразования отдельных частей программ для ускорения процесса поиска информации. Целесообразность такого приема обусловлена тем обстоятельством, что наилучший вид программ поиска не всегда можно определить заранее, из-за изменяемости массива информации, в котором производится поиск.

Точное определение понятия А. р. п. зависит от языков, на которых формально описываются алгоритмы, исходные данные к ним и их результаты, т. к. лежащие в основе понятия эквивалентности исходных данных (результатов) простые приемы их преобразования друг в друга связаны с особенностями этих языков. При А. р. п. в случае ЯЛС, исходными данными и результатами являются т. н. состояния памяти, которые записываются в виде последовательностей равенств вида , где — число ячеек памяти, занятых информацией, названия ячеек, — их состояния (содержащаяся в ячейках информация), а знак равенства употребляется в смысле «имеет значение». Для такой формы исходных данных и результатов вполне естественно весьма простыми считать следующие приемы: переименование ячеек (в частности, тождественное переименование, т. е. сохранение их названий); включение в исходные данные ячеек, не используемых в преобразуемом алгоритме; удаление из исходных данных таких фиктивных ячеек; совмещение ячеек, если заранее известно, что в любом варианте исходных данных (результатов) состояния этих ячеек тождественны между собой; включение в исходные данные или результаты ячеек, состояния которых при любом варианте тождественны с состояниями уже имеющихся ячеек. В ЯЛС эквивалентные преобразования входят в понятие А. р. п. Расширение понятия эквивалентности алгоритмов, связанное с описанным выше пониманием эквивалентности исходных данных (и результатов), а также с тем, что рассматриваются не области применимости, а более узкие области задания алгоритмов, значительно расширяет возможности А. р. п. по сравнению с возможностями их эквивалентных преобразований.

Алгоритмы, заданные на ЯЛС, обычно подвергаются А. р. п. с целью экономии расхода времени на их выполнение (а, следовательно, и машинного времени) или экономии необходимых объемов запоминающих устройств.

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

Алгоритм на ЯЛС задают в виде конечной строки, образованной из операторов (описывающих действия) и знаков перехода (позволяющих при выполнении алгоритма определить порядок выполнения операторов). А. р. п. в случае применения ЯЛС делят на следующие группы: 1) равносильные преобразования отдельных операторов; 2) А. р. п., не вызывающие внутренних изменений операторов (преобразования логических схем алгоритмов); 3) А. р. п., связанные с преобразованиями логических операторов; 4) А. р. п., связанные с преобразованиями нелогических операторов; 5) перестановка операторов; 6) А. р. п., учитывающие подчиненность операторов условиям (оператор подчинен некоторому условию, если его выполнение возможно тогда, когда утверждение, содержащееся в условии, является истинным).

Описанная система А. р. п. полная для прямых или спрямляемых алгоритмов в том смысле, что коль скоро два такие алгоритма эквивалентны в расширенном смысле, то с помощью конечного числа А. р. п. любой из них можно преобразовать в другой. При этом алгоритмы, заданные на ЯЛС, наз. спрямляемыми, если с помощью конечного числа преобразований их можно свести к прямым, т. е. к алгоритмам, при выполнении которых после работы к.-л. оператора не может работать ни один оператор, расположенный в строке левее от него. Вопрос о полноте системы А. р. п. для любых алгоритмов, заданных на ЯЛС, не решен. Проблема определения равносильности (эквивалентности в расширенном смысле) алгоритмов, заданных на ЯЛС, эквивалентна широко известной проблеме тождества и, следовательно, относится к неразрешимым алгоритмическим проблемам.

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

, которая эквивалентна записи на адресном языке являющейся частным случаем записи элементарного оператора ). Последнее обстоятельство приводит к тому, что систему А. р. п., разработанную для алгоритмов, заданных на ЯЛС, непосредственно нельзя переносить на алгоритмы адресного языка, так что разработка А. р. п. для адресного языка явилась самостоятельной проблемой.

Область приложений А. р. п. не ограничивается программированием. А. р. п. являются ценным аппаратом при практической алгоритмизации, напр., творческих процессов (см. Алгоритмизация творческих процессов). В ряде случаев в результате анализа реальных процессов (напр., процессов управления) их удается описать в виде сложных алгоритмов, выполнить которые практически невозможно. Только после А. р. п. удается получить из них алгоритмы, пригодные для использования. На практике приходится иметь дело с направленными А. р. п., преследующими цель оптимизации алгоритма по к.-л. заданному критерию. Разработка алгоритмов направленного применения А. р. п. представляет группу важнейших математических проблем кибернетики. Результаты, полученные в этой области, еще незначительны (напр., к ним относится направленное применение А. р. п. при поиске информации, выполняемое самой ЭВМ, и некоторые др.). Однако и там, где алгоритмы направленных преобразований еще не найдены, направленные А. р. п. можно производить, правда не самими ЭВМ в автомат, режиме, а с участием людей. Поиск необходимой последовательности А. р. п. можно осуществлять эвристическими методами (по интуиции, догадкам и пробам) с помощью ЭВМ, которая по спец. программам и приказам, вводимым в нее математиком, должна производить трудоемкие преобразования введенного в ее память алгоритма и выдавать информацию о получаемых результатах.

Лит.: Поршнева В. Н. Об эквивалентных преобразованиях адресных комплексов. В кн.: Цифровая вычислительная техника и программирование, в. 2. М., 1967; Криницкий Н. А. Равносильные преобразования алгоритмов и программирование. М., 1970. Н. А. Критщкий.