Эквивалентность логических схем (конспект)

Проблемы эквивалентности и распознавания принадлежности к некоторому классу алгоритмов в своей полной подстановке являются алгоритмически неразрешимыми проблемами. До сих пор их решали только для некоторых видов алгоритмических систем при довольно узком определении эквивалентности. Основные результаты относятся к операторным схемам. В качестве характерных черт операторных схем можно выделить следующие черты:-совокупность операторов, образующих схему алгоритма, изображается явно; -для каждого оператора явно указываются его приемники и предшественники по выполнению, а также его аргументы и результаты; -при построении реализации приемник оператора обычно выбирается без учета истории движения к этому оператору; -если в рассмотрение вовлекается некоторая величина, "вырабатывается" некоторым оператором, то она трактуется как независимая переменная, то есть считается, что после выполнения данного оператора она может принимать любое значение независимо от предыдущей истории; -если аргументом или результатом оператора оказывается компонента массива, указанная индексом, то значение индекса обычно игнорируется и считается, что аргументом и результатом оператора является весь массив. Первой работой, посвященной общей теории преобразования алгоритмов, явилась работа Ю. И. Янова "О логических схемах алгоритмов". В ней были сформулированы основные компоненты теории преобразования алгоритмов, а именно:-формализация понятия схемы алгоритма; -задание отношения эквивалентности; -определение алгоритма, распознающего эквивалентность схем; -построение системы преобразований, полной в том смысле, что любую пару эквивалентных алгоритмов можно трансформировать один в другой последовательным применением этих преобразований, сохраняющих эквивалентность. Всякий алгоритм при переработке конкретного объекта предписывает однозначно определенную последовательность элементарных действий. Такая последовательность, вообще говоря, различна для различных объектов, к которым данный алгоритм может быть применен. Однако всегда найдется конечное множество предикатов, характеризующих некоторые свойства перерабатываемых объектов, такое, что для данного алгоритма зависимость порядка выполнения элементарных действий от перерабатываемых объектов будет однозначной функцией этих предикатов. Такая функция может быть записана при помощи конечной строки, составленной из символов элементарных действий А1, A2, ..., An (называемых операторами), предикатов и некоторых вспомогательных символов: [i; i] (i=1.2 ...), называемых соответственно левой и правой полускобками. Строка А1 А2 А3 ... Аs означает, что последовательно должны быть выполнены операторы А1, А2, А3, ..., Аs. Строка А1 р[iA2 ... i]A3, где р - некоторый предикат, означает, что после выполнения оператора А1 в случае р=1 должен быть выполнен оператор А2, стоящий непосредственно правее р[i, а если р=0, то оператор А3, стоящий справа от полускобки i]. Строки такого вида называются схемными записями алгоритмов. Один и тот же алгоритм при фиксированном множестве элементарных операций и предикатов может иметь различные логические схемы.