Задача 1. Напишите программу, моделирующую работу автомата с четырьмя внутренними состояниями. Диаграмма Мура задана. На вход автомата поступает последовательность символов "baba ... acbb".

Рис. 1. Диаграмма Мура автомата с четырьмя состояниями.

Автомат - это дискретное устройство, имеющее конечное множество внутренних состояний Q={q1, q2, ...} и преобразующее входные сигналы (символы) X={x1, x2, ...} в выходные сигналы (символы) Y={y1, y2, ...} в соответствии с определенными правилами, задаваемыми функцией перехода и функцией выходов. Для задания автомата строят диаграмму Мура, которая представляет собой ориентированный граф. Вершины графа изображают состояния автомата Q={1, 2, 3, 4}. Каждой команде соответствует ребро, идущее из qi в qj. Из диаграммы на рис. 1 видно, что если автомат находится в состоянии 2, на вход поступает символ "c", то автомат переходит в состояние 4, на выходе получается символ A. Компьютерная программа ПР-1 моделирует работу автомата с четырьмя внутренними состояниями, на вход которого поступает последовательность символов S:="baba ... acbb". При ее работе на экране появляется номер состояния автомата, символ на его выходе в результате первого, второго, третьего ... шага.

Программа ПР-1.

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

Рис. 2. Диаграмма Мура автомата с двумя состояниями.

Рассмотрим абстрактную модель ученика, представляющую собой вероятностный автомат с двумя состояниями. При переходе из одного состояния в другое автомат как бы выполняет некоторую операцию (действие). Будем считать, что автомат обучен, когда из состояния 1 он переходит в состояние 2, а из состояния 2 - в состояние 1 и т.д.: 1-2-1-2-1-2-... Если из состояния 1 автомат переходит в состояние 1 или из состояния 2 переходит в состояние 2, то он совершает ошибку. Вероятность правильного действия обозначим через p, тогда вероятность неправильного действия равна q = 1 - p. В принципе можно изучать работу вероятностного автомата с большим числом состояний, но при этом всегда один из переходов будет правильным, а остальные - неправильными.

Изначально автомат не обучен. Пусть он может совершить 100 различных операций с равными вероятностями, тогда вероятность правильного действия p=0.01. Программа ПР-2, моделирующая ученика, содержит цикл, в котором выбор каждой операции осуществляется с помощью генератора случайных чисел. Если случайное число x, находящееся в интервале [0;1], меньше p, то АМУ совершает правильное действие, если нет - делает ошибку. Процесс обучения приводит к изменению матрицы вероятностей: вероятность правильного выбора p увеличивается на a*q, где a - коэффициент научения, а вероятность ошибки уменьшается на ту же величину. Уровень знаний Z будем считать равным вероятности p правильного перехода.

Чтобы учесть забывание необходимо на каждом временном шаге уменьшать p на g*p (g - коэффициент забывания) и на такую же величину увеличивать q:

p:=p-g*p; q:=q+g*p; {забывание}

Программа позволяет промоделировать ситуации:

Обучение с поощрением: при выполнении правильного действия ученика "поощряют", пересчитывая вероятности p и q. Так как сначала ученик ошибается гораздо чаще (q превосходит p), то сначала обучение происходит медленно (рис. 2). Зато по мере увеличения "знаний" вероятность совершения правильного действия растет. Акты обучения происходят все чаще, вероятность p увеличивается до 1. Программа содержит строку:

If (x<p)and(t<4000) then 
begin p:=p+a*q; q:=q-a*q; end;

Обучение с наказанием: в случае ошибки ученика "наказывают", подсказывая ему правильный ответ, что приводит к росту p и уменьшению q. Сначала ученик ошибается часто, поэтому уровень его "знаний" быстро растет, вероятность ошибки q падает (рис. 3). Акты обучения происходя реже, вероятность правильного действия не достигает 1 (за счет забывания). Программа содержит строку:

If (x>p)and(t<4000) then 
begin p:=p+a*q; q:=q-a*q; end;

