Шпаргалка по "Математическому моделированию"

В качестве математических моделей в D-схемах (от английского dynamic) используются дифференциальные уравнения.

Дифференциальными уравнениями называются такие уравнения, в которых неизвестными будут функции одной или нескольких переменных, причем в уравнение входят не только функции, но и их производные различных порядков. Если неизвестные – функции многих переменных, то уравнения называются уравнениями в частных производных, в противном случае при рассмотрении функций только одной независимой переменной уравнения называются обыкновенными дифференциальными уравнениями.

Обычно в таких математических моделях в качестве независимой  переменной, от которой зависят неизвестные искомые функции, служит время t. Тогда математическое соотношение для детерминированных систем в общем виде будет

у'' = f(y,t), J(to) = yo> где у = (У\,Уг,---,У_п) «-мерный вектор, f = ( f\,fi,---,f_n) «-мерная функция.

Наиболее широко этот подход используются в теории систем автоматического управления (САУ) при анализе точности и устойчивости САУ в переходных процессах.

Задачей системы является изменение выходной переменной (выходного  сигнала) y(t) согласно заданному закону с определенной точ

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

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

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

10. Математические  модели. Дискретно–детерминированные модели (F–схемы, конечные автоматы).

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

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

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

Абстрактно конечный автомат (англ. finite automata) можно представить как математическую схему (F-схему), характеризующуюся шестью элементами: конечным множеством X входных сигналов (входным алфавитом); конечным множеством Y выходных сигналов (выходным алфавитом); конечным множеством Z внутренних состояний (внутренним алфавитом или алфавитом состояний); начальным состоянием zo, функцией переходов Ф(г, х), функцией выходов W(z, х). Автомат, задаваемый F-схемой, функционирует в дискретном автоматном времени, моментами которого являются такты, т. е. примыкающие друг к другу равные интервалы времени. Изменение состояния автомата и выходного сигнала может произойти только в тактовые моменты. Таким образом, работа конечного автомата происходит по следующей схеме: в каждом t-м такте на вход автомата, находящегося в состоянии z (t), подается некоторый сигнал x(t), на который он реагирует переходом в (Н-1)-м такте в новое состояние z (t+l) и выдачей некоторого выходного сигнала. Это можно описать следующими уравнениями: z (t+\) = <P[z(t), x(t)], t=0,l,2...;

У (t) = Ґ[z(t), x(t)], t=0,l,2... .

Различают два вида конечных автоматов. Приведенные выше уравнения описывают работу автомата первого рода, называемого также автоматом Мили. Для F-автомата второго рода

z (t+\) = <P[z(t), x(t)], t=0,l,2...;

у (t) = Ґ[z(t), x(t-\)], t=l,2,3....

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

z (t+V) = <P[z(t), x(t)], t=0,l,2...;

у (t) = Ґ[z(t)], t=1,2,3....

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

Чтобы задать конечный F-автомат, необходимо описать все элементы множества F = (Z, X, 7, Ф, ¥ ), т. е. входной, внутренний и выходной алфавиты, а также функции переходов и выходов. Причем среди множества состояний необходимо выделить состояние zq, в котором автомат находился в момент времени t = 0. Существуют несколько способов задания работы F-автоматов, но наиболее часто используются табличный, графический и матричный.

Простейший табличный  способ задания конечного автомата основан на использовании таблиц переходов и выходов, строки которых соответствуют входным сигналам автомата, а столбцы — его состояниям. При этом обычно первый слева столбец соответствует начальному состоянию zq. На пересечении z-й строки и к-го столбца таблицы переходов помещается соответствующее значение Ф(г^ x_t) функции переходов, а в таблице выходов — соответствующее значение Ґ(zk, x_t) функции выходов. Для F-автомата Мура обе таблицы можно совместить, получив так называемую отмеченную таблицу переходов, в которой над каждым состоянием Zk автомата, обозначающим столбец таблицы, стоит соответствующий этому состоянию выходной сигнал ¥ (zk)-

При другом способе задания  конечного автомата используется понятие  направленного графа. Граф автомата представляет собой набор вершин, соответствующих различным состояниям автомата и соединяющих вершины дуг графа, соответствующих тем или иным переходам автомата. Если входной сигнал Xk вызывает переход из состояния z_t в состояние z,, то на графе автомата дуга, соединяющая вершину z_i с вершиной z_j, отмечается сигналом x_k. Для того чтобы задать функцию выходов, дуги графа необходимо отметить соответствующими выходными сигналами Ψ(z_i, x_k ). Для автомата Мура выходные сигналы связаны только с состояниями и поэтому значениями Ψ(z_k) отмечают соответствующие вершины графа.

На рис. 2.1 и 2.2 приведены  примеры задания автоматов Мили и Мура.

 

Более подробно вопросы, связанные с построением и  исследованием конечных автоматов, рассматриваются в курсе «Организация и функционирование ЭВМ».

 

 

 

 

 

 

 

 

 

 

11. Математические  модели. Дискретно–стохастические модели (P–схемы, вероятностные автоматы).

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

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

