41276

Дискретно-детерминированные модели (F-схемы). Основные соотношения. Возможные приложения F-схемы

Лекция

Математика и математический анализ

Система представляется в виде автомата как некоторого устройства с входными и выходными сигналами перерабатывающего дискретную информацию и меняющего свои внутренние состояния лишь в допустимые моменты времени. В каждый момент t = 0 1 2 дискретного времени Fавтомат находится в определенном состоянии zt из множества Z состояний автомата причем в начальный момент времени t = 0 он всегда находится в начальном состоянии z0 = z0. Другими словами если на вход конечного автомата установленного в начальное состояние z0 подавать в...

Русский

2013-10-23

170.5 KB

23 чел.

Лекция 6. Дискретно-детерминированные модели (F-схемы). Основные соотношения. Возможные приложения F-схемы

2.3. Дискретно-детерминированные модели (F-схемы)

Основные соотношения

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

Абстрактно конечный автомат (англ. finite automata) можно представить как математическую схему (F-схему), характеризующуюся шестью элементами: конечным множеством Х входных сигналов (входным алфавитом); конечным множеством Y выходных сигналов (выходным алфавитом); конечным множеством Z внутренних состояний (внутренним алфавитом или алфавитом состояний); начальным состоянием z0, z0  Z; функцией переходов (z, x); функцией выходов (z, x). Автомат, задаваемый F-схемой: F = Z, X, Y, , , z0, функционирует в дискретном времени, моментами которого являются такты, каждому из которых соответствуют постоянные значения входного и выходного сигналов и внутренние состояния. Обозначим состояние, а также входной и выходной сигналы, соответствующие t-му такту при t = 0, 1, 2, …, через z(t), x(t), y(t). При этом по условию z(0) = z0, а z(t)Z, x(t)X, y(t)Y.

Абстрактный конечный автомат имеет один входной и один выходной каналы. В каждый момент t = 0, 1, 2, … дискретного времени F-автомат находится в определенном состоянии z(t) из множества Z состояний автомата, причем в начальный момент времени t = 0 он всегда находится в начальном состоянии z(0) = z0. В момент t, будучи в состоянии z(t), автомат способен воспринять на входном канале сигнал x(t)X и выдать на выходном канале сигнал y(t) = [z(t), x(t)], переходя в состояние z(t+1) = [z(t), x(t)], z(t) Z, y(t)Y. Абстрактный конечный автомат реализует некоторое отображение множества слов входного алфавита X на множество слов выходного
алфавита
Y. Другими словами, если на вход конечного автомата, установленного в начальное состояние z0, подавать в некоторой последовательности буквы входного алфавита x(0), x(1), x(2), …, т.е. входное слово, то на выходе автомата будут последовательно появляться буквы выходного алфавита y(0), y(1), y(2), …, образуя выходное слово.

Таким образом, работа конечного автомата происходит по следующей схеме: в каждом t-м такте на вход автомата, находящегося в состоянии z(t), подается некоторый сигнал x(t), на который он реагирует переходом (t+1)-го такта в новое состояние z(t+1) и выдачей некоторого выходного сигнала. Сказанное выше можно описать следующими уравнениями: для F-автомата первого рода, называемого также автоматом Мили,

z(t+1) = [z(t), x(t)], t = 0, 1, 2, …;    (2.15)

y(t) = [z(t), x(t)], t = 0, 1, 2, …;    (2.16)

для F-автомата второго рода

z(t+1) = [z(t), x(t)], t = 0, 1, 2, …;    (2.17)

y(t) = [z(t), x(t1)], t = 1, 2, 3,….   (2.18)

Автомат второго рода, для которого

y(t) = [z(t)], t = 0, 1, 2, …,    (2.19)

т.е. функция выхода не зависит от входной переменной x(t), называется автоматом Мура.

Таким образом, уравнения (2.15)-(2.19), полностью задающие
F-автомат, являются частным случаем уравнений (2.3) и (2.4), когда
система
S – детерминированная и на её единственный вход поступает дискретный сигнал X.

По числу состояний различают конечные автоматы с памятью и без памяти. Автоматы с памятью имеют более одного состояния, а автоматы без памяти (комбинационные или логические схемы) обладают лишь одним состоянием. При этом, согласно (2.16), работа комбинационной схемы заключается в том, что она ставит в соответствие каждому входному сигналу x(t) определенный выходной сигнал y(t), т.е. реализует логическую функцию вида

y(t) = [ x(t)], t = 0, 1, 2, … .

Эта функция называется булевой, если алфавит X и Y, которым принадлежат значения сигналов x и y, состоят из двух букв.

По характеру отсчета дискретного времени конечные автоматы делятся на синхронные и асинхронные. В синхронных F-автоматах моменты времени, в которые автомат «считывает» входные сигналы, определяются принудительно синхронизирующими сигналами. После очередного синхронизирующего сигнала с учетом «считанного» и в соответствии с уравнениями (2.15)-(2.19) происходит переход в новое состояние и выдача сигнала на выходе, после чего автомат может воспринимать следующее значение входного сигнала. Таким образом, реакция автомата на каждое значение входного сигнала заканчивается за один такт, длительность которого определяется интервалом между соседними синхронизирующими сигналами. Асинхронный F-автомат считывает входной сигнал непрерывно и поэтому, реагируя на достаточно длинный входной сигнал постоянной величины x, он может, как следует из (2.15)-(2.19), несколько раз изменять состояние, выдавая соответствующее число выходных сигналов, пока не перейдет в устойчивое, которое уже не может быть изменено данным входным сигналом.

Возможные приложения F-схемы.

Чтобы задать конечный F-автомат, необходимо описать все элементы множества F = <Z, X, Y, , , z0>, т.е. входной, внутренний и выходной алфавиты, а также функции переходов и выходов, причем среди множества состояний необходимо выделить состояние z0, в котором автомат находится в состоянии t = 0. Существуют несколько способов задания работы F-автоматов, но наиболее часто используются табличный, графический и матричный.

В табличном способе задаются таблицы переходов и выходов, строки которых соответствуют входным сигналам автомата, а столбцы – его состояниям. Первый слева столбец соответствует начальному состоянию z0. На пересечении i-й строки и k-го столбца таблицы переходов помещается соответствующее значение (zk, xi) функции переходов, а в таблице выходов – соответствующее значение (zk, xi) функции выходов. Для F-автомата Мура обе таблицы можно совместить.

Описание работы F-автомата Мили таблицами переходов и выходов иллюстрируется табл. 2.1, а описание F-автомата Мура – таблицей переходов (табл. 2.2).

Таблица 2.1

Xi

zk

z0

z1

zk

Переходы

x1

(z0, x1)

(z1, x1)

(zk, x1)

x2

(z0, x2)

(z1, x2)

(zk, x2)

xi

(z0, xi)

(z1,  xi)

(zk, xi)

Выходы

x1

(z0, x1)

(z1, x1)

(zk, x1)

x2

(z0, x2)

(z1, x2 )

(zk, x2)

xi

(z0, xi)

(z1, xi)

(zk, xi)

Таблица 2.2

xi

(zk)

(z0)

(z1)

(zk)

z0

z1

zk

x1

(z0, x1)

(z1, x1)

(zk, x1)

x2

(z0, x2)

(z1, x2)

(zk, x2)

xi

(z0, xi)

(z1, xi)

(zk, xi)

Примеры табличного способа задания F-автомата Мили F1 приведены в табл. 2.3, а для F-автомата Мура F2 – в табл. 2.4.

Таблица 2.3

xi

zk

z0

z1

z2

Переходы

x1

z2

z0

z0

x2

z0

z2

z1

Выходы

x1

y1

y1

y2

x2

y1

y2

y1

