Контрольная работа: Математические основы теории систем

Второй шаг.1. Помечаем столбцы табл.2, находим второй путь l2 = (x1,x3, х7, х9) и расставляем знаки.

2. Пропускная способность пути l2

Изменим пропускные способности помеченных дуг на С2 в табл.3.

Tаблица 3

Третий шаг.1. Пометив столбцы, находим l3 = (x1, х4, х7,x9).

Величина потока по пути l3

Вычислив новые пропускные способности дуг, приходим к табл.4.

Таблица 4

Четвертый шаг.1. Помечаем столбцы табл.4, находим четвертый путь l4 = (x1, х2, х8, х9) и расставляем знаки.

2. Пропускная способность пути l4

Изменим пропускные способности помеченных дуг на С4 в табл.5.

Таблица 5

Пятый шаг.1. Помечаем столбцы табл.5, находим четвертый путь l5 = (x1, х4, х8, х9) и расставляем знаки.

2. Пропускная способность пути l5

Изменим пропускные способности помеченных дуг на С5 в табл.6.

Таблица 6

Шестой шаг. Просматривая строки и помечая столбцы, убеждаемся в том, больше не существует ни одного пути с положительной пропускной способностью из вершины x1 в вершину x9. Подмножество R образуют помеченные вершины х1, х2, х3, х4, х5, х6, х7, х8, а подмножество  - одна непомеченная вершины х9. Разрез с минимальной пропускной способностью образуют дуги, начальные вершины которых принадлежат подмножеству R, а конечные - . Таким образом, разрез с минимальной пропускной способностью . Удалив дуги этого разреза, блокируем все пути из источника в сток. Пропускная способность разреза

Заключительный шаг. Вычитая из элементов табл.1 соответствующие элементы табл.6, получим табл.7

Таблица 7.

Величина максимального потока равна сумме элементов x1-й строки табл.7 или сумме элементов x9-го столбца.

Максимальный поток равен .

Задача 3. Анализ сетей Петри

Сеть Петри задана графически (рис.23…30). В табл.1 в соответствии с вариантом и указанным номером рисунка приведены различные начальные маркировки сети.

Выполнить следующие действия:

Описать сеть аналитическим и матричным способами.

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

Построить дерево достижимости заданной сети.

Проверить, является ли достижимой одна из маркировок, получаемых на четвертом шаге построения дерева, составив и решив матричные уравнения.

Таблица 1

Решение:

Опишем сеть аналитическим и матричным способами. Приведем графическое представление сети Петри, в которой позиции P = {p1, p2, p3, p4, p5} и переходы T = {t1, t2, t3 , t4 }.

Начальная маркировка сети обозначается вектором μ0 [μ1,μ2,μ3,μ4,μ5], μ0 [1 3 0 1 2]. Отсюда получим:

При аналитическом способе задания сеть Петри задается как C = (P,T,F,H,μ0), где, кроме множеств позиций Р и переходов Т, задаются входная F и выходная Н функции.

Через F (tj) обозначается множество входных позиций, а через H (tj) - множество выходных позиций перехода tj; μ0 - начальная маркировка сети.

F (t1) = {p5},H (t1) = {p1, p2 },

F (t2) = {p1},H (t2) = {p3, p4},

F (t3) = {p3, p4}H (t3) = {p1 },

F (t4) = {p2, p3, p4}H (t4) = {p5 }.

μ0 [1 3 0 1 2]

Матричная форма определения сети Петри эквивалентна аналитическому способу задания C = (P,T,D-,D+,μ0). Здесь D- и D+ - матрицы входных и выходных инциденций соответственно размером m × n, где m - число переходов и n - число позиций.

Элемент dij- матрицы D- равен кратности дуг, входящих в i-й переход из j-й позиции.

Элемент dij+ матрицы D+ равен кратности дуг, выходящих из i-ro перехода в j-ю позицию.

Для рассматриваемой сети Петри

Матрица D = D+ - D - называется матрицей инцидентности сети Петри,

2. При начальной маркировке μ0 [1 3 0 1 2] сети Петри разрешенными являются переходы t1 и t2.

Условия срабатывания для перехода t3 и t4 не выполняется.

Переход t1

[μ0] ≥ [1000]* D- = [1000] · ; [1 3 0 1 2] ≥ [00001] –

условие выполняется, переход разрешен.

Новая маркировка при срабатывании перехода t1 равна:

.

Переход t2

