От операторного метода А.А. Ляпунова — к теории алгебраических моделей программ

Подловченко Р.И.

Тема доклада подсказана тем, что в этом году исполняется 100 лет со дня рождения Алексея Андреевича Ляпунова и 80 лет со дня рождения Андрея Петровича Ершова. А. А. Ляпунов является основоположником отечественной кибернетики и программирования как самостоятельного научного направления. Его ученик А. П. Ершов в течение нескольких десятилетий был лидером программирования в нашей стране. История моделирования последовательных программ началась с создания А. А. Ляпуновым операторного метода программирования и активно поддерживалась работами А. П. Ершова. Концепции, на которых базируется операторный метод, послужили основанием теории алгебраических моделей программ. Это побуждает уделить ей основное внимание в докладе.

Краткий экскурс в историю

Официальное признание заслуг А. А. Ляпунова в отечественной науке произошло в 1964 году присвоением ему звания члена-корреспондента Академии Наук СССР. Международное признание заслуг А. А. Ляпунова выразилось в присуждении ему в 1996 году медали Computer Pioneer одной из самых авторитетных профессиональных организаций в сфере высоких технологий – IEEE Computer Society. Медаль А. А. Ляпунову украшает надпись: «Компьютерное общество признало А. А. Ляпунова основателем советской кибернетики и программирования». В программировании А.А. Ляпуновым заложены его основы – создан операторный метод. Концепции операторного метода формировались в процессе чтения А. А. Ляпуновым лекционного курса « Принципы программирования» для студентов механико-математического факультета МГУ. Это состоялось в 1952-53 учебном году. Из слушателей этого курса выросли первые составители отечественных трансляторов – А. П. Ершов, Э.З. Любимский и многие видные представители программирования. Сам лекционный курс был опубликован только в 1958 году в достаточно урезанном виде [4].

В операторном методе А.А. Ляпунов исходил из необходимости нового подхода к определению алгоритма: традиционные модели теории алгоритмов (машины Тьюринга, продукции Поста, нормальные алгоритмы Маркова, исчисление Чёрча-Клини) хороши для исследования природы вычисления, но непригодны для описания алгоритмов в форме, удобной для решения практических задач.

Операторный метод базируется на следующих концепциях:

• Ввести новое понятие алгоритма-программы как объекта математической модели вычислений.
• Изучать для таких алгоритмов проблему эквивалентности и проблему эквивалентных преобразований, обращаясь к схемам алгоритмов, игнорирующим некоторые особенности самих алгоритмов-программ; иными словами – создать другую математическую модель вычислений, объектами которой являются схемы программ.

Отметим, что проблема эквивалентности в математической модели вычислений состоит в поиске алгоритма, который распознаёт эквивалентность объектов модели, а проблема эквивалентных преобразований – в построении такой их системы, в рамках которой, какими бы ни были два эквивалентных объекта модели, любой из них трансформируем в другой (такая система эквивалентных преобразований называется полной в модели).

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

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

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

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

Операторный метод содержит лишь неформальные определения программы и её схемы. Формализация понятия схемы была выполнена Ю.И. Яновым, в ту пору являвшимся аспирантом А.А. Ляпунова, и вошла в теорию схем программ под названием схем Янова. Последние, в сущности, являются схемами Ляпунова-Янова. Разрешимость для них проблемы эквивалентности и проблемы эквивалентных преобразований, установленная Ю.И. Яновым (см. [10]), стала первым результатом в теории схем программ. Следует отметить, что этот результат оставался почти незамеченным программистами десяток лет. Внимание к нему появилось благодаря его интерпретации, выполненной А. П. Ершовым [2]. Немалую роль здесь сыграло введённое А. П. Ершовым описание схемы в виде конечного ориентированного графа с размеченными вершинами и дугами.

Концепции операторного метода положены в основу теории алгебраических моделей программ. В этой теории

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

Несомненной привлекательностью теории алгебраических моделей программ является то обстоятельство, что она вобрала в себя результаты, полученные для дискретных преобразователей Глушкова-Летичевского и для схем программ со структурированной памятью (стандартных схем, в терминологии А.П. Ершова).

Обратимся к тому, как концепции операторного метода реализуются в теории алгебраических моделей программ. В ней формализованные программы строятся над двумя конечными алфавитами Y и Р. Элементы алфавита Y называются операторными символами, а элементы алфавита Р – логическими переменными (они принимают значения 0 и 1). Структура программы поясняется рисунком 1; здесь полыми кружочками изображены вход и выход программы, прямоугольниками – преобразователи с приписанными им операторными символами, овалами – распознаватели с приписанными им логическими переменными.

Семантика программы индуцируется семантикой σ базиса Y, Р; последняя состоит в выборе предметного множества (его элементы именуются состояниями), в приписывании каждому символу из Y отображения этого множества в себя и в приписывании каждой переменной из Р отображения множества состояний в множество (0,1).

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

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