Таблица 2.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 c вершиной zj, обозначается xk. Для того чтобы задать функцию выходов, дуги графа необходимо отметить соответствующими выходными сигналами. Для автоматов Мили эта разметка производится так: если входной сигнал xk действует на состояние zi, то получается дуга, исходящая из zi и помеченная xk; эту дугу дополнительно отмечают выходным сигналом y = (zi, xk). Для автомата Мура аналогичная разметка графа такова: если входной сигнал xk, действуя на некоторое состояние автомата, вызывает переход в состояние zj, то дугу, направленную в zi и помеченную xk, дополнительно отмечают выходным
сигналом
y = (zj, xk).

На рис. 2.4. а, б приведены заданные ранее таблицами F-автоматы Мили F1 и Мура F2 соответственно.    

a

б

Рис. 2.4. Графы автоматов а – Мили  и б – Мура

При матричном задании конечного автомата матрица соединений автомата квадратная С=сij, строки соответствуют исходным состояниям, а столбцы – состояния перехода. Элемент сij = xk/ys, стоящий на пересечении
i-й строки и j-го столбца, в случае автомата Мили соответствует входному сигналу xk, вызывающему переход из состояния zi в состояние zj, и выходному сигналу ys, выдаваемому при этом переходе. Для автомата Мили F1, рассмотренного выше, матрица соединений имеет вид:

x2 / y1     –   x1 / y1

C1=     x1 / y1     – x2 / y2    .

x1 / y2  x2 /y1   

Если переход из состояния zi в состояние zj происходит под действием нескольких сигналов, элемент матрицы cij представляет собой множество пар «вход-выход» для этого перехода, соединенных знаком дизъюнкции.

Для F-автомата Мура элемент сij равен множеству входных сигналов на переходе (zi,zj), а выход описывается вектором выходов

(z0)

(z1)

……

=     (zk)     ,

……

(zK)

i-я компонента которого – выходной сигнал, отмечающий состояние zi.

Для рассмотренного выше F-автомата Мура F2 матрицы соединений и вектор выходов имеют вид:

 x1   x2     у1

 x2   x1    у1

C2=       x2    x1     ;     =   у3

x2  x1      у2

x2  x1      у3

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

Для F-автомата состояние zk называется устойчивым, если для любого входа xiX, для которого (zk, xi) = zk , имеет место (zk,xi) = уk. F-автомат называется асинхронным, если каждое его состояние zkZ устойчиво.

Таким образом, понятие в дискретно-детерминированном подходе к исследованию на моделях свойств объектов является математической абстракцией, удобной для описания широкого класса процессов функционирования реальных объектов в автоматизированных системах управления. С помощью F-автомата можно описать объекты, для которых характерно наличие дискретных состояний, и дискретный характер работы во времени – это элементы и узлы ЭВМ, устройства контроля, регулирования и управления, системы временной и пространственной коммутации в технике обмена информацией и т.д.

БИБЛИОГРАФИЧЕСКИЙ СПИСОК

1. Советов Б.Я. Моделирование систем : учеб. для вузов / Б.Я. Советов, С.А. Яковлев. М. : Высш. шк., 2001. 343 с.

2. Советов Б.Я. Моделирование систем : учеб. для вузов / Б.Я. Советов, С.А. Яковлев. 2-е изд. М.: Высшая школа, 1998. 319 с.

3. Тарасик В.П. Математическое моделирование технических систем: учеб. для вузов / В.П. Тарасик. М.: Наука, 1997. 600 с.

4. Введение в математическое моделирование: учеб. пособие для вузов/ под ред. П.В.Тарасова. М.: Интермет Инжиниринг, 2000. 200 с.

5. Ивченко Г.И. Математическая статистика: учебное пособие для втузов / Г.И. Ивченко, Ю.И. Медведев. М.: Высш. шк., 1984. 248 с.

6. Альянах И.Н. Моделирование вычислительных систем / И.Н. Альянах. Л.: Машиностроение, 1988. 233 с.

7. Шеннон Р. Имитационное моделирование систем – искусство и наука / Р. Шеннон. М.: Мир, 1978. 308 с.

6

 у1

 

           х1

у3            у1

  х2       х2

         х1

   

        х2            х2

     х1 х1  

      х1           х2

у2   у3

z0

z3

z2

z2

z1

z0

   х2           у1

    у1                   x1

 у2

