Дискретно - детерминированные модели (F-схемы) - Виды математических моделей
Дискретно - детерминированные модели (ДДМ) являются предметом рассмотрения теории автоматов (ТА). ТА - раздел теоретической кибернетики, изучающей устройства, перерабатывающие дискретную информацию и меняющего свои внутренние состояния лишь в допустимые моменты времени.
Конечный автомат имеет множество внутренних состояний и входных сигналов, являющихся конечными множествами. Автомат задается F - схемой:
F=<z, x,y,,,z0>,
Где z, x,y - соответственно конечные множества входных, выходных сигналов (алфавитов) и конечное множество внутренних состояний (алфавита). z0Z - начальное состояние; (z, x) - функция переходов; (z, x) - функция выхода. Автомат функционирует в дискретном автоматном времени, моментами которого являются такты, т. е. примыкающие друг к другу равные интервалы времени, каждому из которых соответствуют постоянные значения входного, выходного сигнала и внутреннего состояния. Абстрактный автомат имеет один входной и один выходной каналы.
В момент t, будучи в состоянии z(t), автомат способен воспринять сигнал x(t) и выдать сигнал y(t)=[z(t),x(t)], переходя в состояние z(t+1)=[z(t),z(t)], z(t)Z; y(t)Y; x(t)X. Абстрактный КА в начальном состоянии z0 принимая сигналы x(0), x(1), x(2) ... выдает сигналы y(0), y(1), y(2)... (выходное слово).
Существуют F - автомат 1-ого рода (Миля), функционирующий по схеме:
Z(t+1)= [z(t),z(t)], t=0,1,2...(1)
Y(t)=[z(t),x(t)], t=0,1,2...(2)
Автомат 2-ого рода:
Z(t+1)= [z(t),z(t)], t=0,1,2...(3)
Y(t)=[z(t),x(t-1)], t=1,2,3...(4)
Автомат 2-ого рода, для которого y(t)=[z(t)], t=0,1,2,...(5)
Т. е. функция выходов не зависит от входной переменной x(t), называется автоматом Мура.
Т. о. уравнения 1-5 полностью задающие F - автомат, являются частным случаем уравнения
(6)
Где - вектор состояния, - вектор независимых входных переменных, - вектор воздействий внешней среды, - вектор собственных внутренних параметров системы, - вектор начального состояния, t - время; и уравнение,(7)
Когда система S - деноминированная и на ее вход поступает дискретный сигнал x.
По числу состояний конечные автоматы бывают с памятью и без памяти. Автоматы с памятью имеют более одного состояния, а автоматы без памяти (комбинационные или логические схемы) обладают лишь одним состоянием. При этом согласно (2), работа комбинационной схемы заключается в том, что она ставит в соответствие каждому входному сигналу x(t) определенный выходной сигнал y(t), т. е. реализует логическую функцию вида:
Y(t)=[x(t)], t=0,1,2,...
Эта функция называется булевой, если алфавиты X и Y, которым принадлежат значения сигналов x и y состоят из 2-х букв.
По характеру отсчета времени (дискретному) F - автоматы делятся на синхронные и асинхронные. В синхронных автоматах моменты времени, в которые автомат "считывает" входные сигналы, определяются принудительно синхронизирующими сигналами. Реакция автомата на каждое значение входного сигнала заканчивается за один такт синхронизации. Асинхронный F - автомат считывает входной сигнал непрерывно и поэтому, реагируя на достаточно длинный водной сигнал постоянной величины x, он может, как это следует из 1-5, несколько раз изменить свое состояние, выдавая соответствующее число выходных сигналов, пока не перейдет в устойчивое.
Для задания F - автомата необходимо описать все элементы множества F=<z, x,y,,,z0>, т. е. входной, внутренний и выходной алфавиты, а также функции переходов и выходов. Для задания работы F - автоматов наиболее часто используются табличный, графический и матричный способ.
В табличном способе задания используется таблицы переходов и выходов, строки которых соответствуют входным сигналам автомата, а столбцы - его состояниям. При этом обычно 1-ый столбец слева соответствует начальному состоянию z0. На пересечении i-ой строки и j-ого столбца таблицы переходов помещается соответствующее значение (zK,xI) функции переходов, а в таблице выходов - (zK, xI) функции выходов. Для F - автомата Мура обе таблицы можно совместить, получив т. н. отмеченную таблицу переходов, в которой над каждым состоянием zK автомата, обозначающим столбец таблицы, стоит соответствующий этому состоянию, согласно (5), выходной сигнал (zI).
Описание работы F - автомата Мили таблицами переходов и выходов иллюстрируется таблицей 3.1., а описание F - автомата Мура - таблицей переходов 3.2..
Таблица 3.1. Описание работы автомата Мили
XJ |
ZK | |||
Z0 |
Z1 |
... |
ZK | |
Переходы | ||||
X1 |
(z0,x1) |
(z1,x1) |
... |
(zK,x1) |
X2 |
(z0,x2) |
(z1,x2) |
... |
(zK,x2) |
.................................................................. | ||||
XL |
... |
... |
... |
... |
Выходы | ||||
X1 |
(z0,x1) |
(z1,x1) |
... |
(zK,x1) |
.................................................................. | ||||
XL |
(z0,xL) |
(z1,xL) |
... |
(zK,xL) |
Таблица 3.2. Описание работы автомата Мура
(zK) | ||||
XI |
(z0) |
(z1) |
... |
(zK) |
Z0 |
Z1 |
... |
ZK | |
X1 |
(z0,x1) |
(z1,x1) |
... |
(zK,x1) |
X2 |
(z0,x2) |
(z1,x2) |
... |
(zK,x2) |
............................................................ | ||||
XL |
(z0,xL) |
(z1,xL) |
... |
(zK,xL) |
Примеры табличного способа задания F - автомата Мили F1 с тремя состояниями, двумя входными и двумя выходными сигналами приведены в таблице 3.3, а для F - автомата Мура F2 - в таблице 3.4.
Таблица 3.3. Способ задания автомата Мили с тремя состояниями
XJ |
Z0 | ||
Z0 |
Z1 |
Z2 | |
Переходы | |||
X1 |
z2 |
Z0 |
Z0 |
X2 |
Z0 |
Z2 |
Z1 |
Выходы | |||
X1 |
Y1 |
Y1 |
Y2 |
X2 |
Y1 |
Y2 |
Y1 |
Таблица 3.4. Способ задания автомата Мура с тремя состояниями
Y | |||||
XI |
Y1 |
Y1 |
Y3 |
Y2 |
Y3 |
z0 |
Z1 |
Z2 |
Z3 |
Z4 | |
X1 |
Z1 |
Z4 |
Z4 |
Z2 |
Z2 |
X2 |
Z3 |
Z1 |
Z1 |
Z0 |
Z0 |
При другом способе задания конечного автомата используется понятие направленного графа. Граф автомата представляет собой набор вершин, соответствующих различным состояниям автомата и соединяющих вершин дуг графа, соответствующих тем или иным переходам автомата. Если входной сигнал xK вызывает переход из состояния zI в состояние zJ, то на графе автомата дуга, соединяющая вершину zI С вершиной zJ обозначается xK. Для того, чтобы задать функцию переходов, дуги графа необходимо отметить соответствующими выходными сигналами. Для автоматов Мили эта разметка производиться так: если входной сигнал xK Действует на состояние zI, то согласно сказанному получается дуга, исходящая из zI и помеченная xK; эту дугу дополнительно отмечают выходным сигналом y=(zI, xK). Для автомата Мура аналогичная разметка графа такова: если входной сигнал xK, действуя на некоторое состояние автомата, вызывает переход в состояние zJ, то дугу, направленную в zJ и помеченную xK, дополнительно отмечают выходным сигналом y=(zJ, xK). На рис. 3 приведены заданные ранее таблицами F - автоматы Мили F1 и Мура F2 соответственно.
Рис. 3. Графы автоматов Мили (а) и Мура (б)
При решении задач моделирования часто более удобной формой является матричное задание конечного автомата. При этом матрица соединений автомата есть квадратная матрица С=|| cIj ||, строки которой соответствуют исходным состояниям, а столбцы - состояниям перехода. Элемент cIj=xK/yS в случае автомата Мили соответствует входному сигналу xK, вызывающему переход из состояния zI в состояние zJ и выходному сигналу yS, выдаваемому при этом переходе. Для автомата Мили F1, рассмотренного выше, матрица соединений имеет вид:
Если переход из состояния zI в состояние zJ происходит под действием нескольких сигналов, элемент матрицы cIj представляет собой множество пар "вход/выход" для этого перехода, соединенных знаком дизъюнкции.
Для F - автомата Мура элемент cIj равен множеству входных сигналов на переходе (zIZJ), а выход описывается вектором выходов:
I-ая компонента которого выходной сигнал, отмечающий состояние zI
Пример. Для рассмотренного ранее автомата Мура F2 запишем матрицу состояний и вектор выходов:
;
Для детерминированных автоматов переходы однозначны. Применительно к графическому способу задания F - автомата это означает, что в графе F - автомата из любой вершины не могут выходить 2 и более ребра, отмеченные одним и тем же входным сигналом. Аналогично этому в матрице соединений автомата С в каждой строке любой входной сигнал не должен встречаться более одного раза.
Рассмотрим вид таблицы переходов и графа асинхронного конечного автомата. Для F - автомата состояние zK называется устойчивым, если для любого входа xIX, для которого (zK,xI)=zK имеет место (zKXI)=yK. Т. о. F - автомат называется асинхронным, если каждое его состояние zKZ устойчиво.
На практике всегда автоматы являются асинхронными, а устойчивость их состояний обеспечивается тем или иным способом, например, введением сигналов синхронизации. На уровне абстрактной теории удобно часто оперировать с синхронными конечными автоматами.
Пример. Рассмотрим асинхронный F - автомат Мура, который описан в табл. 3.5 и приведен на рис. 4.
Таблица 3.5. Асинхронный автомат Мура
Y | |||
XI |
Y1 |
Y2 |
Y3 |
Z0 |
Z1 |
Z2 | |
X1 |
Z1 |
Z1 |
Z1 |
X2 |
Z2 |
Z1 |
Z2 |
X3 |
Z0 |
Z0 |
Z2 |
Рис. 4. Граф асинхронного автомата Мура
Если в таблице переходов асинхронного автомата некоторое состояние zK стоит на пересечении строки xS и столбца zS(Sk), то это состояние zK обязательно должно встретиться в этой же строке в столбце zK.
С помощью F-схем описываются узлы и элементы электронных вычислительных систем, устройства контроля, регулирования и управления, системы временной и пространственной коммутации в технике обмена информацией. Широта применения F-схем не означает их универсальность. Этот подход непригоден для описания процессов принятия решений, процессов в динамических системах с наличием переходных процессов и стохастических элементов.
Похожие статьи
-
Уравнение динамики теплообменника: Передаточные функции объекта получим по его уравнению динамики. Для этого запишем уравнение по заданному каналу. Затем...
-
В большинстве случаев структурная неопределенность вызвана неполнотой знания аналитической структуры уравнений модели объекта управления. При не...
-
Z -преобразование является одним из математических методов, разработанных для анализа и проектирования дискретных систем. Аппарат Z -преобразования...
-
Нахождение функций роста экономики региона Применив математическую модель на практике, можно узнать на сколько увеличится валовый региональный продукт,...
-
Уровень науки и техники Надежность средств, с помощью которых человек достигает космоса высокая, но не идеальна. РН -- сложная конструкция, и даже в...
-
Построим функцию роста валового регионального продукта: Таблица 11-Данные для функции роста ВРП Год (t) Y (миллион рублей) 1 372930 2 483951 3 648211 4...
-
Для трехотраслевой экономической системы заданы матрица коэффициентов Прямых материальных затрат И вектор конечной продукции Найти коэффициенты полных...
-
Выделим случай, когда входной сигнал X ( T ) является элементарной функцией 1( T ). Реакцию системы на воздействие 1( T ) можно компактно: [1] Где...
-
Для того, чтобы узнать, на сколько максимум может увеличится ВРП Краснодарского края, не хватает оптимального значения капитала. Для этого построим...
-
Пусть есть математическое ожидание цены состояния объекта при условии, что в момент времени tдопустимое экологическое состояние не достигнуто и цена...
-
Модель "вход - выход" для нестационарной системы управления можно представить в следующем виде [2] . Где коэффициенты матриц возмущения и ограничены...
-
Любой электромеханический преобразователь можно рассматривать в установившемся и динамическом режиме. Модель в установившемся режиме, по сути, является...
-
Задача кластеризации может быть сведена к задаче раскраски вершин графа. Для этого строится граф несовместимости. Вершинам графа соответствуют...
-
Реализуем математическую модель (2) (6) в MS Excel. Для этой цели построим таблицы исходных данных задачи по расчету оптимального графика занятости при...
-
Теоретическое обоснование математического моделирования - Математические методы и модели в экономике
Коммерческая деятельность в том или ином виде сводится к решению таких задач: как распорядиться имеющимися ресурсами для достижения наибольшей выгоды или...
-
Решение симплекс-методом с помощью симплекс-таблиц - Математические методы и модели в экономике
Определим оптимальный план выпуска продукции, решив задачу линейного программирования (ЗЛП). Для этого сначала приведем модель к каноническому виду...
-
Для обеспечения бесперебойной и эффективной работы некоторых предприятий, работающих в условиях неравномерной нагрузки, важное значение имеет оптимальный...
-
Часто оказывается, что входные величины, приложенные к системе, имеют стохастический характер. В этом случае нельзя использовать детерминированные...
-
Как и каждый достаточно ярко выраженный класс экономико-математических моделей, совокупность моделей календарного планирования обладает рядом...
-
Модель парной линейной регрессии - Математическое описание связи: регрессия, корреляция
Предположим, что у нас есть все основания считать, что два экономических показателя взаимосвязаны. Например, уровень инфляции и уровень безработицы в...
-
ЗАКЛЮЧЕНИЕ - Математическая модель роста экономики Краснодарского края
Целью дипломной работы было построение математической модели многосекторной экономики и ее применение на практике. В ходе работы были изучены...
-
Разработка электрической схемы (выбор элементной базы, обоснование выбора) Рисунок 2- Функциональная схема блока управления Для обеспечения требований...
-
В 1974г. группа аргентинских ученых во главе с профессором А. Эррерой получила предварительные результаты работы над латиноамериканской моделью...
-
Решение транспортной задачи методом потенциалов - Математическая модель решения транспортной задачи
Этот метод позволяет автоматически выделять циклы с отрицательной ценой и определять их цены. Пусть имеется транспортная задача с балансовыми условиями...
-
Классификация математических моделей - Построение и классификация математических моделей
К классификации математических моделей разные авторы подходят по-своему, положив в основу классификации различные принципы. Можно классифицировать...
-
Важнейшие математические модели обычно обладают важным свойством Универсальности : принципиально разные реальные явления могут описываться одной и той же...
-
Жесткие и мягкие модели - Экономико-математическая детерминированная модель
Гармонический осциллятор - пример так называемой "жесткой" модели. Она получена в результате сильной идеализации реальной физической системы. Для решения...
-
Теперь исходя из нашей модели мы можем просчитать оптимальное кол-во трудящихся, которое потребуется для роста экономики: (39) Рассчитаем данные по годам...
-
Цели и задачи моделирования, Требования к модели - Виды математических моделей
Основные цели и задачи моделирования сводятся к следующему: 1. Оптимальное проектирование новых и интенсификация действующих технологических процессов....
-
Для заданного региона обслуживания с помощью технологии ГИС предоставляется карта автомобильных дорог, на которой указаны пункты, соответствующие...
-
Проверить ряд на наличие выбросов методом Ирвина, сгладить методом простой скользящее средней с интервалом сглаживания 3, методом экспоненциального...
-
Описание модели Экономические агенты, участвующее в модели: 1) производство 2) население 3) центральный банк 4) администрация региона Создадим...
-
Заключение, Список использованной литературы - Моделирование математической модели теплообменника
В данной курсовой работе была получена математическая модель теплообменника в виде дифференциальных уравнений. Также была получена передаточная функция...
-
В основе метода площадей лежит предположение, что объект может быть описан линейным дифференциальным уравнением с постоянными коэффициентами, а его...
-
Маркетинговое исследование представляет собой системный сбор, обработку и анализ всех аспектов процесса маркетинга: продукта, его рынка, каналов...
-
Понятие многосекторной экономики Многосекторная экономика-- экономическая система, в которой на рыночной основе сосуществуют частная, государственная и...
-
ВВЕДЕНИЕ - Математическая модель роста экономики Краснодарского края
В наше время математическое моделирование используется во всех отраслях науки. В своей дипломной работе, с помощью математического моделирования, я...
-
Введение - Моделирование математической модели теплообменника
Математический динамический модель канал Качественные и количественные изменения в промышленности, науке и технике составляют основу для значительного...
-
На основании проведенного моделирования можно сделать выводы: - происходящие тепловые процессы скоротечны и не приводят к перегреву конструкции блока...
-
Исследование тепловых режимов с помощью математической модели При запуске любого электродвигателя возникает ток превышающий номинальный ток в рабочем...
Дискретно - детерминированные модели (F-схемы) - Виды математических моделей