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

⇐ ПредыдущаяСтр 12 из 14Следующая ⇒

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

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

Абстрактно конечный автомат (англ. finite automata) можно представить как математическую схему (F-схему), характеризующуюся шестью элементами: конечным множеством X входных сигналов (входным алфавитом); конечным множеством Y выходных сигналов (выходным алфавитом); конечным множеством Z внутренних состояний (внутренним алфавитом или алфавитом состояний); начальным состоянием z0, z0 Î Z; функцией переходов j (z, х)\ функцией выходов y (z, х).

Автомат, задаваемый F-схемой: , — функционирует в дискретные моменты времени, которые называются такты, равные друг другу, каждому из которых соответствуют постоянные значения входного и выходного сигналов и внутренние состояния.

Абстрактный конечный автомат имеет один входной и один выходной каналы. В каждый момент t = 0, 1, 2, ... дискретного времени F-автомат находится в определенном состоянии z(t) из множества Z состояний автомата, причем в начальный момент времени t = 0 он всегда находится в начальном состоянии z(0)=zo.

Моделирование дискретно-стохастических систем (Р-схемы).

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

Введем математическое понятие Р-автомата, используя понятия, введенные для F-автомата. Рассмотрим множество элементами которого являются всевозможные пары, где и — элементы входного подмножества X и подмножества состояний соответственно. Если существуют две такие функции то с их помощью осуществляются отображения и, то говорят, что определяет автомат детерминированного типа.

Схемы вероятностных автоматов (Р-схем) применяются:

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

в определении алгоритмических возможностей систем;

в обосновании границ целесообразности их использования;

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

Математическое понятие Р-автомата формируется на понятиях, введенных для F-автомата.

Пусть множество G, элементами которого являются всевозможные пары где xi и zs — элементы входного подмножества X и подмножества состояний Z соответственно. Если существуют две такие функции и, то с их помощью осуществляются отображения и, то говорят, что (1) определяет конечный автомат детерминированного типа.

Введем более общую математическую схему. Пусть Ф — множество всевозможных пар вида (zk, yj), где yj — элемент выходного подмножества Y, т.е.. Пусть в любой элемент множества G индуцирует на множестве Ф некоторый закон распределения следующего вида:

При этом, (2) где bkj — вероятности перехода автомат в состояние zk и выдаче на выходе сигнала yj, если автомат был в состоянии z.S, и на его вход в момент времени поступил сигнал хi. Число таких распределений, представленных в виде таблиц, равно числу элементов множества G.

Обозначим множество этих таблиц через ^ В. Тогда четверка элементов (3) называется вероятностным автоматом (Р-автоматом).

У-детерминированного Р-автомата

Вероятностный автомат Мили

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

Марковские последовательности, согласно теореме Маркова, –это последовательность случайных величин, для которой справедливо выражение

где N – количество независимых испытаний; D–- дисперсия.

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

Y – детерминированный Р– автомат можно задать двумя таблицами: переходов (табл.1.1) и выходов (табл.1.2).

Схемы вероятностных автоматов (Р-схем)применяются:

- в проектировании дискретных систем, проявляющих статистически закономерное случайное поведение;

- в определении алгоритмических возможностей систем;

- в обосновании границ целесообразности их использования;

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

Математическое понятие Р-автоматаформируется на понятиях, введенныхдля F-автомата.

⇐ Предыдущая 5 6 7 8 9 10 111213 14 Следующая ⇒