x1   x1         у1

         x2          y2

 y1         x2

z4

z1


 

А также другие работы, которые могут Вас заинтересовать

28455. Правовое обеспечение воздушных перевозок в международном и внутреннем сообщениях 107.5 KB
  И этому есть ряд причин: вопервых авиация самый быстрый и удобный вид транспорта при переездах на дальние расстояния; вовторых сервис на авиарейсах в настоящее время имеет привлекательный для туристов вид; втретьих авиационные компании напрямую и через международные сети бронирования и резервирования выплачивают туристским агентствам комиссионные за каждое забронированное в самолете место мотивируя их тем самым выбирать авиаперевозки. Основными документами регулирующими международные воздушные перевозки являются международные...
28456. Осмысление потребности в сущности бытия и сущности человека. Индивидуальные основные потребности и психофизиологические возможности человека 51.5 KB
  Осмысление потребности в сущности бытия и сущности человека. Индивидуальные основные потребности и психофизиологические возможности человека. Потребность – отражение в сознании человека необходимости получения чегото жизненно важного побуждающего его к активной целенаправленности деятельности. Удовлетворение потребностей – цель любой деятельности человека.
28457. Сутність та задачі психологічної підготовки 105.5 KB
  Зміст морально-психологічного забезпечення та його особливості при виконанні службово-бойових завдань у повсякденній діяльності військ. Особливості при виконанні службово-бойових завдань у повсякденній діяльності військ...
28458. Понятие и сущность сервисной деятельности. Отличительные особенности услуг от товаров 108.5 KB
  В соответствии с Российским ГОСТ 564694 Услуги населению. По функциональному назначению услуги оказываемые населению подразделяются на – материальные по удовлетворению материальнобытовых потребностей потребителя бытовых услуг и социальнокультурные услуги удовлетворение духовных интеллектуальных потребностей и поддержание нормальной жизнедеятельности потребителя. лиц оказывающих услуги населению. Обслуживание – это деятельность исполнителя при непосредственном контакте с потребителем услуги.
28460. Предмет, сущность и задачи рекламы в СКС и Т 96 KB
  Предмет сущность и задачи рекламы в СКС и Т. В качестве объекта рекламы может выступать товар продажи или услуги. Предметом изучения рекламы являются стоящие перед ней цели и задачи. Сущность рекламы можно определить: в узком смысле как неличное информационное эмоциональное побуждение целевой группы людей к определенным поступкам.
28461. Необходимость и особенности страхования в туризме 59 KB
  Необходимость и особенности страхования в туризме. Объектами страхования в туризме являются как отдельные граждане так и туристские фирмы. Эти виды страхования в туризме проводятся в том же порядке что и страхование в других отраслях экономики. Страхование туристов это особый вид страхования обеспечивающий страховую защиту имущественных интересов граждан во время их пребывания в турпоездках.
28462. Компьютерные системы бронирования 55.5 KB
  Micros Fidelio Opera работает на более сложной с позиции освоения платформе Oracle. Данные о положительных сторонах АСУ были получены от дистрибьюторов данных программ а так же проанализированы и сопоставлены с данными полученными в ходе анонимного опроса персонала гостиничного комплекса использующего АСУ Micros Fidelio. Отсутствие возможности у ПО Micros Fidelio автоматического формирования цены на проживание. ПО Micros Fidelio не умеет формировать автоматическую цену на проживание и рассчитывать ее на будущее.
28463. Требования, предъявляемые к знаниям и профессиональным навыкам персонала гостиниц (речь, стиль, внешний вид и т.д.) 39.5 KB
  Потребитель при обнаружении недостатков оказанной услуги вправе по своему выбору потребовать: безвозмездного устранения недостатков; соответствующего уменьшения цены за оказанную услугу. Исполнитель должен устранить недостатки оказанной услуги в течение часа с момента предъявления потребителем требования. Требования потребителя об уменьшении цены оказанной услуги а также о возмещении убытков причиненных расторжением договора подлежат удовлетворению в течение 10 дней со дня предъявления соответствующего требования. Потребитель вправе...