Математические основы теории систем

Задание 12.docx

Министерство образования Республики Беларусь
Факультет заочного обучения
Кафедра: систем управления
Контрольная работа № 1
по дисциплине:«Математические основы теории систем»
Специальности ИТиУвТС
Задание 1. Элементы теории графов
Связный ориентированный граф G(Х Г) задан множеством вершин X = и отображением = i = 1 2 n. Здесь i – текущий номер вершины n – количество вершин графа. Значение индексов n k и l взять из табл. 2.1 в соответствии с номером варианта. Индексы k и l формируют значения индексов α γ переменной x в отображении = Если значения индексов α γ переменной x не соответствуют ни одному из номеров вершин графа то эта переменная не учитывается во множестве .
Выполнить следующие действия:
а) определить исходный граф и ассоциированный с ним неориентированный граф графическим матричным и аналитическим способами;
б) установить центры и периферийные вершины графов найти радиусы и диаметры графов;
в) выделить в ориентированном графе два подграфа. Найти объединение пересечение и разность подграфов;
г) описать систему уравнений соответствующую сигнальному графу считая что передача между вершинами и :
Найти передачу между вершинами и используя правило Мезона. Построить структуру кибернетической системы определяемой топологией графа;
д) определить количество покрывающих деревьев которые можно построить на неориентированном графе; найти эти деревья;
е) для одного из деревьев записать символ дерева представить дерево в корневой форме и записать код дерева.
А) Определим исходный ориентированный граф.
Аналитический способ:
Рис.1.1. Ориентированный граф.
Матрица смежности ориентированного графа строится по правилу:
Для нашего ориентированного графа матрица смежности будет иметь вид:
Матрица инцидентности ориентированного графа строится по правилу:
Для нашего ориентированного графа матрица инцидентности будет иметь вид:
Определим исходный неориентированный граф.
Аналитический способ. Описание неориентированного графа полностью совпадает с описанием ориентированного графа приведенным выше:
Рис.1.2. Неориентированный граф.
Матрица смежности неориентированного графа строится по правилу:
Для нашего неориентированного графа матрица смежности будет иметь вид:
Матрица инцидентности неориентированного графа строится по правилу:
Для нашего неориентированного графа матрица инцидентности будет иметь вид:
Б) Установим центры и периферийные вершины графов найдем радиусы и диаметры графов.
Построим матрицу отклонений ориентированного графа:
Вектор отклоненностей ориентированного графа:
Центр графа – вершина с наименьшей отклоненностью. В нашем случае центра нет.
Периферийная вершина – вершина с наибольшей отклоненностью. Для ориентированного графа периферийными вершинами являются вершины Радиус графа – отклоненность центра. Для ориентированного графа радиус равен: .
Диаметр графа – максимальная отклоненность периферийной вершины. Для ориентированного графа диаметр равен .
Построим матрицу отклонений неориентированного графа:
Вектор отклоненностей неориентированного графа:
В нашем случае периферийные вершины радиус и диаметр неориентированного графа совпадают с аналогичными параметрами ориентированного графа.
В) Выделим в ориентированном графе два подграфа. Найдем объединение пересечение и разность подграфов.
Разобьем ориентированный граф на два подграфа:
Рис.1.3. Подграф . Рис.1.4. Подграф
Подграф описывается следующим образом:
Объединение подграфов и :
Графически объединение подграфов выглядит следующим образом:
Рис.1.5. Объединение подграфов.
Пересечение подграфов и :
Графически пересечение подграфов выглядит следующим образом:
Рис.1.6. Пересечение подграфов.
Разность подграфов .
Найдем дополнение по отображению подграфа до насыщенного:
Тогда искомая разность подграфов будет следующей:
Графически разность подграфов выглядит следующим образом:
Рис.1.7. Разность подграфов.
Г) Опишем систему уравнений соответствующую сигнальному графу считая что передача между вершинами и :
Найдем передачу между вершинами и используя правило Мезона. Построим структуру кибернетической системы определяемой топологией графа.
Рассчитаем передачу согласно заданному правилу:
Сигнальный граф имеет вид:
Рис.1.7. Сигнальный граф.
Система уравнений соответствующая сигнальному графу задается следующим образом:
Если в одну вершину сходится n направленных к ней дуг то сигнал вершины определяется суммой .
В нашем случае система будет иметь вид:
Подставляем полученные ранее значения . Получим систему:
Найдем передачу между вершинами и используя правило Мезона.
Формула Мезона имеет вид:
где - передача s-того элементарного пути; – алгебраическое дополнение для s-того пути; D – определитель графа зависящий только от передачи контуров; s – число элементарных путей.
Определитель графа D определяется в соответствии с выражением:
где - произведение передач r-й комбинации из q несоприкасающихся контуров.
Выделим элементарные пути из в :
Контура которыми можно описать данный сигнальный граф:
Перечислим пары несоприкасающихся контуров:
Перечислим независимые тройки контуров:
Вычислим определитель сигнального графа D:
+ + + + + + + + + + + + + .
Тогда передача между вершинами и с учетом правила Мезона будет рассчитываться следующим образом:
Структура кибернетической системы определяемой топологией графа будет иметь вид:
Д) Определим количество покрывающих деревьев которые можно построить на неориентированном графе; найдем эти деревья.
Для построения дерева возьмем неориентированный граф аналогичный заданному и пронумеруем ребра:
Рис.1.9. Неориентированный граф
Количество покрывающих деревьев для графа без петель определяется теоремой Трента. В графе G без петель с n вершинами число L различных деревьев равно минору любого из элементов главной диагонали матрицы В порядка n.
Матрица В строится следующим образом: на главной диагонали записываются степени вершин графа а ij и ji-й элементы равны взятому со знаком минус числу ребер связывающих вершины i и j. В нашем случае получим:
Найдем все покрывающие деревья:
Е) Для одного из деревьев запишем символ дерева представим дерево в корневой форме и запишем код дерева.
В качестве покрывающего дерева возьмем дерево выделенное в предыдущей матрице. Выглядит оно следующим образом:
Рис.1.10. Дерево с кодом 3451.
Символ дерева запишется следующим образом:
Рис. 1.11. Вид дерева в корневой форме
Аналитическая запись:
Задание 2. Задача о максимальном потоке и потоке минимальной стоимости
На рис. 2.1 приведена транспортная сеть в виде ориентированных графов. На каждом из ребер через черту проставлены значения пропускной способности С() ребра и стоимость транспортировки единицы потока d() по этому ребру.
Для заданной сети определить:
) максимальный поток транспортировки груза между указанной парой вершин считая одну из них источником а другую – стоком;
) стоимость доставки груза по путям формирующим максимальный поток в сети;
) найти поток из источника в сток заданной величины обладающий минимальной стоимостью.
Рис. 2.6 Задание. Транспортная сеть.
) Определим максимальный поток транспортировки груза между вершинами и считая вершину источником а – стоком.
Находим какой-либо путь из в . Если пропускная способность дуги () больше нуля а пропуская способность симметричной ей дуги равна нулю то клетку (ij) заносится элемент . Остальные клетки не заполняются.
Элементы этого пути отмечаем знаком «-» а симметричные ему – знаком «+».
Определим пропускную способность найденного пути которая равна наименьшей из пропускных способностей дуг:
Определяем остаточные пропускные способности дуг найденного пути и симметричных им дуг. Для этого из элементов вычитаем а к элементам прибавляем . Получим таблицу:
Повторяем поиск пути. Получаем путь .
Столбцы пометить невозможно. Следовательно больше не существует ни одного пути с положительной пропускной способностью из в
Подмножество R образует отмеченная вершина ; подмножество .
Разрез с минимальной пропускной способностью формируют дуги начальные вершины которых принадлежат R а конечные - . Таким образом разрез с минимальной пропускной способностью будет иметь вид:
Удалив эти дуги мы блокируем все пути из источника в сток.
Пропускная способность разреза:
Вычитая из значений первой таблицы соответствующие значения последней таблицы получим:
Положительные элементы этой таблицы характеризуют величины дуговых потоков. Следовательно:
Потоки остальных дуг равны нулю.
Величина максимального потока равна сумме элементов -й строки или -того столбца. Таким образом максимальный поток для транспортной сети равен:
) Определим стоимость доставки груза по путям формирующим максимальный поток в сети.
С учетом последней полученной таблицы получим стоимость доставки груза по путям формирующим максимальный поток в сети:
) Найдем поток из источника в сток заданной величины обладающий минимальной стоимостью.
Примем поток равным 7 (1023).
Задание 3. Анализ сетей Петри
Сеть Петри задана графически (рис. 3.1). Также приведена начальная маркировка сети.
Описать сеть аналитическим и матричным способами.
Проверить условия срабатывания каждого из переходов и найти новые маркировки к которым приведет срабатывание соответствующих переходов путем выполнения матричных преобразований.
Построить дерево достижимости заданной сети.
Проверить является ли достижимой одна из маркировок получаемых на четвертом шаге построения дерева составив и решив матричные уравнения.
Рис.3.1. Задание. Сеть Петри.
Начальная маркировка В6:
Опишем сеть аналитическим и матричным способами.
где – множество позиций; – множество переходов; - входная функция; - выходная функция; - начальная маркировка сети.
Заданная сеть Петри описывается следующими параметрами:
где - матрицы входных и выходных инциденций размером где m – число переходов n – число позиций.
Элемент матрицы равен кратности дуг входящих в i-тый переход из j-той позиции.
Элемент матрицы равен кратности дуг выходящих в i-тый переход в j-той позиции.
Матрица инцидентности сети Петри:
Проверим условия срабатывания каждого из переходов и найти новые маркировки к которым приведет срабатывание соответствующих переходов путем выполнения матричных преобразований.
Начальная маркировка: .
Рис. 3.1. Сеть Петри с начальной маркировкой.
Необходимое условие срабатывания перехода : каждая из его входных позиций должна иметь не меньше фишек чем число дуг из этой позиции в переход.
Условие срабатывания в имеющейся маркировке :
где - вектор-строка компоненты которой соответствуют переходам и равны нулю за исключением i-той которая равна единице.
Проверим срабатывание :
Векторы сравниваются каждой из составляющих. Очевидно данный переход возможен.
Проверим условие срабатывания перехода :
Таким образом из маркировки возможно срабатывание всех переходов. При срабатывании переходов получим маркировку .
Маркировка полученная при срабатывании
Построим дерево достижимости заданной сети.
Пользуясь условием срабатывания переходов вычислим возможные срабатывания переходов из маркировки [11023] полученной в предыдущем пункте.
Расчет производится по одной ветке дерева достижимости.
Условие срабатывания перехода :
Маркировка которая будет получена при срабатывании данного перехода:
Перейдем к проверке маркировки [10033]:
Перейдем к проверке маркировки [20022]:
Перейдем к проверке маркировки [30011]:
Исходя из расчётов построим следующее дерево достижимости:
Рис. 3.2. Дерево достижимости заданной сети Петри.
Расчет производился по одной ветке дерева достижимости.
Проверим является ли достижимой одна из маркировок получаемых на четвертом шаге построения дерева составив и решив матричные уравнения.
Маркировка для которой будем проверять её достижимость – [30011].
Общее уравнение для проверки достижимости искомой маркировки имеет вид:
Система уравнений полученная из данного равенства будет иметь вид:
Система имеет решение.
Следовательно маркировка [30011] достижима при этом для ещё достижения из исходной маркировки переходы не встретятся ни разу встретятся один раз а переход встретится 2 раза.
Задание 4. Математическая логика и теория автоматов
Конечный автомат задан графом определенным в задании 1 контрольной работы. Вершины графа отожествляются с состояниями автомата таким образом что множество состояний . Переход автомата из одногосостояния в другое осуществляется под воздействием множества входных сигналов Переходы определяются законом отображения Г вершин графа причем каждому переходу соответствует только одна из букв множества . При задании графа эти буквы расставить произвольно. Автомат позволяет вырабатывать выходные сигналы
– переход из состояния в состояние (петля);
– переход из состояния в при
– переход из состояния в при i > j.
Осуществить структурный синтез конечного автомата. Реализацию осуществить на D -триггерах на элементах ИЛИ-НЕ. Обязательной является минимизация реализуемых функций.
В задании 1 был получен следующий граф:
Задается множество входных сигналов Буквы соответствуют переходам и проставляются произвольно:
Рис.4.1. Ориентированный граф
Множество состояний при переходе к конечному автомату: . С учетом условий закон отображения запишется следующим образом:
Обобщенная таблица переходов и выходов соответствующего конечного автомата имеет вид:
Количество букв входного алфавита выходного алфавита количество состояний Определим:
- количество входов СА:
- количество выходов СА:
- количество элементов памяти т.е. количество необходимых триггеров:
Производим кодирование:
На основании результатов кодирования строим обобщенную таблицу переходов и выходов СА:
Используя таблицу переходов D-триггера и данные полученной таблицы составим обобщенную таблицу функционирования структурного автомата.
Из данной таблицы видно что:
Минимизируем данные функции пользуясь картами Карно.
Построим шифратор и дешифратор сигналов на входе и выходе:
Так как в минимизированных функциях используются элементы И-ИЛИ-НЕ а в задании указано реализацию осуществить на элементах ИЛИ-НЕ преобразовываем полученные функции к заданному базису.

Чертеж1.dwg