Обучение с поощрением и наказанием: при правильном ответе ученика поощряют, а при неправильном - наказывают, подсказывая правильный ответ. В обоих случаях вероятность правильного действия p растет, а вероятность ошибки снижается. За счет того, что при любом действии учащегося его учат, уровень знаний быстро растет и достигает 1 (рис. 4). Программа содержит строку:

If t<4000 then begin p:=p+a*q; q:=q-a*q; end;

Программа ПР-2.

Рис. 3. Обучение с поощрением

Рис. 4. Обучение с наказанием

Рис. 5. Обучение с поощрением и наказанием

Рассмотрим другой вариант решения задачи (программа ПР-3). В процедуре Uchenik случайным образом (исходя из матрицы вероятностей) производится переход в следующее состояние. В процедуре Obuchenie осуществляется пересчет вероятностей переходов из одного состояния в другое, в процедуре Zabyvan различие между вероятностями правильных и неправильных переходов уменьшается. На экране получаются графики зависимости уровня знаний от времени при различных коэффициентах научения и забывания (рис. 5).

Программа ПР-3.

Рис. 6. Кривые обучения

Задача 3. Промоделируйте работу гомеостата Эшби - адаптирующегося устройства с тремя степенями свободы x1, x2, x3, которое при выводе из положения равновесия (0,0,0) самостоятельно в него возвращается.

Гомеостат описывается тремя диффуравнениями:

Программа ПР - 4 для нахождения коэффициентов a_i,j, определяющих работы гомеостата, работает так. Значения a_i,j и x_j задаются случайным образом. Вычисляются скорости v₁, v₂, v₃ и координаты x₁, x₂, x₃ в последовательные моменты времени. Если модуль хотя бы одной из координат превысил 1, то коэффициенты a_i,j изменяются случайным образом. Так продолжается до тех пор, пока система не вернется в положение равновесия (0,0,0). Найденные значения коэффициентов a_i,j печатаются в файл. На рис. 7 показана фазовый портрет гомеостата на этпе подбора коэффициентов.

Программа ПР-4.

Рис. 7. Подбор параметров гомеостата

В результате работы программы ПР-4 рассчитываются коэффициенты a_i,j, при которых гомеостат находится в положении равновесия (0,0,0). Эта задача имеет несколько решений. Допустим, получились следующие значения:

После того, как найдены оптимальные параметры гомеостата, можно исследовать, как ведет себя гомеостат при выводе его из положения равновесия. В программе ПР-5, содержащей оптимальные параметры, случайным образом задаются начальные координаты x₁, x₂, x₃ из интервала [-0,9; 0,9] и рассчитывается "поведение" гомеостата в последующие моменты времени. Во всех случаях гомеостат возвращается в положение равновесия (рис. 8).

Программа ПР-5.

Рис. 8. Функционирование гомеостата.

Задача 4. Промоделируйте игру "Жизнь". Плоская поверхность разбита на клетки, ведущие себя, как автоматы, способные находиться в двух состояниях: "живой" и "мертвый". Клетка оживает при наличии 3 живых соседей. Если живых соседей 4 и больше, она умирает от перенаселенности. Если живых соседей меньше 2, она умирает от одиночества.

Представим двумерную сетку, в каждом узле - автомат, реализующий заданное правило. Используется программа ПР - 6. Состояния клеток закодированы так: клетка "жива" - 1, "мертва" - 0. Вычисление числа "живых" соседей и установление, "жива" данная клетка или нет на следующем временном шаге, осуществляется в процедуре Raschet и записывается в массив x[i, j]. В массив x1[i, j] записывается состояние клеток на предыдущем временном шаге. В начале программы следует задать исходное распределение "живых" клеток.

Программа ПР-6.

Задача 5. Промоделируйте распространение автоволн в двумерной активной среде. Изучите однорукавную и двурукавную автоволны, подавление высокочастотного источника низкочастотным, дифракцию автоволн.

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

