Горбатов В.А. Фундаментальные Основы Дискретной Математики. Информационная Математика

§4.11. Моделирование автоматных систем сетями Петри 381

Возможность решения задач активности и достижимости огра

ничена существованием символа ш, скрывающего конкретную ин

формацию о числе фишек. Например, если в сеть Петри, изобра

женную на рис. 4.87,5, ввести две дуги (^, р2)i (Р2, h), то полу

ченная сеть Петри будет иметь то же дерево достижимости, что и

первоначальная. При этом в новой сети Петри в позиции р2 может

быть только четное число фишек, тогда как в первоначальной се

ти — любое, т. е. множества достижимости этих сетей Петри

не совпадают. Можно привести разные сети с различными свой

ствами активности, но имеющие одно дерево достижимости.

Тем не менее, хотя дерево достижимости и не дает полной ин

формации о свойствах достижимости и активности, в некоторых

случаях оно позволяет ответить на вопросы по достижимости и ак

тивности. Например, если в нем имеется терминальная вершина,

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

может оказаться, что маркировка у! присутствует в дереве дости

жимости (положительный ответ) или что маркировка ц' не покры

вается никакой вершиной дерева достижимости, т. е. /х" ^ ц для

всех вершин fi" (отрицательный ответ).

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

и основан на их матричном представлении. Введем матрицы D~

и D+, столбцам которых соответствуют позиции, строкам — пе

реходы, и D~{j, t) = #(р,-, D+{j, г) = 0{tj)). Пусть

e(j) — вектор-строка, компоненты которой соответствуют пере

ходам и все равны нулю, за исключением j-й, которая равна 1.

Тогда переход tj разрешен, когда fi > e(j) • D~ (р. рассматри

вается как вектор), а результатом запуска tj из fi является fi' =

- f i- e(j)D~ + e(j)D+ = fi + e(j) • (D+ ~D~)~ ц + e(j) ■ D, где

D — D+ — D~ — составная матрица изменений.

Маркировка fi', получающаяся из fi в результате запуска после

довательности а = tjl tj2.. ,tjk, определяется как

ц' = ц + e(ji)D + e(j2)D + ... + e(jk)D =

= M + (с(л) + • • • + e(j*)) =fi + }{o)D,

где f(a) = e(ji) + ... + e(jk) — вектор запуска, i-я компонента

которого равна числу запусков tji в а.

Если маркированная сеть Петри является сохраняющей по от

ношению к некоторому вектору взвешивания W (W — вектор-

столбец), то fiW — fi'W для любой fi' — R(C, fi). Так как fi' —

55 fi + то f (a)DW — 0. Поскольку это верно для всех

/(<т), имеем DW — 0. Следовательно, сеть Петри является сохра

няющей по отношению к некоторому вектору взвешивания тогда

и только тогда, когда имеется такой вектор W, что DW = 0. Это

уравнение позволяет отыскать и сам вектор взвешивания W.

382

Гл. 4. Теория формальных грамматик и автоматов

Бели маркировка /х' достижима из начальной маркировки /х

сети Петри, то должно существовать целое неотрицательное реше

ние уравнения /х' = /х + хD, решением которого будет х = /(с).

Исследуем задачу достижимости для сети Петри, изображенной на

рис. 4.87,5, с начальной маркировкой (1,0,0,0) для маркировки р! = (0,2,1,2).

Уравнение р! = р + xD принимает вид

0 10 0

(0, 2, 1, 2) = (1, 0,0,0)+х- ‘

0-1 0 1

- 1 0 1 0

0 0 -1 0 J

и имеет решение х = (4, 2, 1, 0), соответствующее последовательности запусков

переходов ti ti t\t\ts t2 t2.

Матричный подход к анализу сетей Петри, как и подход, осно

ванный на дереве достижимости, не позволяет в общем случае ре

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

анализа заключаются в том, что, во-первых, вектор запуска, полу

чаемый при решении уравнения, не дает информации о порядке

запуска переходов и, во-вторых, может соответствовать неразре

шенной последовательности запусков.

В настоящее время установлено, что задачи достижимости и

активности эквивалентны, но не известно, разрешимы ли они

вообще, т. е. нет ни алгоритма, позволяющего решить эти задачи,

ни доказательства его отсутствия.

Рассмотрим применение методов анализа сетей Петри, модели

рующих практические системы.

Специализированная параллельная система для реализации интеграцион

ных вычислительных процессов состоит из совокупности процессорных элемен

тов (ПЭ) и модулей памяти (памяти данных (МПД) и памяти команд (МПК)),

