Области применения

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

Контрольная работа №2

Автомат должен выполнять три алгоритма U ₁, U ₂ и U ₃ в зависимости от значений набора логических условий r₁, r₂. Первый оператор алгоритмов А₀ – инициализация массива и его индекса. Нумерация элементов массива с 1 до 10. Последний оператор алгоритмов А_к – вывод искомого значения на экран.

Построить граф-схемы и матричные схемы исходных алгоритмов, ЛСА минимизированного объединенного алгоритма U _об, в котором отсутствуют повторяющиеся операторы и минимально число логических условий. Проверить выполнение каждого из алгоритмов в объединенном алгоритме, подставляя значения соответствующих r₁ и r₂ .

1 вариант:

U ₁ – вывести минимум массива.

U ₂ – вывести номер третьего эл-та массива, большего 5, или 0, если его нет.

U ₃ – вывести сумму положительных элементов массива.

2 вариант:

U ₁ – вывести среднее арифметическое элементов массива.

U ₂ – вывести номер предпоследнего эл-та массива, большего 5, или 0, если его нет.

U ₃ – вывести разность между максимальным и минимальным элементом массива.

В соответствии с классификацией, введенной Д. Харелом, любую программную систему можно отнести к одному из следующих классов.

- Трансформирующие системы осуществляют некоторое преобразование входных данных, и после этого завершают свою работу. В таких системах, как правило, входные данные полностью известны и доступны на момент запуска системы, а выходные – только после завершения ее работы. К трансформирующим системам относятся, например, архиваторы и компиляторы.

- Интерактивные системы взаимодействуют с окружающей средой в режиме диалога (например, текстовый редактор). Характерной особенностью таких систем является то, что они могут контролировать скорость взаимодействия с окружающей средой – заставлять среду «ждать».

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

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

Другая традиционная область использования автоматов – задачи логического управления – является подклассом реактивных систем. Здесь автомат – это, на первый взгляд, совсем другое устройство. У него несколько параллельных входов (чаще всего двоичных), на которые в режиме реального времени поступают сигналы от окружающей среды. Обрабатывая эти сигналы, автомат формирует значения нескольких параллельных выходов.

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

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

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

Сущность с простым поведением (слева) и со сложным поведением (справа)

Рассмотрим в качестве примера электронные часы. Пусть у них имеется только две кнопки, которые служат для установки текущего времени: кнопка «H» (Hours) увеличивает на единицу число часов, а кнопка «M» (Minutes) – число минут. Увеличение происходит по модулю 24 и 60 соответственно. Такие часы обладают простым поведением, поскольку каждое из двух входных воздействий (нажатие первой или второй кнопки) приводит к единственной, заранее определенной реакции часов.

Электронные часы

Рассмотрим теперь электронные часы с будильником. Дополнительная кнопка «A» (Alarm) служит в них для включения и выключения будильника. Если будильник выключен, то кнопка «A» включает его и переводит часы в режим, в котором кнопки «H» и «M» устанавливают не текущее время, а время срабатывания будильника. Повторное нажатие кнопки «A» возвращает часы в обычный режим. Наконец, нажатие кнопки «A» в обычном режиме при включенном будильнике приводит к выключению будильника.

Электронные часы с будильником

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

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

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

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

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

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

Дата добавления: 2015-05-26