Автоматный серпентарий

Статья в формате PDF
Статья в виде программных файлов

Данная программа представляет собой реализацию алгоритмов, описанных в статье Even, S., Litman, A., Winkler, P., Computing with Snakes in Directed Networks of Automata, Journal of Algorithms 24 (1997), 158–170.

Программа написана на языке CWEB, который Donald E. Knuth предложил в качестве реализации своей концепции грамотного программирования для языков C и C++.

Программа написана в стиле синхронного программирования. Интересно отметить, что автор сначала написал программу, а лишь затем обнаружил, что он по существу использовал синхронное программирование. На русском языке существует описание синхронного программирования.

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

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