Блок схемы

Каждый отдельный процесс описывается программой. Программа представляет два различных аспекта процесса: вычисление и управление. Вычисление связано с текущими арифметическими и логическими операциями. Управление же связано не со значениями или выполняемыми вычислениями, а только с порядком их выполнения.

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

Стандартный способ представления структуры управления программ – блок-схемы. Блок схема представляет поток управления в программе.

Оказывается, блок схема во многом подобна сети Петри. Блок схема представима в виде узлов двух типов: принятия решений и дуг между ними. Удобный способ выполнения блок схемы – введение фишки, которая представляет текущую инструкцию. По мере выполнения инструкции фишка передвигается по блок схеме. Из сходства между графическим представлением программы и сети Петри можно заменить узлы блок-схемы на позиции, дуги на переходы.

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

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

Параллелизм.

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

Например, предложение по введению параллелизма основано на операциях parbegin parend. Смысл конструкции заключается в параллельном выполнении каждого из предложений S1 S2 …Sn. Эта конструкция может быть представлена сетью Петри.

Задача об обедающих мудрецах.

Связана с 5 мудрецами, которые по переменно то думали, то ели. Мудрецы сидят за большим круглым столом, на котором много блюд китайской кухни. Между соседями лежит одна палочка для еды. Однако для приема китайской пищи необходимо две палочки, следовательно, каждый мудрец должен взять палочку слева и палочку справа. Проблема, естественно, заключается в том, что если все мудрецы возьмут по палочку, то в итоге второй палочки они будут ждать вечно. Это моделируется сетью Петри. Позиции С1…с5 представляют палочки для еды. Каждый мудрец представлен 2 позициями – состояние размышления и принятия пищи. Для того, чтобы мудрец перешел из состояния размышления в состояние приема пищи, необходимо, чтобы палочки слева и справа были свободны.

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

Например, соединение водорода и этилена образует этан только в присутствии платины.

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

Агрегативные системы (Садовская А.)

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

Рассмотрим класс сложных систем, обладающих следующим свойством: существует такое – не однозначное в общем случае – разбиение системы на элементы, при котором каждый полученный элемент представляет собой агрегат. В дальнейшем такого рода сложные системы мы будем называть агрегативными или А-системами.

Естественно, что каждый элемент А-системы, будучи в общем случае агрегатом, не обязательно должен обладать полным комплексом свойств агрегата; он может быть и более простым объектом, представляющим собой частный случай агрегата. Вместе с тем среди элементов А-системы не может быть ни одного элемента, который не являлся бы агрегатом.

В качестве примера одна из возможных схем А-системы приводится на рисунке. Прямоугольники, помеченные буквами А1, А2 … обозначают агрегаты А-системы. Функционирование А-системы с переработкой информации. Передача информации показана стрелками.

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

Обмен информацией между А-системой и внешней средой происходит через агрегаты, называемые полюсами системы. Так, имеются входные полюсы, представляющие собой агрегаты, для которых входная информация, поступающая в виде (х)-сообщений, является полностью или частично внешней информацией. На рисунке входными полюсами являются агрегаты А1 и А4. Все (х)-сообщения, поступающие к агрегату А1, представляют собой внешнюю информацию. Для агрегата А4 дело обстоит иначе. Соответствующие (х)-сообщения являются лишь частично внешней информацией. Некоторая часть (х)-сообщений поступает к агрегату А4 от агрегата А5 и является внутренней информацией А-системы. Наряду с входными полюсами рассматриваются управляющие полюсы. Управляющими полюсами А-системы называются агрегаты, для которых (g)-сообщения, поступающие по особым входным каналам, представляют собой полностью или частично внешнюю информацию.

Для случая А-системы на примере, управляющими полюсами являются агрегаты А1, А3 и А6. Все (g) – сообщения, поступающие к агрегатам А1 и А3 являются внешней информацией. Поступающие к агрегату А6 сообщения частично оказываются внешней информацией и частично внутренней, поступающей от агрегата А2.

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

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

В частном случае А-система может не содержать внутренних агрегатов и состоять только из полюсов. Могут быть также случаи, когда в А-системе отсутствуют входные и управляющие полюсы. Такая А-система воспринимает соответственно только управляющую или только входную информацию. Наконец А-система может состоять лишь из одного агрегата. Этот агрегат может быть входным, управляющим и выходным полюсом А-системы.

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

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

Свойства А-системы определяются не только свойствами составляющих агрегатов, но также и её структурой. Рассмотрение структуры начнем с определения соотношений взаимодействий между агрегатами.

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

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

Агрегат А1 непосредственно предшествует агрегатам А2 и А5. Агрегат А3 непосредственно следует за А2 и предшествует А7.

Агрегат В непосредственно управляет агрегатом С, если некоторая часть управляющей информации агрегата С представляет собой часть выходной информации агрегата В. данный агрегат может непосредственно управлять несколькими агрегатами или быть непосредственно подчинен нескольким агрегатам А-системы. В примере, А1 непосредственно управляет агрегатом А2, а агрегат А6 непосредственно подчинен агрегату А2.

Любая подсистема А-системы представляет собой также А-систему. А-система называется комплексом, если любой её агрегат связан хотя бы с одним агрегатом этой А-системы.

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

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

Агрегаты А1, А2,А3,А4 – комплекс Ф1. Агрегат А5- Ф2. А6,А7 и А8 представляют комплекс Ф3.

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

В комплексе К1 – входной полюс агрегат А1, в комплексе К2 - агрегат А8, в комплексе К3 – агрегат А10. Выходными полюсами являются агрегаты А7, А9, А15. Многоканальная А-система не является комплексом. А-система называется иерархической. Если она состоит из некоторого количества комплексов, подчиненных 1 комплексу.

Разбиение системы на агрегаты не является единственным. Возможны различные варианты агрегативного представления системы. Необходимо иметь в виду, что при объединении нескольких агрегатов в один суммарный существенную роль играют связи между агрегатами. Характер этих связей оказывает значительное влияние на тип и свойства суммарного агрегата. К этому объединению можно подойти и чисто формально. Для этого должны быть построены операции над агрегатами, отображающие множество агрегатов на себя.