1. Куркчи В.А. Параллельные алгоритмы для решения задач на графах.

     В данной работе представлены результаты исследования алгоритмов для нахождения максимальных независимых множеств вершин. Был рассмотрен алгоритм Брона-Кэрбоша, и произведена его модификация.

Рассматривается многоуровневый алгоритм разбиения графа и его эффективность. Приведены экспериментальные данные об эффективности данного подхода для графов с различными характеристиками.

    В работе осуществляется проектирование и разработка средства проектирования цифровых устройств (в частности управляющих автоматов) с использованием управляемой моделями архитектуры и языка моделирования UML

    Разбиение графа – NP-сложная задача, и поэтому все известные алгоритмы разбиения являются эвристическими и дают приближенный к оптимальному результат. Однако, не смотря на это ограничение, было разработано много алгоритмов разбиения графов, дающих высококачественное разбиение за малое время

    Целью данной научно-исследовательской работы является разработка программы для создания VHDL-модели цифрового автомата Мура.

 6. Силуанов А.Ф. Автоматизированное проектирование микропрограмных автоматов Мили с преобразованием объектов в базисе FPGA.

    Данная работа ставит себе целью автоматизированную разработку устройств микропрограммного управления, а именно автоматов Мили, с дальнейшей их реализацией в базисе FPGA.

 7. Костянок Т.Н. Разработка методов синтеза микропрограммных автоматов Мили с кодированием объектов

    Целью данной научно-исследовательской работы является усовершенствование и разработка новых методов синтеза микропрогрраммных автоматов Мили.

8. Санкт-Петербургский Государственный Университет информационных технологий, механики и оптики. Кафедра «Технологии программирования»

Статьи по автоматному программированию

Статьи по автоматному программированию, проектированию

 Этот пакет предлагает, сохранив автоматный подход, использовать UML-нотацию при построении моделей в рамках SWITCH-технологии.

UML и всё, что с ним связано.

Множество статей по автоматному и объектному проектированию.

13. Конечный автомат

Статья на Wiki о конечных автоматах

Статья на Wiki о конечных автоматах

Конспект лекций по дисциплине «Прикладная теория цифровых автоматов»

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

    В работе выполнен анализ недостатков, затрудняющих понимание граф-схем алгоритмов и программ, построенных на их основе. Приведена классификация граф-схем алгоритмов. Показано, что основные трудности их понимания возникают из-за умолчаний и не использования в них такого понятия как "состояние". Введение этого понятия позволяет переходить от граф-схем алгоритмов к графам переходов. Сформулированы требования к графам переходов, выполнение которых обеспечивает их "понятность".

    Известны различные методы программной и аппаратной реализаций булевых формул. В описанном в данной работе методе объединяются идеи как программных, так и аппаратных методов реализации булевых формул. При этом сначала для формулы строится линейный бинарный граф, по которому эта формула может быть программно вычислена. Граф преобразуется в схему — мультиплексорный каскад. Анализ формул, которые формируются на выходе каждого элемента каскада показывает, что при таком подходе формула реализуется не по подформулам, а по фрагментам. На основе возврата от аппаратной реализации к программной (моделируя каскад) формируется принципиально новый способ программного вычисления булевой формулы по фрагментам, которые могут не являться ее подформулами.

 19. Программная реализация управляющих автоматов

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

 20. Структурные модели и кодирование состояний автоматов

    Описываются основные структурные модели и алгоритмы кодирования состояний автоматов

 21. Алгоритмические модели автоматов

    Рассмотрены методы построения формул переходов и выходов

 22. Switch-технология

    Switch-технология — технология для поддержки автоматного программирования (технология автоматного программирования), была предложена А.А. Шалыто в 1991 году. Она охватывает спецификацию, проектирование, реализацию, отладку, документирование и сопровождение программ.

    Излагается технология алгоритмизации и программирования задач логического управления на основе теории автоматов.

    Описывается внедрение паттерна State Machine, предложенного авторами, при проектировании системы управления потоками (thread), осуществляющими асинхронные запросы к базе данных. Выполнено сравнение реализации с использованием предлагаемого паттерна с реализациями на основе флагов и SWITCH-технологии.

 25. Реализация диаграмм состояний 

    Часто при проектировании сталкиваются с ситуацией, когда поведение объекта определяется его некоторым текущим состоянием. Как правило, подобные конструкции естественно появляются при проектировании реактивных систем - событийно-управляемых систем, реагирующих на воздействия внешней среды.В этой работе исследуются принципы построения систем с выделенными состояниями, поведение которых описано при помощи диаграмм состояний (Statechart), предложенных Дэвидом Харелом.

 26. Редактор графа переходов

    Целью работы является создание приложения для редактирования графа переходов автомата, алгоритм работы которого описывается на основе автоматного подхода.

 27. Эффективный метод программной реализации дискретных управляющих автоматов во встроенных системах управления

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

 28. State Machine — новый паттерн объектно-ориентированного проектирования

    В статье предлагается новый паттерн объектно-ориентированного проектирования, названный State Machine. Этот паттерн расширяет возможности паттерна State, предназначенного для реализации объектов, поведение которых зависит от их состояния. В статье предложено использовать события для уведомления об изменении состояния. Это позволяет проектировать объекты такого рода из независимых друг от друга классов. Приведенный паттерн по сравнению с паттерном State лучше приспособлен для повторного использования входящих в него классов.

 29. Программная реализация управляющих автоматов и моделей объектов управления

 30. Операционная семантика UML диаграмм состояний в программном пакете UniMod

  В последнее время идея запускаемого UML приобретает все большую популярность. Это связано с тем, что практическое использование UML, в большинстве случаев, ограничивается моделированием статической части программы с помощью диаграммы классов. Моделирование динамических аспектов программы на языке UML затруднено в связи с отсутствием в стандарте формального однозначного описания правил интерпретации поведенческих диаграмм.

 31. Формальная семантика диаграмм состояний, удобная для практического применения  

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

 32. Организация взаимодействия в системе графов переходов

Рассматриваются различные варианты декомпозиции графа переходов

 33. Таблицы решений и графы переходов

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

 34. Сети Петри и графы операций

 35. Язык "Графсет" и графы переходов

  Наиболее известным из современных языков спецификации и программирования для решения задач логического управления является язык "Графсет"

 36. Применение граф-схем алгоритмов и графов переходов при программной реализации

 37. Модели и методы описания потоков работ

В работе рассматриваются сети Петри и теория автоматов

 38. GML: A portable Graph File Format

 39. XGMML (eXtensible Graph Markup and Modeling Language)

Спецификация вормата описания графов XGMML

 40. GXL - Graph eXchange Language

Стандарт для обмена графами в Интернет

 41. Быстрое разбиение графа для высокопроизводительных научных моделей

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

 42. Graph Partitioning Algorithms for Distributing Workloads of Parallel Computation

  Внимание уделяется алгоритмам разбиения графа, используемым для параллельного вычисления, с акцентом на проблеме распределения рабочих нагрузок для параллельных вычислений. Различные классы алгоритмов разбиения оценены качественно по скорости выполнения и качеству, создаваемых ими разделов графа.

 43. Graph partitioning - a survey

  Рассматривается проблема разбиения графов, описываются некоторые приложения и методы решения данной проблемы.