связанных в кольцо (рис. 4.89). ПЭ работает в двух режимах. В первом слу

чае он захватывает оба смежных МПД, используя левый для извлечения исход-

МПК

[МПД71 |мпдЗ

[ ш ж Н г о р р т а Л =|мпк1

Рис. 4.89

ных данных новой итерации, правый — для выборки результатов предыдущей

итерации. По завышении итерации он помещает результат в правый МПД и

освобождает оба МПД. В другом режиме ПЭ работает с внутренними данными.

Режим указывается командой, считываемой их МПК. Рассмотрим два варианта

реализации устройств управления ПЭ. В первом варианте захват МПД при осу

ществлении итерации производится последовательно. ПЭ может находиться в

следующих состояниях: “обработка внутренних данных” (Si), “захвачен левый

§4.11. Моделирование автоматных систем сетями Петри 383

МПД” (S2), “захвачен правый МПД” (S3), “захвачены оба МПД, обработка дан

ных очередной итерации” (£ 4)- МПД может быть либо свободным, либо захва

ченным. Событиями будем считать захват и освобождение МПД. Этот вариант

работы представляется сетью Петри, в которой каждому ПЭ соответствуют четыре

позиции, реализующие описанные условия, а каждому МПД — позиция (фишка

х которой означает, что МПД свободен; (рис. 4.90). Можно убедиться, что де

рево достижимости этой сети Петри содержит две терминальные маркировки:

Рис. 4.90

Рис. 4.91

384

Гл. 4. Теория формальных грамматик и автоматов

щ = {Sj, Sj, S|} и Ц2 = {5з, 5|, S f}, представляющие ситуацию, когда ка

ждый ИЭ захватывает левый и правый МПД соответственно. Это означает, что

сеть Петри не активна, т. е. в системе возможны тупиковые ситуации.

При другом варианте работы системы ПЭ осуществляют только одновремен

ный захват смежных МПД (если он возможен). В этом случае каждому ПЭ соот

ветствуют только условия Si и St (рис. 4.91). Дерево достижимости (рис. 4.92)

не содержит терминальных маркировок, сеть Петри активна. Кроме того, из рас-

СО 1 0 0 1 10 1

(11110 10 1

(111 1 0 10 10)

0) (0 0 1 1 0 0 1 1 0) (1 0 0 1 0 1 0 0 1)

\ч

0) (11110 10 10) (111101010)

Рис. 4.92

Г -1

0 -1 -1 1 0 0 0

0 1

1 1

-1 0 0

-1

-1 0 0

0 -1

1 0

1 1 0

0 0 1 -1

0 -1 -1 0

0 0

0 -1

. 0 1 1 0

0 0 1

-1 .

смотрения дерева достижимости очевидно, что сеть Петри безопасная (позиция

интерпретируется как простые условия). В системе осуществляется распреде

ление ресурсов, которые ие появляются и ие исчезают, т. е. выполняется закон

сохранения. Определим, является ли сеть Петри сохраняющей. Для этого решим

уравнение DW = 0, которое принимает вид

U12

U)3

U)4

Ws = 0.

. 11)9

Решением его является W = (1, 1, 1, 1, 3, 1, 3, 1, 3). Действительно, позиции

Pii Рт, Рэ представляют условия, связанные с тремя устройствами, остальные

позиции — условия, которые связаны с одним устройством. Таким образом, сеть

Петри обладает основными необходимыми свойствами, что обеспечивает работо

способность второго варианта.

Попытки моделирования реальных систем привели к различ

ным доопределениям и модификациям сетей Петри. В основном

эти модификации связаны с изменением правила запуска перехо

дов.

Мощность моделирования

обычных сетей Петри ограничена

невозможностью проверки позиции на нуль (т. е. того, что мар

кировка позиции нулевая). Одним из способов преодоления этого

недостатка является введение сдерживающих дуг. По новым пра

вилам запуска переход разрешен, если фишки есть в его обычных

входных позициях (из которых ведут обычные дуги) и отсутствуют

в сдерживающих входных позициях (из которых ведут обычные

дуги). Сдерживающая дуга изображается как обычная, только

на конце имеет вместо стрелки маленький кружок (это обозначе

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

§4.12. Задачи и упражнения 385

означает “не”) (рис. 4.93). Если в обычных сетях Петри пере

ход запускается по логике И, то в сетях Петри со сдерживающими

дугами логика расширена до включения отрицаний. Поскольку

событие может представляться несколькими переходами, можно

