Информатика и выч. техника \ Информатика

Программа как математический объект: Методические указания для самостоятельного изучения темы и выполнения РГР, страница 6

[Символ ©-- маркер начала цепочки; ª -- маркер конца цепочки]

[Удобно искать подцепочку yyR, начиная с конца, т.к. в этом случае можно не обращать внимание на x]

sequence S

scalar success: bool[success ----- истина, если цепочка SÎL; исходное состояние - ложь]

queue b [записывается копия цепочки yR]

stacka   [записывается  цепочки yR]

success := false; a:= empty; b:= empty;

[найти конец цепочки  S= S+|| Æ]

while current (S) ¹ ª do

        next( S)              od [S= S+|| Æ]

[установить  указатель на последний символ]

backspace(S) [S =T-(S+) || H-(S+) + S-]

[основной цикл поиска цепочки yyR]

[инвариант S= S+||S-  Ù Ø( S = Æ || S- Ù success)]

while current (S) ¹ © ÙØ success do

top (a) := current (S); end(b) := current (S)

back(S)

[проверить y = yR]

while current (S) = top(a) Ù a ¹ empty do

back(S) od ;[a = empty Ú current (S) ¹ top(a)]

if a = empty then [ стек пуст, значит есть подцепочка yyR и SÎL]

  success := true else [ восстановить стек и продолжить поиск yyR]

restore(a, b) fi od

proc restore( alt a, b )

a := empty

while b¹ empty do

top(a) := end(b) od

corp

2.  Проектирование с помощью конечных автоматов

2.1 Новые технологии

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

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

- логическая завершенность. Функция (модуль) должна реализовывать логически законченный, целостный алгоритм ;

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

- замкнутость. Функция (модуль) не должна использовать глобальные данные, иметь " связь с внешним миром" помимо программного интерфейса, не должна содержать ввода и вывода результатов во внешние потоки - результаты должны быть размещены в структурах данных ;

- универсальность. Функция (модуль) должна быть универсальна, параметры процесса обработки и сами данные должны передаваться извне, а не должны подразумеваться или устанавливаться постоянными ;

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

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

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


2.2 Семантика конечных автоматов

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

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

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

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

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

Целевое состояние – состояние, которое активизируется после завершения перехода.

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

Пример сложного сторожевого условия:
Скачать файл