Рассмотрим обобщенную модель Винера - Розенблюта. Пусть состояние каждого элемента в момент t описывается фазой y_i,j^t, и концентрацией активатора u_i,j^t. Если элемент находится в покое, то будем считать, что y_i,j^t=0. Если вследствие близости возбужденных элементов концентрация активатора u_i,j^t достигает порогового значения h, то элемент возбуждается и переходит в состояние 1. Затем на следующем шаге он переключается в состояние 2, затем - в состояние 3 и т.д., оставаясь при этом возбужденным. Достигнув состояния r, элемент переходит в состояние рефрактерности. Через s (s>r) шагов после возбуждения элемент возвращается в состояние покоя:

Будем считать, что при переходе из состояния s в состояние покоя 0 концентрация активатора становится равной 0. При наличии соседнего элемента, находящегося в возбужденном состоянии, она увеличивается на 1. Можно ограничиться учетом ближайших восьми соседних элементов. Используется программа ПР-7, получающиеся результаты представлены на рис. 9 и 10.

Программа ПР-7.

Рис. 9. Однорукавная и двурукавная автоволны.

Рис. 10. Подавление низкочастотного источника высокочастотным. Дифракция автоволн.

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

Рис. 11. Струя жидкости, наполняющая сосуд

Рассмотрим струю вязкой жидкости, падающую в сосуд (рис. 11). Будем различать три области: 1) собственно струя, то есть область, включающая падающие вниз частицы жидкости; 2) область, включающая часть жидкости, которая растекается в горизонтальном направлении; 3) область, включающая неподвижные частицы жидкости, полностью заполняющие горизонтальные строки матрицы ai,j. Промоделируем это явление с помощью двумерных клеточных автоматов. Разобьем плоскость на клетки с координатами i и j (ось i направим вправо, ось j - вверх) и введем двумерный массив ai,j. Будем считать, что если клетка пустая, то ai,j=0, если в клетке имеется жидкость, то ai,j=1. Препятствия, дно и стенки сосуда состоят из клеток, для которых xi,j=-2 (можно было бы присвоить значение -1, но в этом случае произведение двух элементов массива ai,j равно 1, когда эти элементы равны 1 или -1, что неудобно). Если произведение a13,24 и a13,25 равно 1, то в обоих клетках находится жидкость.

Рис. 12. Опускание частиц жидкости.

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

Если a[i,j]=1 (жидкость), то
1. Если a[i,j-1]=0, то a[i,j-1]:=1, a[i,j]:=0;
2. Если a[i,j]=1 и a[i-1,j-1]=0 и a[i+1,j-1]=0, 
             то a[i,j]:=0 и с вероятностью 0,5 
               a[i-1,j-1]:=1 или a[i+1,j-1]:=1;
3. Если a[i-1,j-1]=0 и a[i+1,j-1]=1, 
                  то a[i-1,j-1]:=1, a[i,j]:=0;
4. Если a[i+1,j-1]=0 и a[i-1,j-1]=1, 
                  то a[i+1,j-1]:=1, a[i,j]:=0;

Если a[i,j]*a[i+1,j]*a[i+2,j-1]=1 и a[i+1,j-1]=0, то
                            a[i+1,j-1]:=1, a[i,j]:=0;
Если a[i,j]*a[i-1,j]*a[i-2,j-1]=1 и a[i-1,j-1]=0), то
                            a[i-1,j-1]:=1, a[i,j]:=0;
Если a[i,j]*a[i+1,j]*a[i+2,j+1]=1 и a[i+1,j+1]=0, то
                            a[i+1,j+1]:=1, a[i,j]:=0;
Если a[i,j]*a[i-1,j]*a[i-2,j+1]=1 и a[i-1,j+1]=0, то
                            a[i-1,j+1]:=1, a[i,j]:=0;

Если a[i,j]=1 и (a[i,j-1]=-2 или a[i,j-2]=-2 или
a[i,j-3]=-2 или a[i,j-4]=-2), то с вероятностью 0,1
смещать элемент по горизонтали влево или вправо до 
первой пустой клетки;