[μ0] ≥ [0100]* D- = [0100] ·;[1 3 0 1 2] ≥ [10000] –

условие выполняется, переход разрешен.

Новая маркировка при срабатывании перехода t2 равна:

.

Переход t3

[μ0] ≥ [0010]* D- = [0010] ·;[1 3 0 1 2] ≥ [00110] - условие не

выполняется, переход запрещен.

Переход t4

[μ0] ≥ [0001]* D- = [0001] ·;[1 3 0 1 2] ≥ [01110] –

условие не выполняется, переход запрещен.

Построим дерево достижимости заданной сети.

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

Уравнение  принимает вид

Перенесем  в левую часть и выполним умножение, тогда

.

Приравняем составляющие векторов

Система имеет решение x1 = 1; x2 = 2; x3 = 0; x4 = 2.

Это значит, что исследуемая маркировка достижима и в последовательности срабатываний переход t1 срабатывает один раз, переходы t2 и t4 - по два раза, переход t3 не срабатывает.

Задача 4. Элементы математической логики и теории автоматов

Конечный автомат задан графом, определенным в задаче 1. Вершины графа отождествляются с состояниями автомата таким образом, что множество состояний Q = {q1, q2 ,…, qn}. Переход автомата из одного состояния в другое осуществляется под воздействием множества входных сигналов X={x1, x2, x3, x4}. Переходы определяются законом отображения Г вершин графа, причем каждому переходу соответствует только одна из букв множества X. При задании графа эти буквы расставить произвольно.

Автомат позволяет вырабатывать выходные сигналы Y={y1, y2, y3}:

y1 - переход из состояния qi в состояние qi (петля);

y2 - переход из состояния qi в qj при i<j;

y3 - переход из состояния qi в qj при i>j.

Осуществить структурный синтез конечного автомата. Реализацию осуществить на элементах, указанных в табл.1, в соответствии с номером варианта. Обязательной является минимизация реализуемых функций.

Таблица 1

Решение:

Множество вершин X = {x1, x2, x3, x4, x5, x6},

Вершины графа отожествляются с состояниями автомата таким образом, что множество состояний Q = {q1, q2, q3, q4, q5, q6}. Переход автомата из одного состояния в другое осуществляется под воздействием множества входных сигналов X={x1, x2, x3, x4}.

Автомат позволяет вырабатывать выходные сигналы Y={y1, y2, y3}.

На основании аналитического описания ориентированного графа из задания № 1 запишем закон отображения состояний автомата:

Гq1 = {q1 (x1/y1), q3 (x2/y2), q2 (x3/y2)},

Гq2 = {q4 (x3/y2), q1 (x4/y3), q3 (x1/y2)},

Гq3 = {q1 (x1/y3), q5 (x2/y2), q2 (x3/y3), q4 (x4/y2)},

Гq4 = {q2 (x1/y3), q6 (x2/y2), q3 (x3/y3), q5 (x4/y2)},

Гq5 = {q3 (x4/y3), q4 (x1/y3), q6 (x2/y2)}, Гq6 = {q4 (x3/y3), q5 (x4/y3)}.

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

Таблица 2

Осуществим структурный синтез автомата, заданного табл.1. В качестве элементов памяти используем D-триггеры, в качестве элементной базы используем логические элементы И-НЕ.

Количество букв входного алфавита n = 4

Количество входовp ≥ log2 n = log2 4 = 2;

Количество букв выходного алфавита m = 2

Количество выходовe ≥ log2 m = log2 3 = 2;

Количество состояний r = 6

Количество триггеровz ≥ log2 r = log2 6 = 3.

Приступаем к кодированию:

На основании результатов кодирования строим обобщенную таблицу переходов и выходов структурного автомата (табл.3), заменяя состояния, входные и выходные переменные их кодами.

Таблица 3

Используя таблицу переходов D-триггера и данные предыдущей таблицы, составим обобщенную таблицу функционирования структурного автомата (табл.4). Функции возбуждения трех триггеров обозначены через D1, D2, D3, соответственно.

Таблица 4

По этой таблице запишем СДНФ выходных функций V и функций возбуждения триггеров D1, D2, и D3, зависящих от набора переменных u1, u2, w1 (t), w2 (t), w3 (t). В результате получим систему логических функций для построения комбинационной части автомата:

.

.

.

.

.

Минимизируем функции согласно картам Карно:

После минимизации имеем набор функций в базисе И-НЕ

=

.

.

.

Функциональная схема структурного автомата: