Автоматное программирование

История развития программного обеспечения

Шалыто А.А.

Введение

Под «автоматным программированием в малом» будем понимать программную реализацию конечных автоматов, как с памятью, так и без памяти, а под «автоматным программированием в большом» или просто «автоматным программированием» – программирование с использованием конечных автоматов для описания поведения программ.

1. Автоматное программирование в малом

1.1. Нетрадиционные методы вычисления булевых функций

1.1.1. Использование спектрального метода

Существуют различные методы программной реализации булевых функций (БФ), примеры использования которых приведены в приложениях к работе [1].

Среди этих методов весьма интересно вычисление БФ при помощи разложения в ортогональные ряды [2, 3]. Такой подход позволяет с единых позиций производить обработку данных и вычислять БФ.

Этот и ряд других нетрадиционных методов вычисления БФ рассмотрен в работе [4].

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

Среди нетрадиционных методов вычисления БФ весьма интересны методы реализации систем БФ (СБФ) арифметическими полиномами. При этом в рассматриваемых ниже работах было установлено, что преобразования в этой области являются разновидностью дискретного преобразования Фурье. Это, в частности, позволяет эффективно проводить параллельные вычисления СБФ.

Известно [5], что произвольная БФ представима полиномом Жегалкина. В работе [6] было показано, что прямое и обратное матричные преобразования полиномов Жегалкина выполнимы и являются одной из разновидностей прямого и обратного дискретных преобразований Фурье, причем базисы этих преобразований для указанных полиномов совпадают.

Однако значительно больший интерес для практического использования связан с совместной реализацией СБФ, что выполнять с применением полиномов Жегалкина обычно нецелесообразно, а в матричной форме и невозможно.

Для эффективного решения задачи совместной реализации СБФ в работе [7] было предложено использовать арифметические полиномы и было показано как применять алгебраические преобразования для построения арифметического полинома по системе булевых формул, заданной в базисе И, ИЛИ, НЕ. При использовании этого подхода путём вычисления арифметического полинома на заданном битовом входном наборе определяется десятичное число, в двоичном представлении которого каждый разряд соответствует значению одной из реализуемых БФ на указанном наборе. Арифметические полиномы, обладающие указанным свойством, названы в работе [4] безызбыточными.

В работе [8], принятой к печати в 1986 г. (это существенно в части приоритета), были предложены прямое и обратное матричные преобразования между системами булевых функций и арифметическими полиномами, которые также являются разновидностями прямого и обратного дискретного преобразования Фурье. При этом базис прямого преобразования совпадает с базисом преобразований для полиномов Жегалкина, а базис обратного отличается только знаком одного элемента в базисной матрице. Такие же результаты независимо и в то же время (1986 г.) были получены в работе [9], что и было отмечено в заключении работы [8].

В работе [8] также были определены условия представимости СБФ линейным арифметическим полином – условия линейности.

В работе [10] были предложены канонические алгоритмические структуры, обеспечивающие реализацию СБФ линейными арифметическими полиномами. Найдены матричные соотношения для вычисления коэффициентов линейных полиномов, входящих в состав указанных структур. Определены условия линейности различных порядков, при выполнении которых канонические структуры могут быть упрощены.

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

В работе [11] были предложены эффективные методы реализации пороговых, порогово-линейных и линейных БФ одним линейным арифметическим полиномом с маскированием. Такие БФ были названы линейно представимыми. Рассмотрен вопрос о реализации систем симметрических функций линейными арифметическими полиномами.

В работе [12] был разработан метод реализации систем линейно представимых булевых функций одним линейным арифметическим полиномом с маскированиями. В работе [13] этот результат был оценен следующим образом: «Этот фундаментальный результат, в частности, может быть использован для моделирования методами арифметической логики нейронных сетей, в которых каждому слою нейронной сети может быть поставлен в соответствие линейный арифметический полином».

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

Работы отечественных авторов по рассматриваемой тематике (включая монографии [13–16]) носили пионерский характер и заложили основы нового научного направления, которое основывается на арифметических аспектах двоичной логики. Это было подтверждено в специальном выпуске журнала «Автоматика и телемеханика». 2004. № 6, составителями которого являлись В.П. Шмерко и С.Н. Янушкевич, работавшие тогда в Университете города Калгари (Канада).

1.1.3. Реализация булевых формул и булевых функций бинарными графами

1.1.3.1. Реализация булевых формул в базисе И, ИЛИ, НЕ линейными бинарными графами

Среди методов вычисления БФ, рассмотренных в работе [4], одним из наиболее важных для теории является метод реализации булевых формул (БФЛ) в базисе И, ИЛИ, НЕ линейными бинарными графами.

В работе [17] было показано, что произвольная нормальная БФЛ (в дальнейшем булева формула) в базисе И, ИЛИ, НЕ из h букв может быть реализована бинарным графом, содержащим h+2 вершины (h – условных и две – операторные: f=0 и f=1).

Из того факта, что число вершин в бинарном графе определяется числом букв в БФЛ, следует, что для уменьшения числа вершин в графе необходимо минимизировать число букв в формуле. Это может быть выполнено с помощью классических методов минимизации. Таким образом, эти методы, предложенные в 50-х годах для минимизации релейно-контактных схем, могут применяться и для упрощения программ, реализующих бинарные графы, которые в работе [17] названы бинарными программами.

При использовании подхода, изложенного в работе [4], реализация повторной в указанном базисе БФЛ сводится к построению бинарного графа для PN-однотипной с ней бесповторной БФЛ с последующей заменой обозначений переменных.

В работе [18] для бесповторных БФЛ был предложен метод построения плоскостных бинарных графов, для реализации которых бинарными программами с одноадресными условными переходами эти графы приходилось линеаризовать, что весьма трудоёмко.

В работах [17, 19] предложен метод непосредственного построения линейного бинарного графа по бесповторной БФЛ, который в работе [17] был назван формульным. Однако этот метод не обеспечивал планарности линейного бинарного графа для произвольной бесповторной БФЛ. Указанный метод был предложен в работах [20-22].

Правильность построения линейного бинарного графа может быть проверена различными методами. Наиболее интересный из них состоит в восстановлении БФЛ по линейному бинарному графу [23, 24]. При этом каждая условная вершина в линейном бинарном графе заменяется мультиплексором «2 в 1» с целью получения изоморфной схемы, в которой на выходе каждого элемента может быть записана формула. Ошибка в линейном бинарном графе может быть обнаружена, как только фрагмент формулы, получающийся при «чтении» схемы от входов к выходу, будет отличаться от соответствующего фрагмента заданной формулы.

При использовании этого метода восстановление бесповторной булевой формулы осуществляется не по подформулам, как это делается обычно, а по фрагментам формулы, несмотря на наличие в ней, в общем случае, скобок произвольной глубины. Это свойство было установлено в работе [23]. Оно, в частности, позволяет более эффективно, чем с помощью известных методов, вычислять БФЛ рассматриваемого класса [4].

Ещё один метод проверки правильности построения линейного бинарного графа состоит в применении тестов. В качестве тестов в работе [4] было предложено использовать все пути в графе, рассматривая его в обратном порядке, которые можно перечислить по реализуемой формуле. При этом ортогональная дизъюнктивная нормальная форма (ОДНФ) булевой формулы перечисляет все единичные (до единичной операторной вершины) пути в графе, а ОДНФ инверсии БФЛ – все нулевые пути [21]. Единичные и нулевые пути покрывают без пересечения (в силу ортогональности путей в графах рассматриваемого типа) все компоненты столбца значений таблицы истинности, построенной по реализуемой формуле, и поэтому меньшего числа тестов, чем все пути для восстановления столбца значений соответствующей таблицы истинности, не существует [4].

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

Для этого необходимо разложить по Шеннону [25] слева направо последовательно по всем переменным формулу и все её остаточные. Основная особенность этого метода состоит в том, что подформулы, получаемые в результате разложения, которые умножаются на ноль, не уничтожаются. В получаемой в результате полного разложения формуле раскрываются скобки. Пометка конъюнкции нулем (единицей) свидетельствует о принадлежности её ОДНФ инверсной (прямой) формулы или о том, что этой конъюнкции соответствует нулевой (единичный) путь в графе [4] .

Для подсчёта числа путей в линейных бинарных графах в работах [4, 21] были предложены два метода, которые значительно менее трудоёмки по сравнению с классическими методами, используемыми в теории графов. Первый из них позволяет подсчитать число единичных и нулевых путей по отдельности, а второй – общее число путей. Методы работают в противоположных направлениях и используют аналог закона Кирхгофа для токов, известный из электротехники.

При использовании первого метода пометки перед вершинами [4] соответствуют пометкам, получаемым при применении динамического программирования. Эти пометки в линейных бинарных графах, реализующих знакочередующиеся бесповторные пороговые формулы в базисе И и ИЛИ, записанные в порядке возрастания весов переменных в них, соответствуют числам Фибоначчи. Такие графы содержат наибольшее число путей, равное(h+2)-ому числу Фибоначчи, где h – число букв в реализуемой формуле [26]. Это соотношение является верхней оценкой числа путей в графах рассматриваемого типа, а нижняя оценка числа путей в них – h+1. При этом имеет место уникальная для дискретной математики ситуация – верхняя (экспоненциальная) и нижняя (линейная) оценки достигаются на одном и том же объекте – описанных выше знакочередующихся формулах, и зависят от порядка их записи. Верхняя оценка достигается при указанном порядке записи формул, а нижняя – при противоположном.

Из изложенного следует, что указанная верхняя оценка, при условии возможности изменения порядка записи реализуемой формулы, является завышенной.

В работе [26] была построена неулучшаемая верхняя оценка числа путей в графах рассматриваемого типа. Она достигается на формулах, инвариантных к перестановкам их составляющих, например, на дизъюнктивных нормальных формах (ДНФ), образованных конъюнкциями, средняя длина которых равна e – указанные формы должны состоять из конъюнкций длины два и/или три. Это приводит к весьма экзотическому виду верхней оценки, состоящей из четырех формул, для выбора которых определены соответствующие условия [4]. Из рассмотрения этой оценки следует, что число путей в линейных бинарных графах может превышать число клик (максимальных подграфов) в графах Муна–Мозера, являющихся наиболее сложными по числу клик графами.

Отметим, что в работе [27] была получена оценка для определения максимального числа конъюнкций в ДНФ, получающихся в результате раскрытия скобок в бесповторных формулах в базисе И, ИЛИ, которая совпадает с оценкой числа клик в графах Муна-Мозера.

В работе [28] был описан метод минимизации числа и длины путей в линейных бинарных графах.

В рассмотренных публикациях описывалась реализация отдельных БФЛ бинарными графами. В работе [29] были предложено использовать настраиваемые бинарные процедуры для циклического вычисления систем БФЛ.

1.1.3.2. Реализация булевых формул в базисе И, ИЛИ, НЕ структурированными бинарными графами

В работе [30] были рассмотрены структурированные бинарные графы, которые строятся в результате преобразования линейных бинарных графов.

В работе [31] изложен значительно более интересный метод построения структурированных бинарных графов, реализующих как отдельные БФЛ в рассматриваемом базисе, так и системы таких формул. Этот метод, в некотором смысле, является аналогом метода построения параллельно-последовательных контактных схем по заданной БФЛ, важнейшим достоинством которого является построение схемы, изоморфной формуле, число контактов в которой равно числу букв в реализуемой формуле. Известный метод [25] позволил построение контактных схем превратить из эвристики в науку, так как минимизацию таких схем стало возможным проводить не в ходе «мозгового штурма», а в результате формальных преобразований реализуемых формул. В известном подходе минимизация числа букв в формуле приводила к такому же сокращению числу контактов в реализующей ее схеме.

Аналогичный подход в программировании отсутствовал. Этот пробел был устранён в работе [31], в которой был предложен метод, обладающий близкими свойствами при построении схем алгоритмов, и не только для одиночных БФЛ, как в известном методе, но и для систем таких формул.

1.1.3.3. Реализация булевых функций бинарными графами

Одним из наиболее эффективных методов реализации БФ является применение бинарных графов, которые называются в зарубежных источниках бинарными деревьями решений (BDD – Binary Decision Diagram) [32]. Эти диаграммы, наряду с их модификациями, используются при решении различных задач, например, при верификации программ на основе метода Model Checking.

При этом отметим, что, за тридцать лет до появления указанной работы, в СССР был разработан метод каскадов Поварова для построения древовидных контактных схем [33], на основе которого, за десять лет до появления работы [32], был создан канонический метод Блоха [34], предназначенный для эффективного построения бинарных деревьев решений для отдельных БФ.

Развитие канонического метода Блоха применительно к реализации СБФ бинарными графами выполнено в работах [35, 36], первая из которых была опубликована одновременно с работой [32].

Во всех работах, рассмотренных выше, предполагалась синхронная реализация бинарных графов. Их асинхронная реализация рассмотрена в работе [37], и показано, что для достаточно широкого класса СБФ противогоночное кодирование состояний автоматов, соответствующих таким графам, оказывается безызбыточным.

1.2. Автоматные схемы алгоритмов и программная реализация автоматов

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

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

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

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

Значения флагов соответствуют отдельным компонентам состояния программы. Вектор значений всех флаговых переменных определяет состояние схемы алгоритма в целом. Это делает указанные значения взаимозависимыми, что резко затрудняет внесение изменений и понимание схемы. Изложенное, естественно, относится не только к схемам алгоритмов и схемам программ [38], но к самим программам, построенным по этим схемам.

В работе [39] показано, что все указанные проблемы возникают из-за того, что в рассматриваемых схемах состояния не используются явно. Для решения этих проблем в работах [4, 39] было предложено начинать построение схем не с дешифратора входных воздействий, что кажется естественным, а с дешифратора состояний, для определения того, в какой точке пространства состояний находится реализуемый автомат в текущий момент времени. Размещение операторных вершин, связанных с выходными воздействиями, определяется типом автомата, который будет использоваться при реализации. При этом для автоматов Мура эти вершины должны располагаться после дешифратора состояний, но перед дешифраторами входных воздействий, а для автоматов Мили – после дешифраторов входных воздействий, которые, в свою очередь, должны быть размещены после дешифратора состояний. Кроме автоматов указанных типов могут использоваться и смешанные автоматы [40], в которых указанные вершины могут располагаться как до, так и после дешифраторов входных воздействий. В последнем слое в схемах, соответствующих любому из рассмотренных типов автоматов, должны размещаться операторные вершины, определяющие следующее состояние схемы, которое при очередном ее проходе, расшифровывается дешифратором состояний.

Схемы алгоритмов, обладающие указанной структурой, в работе [39] были названы автоматными.

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

Могут применяться различные виды кодирования состояний автоматов [39]. Наиболее простая реализация программы обеспечивается при их многозначном кодировании, при котором для каждого автомата, поведение которого задается графом переходов, используется только одна многозначная переменная, каждое значение которой присваивается одному из состояний автомата – значность переменной равна числу состояний автомата. Естественно, что так кодировать состояния можно только в том случае, если поведение программы предварительно формально описано – построен граф переходов, число вершин в котором определяет значность указанной переменной.

В работе [39] показано, что при применении многозначного кодирования состояний автоматные схемы алгоритмов, графы переходов и конструкция switch языка С или её аналоги в других языках программирования являются изоморфными друг другу и обеспечивают понятность программ, построенных на их основе.

Изложенное естественным образом обобщается на случай, когда поведение программы описывается не одним автоматом, а системой взаимодействующих автоматов. При этом каждому автомату вне зависимости от числа состояний соответствует одна многозначная переменная, и появляется возможность обеспечения взаимодействия автоматов за счёт включения в условия переходов одних автоматов проверок номеров состояний других автоматов [1].

Изложенное легло в основу автоматного программирования [41], для поддержки которого разработана Switch-технология [1]. Она была также названа технологией автоматного программирования [42].

В заключение раздела отметим, что кроме схем алгоритмов известны также используемые в связи SDL-диаграммы (Specification and Description Language), в которых состояния явно выделены. Однако такие диаграммы чрезвычайно громоздки [1], что резко уменьшает их конгнитивность.

