Питерсон Дж. - Теория сетей Петри и моделирование систем - 1984 (1184511), страница 41
Текст из файла (страница 41)
Теория комплектов является естественным расширением теории множеств. Комплект, подобно множеству, есть набор элементов из некоторой области. Однако в отличие от множества комплекты допускают присутствие нескольких экземпляров одного и того же элемента. В теории множеств элемент есть либо элемент множества, либо не элемент множества. В теории комплектов элемент может входить в комплект нуль раз (не входить 'в комплект) или один, два, три или любое заданное число раз. Теория комплектов была разработана в (50, 237].
В качестве примера рассмотрим следующие комплекты над областью(а,Ь,с,а):В, = (а,Ь,с),В»= (а), В, = (а,Ь,с,с),В»= = (а, а, а), В» =- (Ь, с, Ь, с), В» =- (с, с, Ь, Ь), Вг — — (а, а, а, а, а, Ь, Ь, с, д, а, д, а, д, с~, а). Некоторые комплекты являются множествами (например, В, и В,).
Так же как и в множествах, порядок элементов в комплекте не важен. Поэтому В, и В, являются одними тем же комплектом (упорядоченные комплекты являются последовательностями). В теории множеств основным понятием является отношение включения. Это отношение связывает элементы и множества и определяет, какие элементы являются членами каких множеств. Основным понятием теории комплектов является функция числавкэелитляров. Эта функция определяет число экземпляров элемента в комплекте.
Обозначим число экземпляров элемента х в комплекте В через ф(х, В) (читается»число х в В»). Исходя из зтога понятия, можем определить основы теории комплектов. Большинство понятий и обозначений заимствованы нз теории множеств. Если мы ограничим число элементов в комплекте так, что О ( Щх, В) ~ 1, то получим теорию множеств. АЛ. Членство Функция Щх, В) определяет число экземпляров элемента х в комплекте В. Отсюда следует, чта ~'-(х, В) ~- 0 для всех х и В. Мы различаем нулевой и ненулевой случаи.
Элемент х является членом комплекта В, если ф~(х, В) = О. Это мы будем обозначать через х ~ с В. Аналогично, если ф(х, В) =- О, то х а В. Определим пустой комплект и, не имеющий членов (для всех х: )ф (х, И ) = 0). Глава 8 А.2. Мо~цность Мощность ~В) комплекта В есть общее число экземпляров элементов в комплекте 1 В ~ =,'Е~ Ф(х, В).
А.З. Включение и равенство комплектов Комплект А есть подкамплаоп комплекта В (обозиачается Аы я; В), если каждый элемент А является элементом В по меньшей мере не большее число раз: Аы В тогда и только тогда, когда ф(х, А) ( Щх, В) для всех х. Два комплекта равны (А = В), если Щх, А) = $„(х, В) для всех х. Из этих определений мы можем непосредственно показать, что А = В тогда и только тогда, когда А =- В и В: — А, Яи В для любого комплекта В; из А = В следует )А [ = ~В1; из А ы В следует 1А) ~ «В!.
Комплект А ппрого включен в комплект В(А ~ В), если Аы В и А + В. Отметим, что ф(х, А) < ф(х, В) не следует из А ~ В, хотя и ~А)~ !В!. А4. Операции Над комплектами определяются четыре операции. Для двух комплектов А и В мы определим: объединениекомплектовАЦВ. "ФФ(х, А() В)=шах (Ф(х, А). Ф(х, В)); пересечениекомплектов А П В .
"Ф: (х, А П В)=пйп (Ф (х, А), Щх, В)); сумму комплектов А+В: 4Ф (х, А+ В) = т" (х, А) + ~ (х, В); разностькомплектовА — В; Ф (х, А — В)= ~ (х, А) — Щх, А()В). Эти операции обладают большинствам ожидаемых свойств. Объединение, пересечение и сумма коммутативиы и ассоциативны, кроме того, справедливы ожидаемые включения: АПВ~Ас:-А~ЗВ; А — В~АаА+В. Различие между объединением и суммой очевидно: !АЦВ! «=)А~+1В!; ~ А+в1= ~ А !+ 1 в~. К сожалению, различия между А Г1 В и А — В нельзя так же легко проиллюстрировать, что объясняется невозможностью для операции разности удаления элементов из комплекта, которые не входят в него. Обзор теории хомплеитое А.%.
Пространство комплектов Определим облить Р как множество элементов, из которых составляются комплекты. Пространство комплектов Р" есть множество всех таких комплектов, что элементы их принадлежат Р и ни один элемент не входит в комплект более и раз. Иначе говоря, для любого В бР": 1 Из х бВ следует х ЕР. 2. Для любого х Щх, В) (и. Множество Р есть множество всех комплектов иад областью Р без какого-либо ограничения на число экземпляров элемента в комплекте. А.б. Отображения Парика Для конечной области Р = (йо е),, ..., а„) существует естественное соответствие между каждым комплектом В над Р и и-некто. ром ~ = ф, ~„..., )„), определяемым соотношением ~; =-- ф(до В). Этот вектор известен как отображение Париха (229).
А.У. Примеры ~З Пусть Р = (а, Ь, с, а) — область. Тогда для следующих комп- лектовЛ=-(а, Ь), В==-(а,а, Ь,с),С=(а,а,а,с,с)имеем: )А! =2, )С! =5; А()В=(а, а, Ь. с) =В, А()С=(а,а, а, Ь, с, с) =В()С; АПС=(а). В()С=-(а, а, с); А+ В =(а, а, а, Ь, Ь, с), А — В = о; С вЂ” Л = (а, а, с, с), С вЂ” В = (а, с). АННО1ИРОВАННАЯ БИБЛИОГРАФИЯ Эта аннотированная библиография дополняет наше изложение теории сетей Петри. Как н следовало ожидать, представить все существующие работы по сетям Петри оказалось невозможно. Более полную информацию вы сможете почерпнуть из другой научной литературы.
К сожалению, многие нсследовання по сетям Петри доступны только в качестве технических отчетов тех институтов, где они были выполнены, а в журналах появляется только нх конспективное изложение. Очевидно, что поиск этих работ соприжен с определенными трудностями. Всего имеются три основных типа источников работ по сетям Петри: журналы, отчеты и материалы конференций. Теоретические журналы по вычислительной технике являются наиболее доступным источником. В число таких журналов следует включить: Тйеогс!!са! Сотригсг 8с!слсе, 1оигпа1 о7 Со!при!ег апд 8уя!ет 8с!епсея, 1пгоггпа!!оN алд Соп!го! апд !оигпа! ог !Ье АСМВ.
Статьи, опубликованные в журналах, как правило, впервые появлялнсь в качестве технических отчетов, которые можно получить только в органнзацкн, выпустившей тот илн иной отчет, обычно это факультет университета. Многие факультеты оформляют диссертации на соискание степени доктора философии, как технические отчеты. Отчеты доступны также в качестве микрофильмов в Аин-Арбор, штат Мичиган. Основным источником по сетям Петри были работы, выполненные в Массачусетском технологическом институте 1МТИ). Первоначально этн отчеты были выпущены Проектом МАС.
Проект МАС изменил свое название н теперь именуется Лабораторией вычислительной техники. Другим важным источником научно-нсследовательскнх отптов является Институт исследований информационных систем при Обществе математики и обработкидаиных в Бонне, ФРГ. Наконец, источником результатов исследований по теории сетей Петри являются материалы конференций. Однако интересующие нас работы рассеяны по многим кояференцням, а число тех, которые представляют действительно новое, небольшое. Сообщения, связанные с сетями Петри, можно встретить на ежегодном симпозиуме. Бнбпиографня 1, АЬгаЬаш 3., Оп Ма1г!х Огапппагя, ТесЬшса1 Керог1 3, Оераг1гпеп! о1 Соври!ег 3с!епсея, ТесЬп!оп — !ягае! !пя1!1п1е о! Тесйпо!оиру, На!!а, 1ягае1, Арг!1 1970, рр.
12. 2. Ас1авя П., А Согпрп!а11опа1 Моде! ъч1Ь Ва1а Г1ояч Бецпепс!пд, РЬ. П. д1яяег!а!!оп, Соври1ег 3с!енсе Берат!вен!, Яап1огд 11п!чегя!1у, Яап!огд, Са!!1огп!а, ПесевЬег 1968, рр. 134; ТесЬпгса1 !1ерог1 117, Соври!ег 3с1епсе Пераг1веп1, Яап!огд Нп!чегя!1у, Яап!огд, Ся!!!ого!а, ОесешЬег 1968, рр. 130.
!) Среди советских журналов следует отметить: Автоматика и телемеханика, Автоматика н вычислительная техника. Кибернетика„Известия АН СССР. Техническая кибернетика. — Прим. ряд. йнногированная библиография 3. Айапв Р., А Мойе1 !ог РагаИе1 СощрЫа11опз, Рагайе1 Ргосеяяог Зрв!етя, Тесйпо!обвея апд А рр!!сабо|и, Хеж 'г'огас; браг1ап ВооИЬ 1970, р. 311— 334. 4. Аяегч|а!а Т., А Соп|р1е1е Мойе! !ог Кер|еяепНпб 1Ье Соогйшайоп о! АяупсЬгопонз Ргоссяяев, НорИпз Сошрц1ег КеяеагсЬ Керог1 Хо. 32, Сощрц1ег бе|енсе Ргобгаш, ЛоЬпз НорИпв 1Лп1тегвНу, Ва1Н|поге, Магу!апд, Лп1у 1974, рр. 58.
Определяется расширенная модель сети Петри, которая допускает сдерживающие дуги. Показано, что эта расширенная модель эквивалентна машине Тьюринга. Поскольку машина Тьюринга может моделировать любую алгоритмическую схему управления происссов, она называется полной. Расширенная модель сети Петри также полна.
5. Абег|ча1а Т., Ап Апа!увМ о1 Соп1гоН!пб Аяеп1в 1ог АяупсЬгопопя Ргосемев, 1.!орИпв Сощрщег КеяеагсЬ Керог1 Хо. 35, Согпрц1ег Бе!енсе Ргоягащ, ЛоЬпв НорЫпв 13п|чешНу„Ва1Вщоге, Магу1апд, Ацпця1 1974, рр. 85. Для получения иерархии моделей, подобной иерархии из гл. 8, анализируются и сравниваются восемнадцать моделей параллельных вычислений, а таки е девять вариантов сети Петри. Эти результаты, хотя и согласуются с результатами работы [240), но они более категоричны и выведены независимо.
6. Аяегша!а Т., богпе АррНсайопя о! Ре1г| Хейн РгосеаБнбз ог Ме 7978 Яагюпа! Е!ес!готов Сол~егенсе, 23, Юс1оЬсг 1978, р. 149 — 154; Рцййпб Ре1г! Хе1з 1о Ъ'огй, Сотри!гг, 12, Хо. 12, 1979, р. 85 — 94. Прекрасная, хотя и краткая работа атом, как сети Петри могут использоваться для моделирования систем с параллельнымн деба|виями. Эго изложение является разумной альтернативой гл. 3. В работе представлены разнообразные приложения, включая аппаратное и программное обеспечение вычислительных систем, асинхронные схемы, явыкн проектирования и некоторые новые приложения.
7. Аяегч|а1а Т., Г1упп М., Сопппеп1в оп СлраЬ|1!11ев, Ь1щйа11опв апд 'Соггес1певв' о1 Ре1п Хейь Норв!из СошрЫег КеяеагсЬ Керог1 Хо. 26, Со|прп1ег Эс1епсе Ргопгаш, ЛоЬпз НорИпв 1 п1чегя11у, Ва!1!эпосе, Магу!апд, Лц1у 1973, рр. 58; Ргосеедй|йв о7 Ме г|гя! Аппии! $9тромит оп Сотри!ег Агой!!есФше, Хегс Уогй: АСМ, 1973, р. 81 — 86. 8.
Анетта!а Т., Г1упп М., Оп 1Ье Сошр1е1епезз о! Кергевеп1а11оп 5сЬе|пев 1ог Сопсцггеп! Буз1ещя, |ЛпрцЫ!вЬед, 1976, рр. 16. 9. Адегтча1а Т., Р!упп М., Моде!!пи вч1Ь Ех1епдед Ре1г! Хейк 1!прцЫ1- яЬед, 1976, рр. 18. 1О. Апдегяоп О., Ярагас!о Р.. Топ|авп1о К., ТЬе 1ВМ буз1еп|!360 Моде! 91: МасЫпе РЫ1ояорЬу апд 1пя1гпсйоп Напй1!пб, 7ВМ Лоигла! ог йевешс!г апд 7|все!ортел1, 11, Хо. 1, 1967, рр 8 — 24. В ЭВМ! ВМ 360|91 для получения высокой производительности используется параллелизм.
Поэтому если сети Петри являются хорошим средством моделирования параллельно действующей аппаратуры, то с их помощью можно моделировать устройство управления. Эта статья описывает основные действия устройства управления модели 1ВМ 360!91. 11. Апйге С., О1аг В1., Спгац11 С., 81!аЫв Л., 5пгтеу о! ГгепсЬ КевеагсЬев апд Арр11саНопв Вазед оп Ре1п' Хе1в, Адчапсед Сопгяе оп С|епега! Хс1 ТЬеогу о1 Ргосевяея апд Був1ещв, НагпЬцгб, 1979; 1.ес1пге Хо1ев |п Соп|рп1ег Бе!енсе, Вег1!п: Бр|!обет-Уег1яд (1980).
12. АпяЬе! М., Песндоп РгоЫегая 1ог НХХ Сгоцрв апд Ъ'ес1ог АйдНюп 'Був1ешз, Ма!!мта!1ся о7 Сотри!абаи, 30, Хо. !33, 1976, р. 154 — 156. !3. АгаИ Т., Казагп1 Т., 5огпе Рес1в1оп РгоЫепж Ке1а1ед 1о 1Ье КеасЬаЬННу РгоЫегп 1ог Ре1п' Хе!я, Тйеоге!Ма! Сотрийг Бс!енсе, 3, Хо. 1, 1976, р. 85 †1. 14. Ага!В Т., Каяащ! Т., Пес!даЫе РгоЫещв оп 1Ье 51гопб СоппесНИ1у о1 Ре1п' Хс1 йеасЬаЬ|1Ну 5е1я, ТБеоге1ка! Сотри!ег Бс!енсе, 4, Хо.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
