Все предыдущее изложение было посвящено интерактивным и реактивным системам (см. параграф 1.1). Однако во введении было упомянуто, что автоматы, по мнению авторов, целесообразно использовать во всех классах программных систем. В этом разделе поговорим о применении автоматов в трансформирующих системах, а более конкретно — в задачах дискретной математики. Здесь автоматы могут использоваться как непосредственно при построении некоторых алгоритмов (например, поиск подстрок), так и для визуализации алгоритмов, реализованных традиционным способом. Методы преобразования традиционных алгоритмов в автоматные описаны в работах Отметим, что в трансформирующих системах чаще всего применяются активные автоматы без событий. При построении алгоритмов дискретной математики наибольшее внимание, как правило, уделяется эффективности по времени и по памяти, и автоматы в этом вряд ли могут помочь. Однако автоматные алгоритмы часто являются более структурированными, а их представление с использованием диаграмм переходов — более наглядным. Эти свойства приобретают особенно большое значение при обучении дискретной математике. В качестве примера использования автоматного подхода при построении алгоритма рассмотрим одну из задач дискретной математики: обход двоичных деревьев. Автоматное решение этой задачи, которое рассматривается ниже, заимствовано из работы [79]. Исходным данным в задаче является двоичное дерево, вершины которого пронумерованы (пример такого дерева приведен на рис. 4.1).Требуется осуществить обход дерева — сформировать последовательность номеров его вершин. При обходе дерева в глубину используются три стандартных порядка обхода: прямой ( preorder), обратный ( postorder) и центрированный (inorder) [76, 80]. В качестве примера приведем последовательности, порождаемые обходами дерева, которое представлено на рис. 4.1:прямой обход: 0, 1, 3, 4, 5, 6, 2, 7, 8, 9; центрированный обход: 3, 4, 1, 6, 5, 0, 8, 7, 9, 2;обратный обход: 4, 3, 6, 5, 1, 8, 9, 7, 2, 0.
Известно несколько классических решений этой задачи: рекурсивное [76, 80], итеративное с применением стека и итеративное без использования стека. Рекурсивное решение является наиболее простым и понятным: в нем процедура обхода дерева вызывает саму себя для левого и правого поддерева. Однако как и все рекурсивные алгоритмы, это решение обладает сравнительно низким быстродействием. Итеративный алгоритм без использования стека предполагает хранение в каждой вершине дерева информации о родительском узле. Такая структура хранения избыточна. Наиболее реалистичным является алгоритм с применением стека, однако он же является и наиболее сложным. Рассмотрим автоматную модификацию этого алгоритма, которая, как сможет убедиться читатель, является не только наглядной, но и эффективной. Будем считать, что в каждой вершине дерева содержится ее номер и указатели на левую и правую дочерние вершины. На языке программирования C++ эту структуру можно представить следующим образом: Идея предлагаемого алгоритма состоит в том, что при обходе двоичного дерева могут быть выделены три направления движения: влево, вправо и вверх. В зависимости от текущего направления движения, свойств текущей вершины и верхнего символа в стеке можно определить, куда двигаться дальше. Поэтому удобно сопоставить каждому направлению движения управляющее состояние автомата. Схема связей автомата, осуществляющего обход двоичных деревьев, приведена на рис. 4.2, а его диаграмма переходов — на рис. 4.3. На диаграмме переходов действие z1 следует поместить в одно из трех состояний в зависимости от требуемого порядка обхода: для прямого порядка обхода — в состояние «Влево»;
для центрированного — в состояние «Вправо»; для обратного — в состояние «Вверх». Отметим, что в графе переходов легко выделить общую часть, которая не зависит от порядка обхода. Таким образом, предложенная реализация является довольно универсальной. Рассмотрим вкратце применение автоматов для построения визуализаторов алгоритмов дискретной математики. Визуализатор — это программа, в процессе работы которой на экране компьютера динамически демонстрируется применение алгоритма к выбранному набору данных. Визуализаторы позволяют изучать работу алгоритмов как в автоматическом, так и в пошаговом режиме, аналогичном режиму трассировки программ. Визуализация шагов алгоритма сопровождается текстовыми комментариями. Автоматный подход оказался очень удобным при создании визуализаторов алгоритмов дискретной математики для описания логики их работы. Введение в «поточные» алгоритмы состояний значительно упрощает проектирование визуализаторов, позволяя выделить в алгоритме значимые для наблюдателя точки, в которых и следует осуществлять визуализацию. На основе автоматного подхода были разработаны метод ручного проектирования визуализаторов , а также технология автоматизированного построения визуализаторов Vizi и инструментальное средство с тем же названием, поддерживающее эту технологию Примеры визуализаторов, построенных с применением автоматного подхода, и проектная документация к ним опубликованы в сети Интернет