Телематика'2002

Всероссийская
научно-методическая
конференция


 

 

РЕАЛИЗАЦИЯ РЕКУРСИВНЫХ АЛГОРИТМОВ АВТОМАТНЫМИ ПРОГРАММАМИ

Н.И.Туккель, А.А.Шалыто, Н.Н.Шамгунов

Санкт-Петербургский государственный институт точной механики и оптики (технический университет), Санкт-Петербург

Тел.: (812) 247-95-45, e-mail: mail@avrorasystems.com

В работе [1] был предложен формальный метод преобразования произвольного итеративного алгоритма в автоматный. При этом алгоритм задается в виде схемы алгоритма (блок-схемы), а автомат - в виде соответствующего графа переходов. Таким образом показано, что произвольный итеративный алгоритм может быть реализован программой, состоящей из одного цикла do-while, телом которого является оператор switch, реализующий указанный граф переходов.
Настоящая работы посвящена разработке методов преобразования алгоритмов с явной рекурсией в автоматные. Ввиду того, что произвольный рекурсивный алгоритм может быть преобразован в итеративный, и наоборот [2], следует, что любой рекурсивный алгоритм также может быть преобразован в автоматный и реализован программой, состоящей из одного цикла do-while, телом которого является оператор switch. При этом для раскрытия рекурсии используется стек, обеспечивающий хранение вместе с другими локальными переменными номеров состояний автомата, в которые он должен переходить при завершении очередной рекурсии. Это делает автоматы зависящими от "глубокой" предыстории, а не только от предыдущего состояния, как это имеет место в работе [1].
Одной из наиболее известных задач этого класса является задача о ханойских башнях [2-5]. Используем эту задачу для иллюстрации предлагаемых методов преобразования.
Первый из этих методов состоит в следующем:
- по тексту рекурсивной функции строится схема программы. В эту схему добавляются пустые операторные вершины, которые размещаются перед проверкой условия завершения рекурсии и после последней рекурсии;
- по этой схеме на основе метода, изложенного в [1], строится граф переходов автомата Мура;
- полученный граф формально преобразуется с учетом того, что рекурсия раскрывается с применением стека. При этом число вершин в преобразованном графе не изменяется, а дуги, исходящие из вершин, содержащих рекурсию, направляются в вершину, предшествующую проверке условия завершения рекурсии. На этих дугах указываются действия, при выполнении которых, используя операцию "push", в стек заносятся текущие значения локальных переменных и номер вершины графа, следующей за рассматриваемой;
- действия, выполняемые при завершении рекурсии, переносятся на дугу, входящую в соответствующую этим действиям вершину. В эту вершину направляется исходящая дуга из вершины следующей за последней рекурсией;
- к вершине графа, содержащей действие, выполняемое при завершении рекурсии, добавляются исходящие дуги, по каждой из которых осуществляется переход в вершину с номером, который является последним из запомненных в стеке. На этих дугах, используя операцию "pop", осуществляется также извлечение последних запомненных в стеке значений локальных переменных. Если стек пуст, выполняется переход в начальную вершину графа, что вызывает завершение работы алгоритма;
- построенный граф переходов смешанного автомата упрощается за счет устранения неустойчивых вершин. Получаемый после упрощения граф переходов содержит три вершины.
Также в работе предлагается аналогичный подход для случая, когда по схеме рекурсивной функции строится не автомат Мура, а автомат Мили.
Эти подходы напоминают изложенный в работе [6], однако являются формальными и основанными на использовании автоматов и явном выделении состояний. Эти преимущества сохраняются и относительно подхода, описанного в работе [7].
Второй метод состоит в построении итеративной программы, осуществляющей обход дерева действий, выполняемых рекурсивной программой. После этого по схеме программы, используя приведенную в [1] методику, строится граф переходов автомата с тремя состояниями.
Рассмотренные методы связаны с использованием стеков и деревьев. Поэтому применение автоматов в них не является первичным, а они строятся в результате преобразования известных вычислительных алгоритмов.
При задании алгоритма только в терминах объекта управления (дисков и стержней), как это предлагается П.Бьюнеманом и Л.Леви [8], его сразу удается описать в виде графа переходов автомата с двумя состояниями. Этот автомат по очереди выполняет всего два действия: перекладывание наименьшего диска циклически по часовой стрелке (z1) и перекладывание единственно возможного диска, кроме наименьшего (z2). После выполнения действия z1 автомат проверяет условие завершения алгоритма (x1). Текст программы, реализующий описываемый автомат, приведен ниже:
int y0 = 0 ;
void main()
{
do
switch( y0 )
{
case 0:
z1() ; y0 = 1 ;
break ;
case 1:
if( x1() ) y0 = 0 ;
else
{ z2() ; z1() ; }
break ;
}
while( y0 != 0 ) ;
}
В этой программе функции z1, z2 и x1 могут быть реализованы по-разному. Например, определение перекладываемого диска может выполняться с помощью перебора, либо аналитически, например так, как это предложено в [9].
В заключение отметим, что обычно под состоянием программы понимается значение ячеек ее памяти [10]. Однако, такое определение не конструктивно, так как практически в любой программе, реализующей вычислительный алгоритм, число указанных значений чрезвычайно велико. Решение этой проблемы основано на том, что в машине Тьюринга небольшое количество состояний в автомате может управлять произвольным количеством состояний на ленте [11]. Такая же ситуация имеет место и в рассмотренных примерах, в которых автомат, содержащий два или три состояния, управляет 2^N состояниями "объекта управления", где N - число дисков.
Несмотря на то, что при автоматном подходе длина программы может возрастать, "автоматные программы" обладают тем преимуществом, что все пути в них трассированы. При этом по тексту такой программы может быть формально построен граф переходов, который является наиболее компактной и удобной для визуализации графической формой представления программы и ее алгоритма.
Выполненная работа подтверждает положение из работы [12] о том, что "перекладывание хотя бы части труда с головы на методику эффективно повышает возможности мозга".
Литература
1. Шалыто А.А., Туккель Н.И. Реализация вычислительных алгоритмов на основе автоматного подхода //Телекоммуникации и информатизация образования. 2001. ╧6.
2. Седжвик Р. Фундаментальные алгоритмы на С++. Киев: ДиаСофт, 2001.
3. Грэхем Р., Кнут Д., Поташник О. Конкретная математика. М.: Мир, 1998.
4. Романовский И.В., Столяр С.Е. Стек и его использование. http://ips.ifmo.ru.
5. Гарднер М. Математические головоломки и развлечения. М.: Мир, 1971.
6. Стивенс Р. Delphi. Готовые алгоритмы. М.: ДМК, 2001.
7. Ахо А., Хопкрофт Д., Ульман Д. Структуры данных и алгоритмы. М.: Вильямс, 2000.
8. Анисимов А.В. Информатика. Творчество. Рекурсия. Киев: Наукова думка, 1988.
9. http://doors.infor.ru/allsrs/alg/paper/hanoy.html
10. Буч Г. Объектно-ориентированный анализ и проектирование с примерами приложений на С++. М.: Бином, СПб.: Невский диалект, 1998.
11. Шалыто А.А., Туккель Н.И. От тьюрингова программирования к автоматному //Мир ПК. 2002. ╧2.
12. Штыков Е., Бакиров М., Шамгунов Н. и др. Как стать чемпионом мира по программированию или разбор полетов //Всероссийская командная олимпиада школьников по программированию. СПб.: СПбГИТМО (ТУ), 2000.

 


Санкт-Петербург, 3 - 6 июня 2002 года,
Всероссийская научно-методическая конференция "Телематика'2002"