Моделирование процессов

 

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

-             процесс, в котором переходы выполняются под влиянием некоторых внешних воздействий. Этот процесс называется автоматом;

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

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

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

 

Конечные автоматы

 

Что такое автомат, будем определять постепенно. Пусть заданы:

М — конечное непустое множество, элементы которого называются состояниями автомата,

А — конечное непустое множество внешних воздействий на автомат, В — множество ответов автомата на внешние воздействия.

Обычно множество А называется входным алфавитом автомата, а множество В — выходным алфавитом.

Автомат — это процесс, который рассматривается в дискретные моменты времени (такты работы) и в каждый момент времени получает внешние воздействия. В зависимости от воздействия и текущего состояния процесса переходит в новое состояние и вырабатывает свой ответ.

Первоначально, в нулевом такте, автомат находится в некотором заданном начальном состоянии i0 Î М. Каждый следующий такт t начинается с того, что в автомат поступает некоторый элемент аt множества A и, в зависимости от этого элемента и текущего состояния процесса it-1 процесс переходит в новое состояние it. Попутно вырабатывается действие автомата bt. Таким образом, в канонических терминах автомат переводит входную строку алфавита А в выходную строку алфавита В.

Правила перехода автомата в новое состояние и выработки им действий определяются в простейшем случае таблицами. Есть более удобные и компактные способы задания правил, но сейчас нам важна не форма зависимости, а набор параметров, определяющий выбор. Итак, пусть правила перехода в новое состояние и выбора действия определяются отображениями Т: М ´ А ® М и D:М ´ А®  В.

Рассмотрим несколько простых примеров.

Пример1. Сканирующий автомат. Задается последовательность символов, в которой требуется выделить запись целого числа (в десятичной системе счисления). Эта запись состоит из последовательности цифр, которая окаймлена нецифровыми символами (кроме знаков - и +, которые могут войти в запись числа, и знака . (точка), который использовать запрещено). Сознаюсь, что я сам выбрал представление числа, в котором запрещено многократное появление знаков - и + и появление точки.

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

Итак, можно выделить следующие состояния автомата:

S0       — состояние начальной готовности — нет еще никакой информации о сканируемом числе, если какие-либо символы и поступили, то они не были использованы;

S1       — состояние чтения числа — прочтен символ - или +, который определяя знак и сделал некорректным появление любого символа кроме цифры;

S2       — состояние чтения числа — прочтена хотя бы одна цифра.

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

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

Теперь можно составить таблицу переходов (левая таблица):

 

 

Ц

З

П

 

 

Ц

З

П

S0

S2

S1

S0

 

S0

D2

D1

D0

S1

S2

S0

S0

 

S1

D3

D4

D5

S2

S2

S0

S0

 

S2

D3

D4

D6

 

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

DO — начальное сканирование — ничего не делать;

DI — прочтен знак числа — установить нулевое значение числа и знаковый, множитель, зависящий от прочтенного символа;

D2 — прочтена первая цифра — установить знаковый множитель, равный +1, и начальное значение числа по прочтенной цифре;

D3 — прочтена очередная цифра — пересчитать значение числа по прочтенной цифре, т.е. умножить на 10 и прибавить цифру;

D4 — прочтен знаковый символ, который уже не нужен — это ошибка;

D5 — прочтен посторонний символ, до того как начато .чтение числа;

D6 — прочтен посторонний символ, завершивший чтение числа, — выдать в качестве результата произведение числа на знаковый множитель.

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

 

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

7,11,12,13,14,23,27,28,32,33,34,35,36,43

должен выглядеть так:

7,11-14,23,27,28,32-36,43.

На вход автомата поступает последовательность символов из такого трехбуквенного алфавита:

Начало   группы   (Н),   Продолжение   группы   (П),   Конец   данных   (К).

В нашем примере последовательность чисел превращается в последовательность букв входного алфавита:

н,н,п,п,п,н,н,п,н,п,п,п,п,н,к.

Автомат имеет следующие состояния:

S0— начальное состояние;

S1— прочтено начало группы;

S2— группа содержит два числа;

S3— группа содержит больше чем два числа.

Таблицы переходов и действий:

 

 

Н

П

К

 

 

Н

П

К

S0

S1

S0

S0

 

S0

D1

D0

D0

S1

S1

S2

S0

 

S1

D2

D3

D4

S2

S1

S3

S0

 

S2

D5

D3

D6

S3

S1

S3

S0

 

S3

D7

D3

D8

 

Переходы достаточно ясны. Опишем действия:

D0 — ошибка, в нулевом состоянии может появиться только начало группы;

D1 — запомнить поступившее начало группы;

D2 — напечатать имеющееся начало группы и запятую, затем выполнить действие D1;

D3 — запомнить поступившее число как конец группы;

D4 — напечатать имеющееся начало группы и точку;

D5 — напечатать имеющуюся группу из двух чисел и запятую, затем выполнить действие D1;

D6 — напечатать имеющуюся группу из двух чисел и точку;

D7 — напечатать имеющуюся группу и запятую, затем выполнить действие D1;

D8 — напечатать имеющуюся группу и точку.

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

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

 

_ 111      а 010      и 000      е 1100      о 1000      м 0110       н 0010     

к 0011      в 11010     л 10100     д 10101    т 10010     р 10011     э 110110      с 101100     б 101101    п 011110     и 011100     у 011101      х 1101110    ш 1101111    ы 1011110       ч 1011111    ж 1011100    ю 1011101   

я 0111110     ь 0111111

и кодовое дерево, изображенное на рисунке. Знак пробела на рисунке изображен звездочкой. Чтобы получить из этого дерева граф переходов автомата,

 

 

 Рисунок1.jpg

 

Кодовое дерево.

 

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

 

 

0

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

0

1

2

и

н

а

м

7

й

п

я

11

12

о

т

15

л

17

с

19

ж

ы

22

е

в

з

х

1

10

4

3

к

5

6

8

у

9

ь

21

14

13

р

16

д

18

б

20

ю

ч

_

23

24

25

ш

 

где для простоты число обозначает новое состояние автомата, а другой знак — 1 вырабатываемый символ и 0— как новое состояние.

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

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