Перейдём теперь к описанию алгебраических моделей программ. Они введены в [5] и составляют семейство, в котором все они для выбранного базиса операторных символов и логических переменных имеют общим множество объектов, называемых схемами программ, и отличаются друг от друга отношением эквивалентности схем программ. Синтаксически схема программы над базисом Y, Р совпадает с программой над тем же базисом. Таким образом, всякое преобразование структуры схемы программы является преобразованием структуры самой программы. Семантика схемы программы состоит в приписывании ей частичного отображения множества Y* в себя. Последнее осуществляется универсальной процедурой выполнения схемы на функции разметки, определяемой как отображение Y* в множество Х, где Х = { x | x: Р → { 0,1 }. Элементы множества Y* называются операторными цепочками, а элементы множества Х – наборами значений логических переменных.

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

Эквивалентность схем над базисом Y, Р индуцируется двумя параметрами:

• эквивалентностью ν в Y*;
• подмножеством L функций разметки

и называется (ν, L) – эквивалентностью.

Множество схем над базисом Y, Р с введённой в нём отношением (ν, L) – эквивалентности схем называется (ν, L) – моделью. (ν, L) – модель называется аппроксимирующей, если существует такой σ-класс программ, что из эквивалентности схем всегда следует эквивалентность программ той же структуры, что и схемы. Таким образом, алгоритм, распознающий эквивалентность схем в аппроксимирующей модели, частично распознаёт эквивалентность программ в аппроксимируемом классе программ. Получен достаточный признак того, что (v, L) – модель является аппроксимирующей, и рассматриваются только модели, ему удовлетворяющие.

В теории алгебраических моделей программ установлено, что для любой модели дискретных преобразователей, введённой в [1], существует равносильная ей алгебраическая модель. Этим в данную теорию вносятся все результаты по проблеме эквивалентности, полученные для дискретных преобразователей. Отметим, что положительные результаты для них получены методикой, предложенной А.А. Летичевским в [1] и состоящей в рекурсивном устранении несущественных ветвлений с целью приведения пары параллельных дискретных преобразователей к общему виду; поэтому алгоритмы, разрешающие эквивалентность, экспоненциальны по сложности. Вместе с тем, этими результатами очерчена область для поиска разрешающих алгоритмов приемлемой сложности в теории алгебраических моделей программ.

Установлено, что и для любой модели, объектами которой являются схемы программ со структурированной памятью, существует равносильная ей алгебраическая модель программ. Этим теория последних пополняется различными фактами, в частности, выявляются модели конечных автоматов-ацепторов, равносильные алгебраическим моделям программ [11]. Новым направлением исследований в теории алгебраических моделей программ является разработка методик распознавания эквивалентности с полиномиальной сложностью, т.е. построение алгоритмов, приемлемых в практическом программировании. К настоящему времени разработаны три методики; они основаны на

• сведении проблемы эквивалентности к проблеме решения уравнений в специальных полугруппах [3];
• применимости техники следов [7];
• сведении проблемы эквивалентности к проблеме пустоты для обобщённых двухленточных автоматов [12].

Установлена результативность каждой из этих техник.

В [8] разработана методика построения систем эквивалентных преобразований, полных в алгебраических моделях программ и продемонстрированы результаты её применения. Изложенное выше говорит об активном развитии теории алгебраических моделей программ. Отметим, что результаты теории находят применение при решении таких актуальных задач, как защита программ от несанкционированного их использования и как выявление в программах «вирусов».

Список литературы

1. Глушков В.М., Летичевский А.А. Теория дискретных преобразователей // Избранные вопросы алгебры и логики. – Новосибирск: Наука. 1973. – С.5-39.
2. Ершов А.П. Об операторных схемах Янова // Проблемы кибернетики. Вып.27. – М: Наука. 1973. – С.87-110.
3. Захаров В.А. Быстрые алгоритмы разрешения эквивалентности операторных программ на уравновешенных шкалах // Математические вопросы кибернетики. Вып.7. 1998. – С.303-324.
4. Ляпунов А.А. О логических схемах программ // Проблемы кибернетики. Вып.1.- М: Физматгиз. 1958. – С.46-74.
5. Подловченко Р.И. Иерархия моделей программ // Программирование. – 1981. -№2. – С.3-14.
6. Подловченко Р.И. , Захаров В.А. Полиномиальный по сложности алгоритм, распознающий коммутативную эквивалентность схем программ // Докл. РАН. Информатика. – 1998. – Т.362, №6. – С.744-747.
7. Подловченко Р.И. Техника следов в разрешении проблемы эквивалентности в алгебраических моделях программ // Кибернетика и системный анализ. – Киев. – 2009, №5.

Об авторе: Московский государственный университет им. М.В. Ломоносова
podlovchenko.rimma@gmail.com

Материалы международной конференции SORUCOM 2011 (12–16 сентября 2011 года)
Статья помещена в музей 05.08.2013 с разрешения автора