Состояния явно не выделялись в диаграммах Насси-Шнейдермана. Это также не произошло и при разработке «дружелюбного русского алгоритмическиго языка, который обеспечивает наглядность» (ДРАКОН). Это визуальный алгоритмический язык программирования и моделирования (https://ru.wikipedia.org/wiki/ДРАКОН). Он был разработан в рамках космической программы «Буран» и должен был заменить специализированные языки, использовавшиеся в этой программе.

Разработка языка велась с 1986 г. при участии Научно-производственного центра автоматики и приборостроения им. акад. Н.А. Пилюгина и Института прикладной математики им. М.В. Келдыша. Язык построен путём формализации, эргономизации и неклассической структуризации блок-схем алгоритмов, а также для разработки программ реального времени. При этом предлагалось строить правильно нарисованные дракон-схемы. Работы по разработке языка были закончены в 1996 г. (спустя три года после закрытия программы «Буран»), когда была создана автоматизированная система проектирования программных систем на его основе. Эта система применялась в некоторых крупных космических программах.

Аналогом языка ДРАКОН является «R-технология производства программ, или технология двумерного программирования», созданная в своё время в Институте кибернетики имени В.М. Глушкова, причем графика дракон-схем в дракон-семействе служит аналогом графики Р-схем в R-технологии (Вельбицкий И.В. Технология программирования. Киев: Технiка, 1984. 279 с.).

Несмотря на то, что последняя книга по языку «Дракон» (Паранджанов В.Д. Учись писать. Читать и понимать алгоритмы. Алгоритмы для правильного мышления. Основы алгоритмизации. М.: ДМК Пресс, 2012. 520 с.) появилась сравнительно недавно, ссылки на автоматное программирование в ней отсутствуют. Только в 2016 г. представители одной из организаций, применявших дракон-схемы, познакомились с автоматным программированием и были удивлены наличием многих достоинств у него. А 12.08.2016 г. В. Паранджанов предложил мне быть «друзьями» в Facebook. Я, естественно, согласился и ответил: «Странно, что Вы столько лет не замечали (не ссылались в книгах) не меня, не автоматное программирование. Теперь надеясь, мы поймем друг друга». Пока ничего не происходит.

2. Автоматное программирование

2.1. Автоматное программирование как стиль программирования

Автоматное программирование является одним из стилей программирования. В работе [43] отмечается: «Термин автоматное программирование принадлежит, насколько нам известно, А.А. Шалыто. Во всяком случае, ему принадлежит заслуга в его развитии вопреки моде и мнению большинства».

Упрощенная трактовка автоматного программирования, предложенного в 1991 г. [44], состоит в том, что это стиль программирования, при использовании которого поведение программ предлагается описывать автоматами, которые в дальнейшем изоморфно преобразуются в код.

При этом отметим, что автоматы давно применяются в программировании, например, при построении компиляторов [45, 46]. Автоматы используются также и при решении многих других задач, например, при реализации протоколов.

В работе [47] подход с использованием автоматов для описания поведения программ был определён как стиль программирования, названный «программирование от состояний». В указанной работе отмечалось, что «это, пожалуй, самый старый стиль программирования, так как на него наталкивает само устройство существующих вычислительных машин, которые представляют собой гигантские конечные автоматы».

На выделение указанного подхода в качестве самостоятельного стиля программирования, на авторов работы [47] повлияла работа [1], на которую они ссылаются, как на современную методику программирования от состояний. В работе [1] было предложено применять автоматы в программировании не от случая к случаю, как одну из моделей дискретной математики, а как универсальный подход, который целесообразно использовать практически во всех случаях, когда программа должна обладать достаточно сложным поведением, и, в особенности, реактивным [48] – реагировать по-разному на события в зависимости от состояний, в которых находится программа.

При этом отметим, что, несмотря на наличие работ Д. Харела, даже реактивные системы проектируются автоматно далеко не всегда. Об этом, в частности, свидетельствует появление только в 2007 г. работ сотрудника компании IBM Э. Принга [49, 50] о реализации медленно всплывающих подсказок с применением автоматов. Однако, даже в этом случае нельзя говорить о применении автоматного программирования, так как переход от модели к программе выполнялся эвристически, что привело к их расхождению.

В заключение раздела отметим, что «программирование с автоматами» нельзя рассматривать как парадигму программирования, так как при этом остается не ясным как с использованием автоматов проектировать и реализовывать программы в целом.

2.2. Автоматное программирование как парадигма программирования

Очень многие системы, которые для внешнего наблюдателя ведут себя достаточно осмысленно, являются автоматизированными объектами.

Автоматизированный объект представляет собой совокупность объекта управления и системы управления, охваченных обратными связями.

Задача построения автоматизированных объектов рассматривается в любом курсе теории автоматического управления применительно к объектам различных типов.

Удивительно, что это почти никак не коснулось практики программирования, несмотря на то, что в теории алгоритмов в качестве одной из основных моделей используется машина Тьюринга, которая, по сути, является автоматизированным объектом [51], в котором объект управления – лента (её ячейки памяти), а система управления – конечный автомат. Сложность программирования на машине Тьюринга (умножение двух на три требует 66 шагов [52]) определяется тем, что ней используются чрезвычайно простые объекты управления (ячейки памяти), которые могут выполнять только простейшие действия (операции) по записи и стиранию отдельных символов. В этой ситуации вычисления, в некотором смысле, приходится выполнять конечному автомату, который для этой цели не приспособлен, так как его предназначение – управление. Другая особенность машины Тьюринга, которая может резко усложнять программы, это использование только одного автомата, которого достаточно для проведения теоретических исследований, но часто бывает мало для практического применения.

Переход к тьюрингова программирования к практическому программированию, названному в работе [51] автоматным, осуществляется за счёт усложнения объектов управления, которые могут выполнять сколь угодно сложные действия (операции), и применения в системе управления системы взаимодействующих автоматов. Из изложенного следует, что универсальность предлагаемого подхода определяется тем, что он основан на расширении машины Тьюринга, которая позволяет реализовать произвольные алгоритмы.

При этом теоретические положения о том, что автоматы позволяют распознавать только регулярные языки [53], а магазинные автоматы – только языки с контекстно-свободными грамматиками, отходят на второй план, так как в рассматриваемом подходе используются не автоматы, а автоматизированные объекты, в которых объекты управления и их сложность не фиксированы.

Учитывая изложенное, в работе [54] была сформулирована основная особенность автоматного программирования – программы предлагается создавать так же, как производится автоматизация технологических (и не только) процессов.

При этом на основе анализа предметной области выделяются источники входных воздействий и автоматизированные объекты, каждый из которых содержит систему управления (система взаимодействующих конечных автоматов) и объекты управления. Эти объекты реализуют выходные воздействия и формирует значения еще одной разновидности входных воздействий, которые по обратным связям передаются системе управления.

Все перечисленные составляющие автоматизированного объекта отображаются на схеме связей, которая может совмещаться со схемой взаимодействия автоматов. На схеме связей для каждого входного и выходного воздействия указывается полное название на русском или, если это необходимо, на иностранном языке, и краткое символьное обозначение, которое в дальнейшем используется в качестве пометки графов переходов и идентификатора переменной в программе. Использование кратких обозначений позволяет даже весьма сложные алгоритмы отражать так компактно, что обычно каждый из графов переходов удаётся размещать на одном экране монитора, позволяя человеку «охватить» весь граф одним взглядом, что резко упрощает понимание таких графов.

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

Объекты управления могут быть реальными или виртуальными – реализованными программно. В первом случае их логика изменена быть не может, а во втором – она, при необходимости, практически вся может быть вынесена в автоматы.

Таким образом, в соответствии с автоматным подходом, сущности со сложным поведением следует представлять в виде автоматизированных объектов управления – так в теории управления называют объект управления, интегрированный с системой управление в одно «устройство».

Парадигма автоматного программирования состоит в представлении сущностей со сложным поведением в виде автоматизированных объектов управления [54].

Как сказано в этой книге, нахождение компромисса между сложностью автомата и сложностью операций объекта управления, примирение тьюрингова программирования с традиционным и есть «миссия» автоматного подхода в мире разработки программного обечпечения.

Интересно, что в своё время при обсуждении содержания страницы «Автоматное программирование» в Wikipedia меня пытались убедить в том, что автоматное программирование – это прогрпаммирование с автоматами, которое давно и хорошо известно. Если придерживаться такой логики, то программирование с линейками – это линейное программирование. Но это не так. На самом, автоматное программирование – это парадигма программирования, которая, как отмечено выше, впервые сформулирована в нашей книге. Вот, и всё, что хотелось сказать по этому поводу.

2.3. Основные положения автоматного программирования

Основным понятием в автоматном программировании является состояние [1].

При написании автоматных программ предлагается (в отличие от работ [55, 56]) разделять состояния на два класса: управляющие и вычислительные. При этом с помощью небольшого числа управляющих состояний, как и в машине Тьюринга, можно управлять сколь угодно большим числом вычислительных состояний [57]. Во введённой классификации управляющие состояния могут быть названы качественными, а вычислительные – количественными. Поэтому в рамках автоматного программирования основное внимание уделяется управляющим состояниям, которые, если это не оговаривается особо, и рассматриваются в дальнейшем.

При этом справедливо соотношение: «Состояния + входные воздействия = конечный (детерминированный) автомат без выхода». Справедливо также: «Автомат без выхода + выходные воздействия = автомат».

Автоматы могут быть абстрактными (входные и выходные воздействия формируются последовательно) и структурными (входные и выходные воздействия формируются «параллельно») [58]. В автоматном программировании, в отличие, например, от программирования компиляторов, обычно применяются структурные автоматы [59].

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

Автоматы могут задаваться в различном виде, однако при их проектировании и использовании человеком, они должны обладать когнитивными свойствами [60], что достигается при задании поведения автоматов графами переходов (диаграммами состояний). В случае, если автоматы генерируются автоматически [61], то они могут задаваться иначе, например, в табличной форме. При этом отметим, что даже при сравнительно небольшом числе состояний и переходов, такое задание затрудняет понимание работы автоматов человеком, так как отражение переходов в них ненаглядно.

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

2.4. Достоинства автоматного программирования

В рамках автоматного программирования предполагается, что собственно написание (генерация) программы начинается только после её проектирования. При этом в инженерной практике проект или его этап обязательно завершается выпуском проектной документации. Поэтому при автоматном программировании, основной областью использования которого являются встроенные системы (чисто инженерная область), должна выпускаться проектная документация [62], а не только документация пользователя, как это обычно принято в программных проектах. При этом для автоматных программ необходимой компонентой, входящей в состав проектной документации, являются графы переходов.

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

При необходимости проведения отладки автоматные программы могут выполняться с применением отладочных протоколов [4], которые отражают поведение программ в терминах автоматов (состояний, переходов, значений входных и выходных воздействий), так как в автоматном программировании автоматы являются не картинками, как считают многие (например, автор работы [63]), а могут быть частью программ, представленных в нетрадиционной для программистов визуальной, а не текстовой форме.

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

Создание программ со сложным поведением без использования формальных моделей приводит к трудностям на всех этапах жизненного цикла. Такие программы писать весьма сложно, так как все особенности их поведения приходится все время держать в голове вместо того, чтобы отобразить их на модели и на время забыть. Еще одним преимуществом автоматных программ является простота внесения изменений в них людьми, для которых автоматный стиль программирования привычен [1]. Этим они принципиально отличаются, например, от нейронных сетей, корректировка которых людьми практически невозможна.

Следующее достоинство рассматриваемого класса программ – эффективность их верификации на основе использования моделей (метод Model Checking) [64]. В этой работе отмечается наша роль в привлечении внимания к проблеме верификации автоматных программ, для которых может быть обеспечен высокий уровень автоматизации процесса верификации, что является их несомненным достоинством.

В заключение раздела отметим, что для автоматных программ естественен параллелизм, что особенно важно при применении многоядерных процессоров [65].

2.5. Разновидности автоматного программирования

С 1991 г. автоматное программирование развивалось в трёх направлениях: логическое управление, программирование с явным выделением состояний и объектно-ориентированное программирование с явным выделением состояний.

2.5.1. Логическое управление

Наиболее просто и естественно применять автоматы в системах логического управления, в которых входные и выходные переменные двоичны. Естественность применения автоматов при программировании этого класса систем объясняется тем, что программы в них заменяют схемы, проектирование которых с использованием автоматов распространено и развивается давно, начиная с релейно-контактных схем [59].

Однако проста и естественность применения автоматов даже для этого класса систем, видимо, далеко не очевидна, так как даже при программировании логических контроллеров [66], практически никто не предлагал сначала проектировать автоматы, а затем их реализовать на выбранном языке программирования.

В работе [67] было показано, что плохого в неавтоматном программировании контроллеров, а работах [68-71] описано применение технологии автоматного программирования для систем логического управления. Эта технология была использована при создании ряда систем управления, которые в основном предназначались для управления судовыми техническими средствами [1].

В работах [72-74] в качестве примеров показано как применять предложенную технологию применительно к языкам функциональных блоков, широко используемым в программируемых логических контроллерах, а также к инструментальному средству LabVIEW, которое может быть

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

2.5.2. Программирование с явным выделением состояний

Значительно более широким классом по сравнению с системами логического управления являются реактивные системы. Для описания поведения этого класса систем, к которым относится, большинство встроенных систем, применение автоматов также естественно [48], как и для систем логического управления. Однако далеко не все программисты и для таких систем используют автоматы, приобретая множество проблем, о которых говорилось выше.

Реактивные системы являются более сложными по сравнению с системами логического управления. В них:

в качестве входных воздействий, наряду с входными переменными, используются события;
запуск программ осуществляется по событиям, а не циклически;
в качестве выходных воздействий могут использоваться не только двоичные, а любые функции, что позволяет называть автоматы, применяемые при этом, гибридными [75];
автоматы могут содержать не только вложенные состояния [48], но и вложенные автоматы;
автоматы могут взаимодействовать не только за счёт проверки номеров состояний, как было предложено для систем логического управления [1], но и путём вызываемости и вложенности.

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

Технология программирования с явным выделением состояний создавалось в ходе выполнения работ по разработке системы управления судовыми дизель-генераторами [76]. Эта технология подробно описана в работах [77-82].

2.5.3. Объектно-ориентированное программирование с явным выделением состояний

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

В рамках этой парадигмы ничего конструктивного относительно описания и реализации поведения объектов не было сказано. Более того, с развитием методов проектирования таких программ [83] в этот вопрос ясность не была внесена, а применять автоматы предлагалось лишь от случая к случаю, а не «как руководство» к действию, пригодное для использования во многих системах при описании их сложного поведения. Даже в тех редких случаях, когда автоматы применялись для описания поведения программ (например, при проектировании программного обеспечения метеостанции в работе [55]) это делалось крайне неубедительно.

Появление унифицированного языка моделирования UML [84], и даже языка UML 2.0 [85], эту проблему не решило, так как, во-первых, в этом языке, кроме диаграмм состояний для описания поведения предлагается использовать и другие типы диаграмм и не говорится когда и какие диаграммы следует применять, во-вторых, в рамках унифицированного процесса разработки программ [86], как впрочем, и при использовании других методологий их создания (например, описанной в работе [87]), не было предложено подходов для совместного использования диаграмм, описывающих статические и динамические свойства программ, и, наконец, в третьих, диаграммы для описания поведения в основном использовались как язык общения между участниками разработки и для документирования программ, в то время как для кодогенерации использовались только диаграммы классов. Лишь в рамках концепции исполняемый UML [88] вопрос о кодогенерации был поставлен шире.

Для решения указанной проблемы в Университе были выполнены исследования по совместному использованию объектной и автоматной парадигм программирования. При этом такой стиль программирования был назван объектно-ориентированное программирование с явным выделением состояний [89].

Возможны различные подходы к решению этой проблемы. Автоматы можно использовать, например, как методы классов [90] или как классы [91].

Более «глубокое проникновение» автоматов в объектно-ориентированное программирование происходит при применении паттернов проектирования. При этом отметим, что применение паттерна State, предназначенного для реализации объектов, поведение которых зависит от состояния, как ни странно, обычно вызывает трудности [92]. Решению этого вопроса посвящена работа [93].

Для устранения недостатков, присущих указанному паттерну, в работах [94, 95] был предложен паттерн State Machine, на базе которого создан язык с тем же названием [96], являющийся расширением языка Java и позволяющий достаточно эффективно реализовывать автоматы.

В работе [97] был предложен ещё один подход к реализации объектно-ориентированных программ с явным выделением состояний, который позволяет обеспечить повторное использование программных компонентов, параллельные вычисления, автоматическое протоколирование работы системы и повышение ее отказоустойчивости. В качестве основы для разработки «автоматной» части программ в этой работе была предложена библиотека, реализованная на языке С++. При использовании этой библиотеки остальная часть программ (контекст) разрабатывается традиционным образом.

Особенности проектирования и свойства автоматных программ позволяют отнести автоматное программирование к одной из разновидностей синхронного программирования [98, 99], которое активно развивается в Западной Европе для создания программного обеспечения ответственных систем.

Высокое качество автоматных программ может быть достигнуто не только за счёт автоматного расширения универсальных языков программирования, но в тех случаях, когда для написания автоматных программ разрабатываются языки, ориентированные на эту предметную область [100, 101].

Существуют и другие подходы к совместному использованию объектной и автоматной парадигм программирования. Классификация таких подходов приведена в работах [102, 103].

Работы в указанном направлении продолжаются. При этом, например, в работе [104] предложена удобная графическая нотация наследования автоматных классов.

2.6. Верификация автоматных программ

Выше отмечалось, что автоматные программы сравнительно легко верифицируются на основе метода Model Checking. Это очень важно для построения ответственных систем, и в особенности систем реального времени. В настоящее время активно ведутся работы в указанном направлении [64, 105-108]. В Университете ИТМО эти работы проводились по теме «Разработка технологии верификации управляющих программ со сложным поведением, построенных на основе автоматного подхода», которая выполнялась в рамках Федеральной целевой программы «Исследования и разработки по приоритетным направлениям развития научно-технологического комплекса России на 2007–2012 годы». В настоящее время совместно с Университетом Аалто (Финляндия) проводятся исследования по теме «Разработка методов, средств и технологий проектирования, верификации и тестирования ответственных кибер-физических систем», выполняемой в рамках Федеральной целевой программы «Исследования и разработки по приоритетным направлениям развития научно-технологического комплекса России на 2014-2020 годы».

2.7. Автоматизация построения автоматных программ

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

В этих случаях можно пытаться применять формализованные методы. Например, в работе [109] предложено использовать динамическое программирование для построения автоматов. Однако такой подход имеет ограниченное использование.

Значительно более универсально применение генетического и эволюционного программирования для генерации автоматов. В Университете ИТМО эти работы, в частности, проводились по теме «Технология генетического программирования для генерации автоматов управления системами со сложным поведением», выполняемой в рамках указанной выше Федеральной целевой программы. Эти исследования проводятся и в настоящее время.

Работы по этой тематике нами активно ведутся работы по этой тематике [109-121]. В [119] автоматы строились на основе моделирования, что требовало много времени, то в [120] автоматы строились на основе обучающих примеров, что позволило значительно уменьшить время построения автоматов. Еще одно существенное отличие этих работ – в первой из них использовались только дискретные выходные воздействия, а во второй – и непрерывные. Если в этих работах предложены подходы к построению автоматов нижнего уровня, то в [121] показано как строить автоматы верхнего уровня.

Дальнейшее сокращение времени генерации автоматов обеспечивается на основе применения муравьиных алгоритмов [122-128].

В работах [129-133] предложены подходы к генерации автоматов на основе совместного применения эволюционных и муравьиных алгоритмов.

В работах [134-136] предложен весьма оригинальный метод генерации автоматов с помощью решателей для задачи выполнимости. В [137] в дальнейшем этот подход был развит на использование решателей для задачи удовлетворения ограничений.

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

Вопросы тестирования автоматных программ рассмотрены в [142, 143], а в [144] показано, что даже о простых автоматных программах нельзя говорить, что они правильные. Про программы можно лишь говорить, что они соответствуют проверенным тестам и темпоральным правилам.

Генерация автоматов позволяет до 80% кода автоматных программ строить почти автоматически, так как в программах этого класса объём кода, порождаемый автоматами, может достигать указанной величины. Функций входных и выходных воздействий при этом должны писаться вручную.

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

Эксперименты показали, что автоматически построенная система управления обеспечивает более эффективную работу мультиагентной системы, по сравнению со случаем, когда в автоматы системы управления (их было семь) строились эвристически [146]. При этом отметим, что поведение системы, построенной человеком, значительно более понятно, и в неё значительно проще вносить изменения.

2.8. Технология автоматного программирования

На основании указанных выше работ была разработана технология автоматного программирования, которая охватывает все этапы жизненного цикла программ рассматриваемого класса. Эта технология описана в работах [147-149], а в работе [150] изложена для массового читателя.

2.9. Инструментальные средства для поддержки автоматного программирования

Рассмотрим средства для поддержки автоматного программирования.

Для процедурных автоматных программ в [151] было описано инструментальное средство, которое по графам переходов, представленным в нотации, предложенной в [79], и изображенным с помощью пакета Visio, генерирует код, изоморфный реализуемым графам переходов, который основан на конструкциях switch языка С.

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

Развитие это направление исследований получило в [152, 153], в которой показано, что аналогичный подход может быть использован для реализации автоматов на любом наперёд заданном языке программирования, и было создано инструментальное средство MetoAuto для поддержки такого подхода.

Переходя к инструментальному средству для поддержки построения объектно-ориентированных автоматных программ, отметим, что если для генерации программ по автоматам, кроме средств, рассмотренных выше, известны также и другие [154], то решение задачи об автоматизации построения объектно-ориентированных программ в целом в открытых источниках не излагалось.

Решение этой задачи было предложено в Университете ИТМО в ходе выполнения работ по теме «Автоматное программирование: применение и инструментальные средства», которая выполнялась в рамках Федеральной целевой научно-технической программы «Исследования и разработки по приоритетным направлениям науки и техники» на 2002–2006 годы [155].

В результате было создано инструментальное средство UniMod [156-160], которое автоматизирует процесс построения объектно-ориентированных автоматных программ. При его использовании структура программ задается диаграммами классов, которые изображаются не традиционным способом, а в форме схемы связей автоматов с поставщиками событий и объектами управления. Динамика программ описывается с помощью диаграмм состояний в нотации языка UML, в которых могут использоваться не только вложенные состояния, но и вложенные автоматы. При этом имеется возможность проверить ряд свойств этих диаграмм, например, полноту и непротиворечивость. Функции входных и выходных воздействий, которые практически не содержат логики, пишутся на языке Java вручную. После этого автоматически может быть скомпилирован код программы в целом или программа может выполняться в режиме интерпретации. Описанное инструментальное средство находится в свободном доступе, и является единственным открытым и бесплатным средством, поддерживающим концепцию исполняемого UML [161].

Это инструментальное средство используется в настоящее время при бакалаврской подготовке в университетах Италии [162]. Его предполагается также применять при магистерской подготовке и при обучении аспирантов (PhD-студентов).

2.10. Технология программирования программируемых логических интегральных схем на основе автоматного подхода

В [163-166] автоматный подход был применен для написания программ для аппаратуры – программируемых логических интегральных схем (ПЛИС). При этом автоматы предлагается строить с помощью программного средства Stateflow, входящего в пакет MATLAB/Simulink. Это средство по графам переходов автоматов строит код, который позволяет автоматически программировать ПЛИС. Вопрос о дальнейшем повышении уровня автоматизации в рамках этой технологии рассмотрен [167].

2.11. Апробация технологии автоматного программирования

Апробация этой технологии выполнялась не только при разработке программного обеспечения систем управления, но и для ряда других задач: игр [168, 169], информационных систем [170] и при использовании FLASH-технологии [171]. С применением автоматов при разработке мобильных устройств можно ознакомиться в [172].

Автоматы применялись также и при выполнении исследований в области искусственного интеллекта. Так, например, в работах [173, 174] рассматривалось применение автоматов при построении мультиагентных систем, а в работе [175] – вопрос о совместном использовании автоматов и нейронных сетей.

Кроме этих работ, на сайте [176], посвящённом автоматному программированию, постоянно публикуются проекты по созданию программного обеспечения для решения различных задач на основе автоматного подхода, каждый из которых содержит, в том числе, и проектную документацию (разделы «Проекты» и «UniMod-проекты»). Указанные проекты выполнены в качестве курсовых работ студентами третьего курса кафедры «Компьютерные технологии» Университета ИТМО.

2.12. Разработка визуализаторов алгоритмов дискретной математики

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

Известны, лишь несколько задач этого класса, в которых применять автоматы эффективно. Это, например, поиск подстрок [177], подсчёт длины слов в строке [178] и обход деревьев [179].

Однако оказалось, что если реализовывать алгоритмы дискретной математики на автоматах часто нецелесообразно, то строить их визуализаторы с применением автоматов крайне полезно всегда, так как при этом визуализацию можно проводить, например, в состояниях, а не там, где захочется разработчику. При решении задачи построения таких визуализаторов был использован ряд работ как теоретического [180-182], так и прикладного характера [183-188]. В результате в Университете ИТМО было разработано инструментальное средство VIZI для автоматизированного построения визуализаторов рассматриваемого класса. Визуализаторы, построенные на основе автоматного подхода, и проектная документация для них опубликованы на сайте [176] в разделе «Визуализаторы».

Несмотря на то, что лекции по курсу «Алгоритмы дискретной математики» читаются практически в каждом университете мира, где обучают информационным технологиям, а в некоторых из них в учебном процессе используются визуализаторы, эффективную методику их построения без применения автоматного подхода создать не удавалось никому.

2.13. Применение и использование автоматного программирования

Вопросы применения автоматного программирования рассматривались в [189-196]. При этом в основном исследовался вопрос о применении автоматов в рамках международного стандарта IEC 61499, которой поддерживает построение распределённых сетей из программируемых логических контроллеров.

Автоматное программирование использовалось в АО «Концерн «НПО «Аврора» при создании [1, 4]:

системы управления дизель-генератором ДГР-2А 500*500 для трёх судов проекта 15640 на базе аппаратуры «Selma-2» фирмы «ABB Stromberg» (Финляндия) [197, 198]. Программирование выполнено в НПО «Аврора» на языке функциональных блоков;
системы управления дизель-генератором того же типа для судна проекта 15967 на базе аппаратуры «Selma-2» фирмы «ABB Stromberg» [197]. Программирование выполнено в НПО «Аврора» на языке функциональных блоков;
системы управления дизель-генератором того же типа для судна проекта 15760 на базе аппаратуры фирмы «Norcontrol» (Норвегия) [199]. Программирование выполнено фирмой на языке ПЛ/М;
комплексной системы управления техническими средствами для судна проекта 17310 на базе программируемых логических контроллеров «Autolog» фирмы «FF-Automation OY» [200]. Программирование для общесудовых систем выполнено НПО «Аврора» на языке инструкций ALPro вручную, а для системы управления вспомогательными механизмами главного двигателя и автоматически с помощью транслятора «Ядро языка СИ – язык инструкций ALPro»;
автоматизированной системы управления технологическими процессами (АСУ ТП) центральной подготовительной станции первичной обработки нефти «Авролог-НП1» (Северо-Ореховское месторождение). Программирование выполнялось на языке инструкций ALPro;
АСУ ТП дожимной насосной станции «Авролог-НП2» (Северо-Покурское месторождение). Программирование выполнялось на языке инструкций ALPro;
системы управления турбокомпрессорным агрегатом «Ларина», используемой при производстве полиэтилена в ПО «Полимир» (Новополоцк). Программирование выполнялось на языке ассемблера однокристальной микроЭВМ КР 1863 ВЕ51;
системы управления электромеханическим приводом, выполненным на основе специально разработанного шагового двигателя на ПЛИС. Программирование выполнялось с помощью пакета «Stateflow», входящего пакет «МATLAB» [163-166];
локальной системы управления дизель-реверс-редукторным агрегатом для одного из проектов судов. Программирование выполнялось на языке C++ с помощью инструментального средства «MetaAuto» [152, 153].

Автоматное программирование использовалось также в ЗАО «Морские навигационные системы» (http://is.ifmo.ru/aboutus/navy) при автоматизации: электроэнергетической системы (управление дизель-генераторами и их параллельной работой), компрессоров системы кондиционирования и вспомогательного котла для пассажирских теплоходов проекта 301 (первое судно – «Константин Федин»); параллельной работы генераторов для корабля проекта 12322; насосов и клапанов на индийском авианосце «Викрамадитья», который появился в результате чудесного превращения тяжёлого авианесущего крейсера «Адмирал Горшков» (http://kramtp.info/news/18/full/id=34098).

Автоматное програмирование применялось и при создании других систем, описанных, например, здесь: http://is.ifmo.ru/aboutus/33/.

Заключение

В ходе работ по автоматному программированию необходимо было решить задачи в области образования, проведения научных исследований и разработки технологии для его поддержки. Все эти задачи удалось решить в результате педагогического эксперимента, проводимого на кафедре «Компьютерные технологии» Университета ИТМО [201], результаты которого вошли в научно-практическую и методическую разработку «Инновационная система поиска и подготовки высококвалифицированных специалистов в области производства программного обеспечения на основе проектного и соревновательного подходов» для образовательных учреждений высшего профессионального образования, за которую в 2008 г. автору в составе авторского коллектива была присуждена премия Правительства РФ в области образования (http://rg.ru/2009/01/16/premii-obrazovanie-dok.html).

Со многими работами, указанными ниже, которые выполнены автором или при его участии, можно ознакомиться на сайте http://is.ifmo.ru/

Литература

Шалыто А.А. SWITCH-технология. Алгоритмизация и программирование задач логического управления. –СПб.: Наука, –1998. http://is.ifmo.ru/?i0=books&i1=switch&i2=1
Карповский М.Г., Москалев Э.С. Спектральные методы анализа и синтеза дискретных устройств. –Л.: Энергия, –1973.
Karpovsky M.G. Finite Orthogonal Series in the Design of Digital Devices. NY: John Wiley & Sons, 1976.
Шалыто А.А. Логическое управление. Методы аппаратной и программной реализации алгоритмов. –СПб.: Наука, –2000.http://is.ifmo.ru/?i0=books&i1=log_upr&i2=1
Жегалкин И.И. О технике вычисления предложений в символической логике // Математический сборник. –1927. Т. 34. Вып. 1.
Авсаркисян Г.С., Брайловский Г.С. Представление логических функций в виде полиномов Жегалкина // Автоматика и вычислительная техника. –1975. № 6.
Малюгин В.Д. Реализация булевых функций арифметическими полиномами // Автоматика и телемеханика (А и Т). –1982. № 4.
Артюхов В.Л., Кондратьев В.Н., Шалыто А.А. Реализация булевых функций арифметическими полиномами // А и Т. –1988. № 4. http://is.ifmo.ru/books/djvu/pdf/A004.pdf
Малюгин В.Д., Кухарев Г.А., Шмерко В.П. Преобразования полиномиальных форм булевых функций. Препринт. –М.: Ин-т проблем управления, 1986.
Кондратьев В.Н., Шалыто А.А. Реализация систем булевых функций использованием линейных арифметических полиномов // А и Т. –1993. № 3. http://is.ifmo.ru/books/djvu/pdf/A003.pdf
Кондратьев В.Н., Шалыто А.А. Реализация булевых функций одним линейным арифметическим полиномом с маскированием // А и Т. 1996. № 1. http://is.ifmo.ru/books/djvu/pdf/A002.pdf
Кондратьев В.Н., Шалыто А.А. Реализация систем булевых функций линейными арифметическими полиномами // А и Т. –1997. № 3. http://is.ifmo.ru/books/djvu/pdf/A001.pdf
Финько О.А. Модулярная арифметика параллельных логических вычислений. –М.: Ин-т проблем управления РАН им. В.А. Трапезникова; Краснодар: Краснодарское воен. ин-т, –2003.
Кухарев Г.А., Тропченко А.Ю., Шмерко В.П. Систолические процессоры для обработки сигналов. –Минск: Беларусь, –1988.
Кухарев Г.А., Шмерко В.П., Янушкевич С.Н. Техника параллельной обработки бинарных данных на СБИС. –Минск: Высшая школа, –1991.
Малюгин В.Д. Параллельные логические вычисления посредством арифметических полиномов. –М.: Наука, –1997.
Кузнецов О.П. О программной реализации логических функций и автоматов // А и Т. –1977. № 7, 9.
Ершов А.П. Введение в теоретическое программирование. –М.: Наука, –1977.
Камынин С.С., Любимский Э.З., Шура-Бура М.Р. Об автоматизации программирования при помощи программирующей программы // Проблемы кибернетики. –М.: Физматгиз. –1958. Вып. 1.
Артюхов В.Л., Кузнецов Б.П., Шалыто А.А. Линейные бинарные графы: свойства, характеристики, алгоритмы / Методы и программы решения оптимизационных задач на графах и сетях. Ч. 2. Тез. докл. III Всесоюз. совещ., Ташкент, –1984.
Кузнецов Б.П., Шалыто А.А. Система преобразований некоторых форм представления булевых функций // А и Т. –1985. № 11.
Кузнецов Б.П., Шалыто А.А. Реализация булевых формул линейными бинарными графами. I. Синтез и анализ // Изв. РАН. Тех. кибернетика. –1994. № 5. http://is.ifmo.ru/books/djvu/pdf/A010.pdf
Артюхов В.Л., Шалыто А.А. Судовые управляющие логические системы. –Л.: Институт повышения квалификации руководящих работников и специалистов судостроительной промышленности, –1984.
Артюхов В.Л., Шалыто А.А. Реализация булевых формул однородными мультиплексорными и мажоритарными каскадами // Известия РАН. Теория и системы управления (Изв. РАН. Т и СУ). –1996. № 5. http://is.ifmo.ru/books/djvu/pdf/A013.pdf
Шеннон К.Э. Работы по теории информации и кибернетике. –М.: Изд-во иностр. лит., –1963.
Кузнецов Б. П., Шалыто А.А. Реализация булевых формул линейными бинарными графами. II. Оценки числа и суммарной длины путей // Изв. РАН. Т и СУ. 1995. № 3. http://is.ifmo.ru/books/djvu/pdf/A011.pdf
Артюхов В.Л., Кузнецова О.С., Шалыто А.А. Оценка функциональных возможностей программируемых логических матриц // Автоматика и вычислительная техника. –1985. № 2. http://is.ifmo.ru/books/djvu/pdf/A001.pdf
Кузнецов Б.П., Шалыто А.А. Реализация булевых формул линейными бинарными графами. III. Оптимизация числа и суммарной длины путей // Изв. РАН. Т и СУ. –1995. № 5. http://is.ifmo.ru/books/djvu/pdf/A012.pdf
Артюхов В.Л., Кузнецов Б.П., Шалыто А.А. Настраиваемые бинарные процедуры и циклические программы // А и Т. 1984. № 11.
Кузнецов Б.П., Шалыто А.А. Структурный подход к программной реализации булевых формул // Автоматика и вычислительная техника. –1985. № 5.
Кузнецов Б.П., Шалыто А.А. Метод независимых фрагментов для построения линеаризованных структурированных граф-схем алгоритмов, реализующих системы булевых формул // А и Т. –1998. № 9. http://is.ifmo.ru/books/djvu/pdf/A006.pdf
Brayant R.E. Graph-Based Algorithms for Boolean Function Manipulation // IEEE Trans. on Computers. –1986. № 8.
Поваров Г.Н. Математическая теория синтеза контактных (1,k)-полюсников // Доклады АН СССР. –1955. № 5.
Блох А.Ш. Граф-схемы и их применение. Минск: Вышэйшая школа, –1975.
Рубинов В.И., Шалыто А.А. Метод построения граф-схем простых бинарных программ для систем булевых функций // Автоматика и вычислительная техника. –1986. № 4.
Рубинов В.И., Шалыто А.А. Построение граф-схем бинарных программ для систем булевых функций, заданных таблицами истинности // Автоматика и вычислительная техника. –1988. № 1.
Сагалович Ю.Л., Шалыто А.А. Бинарные программы и их реализация асинхронными автоматами // Проблемы передачи информации. –1987. Вып. 1. http://is.ifmo.ru/books/djvu/pdf/A019.pdf
Шалыто А.А. Использование граф-схем и графов переходов при программной реализации алгоритмов логического управления. I // А и Т. –1996. № 6. http://is.ifmo.ru/books/djvu/pdf/A008.pdf
Шалыто А.А. Использование граф-схем и графов переходов при программной реализации алгоритмов логического управления. II // А и Т. –1996. № 7. http://is.ifmo.ru/books/djvu/pdf/A009.pdf
Баранов С.И. Синтез микропрограммных автоматов (граф-схемы и автоматы). –Л.: Энергия, –1979.
Шалыто А.А. Автоматное программирование // Известия Уральского государственного университета. –2006. № 43. (Компьютерные науки и информационные технологии. Вып. 1).
Шалыто А.А. Технология автоматного программирования / Материалы XI Всероссийской конференции по проблемам науки и высшей школы «Фундаментальные исследования и инновации в технических университетах». СПбГПУ. –2007.
Непейвода Н.Н. Стили и методы программирования. –М.: Интернет-университет информационных технологий, –2005.
Шалыто А.А. Программная реализация управляющих автоматов // Судостроительная промышленность. Серия «Автоматика и телемеханика». –1991. Вып. 13.
Ахо А., Сети Р., Ульман Д. Компиляторы. Принципы, технологии, инструменты. –М.: «Вильямс», –2001.
Хопкрофт Д., Мотвани Р., Ульман Д. Введение в теорию автоматов, языков и вычислений. –М.: «Вильямс», –2002.
Непейвода Н.Н., Скопин И.Н. Основания программирования. –М., -Ижевск: Институт компьютерных исследований, –2003.
Harel D. et al. Statemate: A Working Environment for the Development of Complex Reactive Systems // IEEE Trans. Software Eng. 1990. № 4.
Принг Э. Конечные автоматы в JavaScript, Часть 1: Разработаем виджет. http://www.ibm.com/developerworks/ru/library/wa-finitemach1/index.html
Принг Э. Конечные автоматы в JavaScript, Часть 2: Реализация виджета. http://www.ibm.com/developerworks/ru/library/wa-finitemach2/wa-finitemac_ru.html
Шалыто А.А., Туккель Н.И. От тьюрингова программирования к автоматному // «Мир ПК», –2002. № 2. http://is.ifmo.ru/?i0=works&i1=turing
Хопкрофт Д. Машины Тьюринга // В мире науки. –1984. № 7.
Карпов Ю.Г. Теория автоматов. –СПб.: Питер, –2002.
Поликарпова Н.И., Шалыто А.А. Автоматное программирование. –СПб.: Питер, –2009, 2010, 2011. 176 с. http://is.ifmo.ru/books/_book.pdf
Буч Г. Объектно-ориентированный анализ и проектирование с примерами приложений на С++. –М.: Бином, –СПб.: Невский диалект, –1998.
Лавров С.С. Программирование. Математические основы, средства, теория. –СПб.: БХВ-Петербург, –2001.
Туккель Н.И., Шамгунов Н.Н., Шалыто А.А. Ханойские башни и автоматы // Программист. Программирование. Математические основы, средства, теория. –2002. № 8.
Глушков В.М. Синтез цифровых автоматов. –М.: Физматгиз, –1962.
Гаврилов М.А., Девятков В.В., Пупырев Е.И. Логическое проектирование дискретных автоматов. –М.: Наука, –1977.
Shalyto A.A. Cognitive Properties of Hierarchical Representations of Complex Logical Structures / Proceeding of the 1995 International Symposium on Intelligent Control (ISIC). Workshop. 1995. Monterey. California.
Фогель Л., Оуэнс А., Уолш М. Искусственный интеллект и эволюционное моделирование. –М.: Мир, –1969.
Шалыто А.А. Новая инициатива в программировании. Движение за открытую проектную документацию // Информационно-управляющие системы. –2003. № 4.
Зюбин В.Е. Программирование информационно-управляющих систем на основе конечных автоматов. Новосибирск: НГУ, –2006.
Кузьмин Е.В., Соколов В.А. Моделирование, спецификация и верификация «автоматных» программ // Программирование. –2008. № 1. http://is.ifmo.ru/download/2008-03-12_verification.pdf.
Любченко В., Тяжлов Ю. Осторожно: многоядерный процессор // Открытые системы. –2007. № 6.
International Standard IEC 1131-3. Programmable controllers. Part 3. Programming languages. International Electrotechnical Commission. 1993.
Вавилов В.К., Шалыто А.А. Что плохого в неавтоматном подходе к программированию контроллеров? // Промышленные АСУ и контроллеры. –2007. № 1.
Шалыто А.А. Технология программной реализации алгоритмов логического управления как средство повышения живучести / Тезисы докладов научно-технической конференции «Проблемы обеспечения живучести кораблей и судов». –СПб.: Судостроение, –1992.
Антипов В.В., Шалыто А.А. Алгоритмизация и программирование задач логического управления техническими средствами. –СПб.: Моринтех, –1996.
Шалыто А.А. SWITCH-технология. Алгоритмизация и программирование задач логического управления // Промышленные АСУ и контроллеры. –1999. № 9.
Шалыто А.А. Автоматное проектирование программ. Алгоритмизация и программирование задач логического управления // Изв. РАН. Теория и системы управления (ТиСУ). –2000. № 6. http://is.ifmo.ru/?i0=works&i1=app-aplu&i2=1
Шалыто А. А. Реализация алгоритмов логического управления программами на языке функциональных блоков // Промышленные АСУ и контроллеры. 2000. № 4. http://is.ifmo.ru/?i0=works&i1=logctr&i2=1
Альтерман И. З., Шалыто А. А. Формальные методы программирования логических контроллеров // Промышленные АСУ и контроллеры. –2005. № 10.
Вавилов В.К., Шалыто А.А. LabVIEW и SWITCH-технология // Промышленные АСУ и контроллеры. –2006. № 6.
Сениченков Ю., Колесов Ю. Моделирование систем. Объектно-ориентированный подход. –СПб.: BXV, –2006.
Туккель Н.И., Шалыто А.А. Проектирование программного обеспечения системы управления дизель-генераторами на основе автоматного подхода // Системы управления и обработки информации. –2003. Вып. 5.
Туккель Н.И., Шалыто А.А. Применение SWITCH-технологии для программирования в событийных системах / Труды международной научно-технической конференции «Пятьдесят лет развития кибернетики», –СПб.: СПбГТУ, –1999.
Туккель Н.И., Шалыто А.А. SWITCH-технология – автоматный подход к созданию программного обеспечения «реактивных» систем // Промышленные АСУ и контроллеры. –2000. № 10.
Туккель Н.И., Шалыто А.А. SWITCH-технология – автоматный подход к созданию программного обеспечения «реактивных» систем // Программирование. –2001. № 5.
Туккель Н.И., Шалыто А.А. Программирование с явным выделением состояний //Мир ПК. –2001. № 8, 9.
Туккель Н.И., Шалыто А.А. Реализация автоматов при программировании событийных систем // Программист. –2002. № 4.
Шалыто А.А. Алгоритмизация и программирование для систем логического управления и «реактивных» систем (обзор) // Автоматика и телемеханика (АиТ). –2001. № 1. http://is.ifmo.ru/?i0=works&i1=arew&i2=1
Грэхем И. Объектно-ориентированные методы. Принципы и практика. –М.: Вильямс, –2004.
Рамбо Дж., Якобсон А., Буч Г. UML. Специальный справочник. –СПб.: Питер, –2001.
Рамбо Дж., Блаха М. UML 2.0. Объектно-ориентированное моделирование и разработка. –СПб.: Питер, –2007.
Рамбо Дж., Якобсон А., Буч Г. Унифицированные процесс разработки программного обеспечения. –СПб.: Питер, –2002.
Ауер К., Миллер Р. Экстремальное программирование: постановка процесса. СПб.: Питер, 2003.
Mellor S. et al. Executabl UML: A Foundation for Model Driven Architecture. MA: Addison-esley, 2002.
Туккель Н.И., Шалыто А.А. Объектно-ориентированное программирование с явным выделением состояний /Материалы Международной научно-технической конференции «Искусственный интеллект». Т. 1. Таганрог. ТГРУ; Донецк. Донецкий гос. ин-т искусств. интеллекта. –2002.
Туккель Н.И., Шалыто А.А. Танки и автоматы // BYTE/Россия. –2003. № 2.
Наумов Л.А., Шалыто А.А. Искусство программирования лифта. Объектно-ориентированное программирование с явным выделением состояний // Информационно-управляющие системы. –2003. № 6.
Гранд М. Шаблоны проектирования в Java. –М.: Новое знание. –2004.
Шопырин Д.Г., Шалыто А.А. Применение класса STATE в объектно-ориентированном программировании с явным выделением состояний / Труды X Всероссийской научно-методической конференции «Телематика-2003» –СПб.: СПбГИТМО (ТУ). –2003. Т. 1.
Корнеев Г. А., Шамгунов Н. Н., Шалыто А. А. Паттерн State Machine для объектно-ориентированного проектирования автоматов // Информационно-управляющие системы. –2004. № 5.
Shamgunov N., Korneev G., Shalyto A. State Machine Design Pattern /.NET Technologies 2006 – Shot Communication Papers Conference Proceedings. 4-th International Conference in Central Europe on .Net Technologies. University of West Bohemia. 2006.
Корнеев Г.А., Шамгунов Н.Н., Шалыто А.А. Язык State Machine – расширение языка Java для эффективной реализации автоматов // Информационно-управляющие системы. –2005. № 1.
Шопырин Д.Г., Шалыто А.А. Объектно-ориентированный подход к автоматному программированию // Информационно-управляющие системы. –2003. № 5.
Туккель Н.И., Шалыто А.А. Автоматное и синхронное программирование // Искусственный интеллект. –2003. № 4.
Шопырин Д.Г., Шалыто А.А. Синхронное программирование // Информационно-управляющие системы. –2004. № 3.
Гуров В.С., Мазин М.А., Шалыто А.А. Текстовый язык для автоматного программирования /XIV Всероссийская научно-методическая конференция «Телематика-2007». СПб.: СПбГУ ИТМО. –2007. Т. 2.
Степанов О.Г., Шопырин Д.Г., Шалыто А.А. Предметно-ориентированный язык автоматного программирования на базе динамического языку RUBY // Информационно-управляющие системы. –2007. № 4.
Наумов Л.А., Шалыто А.А. Методы объектно-ориентированной реализации реактивных агентов на основе конечных автоматов // Искусственный интеллект. –2004. № 4.
Naumov L., Korneev G., Shalyto A. Methods of Object-Oriented Reactive Agents Implementation on the Basis of Finite Automata /2005 International Conference on «Integration of Knowledge Intensive Multi-Agent Systems: Modeling, Exploration and Engineering» (KIMAS-05). Boston: IEEE. –2005.
Шопырин Д.Г., Шалыто А.А. Графическая нотация наследования автоматных классов // Программирование. –2007. № 5.
Вельдер С.Э., Шалыто А.А. О верификации простых автоматных программ на основе метода Model Checking // Информационно-управляющие системы. –2007. № 3.
Корнеев Г.А., Парфенов В.Г., Шалыто А.А. Верификация автоматных программ /Тезисы докладов Международной научной конференции, посвященной памяти профессора А.М. Богомолова «Компьютерные науки и технологии». Саратов: СГУ. –2007.
Гуров В.С., Шалыто А.А., Яминов Б.Р. Технология верификации автоматных моделей программ без их трансляции во входной язык верификатора / Материалы международной научно-технической мультиконференции «Проблемы информационно-компьютерных технологий и мехатроники» (ИКТМ–2007). Таганрог: НИИ МВС ЮФУ. –2007.
Вельдер С.Э., Лукин М.А., Шалыто А.А., Яминов Б.Р. Верификация автоматных программ. –СПб.: Наука, –2011.
Оршанский С.А., Шалыто А.А. Применение динамического программирования при решении задач на конечных автоматах // Компьютерные инструменты в образовании. –2007. № 4.
Лобанов П.Г., Шалыто А.А. Использование генетических алгоритмов для автоматического построения конечного автомата в задаче о флибах / 1-я Российская мультиконференция по проблемам управления. Сборник докладов четвертой научной конференции «Управление и информационные технологии». СПбГУ ЭТУ «ЛЭТИ». –2006.
Лобанов П.Г., Шалыто А.А. Использование генетических алгоритмов для автоматического построения конечных автоматов в задаче о флибах // Изв. РАН. ТиСУ. –2007. № 5.
Мандриков Е.А., Кулев В.А., Шалыто А.А. Построения автоматов с помощью генетических алгоритмов для решения задачи о флибах / Сборник X международной конференции по мягким вычислениям и измерениям. СПбГУ ЭТУ «ЛЭТИ». –2007. Т. 1.
Мандриков Е.А., Кулев В.А., Шалыто А.А. Применение генетического программирования при решении задачи о флибах // Информационные технологии. 2007. № 12.
Царев Ф.Н., Шалыто А.А. Применение генетического программирования для генерации автоматов в задаче об «умном муравье» / Сборник научных трудов. IV-я Международная научно-практическая конференция «Интегрированные модели и мягкие вычисления в искусственном интеллекте». Коломна: –2007.
Царев Ф.Н., Шалыто А.А. О построении автоматов с минимальным числом состояний для задачи об «умном муравье» /Сборник докладов X международной конференции по мягким вычислениям и измерениям. СПбГУ ЭТУ «ЛЭТИ». –2007. Т. 2.
Davydov A., Sokolov D., Tsarev F., Shalyto A. Application of Genetic Programming for Generation of Controllers Represented by Automata / Preprints of the 13th IFAC Symposium on Information Control Problems in Manufacturing. Moscow. 2009, pp. 684-689.
Aleksandrov A., Kazakov S., Sergushichev A., Tsarev F. Genetic algorithm for induction of finite automata with continuous and discrete output actions / Proceedings of the 13th annual conference companion on Genetic and evolutionary computation (GECCO '11). ACM, NY, pp. 775-778.
Поликарпова Н.И., Точилин В.Н., Шалыто А.А. Разработка библиотеки для генерации автоматов методом генетического программирования / Сборник докладов X международной конференции по мягким вычислениям и измерениям. СПбГУ ЭТУ «ЛЭТИ». –2007. Т. 2.
Поликарпова Н.И., Точилин В.Н., Шалыто А.А. Метод сокращенных таблиц для генерации автоматов с большим числом входных переменных на основе генетического программирования // Изв. РАН. ТиСУ. 2010. № 2.
Александров А.В., Казаков С.В., Сергушичев А.А., Царев Ф.Н., Шалыто А.А. Применение эволюционного программирования на основе обучающих примеров для генерации конечных автоматов, управляющих объектами со сложным поведением. // Изв. РАН. ТиСУ. –2013. № 3.
Казаков С.В., Царев Ф.Н., Шалыто А.А. Метод построения конечных автоматов верхнего уровня для управления моделью беспилотного самолета на основе обучающих примеров // Научно-технический вестник СПбГУ ИТМО. –2011. № 6.
Chivilikhin D., Ulyantsev V. Learning Finite-State Machines with Ant Colony Optimization // Lecture Notes in Computer Science. 2012. Volume 7461/2012, pp. 268-275.
Buzhinsky I., Chivilikhin D., Ulyantsev V., Tsarev F.Improving the Quality of Supervised Finite-State Machine Construction Using Real-Valued Variables / Proceedings of the 16th Genetic and Evolutionary Computation Conference companion (GECCO'14). ACM. NY, USA. 2014, pp. 1037-1040.
Чивилихин Д.С., Ульянцев В.И., Шалыто А.А. Муравьиный алгоритм для построения автоматных программ по спецификации / XII Всероссийское совещания по проблемам управления (ВСПУ-2014). ИПУ РАН. –2014.
Бужинский И.П., Ульянцев В.И., Чивилихин Д.С., Шалыто А.А. Генерация управляющих автоматов по обучающим примерам на основе муравьиного алгоритма // Изв. РАН. ТиСУ. 2014. № 2.
Бужинский И.П., Казаков С.В., Ульянцев В.И., Царев Ф.Н., Шалыто А.А. Модификация метода генерации управляющих конечных автоматов с непрерывными воздействиями по обучающим примерам // Изв. РАН. ТиСУ. –2015. № 6.
Чивилихин Д.С., Ульянцев В.И., Вяткин В.В., Шалыто А.А. Построение автоматных программ по спецификации с помощью муравьиного алгоритма на основе графа мутаций // Научно-технический вестник информационных технологий, механики и оптики. –2014. № 6.
Чивилихин Д.С., Ульянцев В.И., Шалыто А.А. Модифицированный параллельный муравьиный алгоритм для построения управляющих конечных автоматов по сценариям работы и темпоральным формулам // АиТ. –2016. № 3.
Chivilikhin D., Ulyantsev V., Tsarev F. Test-Based Extended Finite-State Machines Induction with Evolutionary Algorithms and Ant Colony Optimization / Proceedings of the 2012 GECCO Conference Companion on Genetic and Evolutionary Computation. ACM. 2012, pp. 603-606.
Chivilikhin D., Ulyantsev V. Learning Finite-State Machines: Conserving Fitness Function Evaluations by Marking Used Transition / Proceedings of the 12th International Conference on Machine Learning and Applications (ICMLA 2013). IEEE Computer Society, 2013, pp. 90-95.
Chivilikhin D., Ulyantsev V. Learning Finite-State Machines with Classical and Mutation-Based Ant Colony Optimization: Experimental Evaluation / Proceedings of the 1st BRICS countries Congress on Computational Intelligence (BRICS-CCI'13). 2013, pp. 528-533.
Chivilikhin D., Ulyantsev V., Shalyto A. Solving Five Instances of the Artificial Ant Problem with Ant Colony Optimization / Proceedings of the 2013 IFAC Conference on Manufacturing Modelling, Management and Control (MIM'13). SPb., Russia, 2013. Vol. 7. Part 1, pp. 1043-1048.
Chivilikhin D., Ulyantsev V., Shalyto A. Extended Finite-State Machine Inference With Parallel Ant Colony Based Algorithms / Proceedings of the International Student Workshop on Bioinspired Optimization Methods and their Applications (BIOMA'14). 2014, pp. 117-126.
Ulyantsev V., Tsarev F. Extended Finite-State Machine Induction using SAT-Solver / Proceedings of the Tenth International Conference on Machine Learning and Applications (ICMLA 2011). IEEE Computer Society, 2011. Vol. 2, pp. 346-349.
Ulyantsev V., Zakirzyanov I., Shalyto A. BFS-based Symmetry Breaking Predicates for DFA Identification / Proceedings of the 9th International Conference on Language and Automata Theory and Applications (LATA-2015). 2015, pp. 611-622.
Ulyantsev V., Zakirzyanov I., Shalyto A. Symmery Breaking Predicates for SAT-based DFA Identification. Cornell University Library. 2016. http://arxiv.org/abs/1602.05028.
Ульянцев В.И. Генерация конечных автоматов с использованием программных средств решения задач выполнимости и удовлетворения ограничений. Автореферат диссертации на соискание ученой сткпени кандидата технических наук. –СПб.: Университет ИТМО, –2015. http://is.ifmo.ru/disser/ulyantsev-synopsis.pdf.
Tsarev F., Egorov K. Finite State Machine Induction Using Genetic Algorithm Based on Testing and Model Checking / Proceedings of the 13th annual conference companion on Genetic and evolutionary computation (GECCO '11). ACM. NY, pp. 759-762.
Chivilikhin D., Ulyantsev V., Shalyto A. Combining Exact and Metaheuristic Techniques for Learning Extended Finite-State Machines from Test Scenarios and Temporal Properties / Proceedings of the 13th International Conference on Machine Learning and Applications (ICMLA'14). 2014, pp. 350-355.
Chivilikhin D., Ivanov I., Shalyto A. Inferring Temporal Properties of Finite-State Machine Models with Genetic Programming / Proceedings of Genetic and Evolutionary Computation Conference. 2015, pp.1185-1188.
Ulyantsev V., Buzhinsky I., Shalyto A. Exact Finite-State Machine Identification from Scenarios and Temporal Properties. Cornell University Library. 2016. http://arxiv.org/abs/1601.06945.
Zakonov A. Stepanov O. Shalyto A. A GA-based approach for test generation for automata-based programs / Proceedings of 4th Spring/Summer Young Researchers' Colloquium on Software Engineering (SYRCoSE 2010). Nizhny Novgorod, pp. 37-42. http://is.ifmo.ru/works/_syrcose_zakonov_text.pdf.
Zakonov A., Stepanov O., Shalyto A. GA-based and Design by Contract Approach to Test Generation for EFSMs / Proceedings of IEEE East-West Design & Test Symposium (EWDTS’10). St. Petersburg. 2010, pp.152-155. http://is.ifmo.ru/works/_ewdts_2010_zakonov.pdf1.
Ульянцев В., Шалыто А. О сложности верификации простых автоматов http://is.ifmo.ru/works/2013/ulyantsev-shalyto-verification.pdf.
Царев Ф.Н., Шалыто А.А. Применение генетического программирования для построения мультиагентной системы одного класса / Материалы международной научно-технической мультиконференции «Проблемы информационно-компьютерных технологий и мехатроники» (ИКТМ-2007). Таганрог: НИИ МВС ЮФУ. –2007.
Paraschenko D., Tsarev F., Shalyto A. Modeling Technology for One Class of Multi-Agent Systems with Automata Based Programming / Proceedings of 2006 IEEE International Conference on Computational Intelligence for Measurement Systems and Application (IEEE CIMSA- 2006). Spain, 2006.
Шалыто А.А. Технология автоматного программирования /Труды первой Всероссийской научной конференции «Методы и средства обработки информации». –М.: МГУ. –2003.
Korneev G.A., Shalyto A.A. State-Driven Programming /Материалы Евразийского научного симпозиума. Корея. Сеул. Политехнический университет. –2007. www.eurasia.re.kr.
Шалыто А.А. Автоматное программирование / Тезисы докладов Международной научной конференции, посвященной памяти профессора А.М. Богомолова «Компьютерные науки и технологии». Саратов: СГУ. –2007.
Шалыто А.А. Технология автоматного программирования // Мир ПК. –2003. № 10.
Головешин А. Использование конвертора Visio2Switch. http://is.ifmo.ru.
Канжелев С.Ю., Шалыто А.А. Автоматическая генерация автоматного кода // Информационно-управляющие системы. –2006. № 6.
Канжелев С.Ю., Шалыто А.А. Преобразование графов переходов, представленных в формате MS Visio, в исходные коды программ для различных языков программирования (инструментальное средство MetaAuto). Университет ИТМО. –2005. http://is.ifmo.ru/projects/metaauto/.
List of state machine CAD tools.
Шалыто А.А. О проекте «Технология автоматного программирования: применение и инструментальные средства» // Информационные технологии. –2006. № 2.
Гуров В.С., Мазин М.А., Нарвский А.С., Шалыто А.А. Разработка UML. SWITCH-технология. Eclipse // Информационно-управляющие системы. –2004. № 6.
Gurov V.S., Mazin M.A., №arvsky A.S., Shalyto A.A. UniMod: Method and Development of Reactive Object-Oriented Programs with Explicit States Emphasis /Proceedings 2005 of St. Petersburg IEEE Chapters. International Conference «110 Anniversary of Radio Invention SPb ETU «LETI». 2005.
Гуров В.С., Мазин М.А., Шалыто А.А. Ядро автоматного программирования / Свидетельство об официальной регистрации программы для ЭВМ. № 2006 613249 от 14.09.2006.
Гуров В.С., Мазин М.А., Шалыто А.А. Встраиваемый модуль автоматного программирования для среды разработки / Свидетельство об официальной регистрации программы для ЭВМ. № 2006 613817 от 07.11.2006.
Гуров В.С., Мазин М.А., Нарвский А.С., Шалыто А.А. Инструментальное средство для поддержки автоматного программирования // Программирование. –2007. № 6.
Гуров В.С., Нарвский А.С., Шалыто А.А. Исполняемый UML из России // PC Week/RE. –2005. № 26.
Ricca F., Leotta M., Reggio G., Tiso A., Guerrini G., Torchiano M. Using UniMod for Maintenance Tasks: An Experimental Assessment in the Context of Model Driven Development /34th International Conference on Software Engineering (ICSE). 4th International Workshop of Modeling in Software Engineering (MISE). http://softeng.disi.unige.it/publications/2012-ricca-MiSE.pdf.
Шалыто А.А., Янкин Ю.Ю. Автоматное программирование ПЛИС в задачах управления электроприводом //Информационно-управляющие системы. –2011. № 1.
Янкин Ю.Ю., Шалыто А.А. Метод создания программного обеспечения модулей, выполненных на основе программируемых логических интегральных схем // Системы управления и обработки информации. –2013. Вып. 26.
Янкин Ю.Ю., Шалыто А.А. Разработка резервированного блока управления электроприводом на основе автоматного подхода // Научно-технический вестник информационных технологий, механики и оптики. –2014. № 6.
Янкин Ю.Ю., Шалыто А.А. Метод создания программного обеспечения модулей, выполненных на основе программируемых логических интегральных схем (видео-презентация в формате exe) http://is.ifmo.ru/present/2012/Yankin-Shalyto-PLIS.exe.
Ведерников Н.В., Демьянюк В.Ю., Кротков П.А., Ульянцев В.И., Шалыто А.А. Применение методов машинного обучения для автоматизированного построения управляющих автоматов в высокоуровневых средствах проектирования систем / XII Всероссийское совещания по проблемам управления (ВСПУ-2014). ИПУ РАН. –2014. http://is.ifmo.ru/works/2014/2014_VSPU_Vedernikov_et_al.pdf.
Беляев А.В., Суясов Д.И., Шалыто А.А. Компьютерная игра «Космонавт». Проектирование и реализация // Компьютерные инструменты в образовании. –2004. № 4.
Корнеев Г.А., Петрошенко П.А., Шалыто А.А. Реализация игры «Морской бой» на основе автоматного подхода // Компьютерные инструменты в образовании. –2005. № 6.
Гуров В.С., Нарвский А.С., Шалыто А.А. ICQ и автоматы // Технология «Клиент-Сервер». –2004. № 3.
Мазин М.А., Парфенов В.Г., Шалыто А.А. Анимация. FLASH-технология. Автоматы // Компьютерные инструменты в образовании. –2003. № 4.
Салмре И. Программирование мобильных устройств на платформе .Net Compact Framework. –М.: Вильямс. –2006. http://is.ifmo.ru/automata/mobdev/.
Naumov L., Shalyto A. Automata Theory for Multi-Agent Systems Implementation / International Conference on «Integration of Knowledge Intensive Multi-Agent Systems: Modeling, Exploration and Engineering». (KIMAS-03). Boston: IEEE. 2003.
Yartsev B., Korneev G., Kotov V., Shalyto A. Automata-Based Programming of the Reactive Multi-Agent Control Systems / 2005 International Conference on «Integration of Knowledge Intensive Multi-Agent Systems: Modeling, Exploration and Engineering» (KIMAS-05). Boston: IEEE. 2005.
Кретинин А.В., Солдатов Д.В., Шостак А.В., Шалыто А.А. Ракеты. Автоматы. Нейронные сети // Нейрокомпьютеры: разработка и применение. –2005. № 5.
Сайт по автоматному программированию. http://is.ifmo.ru.
Кормен Т., Лейзерсон Ч., Ривест Р. Алгоритмы. Построение и анализ. –М.: МЦНМО, –1999.
Лобанов П.Г., Шалыто А.А. Подсчет длины слов в строке // Мир ПК. –2005. № 7.
Корнеев Г.А., Шамгунов Н.Н., Шалыто А.А. Обход деревьев на основе автоматного подхода // Компьютерные инструменты в образовании. –2004. № 3.
Туккель Н.И., Шалыто А.А. Реализация вычислительных алгоритмов на основе автоматного подхода // Телекоммуникации и информатизация образования. –2001. № 6.
Туккель Н.И., Шалыто А.А. Преобразование итеративных алгоритмов в автоматные // Программирование. –2002. № 5.
Туккель Н.И., Шамгунов Н.Н., Шалыто А.А. Реализация рекурсивных алгоритмов на основе автоматного подхода // Телекоммуникации и информатизация образования. –2002. № 5.
Казаков М.А., Корнеев Г.А., Шалыто А.А. Метод построения логики работы визуализаторов алгоритмов на основе конечных автоматов // Телекоммуникации и информатизация образования. –2003. № 6.
Корнеев Г.А., Шалыто А.А. Преобразование программ в систему взаимодействующих конечных автоматов / Труды Второй Всероссийской научной конференции «Методы и средства обработки информации». –М.: МГУ. –2005.
Казаков М.А., Шалыто А.А. Иcпользование автоматного программирования для реализации визуализаторов // Компьютерные инструменты в образовании. –2004. № 2.
Казаков М.А., Шалыто А.А. Реализация анимации при построении визуализаторов алгоритмов на основе автоматного подхода // Информационно-управляющие системы. –2005. № 4.
Корнеев Г.А., Шалыто А.А. VIZI – язык описания визуализаторов алгоритмов // Научно-технический вестник СПбГУ ИТМО. Высокие технологии в оптических и информационных системах. –2005. Вып. 23.
Корнеев Г.А., Шалыто А.А. Построение визуализаторов алгоритмов дискретной математики // Научно-технический вестник СПбГУ ИТМО. Высокие технологии в оптических и информационных системах. –2005. Вып. 23.
Zakonov A., Shalyto A. Automatic Extraction and Verification of State-Models for Web Applications // Lecture Notes in Electrical Engineering. 2012. V.133. Part 1, pp. 157-160.
Pang C., Patil S., Yang C., Vyatkin V., Shalyto A. A Portability Study of IEC 61499: Semantiac and Tools / Proceedings of the 12th IEEE International Conference on Industrial Informatics (INDIN'14). 2014, pp.440-445.
Chivilikhin D., Shalyto A., Vyatkin V. Inferring Automata Logic From Manual Control Scenarios: Implementation in Function Blocks / Proceedings of the 13th IEEE International Symposium on Parallel and Distributed Processing with Applications (ISPA'15). 2015, pp. 307-312.
Chivilikhin D., Shalyto A., Patil S., Vyatkin V. Reconstruction of Function Block Logic using Metaheuristic Algorithm: Initial Explorations / Proceedings of the 13th IEEE International Conference on Industrial Informatics (INDIN'15). 2015, pp. 1239-1242.
Chivilikhin D., Ivanov I., Shalyto A., Vyatkin V. Reconstruction of Function Block Controllers Based on Test Scenarios and Verification / Proceedings of the 14th IEEE International Conference on Industrial Informatics (INDIN'16). 2016, pp.646-651.
Chivilikhin D. Experimental Study of Automated Offline Parameter Tuning on the Example of irace and the Traveling Salesman Problem / Proceeding of the 18th Genetic and Evolutionary Computation Conference (GECCO 2016). Companion, 2016, pp.45, 46.
Pang C., Pakonen A., Buzhinsky I., Vyatkin V. A Study on User-Friendly Formal Specification Languages for Requirements Formalization / Proceedings of the 14th IEEE International Conference on Industrial Informatics (INDIN 2016), 2016, pp. 676-682.
Buzhinsky I., Vyatkin V. Plant Model Inference for Closed-Loop Verification of Control Systems: Initial Explorations. IEEE International Conference on Industrial Informatics (INDIN 2016). 2016, pp. 736-739.
«Селма-2». Описание функциональных блоков. АББ Стромберг Драйвс, 1989.
Project 15640. AS 21.DG1. CONTROL. АМИЕ. 95564.12M. St. Petersburg. ASS «Avrora», 1991.
Functional Description. Warm-up & Prelubrication logic. Generator Control Unit. Severnaya Hull № 431. Norcontrol, 1993.
Autolog 32. Руководство пользователя. FF-Automation.
Шалыто А.А. Триединая задача одного педагогического эксперимента в области IT-образования // Инженерное образование. –2007. № 4.

Дополнительные материалы

Автоматное программирование. Обзорная статья.

Об авторе: докт. техн. наук, профессор, Университет ИТМО
Помещена в музей с разрешения автора 28 января 2019