33632

Графические модели

Доклад

Информатика, кибернетика и программирование

Графические модели сети Петри которые позволяют построить модели дискретных систем. Определение: Сеть Петри это набор N =STFWM0 где S непустое множество элементов сети называемое позициями T непустое множество элементов сети называемое переходами отношение инцидентности а W и M0 две функции называемые соответственно кратностью дуг и начальной разметкой. Если п 1 то в графическом представлении сети число n выписывается рядом с короткой чертой пересекающей дугу. Часто такая дуга будет также заменяться пучком из п...

Русский

2013-09-06

44 KB

2 чел.

51. Графические модели

сети Петри, которые позволяют построить модели дискретных систем.

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

Определение: Сеть Петри это набор N =(S,T,F,W,M0), где S — непустое множество элементов сети, называемое позициями, T — непустое множество элементов сети, называемое переходами, - отношение инцидентности, а W и M0  — две функции, называемые соответственно кратностью дуг и начальной разметкой.

Первая сопоставляет каждой дуге число п > 0 (кратность дуги). Если п>1, то в графическом представлении сети число n выписывается рядом с короткой чертой, пересекающей дугу. Часто такая дуга будет также заменяться пучком из п дуг, соединяющих соответствующие элементы сети. Условимся никак не отмечать кратность дуг, равную 1. Вторая функция сопоставляет каждой позиции  некоторое число М0 (s)  N (разметка позиции).

В графическом представлении сети разметка позиции s изображается помещением в вершину-кружок числа М0(s) или, если это число невелико, соответствующего числа точек (маркеров).

Разметка сети N — это функция М: S N. Если предположить, что все позиции сети N строго упорядочены каким-либо образом, т.е. S = (s1,... ,sn), то разметку М сети (в том числе начальную разметку) можно задать как вектор чисел М = (m1, . . ., mn) такой, что для любого i, , mi = M(si).

На основе отношения инцидентности F и функции кратности дуг W можно ввести функцию инцидентности , которая определяется:

 F(x,y) = если  

Если позиции сети упорядочены, то можно каждому переходу t сопоставить два целочисленных вектора 'F(t) и F'(t) длиной n, где  n = | S |:

'F(t) = (b1, . . . ,bn),  где bi=F(si,t),

F'(t)  = (b1, . . . ,bn),  где bi=F(ti,s),

Переход t может сработать при некоторой разметке М сети N, если , т.е. каждое входная позиция s перехода t имеет разметку, не меньшую, чем кратность дуги, соединяющей s и t. Это условие можно переписать в векторной форме следующим образом:

М'F(t).

Срабатывание перехода t при разметке M порождает разметку М' последующему правилу:

M'(s)=M(s) - F(s,t) + F(t,s),  т.е.

М'=М - 'F(t) + F'(t).

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

Сети Петри позволяют моделировать сложные параллельные процессы и часто используются для моделирования систем защиты ВС.

Среди достоинств аппарата сетей Петри можно указать следующие:

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

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

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

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

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


 

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

77536. ГЕНЕТИЧЕСКИЕ АЛГОРИТМЫ И ИХ ПРИМЕНЕНИЕ 299 KB
  В животной клетке каждая молекула ДНК окружена оболочкой – такое образование называется хромосомой. Основная часть хромосомы нить ДНК определяющая какие химические реакции будут происходить в данной клетке как она будет развиваться и как функции выполнять. В каждой соматической клетке человека содержится 46 хромосом. Эти 46 хромосом на самом деле 23 пары причем в каждой паре одна из хромосом получена от отца а вторая от матери.
77537. РАСПОЗНАВАНИЕ ОБРАЗОВ И СИТУАЦИЙ 89 KB
  Суть задачи распознавания – установить обладают ли изучаемые объекты фиксированным конечным набором признаков позволяющим отнести и ке определенному классу. Цели науки распознавания образов: замена человеческого эксперта или сложной экспертной системы более простой системой автоматизация деятельности человека или упрощение сложных систем; построение обучающихся систем которые умеют принимать решения без указания четких правил а именно систем которые умеют сами синтезировать правила принятия решений на основе некоторого конечного...
77538. МУЛЬТИ-АГЕНТНЫЕ ИНТЕЛЛЕКТУАЛЬНЫЕ СИСТЕМЫ 96.5 KB
  Системы группового управления должны обеспечить возможность быстрой перестройки производства к изменению типа и объёма выпускаемой продукции в изменяющейся среде. Первоначально были разработаны принципы централизованного и децентрализованного группового управления сложными робототехническими системами. При децентрализованном управлении использовались распределённая группа микропроцессоров встроенных в локальные системы управления гибко программирующие поведение роботов и оборудования в соответствии с заданной в реальном времени...
77539. ИНТЕЛЛЕКТУАЛЬНЫЕ СИСТЕМЫ УПРАВЛЕНИЯ 66 KB
  Изменения во внешней среде влияют не только на сам МО но и на выбор требований к цели и качеству управления и как следствие на характер желаемых траекторий движения рабочих органов. Современные МО должны обладать возможностями выполнения функций принятия решений и управления близкими к интеллектуальным функциям человека а по скорости получения решений существенно превышать возможности человека. Эти функции реализуются с помощью современных средств вычислительной техники в интеллектуальных системах управления ИСУ.
77540. Основы искусственного интеллекта (ИИ). Создание высокоавтоматизированных производств 111 KB
  Прогресс в области информатизации практически всех сфер деятельности человека, в том числе в мехатронике и робототехнике связан с тем, что часть интеллектуальной нагрузки берут на себя компьютеры. Одним из способов достигнуть максимального прогресса в этой области, является искусственный интеллект
77541. Представление знаний о внешнем мире в интеллектуальных системах 146.5 KB
  Определение того что представлять и как представлять знания. Для функционирования ИС требуются следующие знания: знания о процессе решения задачи; знания о языке общения и способах организации диалога используемые лингвинистическим процессором; знания о способах представления модификации знаний используемые компонентом приобретения знаний; поддерживающие структурные и управляющие знания используемые объяснительным компонентом; знания о методах взаимодействия с внешним окружением; знания о модели внешнего мира. Знания....
77542. Продукционные модели знаний 87.5 KB
  Продукционные модели знаний занимают особое положение, т. к. они являются наиболее декларативным способом представления знаний. Продукционная модель представления знаний – это набор правил вила
77543. Семантические сети и их особенности 108.5 KB
  В бытовом понимании семантика означает смысл слова, действия, художественного произведения и т.п. Семантическая сеть – это граф, вершинам которого сопоставляются понятия (объекты, процессы, явления), дуги графа – это отношения между вершинами.
77544. Крепостное право и кодификация законов 213 KB
  Понять, как положение крепостных отражено в праве. Проанализировать, как сочетаются крепостное право и абсолютизм. Разобраться в том, какие права были у помещиков, а какие у крепостных. Найти ответ на вопрос, что представляло собой крепостное право в эпоху оформления законов и сохранения крепостничества.