Для того, чтобы задать вероятностный автомат надо, как  и для конечного автомата определить множество X = (x₁, x₂, … x_n) входных сигналов, множество Y=(y₁, y₂, … y_r) выходных сигналов и множество Z=(z₁, z₂,… z_s) внутренних состояний. Описание процесса функционирования автомата осуществляется путем задания ряда распределений вероятностей.

Рассмотрим множество G пар ( x_iz_j ) и множество D пар (z_ky_h). Для задания вероятностного автомата надо определить для каждой пары из множества G вероятности b_kh перехода автомата в состояние z_k и появления на выходе сигнала y_h

Число таких распределений, представленных в виде таблиц, равн о числу элементов множества G. Обозначим множество таких распределений как B. Тогда совокупность множеств Z, X, Y, B определяет вероятностный автомат.

Это наиболее общий случай. Если распределения для нового состояния Р-автомата и его выходного сигнала независимы, то это вероятностный автомат Мили. Для его задания надо определить множества распределений

Число таких распределений  равно числу элементов множества G. Говорят, что задан вероятностный автомат Мили, если заданы два распределения вероятностей

Здесь и при этом  распределения для q  и  p независимы.

 

Вероятностный автомат  Мура имеет место, если определение  выходного сигнала Р-автомата зависит лишь от того состояния, в котором находится автомат в данном такте работы, а элементы из Z определяются как у автомата Мили.

Детерминированные автоматы это частный случай Р-автомата. Также частными случаями являются Y – детерминированный и Z – детерминированные автоматы. Если выходной сигнал Р-автомата определяется детерминированно, то такой автомат называется Y-детерминированным вероятностным автоматом. Аналогично, Z-детерминированным вероятностным автоматом называется Р-автомат, у которого выбор нового состояния является детерминированным. 

 

12. Дискретная  марковская  цепь. Геометрическое  распределение. Нормировочное уравнение. Граф состояний.

ДИСКРЕТНАЯ  ЦЕПЬ МАРКОВА

Множество случайных  величин {xi} (состояний) образуют цепь Маркова, если вероятность того, что следующее состояние окажется равным xi+1 зависит только от значения xi и не зависит от предыдущих значений процессов.

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

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

Геометрическое  распределение

p1=π– событие не происходит.

p2=1-π – событие происходит.

Описание этого процесса и есть геометрическое распределение. Какова вероятность того, что интервал

между событиями в  сформированном потоке будет равен i тактовым интервалам.

 - математическое описание геометрического распределения.

Основные характеристики:

Т – величина тактового интервала. Необходимо определить среднее значение случайной величины m. Интервал может оказаться равным величине Т, 2Т…

Сумма бесконечной геометрической прогрессии Sгп=b1/(1-q). b1 – первый элемент прогрессии, q – множитель.

Пример  исследования узла память-АЛУ.

Требуется построить  и исследовать модель следующего вычислительного узла.

МК – память макрокоманд.

СИ – синхро-импульсы.

Работа узла: через  каждые 2 такта из памяти макрокоманд  происходит выборка и команда передается в АЛУ. Интервалы времени обработки команд АЛУ распределены по геометрическому распределению с вероятностью окончания обслуживания 1- π. Если выбранная макрокоманда застает АЛУ занятым, она занимает место в очереди БЗУ (буферное ЗУ). В случае, если АЛУ занято, а БЗУ заполнено, то очередная команда блокируется в памяти и выборка из памяти прекращается, пока не освободится место в очереди. Примем количество мест ожидания в БЗУ равным n. Требуется определить характеристики этой системы.

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

Система массового обслуживания: источник, очередь, обслуживающий прибор. Построим граф состояний: будем кодировать состояния с помощью следующих 3х компонент: j, t1, t2. j – будет обозначать количество заявок в очереди БЗУ (значения от 0 до n). t1 – количество интервалов времени до появления очередной заявки (возможные значения 2, 1, 0 (состояние блокировки)). t2 – состояние АЛУ (0 – свободно, 1 – занято).

π – обслуживания не произойдет .

1- π – обслуживание  произойдет.

Определим вероятности  состояний:

P020=0

P010=(1-π)P021

P021=P010+(1- π)P011

В этом графе есть стандартные и нестандартные состояния. Нестандартные – первые три и последние три.

Остальные стандартные.

Pi21= πPi-1 11+(1- π)Pi11 (i от 1 до n-1).

Pi11=(1- π)Pi+1 21 + πPi21 (i от 1 до n-1).

Еще нестандартные:

Pn21=Pn-1 11 + (1- π)(Pn11+Pn01)

Pn11= πPn21

Pn01= π(Pn11+Pn01)

Обозначим P010=p, w=π/(1-π).

Тогда:

P021=p/(1- π)

P011=wp/(1- π)

Если двигаться дальше, то используя математическую индукцию по i получим:

Для нахождения вероятности P010 воспользуемся нормировочным  уравнением:

с учетом того, что сумма у нас – это сумма геометрической прогрессии

Определим характеристики системы. Определим среднее время  обслуживания 1 заявки системой в целом.