УНИВЕРСИТЕТ ИТМО
Кафедра «Технологии программирования»



Главная

Новости
 Новости науки
 Важное
 Почетные доктора
 Инновации
 Культура
 Люди
 Разное
 Скартел-Yota
 Стрим
 Смольный
Учебный процесс
 Образование
 Дипломы
 Курсовые проекты
 Лабораторные работы
 Учебные курсы
 Визуализаторы
 Unimod-проекты
 Семинары
 Стипендии
Наука
 События и факты
 Госконтракты
 Статьи
 Диссертации
 Книги
 Презентации
 Свидетельства
 Сотрудничество
Исследования
 Автоматы
 Верификация
 Геном
 Искусственный интеллект
 Генетические алгоритмы
 Движение
 UniMod
 Роботы и агенты
 Нейронные сети
 ФЦП ИТМО-Аалто
 Разное

О нас
 Премии
 Сертификаты и дипломы
 Соревнования по программированию
 Прорыв
 Автографы
 Рецензии

Беллетристика
 Мотивация
 Мысли
Медиа
 Видео
 Фотографии
 Аудио
 Интервью

English
 Home

 Articles
 Posters
 Automata-Based Programming
 Initiatives
 Projects
 Presentations
 UniMod
 UniMod Projects
 Visualizers


Поиск по сайту

Яndex



   Главная / Статьи / Автоматный серпентарий (версия для печати)


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





Д. Павлов

Статья в формате 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++.

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

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

  • передать заданное сообщение всем узлам;
  • построить ориентированное остовное дерево, в котором рёбра идут к корню или от корня;
  • выполнить на получившемся дереве поиск в глубину;
  • передать сообщение от одного узла к другому;
  • синхронизировать узлы (заставить их одновременно выполнить некоторое действие).
© 2006 Дмитрий Павлов. SMTP: pavlov at this host



© 2002—2017 По техническим вопросам сайта: vl.ulyantsev@gmail.com