смоделировать событие, предусловие которого записывается как

объединение нескольких конъюнкций

условий и отрицаний условий, соответ

ствующих позициям сети Петри со сдер

живающими дугами. Таким образом,

сети Петри позволяют моделировать

предусловия в виде ДНФ, т. е. условия 1

самого общего вида.

Рассмотренная задача организации работы

специализированной вычислительной системы

может быть решена и первым вариантом, в ко

тором разрешен последовательный захват МПД ^ 3

(см. рис. 4.90), но с предотвращением тупико- 2 2

вых ситуаций. Очевидно, что возможны две ту- рис_ 4 93

пиковые ситуации, описываемые маркировками

с фишками в позициях 5^, S|, и S3 , S3 , S3 . Для предотвращения первой

тупиковой ситуации необходимо в маркировках {Sj, 5?}, {£2 , { 5 | , 5| }

предотвратить появление фишки в позициях S%, S%, соответственно. Следо

вательно переход t\ должен иметь в качестве предусловия конъюнкцию МПД1 &

icSI ic(S[ к S | ), т. е. его нужно заменить иа переходы t[ и t" с предусловиями

МПД! L. s j fc Si и МПД! icSf к S j (см. рнс. 4.93). Аналогично следует посту

пить с переходами 15 , 19 (см. рис. 4.90). Подобные действия предпринимаются

и для предотвращения второй тупиковой ситуации.

Другие предложения по изменению правил запуска либо экви

валентны введению сдерживающих дуг, либо носят даже более

частный характер. Например, в сетях Петри с областями ограни

чения имеются множества позиций (называемые областями огра

ничения), в которых фишки одновременно находиться не могут.

Правила запуска модифицированы так, чтобы не нарушать это

условие. Если в сеть Петри, изображенную на рис. 4.90, включить

две области ограничения, {5^, 5|, и {5з, 5|, 5|}, то можно

предотвратить возникновение тупиковых ситуаций.

§4.12. Задачи и упражнения

4.1. Составить функциональную таблицу машины Тьюринга при суммиро

вании 1 к числу, записанному в троичной системе счисления.

4.2. На ленте записано число в системе счисления с основанием Q. Сос

тавить функциональные таблицы, с помощью которых можно записать число:

а) непосредственно следующее за данным; б) непосредственно предшествующее

данному.

4.3. На ленте записано число х в троичной системе. Составить функцио

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

иа 3 без остатка, и х — 1 в противном случае.

4.4. Синтезировать криотрониую схему, реализующую функцию

13 В. А. Горбатов

/(*,,**, хз, х4)|, = V(l, 3, 7, 8, 9, 10, 12, 15).

386

______

Di. 4. Теория формальных грамматик и автоматов

4.5. Как учитывается коэффициент разветвления, определяемый нагрузоч

ными способностями заданного базисного элемента, при использовании коалгеб-

ры графов К1

4.8. Сравнить сложности счетчиков четности от трех переменных в базисе

Вебба и Шеффера.

4.7. Сравнить сложности счетчика четности от трех переменных в базисе

Шеффера, построенного методом моделирования связок алгебры Буляи методом,

который осиоваи иа применении коалгебры графов К.

4.8. Минимизировать количество нетерминальных символов автоматной

грамматики, определяемый секвенциями вида:

051 —^ 521, 5в0, 052 5з 1, 152 570,

053 —> 551, 153 5$0, O54 —> 5g0, I54 —> 531,

O55 5^1, 1.55 54O, 056 —^ 5g0, 15б —► 5s0,

O57 —> 5g0, I57 — i 5j 1, Osg -+ 5g0, l5g -+ 520,

где Si (i = 1, ..., 8) — нетерминальный символ; 0, 1 — терминальные символы

(левый относительно стрелки входной, правый выходной).

4.9. Произвести соседнее кодирование нетерминальных символов автомат

ной грамматики, заданной в предыдущей задаче.

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

дами для автомата, рассмотренного в предыдущей задаче.

4.11. Построить функцию возбуждения второго триггера со счетным входом

для автомата, рассмотренного в задаче 4.9.

4.12. Синтезировать триггер со счетным входом в импликативном базисе.

4.13. Синтезировать триггер с раздельными входами в коимпликативном

базисе.

4.14. Синтезировать генератор последовательности чисел 1, 7, 0, 2, 5, 1, ...

в базисе Жегалкина.

4.15. Синтезировать логическую схему, реализующую булеву функцию

/(хj, х2, хз, x4)|i = V(0, 1, 2, 7, 11),

в первом топологическом базисе.

4.18. Синтезировать логическую схему, реализующую булеву функцию

/(х 1, Х2, хз, x4)|i = V(0, 1, 2, 4, 15),

во втором топологическом базисе.

4.17. Синтезировать, логическую схему, реализующую булеву функцию

/(х 1, Х2, х3, x4)|i = V(0, 3, 5, 10, 12, 15),

в третьем топологическом базисе.

4.18. Синтезировать логическую схему, реализующую булеву функцию

/(гI, х2, х3, x4)|i = V(0, 3, 5, 6, 9, 10),

в четвертом топологическом базисе.

4.19. Синтезировать логические схемы, реализующие булеву функцию

/(хj, Х2, х3, x4)|i = V(0, 1, 2, 12, 13, 14),

в базисах Вебба и Шеффера. Сравнить, сложности полученных схем.

4.20. Синтезировать логическую схему, реализующую булеву функцию

/(xi, х2, х3, x4)|i = V(0, 1, 2, 4, 7, 9),

в базисе УСЭППА.

4.21. Может ли иметь автомат эквивалентные состояния, если его граф

переходов представляет собой взвешенный путь?

4.22. Синтезировать иейрон, реализующий булеву функцию вида

/(xi, Х

, Х3, x4)|i = V(0, 2, 3, 5, 12, 14).

§4.13. Комментарии 387

§ 4.13. Комментарии

Создание систем автоматизации проектирования, гибкого автоматизирован

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

знаний — решение этих и других проблем невозможно без формализации, основу

которой составляет теория формальных грамматик и автоматов. В развитие этой

теории большой вклад внесли ученые — члены академий: Международной Ака

демии информатизации, Российской академии наук, Российской академии есте

ственных наук — В.М.Глушков, М.А. Гаврилов, В.А. Горбатов, Э.В.Евреинов,

А.В. Каляев, В.Г. Лазарев, П.П. Пархоменко, Д.А. Поспелов, В.П. Чистов, И.И. Юз-

аишнн, Э.А. Якубайтис и др.

Для углубления знаний по теории1 формальных грамматик и автоматов ре

комендуем [1,6,7,10,13,21,27].

Где круга этого начало, где конец, откуда мы

пришли, куда уйдем отселе?

Омар Хайлм

Глава 5

ПРИКЛАДНАЯ ТЕОРИЯ АЛГОРИТМОВ.

ХАРАКТЕРИЗАЦИОННЫЙ АНАЛИЗ

§ 5.1. Принципы характеризационного анализа.

Построение комбинаторных алгоритмов

Характерной чертой современной научно-технической револю

ции является возрастающая роль вычислений комбинаторного (пе

реборного) характера в прикладных задачах. Актуальной пробле

мой дискретной математики является построение эффективных

как по объему необходимой памяти, так и по быстродействию ком

бинаторных алгоритмов.

Прикладные задачи можно подразделить на задачи анализа и

задачи синтеза дискретных систем. Под решением задачи анализа

подразумевается определение того, обладает ли модель Ф„, пред

ставляющая дискретную систему, требуемыми свойствами. Ре

шение задачи синтеза предполагает проведение преобразования

модели Фа в модель Ф(,, при котором достигается экстремум за

данного функционала качества <^(Фь). В обоих случаях можно

говорить об эквивалентировании. В задачах анализа по модели

Фв строится ее эквивалент, раскрывающий свойства модели. В

задачах синтеза модель Фа эквивалентируется синтезируемой мо

делью Ф(,. Как анализ, так и синтез осуществляют с помощью

комбинированных алгоритмов.

Примитивным классом комбинаторных алгоритмов являются

ГСН-алгоритмы (ГСН — грубая сила и невежество). Это алго

ритмы, лишенные какой-либо “искусности”, они решают задачи

“вслепую”, проводя полный перебор возможных преобразований.

В этом случае отсутствуют теоретические предпосылки, на основа

нии которых можно было бы предложить “утонченный” алгоритм

решения. В алгоритмах этого класса реализуется синтаксическое

эквивалентирование.

Синтаксическое эквивалентирование, называемое эквивален

тным преобразованием, соответствует уровню знаний, при кото

ром известна полная система аксиом. Оно заключается в построе

нии очередного варианта для задач анализа и в замене модели Ф„

моделью Ф(, для задачи синтеза на основании той или иной акси

омы или закона, полученного из системы аксиом. Дерево решений

при синтаксическом эквивалентировании изображено на рис. 5.1, а.

§5.1. Принципы характеризационного анализа

389

Каждая висячая вершина дерева соответствует тупиковому ре

шению. Характерными свойствами этого дерева являются:

1) комбинаторный рост числа висячих вершин при линейном

росте размерности задачи;

2) необходимость возврата на предыдущий, (г - 1)-й уровень

при вычислении информации, соответствующей соседней вершине

В i-м уровне. Следствием этого свойства является принципиальная

необходимость обхода всего дерева при поиске минимального ре

шения.

Эти свойства определяют явление, называемое “проклятием

размерности” или “информационным взрывом”.

При разработке математического и программного обеспечения

ЭВМ) особенно при работе в реальном масштабе времени, при со

здании систем автоматизации проектирования (проблема САПР)

я Т. д. актуальным является проектирование быстродействующих

пакетов прикладных программ. Для повышения быстродействия

алгоритмов используют эвристики в виде соответствующих функ

ционалов, найденных на основании опыта, аналогий, здравых со

ображений. В результате получают класс эвристических алгорит

мов. Примерами эвристических алгоритмов являются генетиче

ские, технологические (типа отжига), жадные, хитрые и другие

алгоритмы. При построении этих алгоритмов используется прин

цип аналогий на основе дескриптивной семантики. Алгоритмы

Этого класса реализуют эвристическое эквивалентирование. При

эвристическом эквивалентировании быстродействие алгоритма по

вышается, но оценить качество полученного решения невозможно;

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

Упрощаемым. Дерево решений, каждая вершина которого соот

ветствует исходному заданию, а дуга — варианту перебора или

преобразованию, изображено на рис. 5.1,5.

390

Гл. 5. Прикладная теория алгоритмов

Рассмотрим, например, задачу синтеза диверсифицированного

портфеля. Эта задача возникла при оценке риска в проводимой

фирмой инвестиционной политике. Финансовый риск связан с

неопределенностью эффективности операций в момент заключе

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

а для акций — и будущих дивидендов. Вложив деньги в акции

одной компании, инвестор оказывается зависящим от колебаний

ее курсовой стоимости. Если он вложит свой капитал в акции

нескольких компаний, то эффективность будет определяться уже

усредненным значением курсовых стоимостей нескольких компа

ний. Средний же курс, как правило, колеблется меньше, поскольку

при понижении курса одной из ценных бумаг курс другой может

повыситься, что приведет к меньшим колебаниям усредненного

курса. Именно этим объясняется, что инвестор часто является

держателем не одного вида ценных бумаг, а нескольких, именуе

мых портфелем инвестора. При росте числа N видов ценных бу

маг, включенных в портфель, риск ограничен и стремится к нулю

при N —^ оо. Этот факт известен в теории финансового риска как

эффект диверсификации (разнообразия) портфеля.

Эвристика, применяемая при решении задачи синтеза дивер

сифицированного портфеля, основана на принципе аналогий.

Вспомнив житейскую мудрость: никогда не клади все яйца в одну

корзину, формулируем эвристику решения этой задачи: задав

шись мощностью диверсифицированного портфеля, приобретаем

слабо связанные между собой виды ценных бумаг. Здесь под

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

Анализ западных финансовых рынков показал, что оптимальная

мощность портфеля инвестора не меньше 15. Для России, в ко

торой финансовый рынок только формируется, это число должно

быть гораздо большим.

Рассмотрим реализацию выбранной эвристики. Имеем множе

ство ценных бумаг М — {&,/ 6,- — ценная бумага}. На основе ана

лиза временных рядов изменения их курсовой стоимости строим

корреляционный граф GKopp =: (U, К)), каждая вершина

Vi € V которого взаимно однозначно соответствует ценной бумаге,

а ребро {и,, Vj} € U взвешено корреляционным коэффициентом

K(bi, bj) между ценными бумагами ft,, bj (рис. 5.2, а).

Установим порог существенной корреляции: K(bi, bj) > 0,5.

Тогда корреляционный граф GKOрр преобразуется в граф связности

ценных бумаг GCB — (V, U), и,- f* 6,-, {и,, Vj} € U if (ft,-, bj) > 5.

Если мощность 17Г| диверсифицированного портфеля 7Г равна

2, то, очевидно, его содержимое будут представлять ценные бу

маги ba, Ьр, расстояние p(ba, Ьр) между которыми равно диаметру

d(GCB) графа GCB:

P(ba, bp) — d(Gсв)-

Горбатов В.А. Фундаментальные Основы Дискретной Математики. Информационная Математика

Подождите немного. Документ загружается.