Спирина, М.С. Дискретная математика

Рис. 2.22. Сеть Петри вокупности фреймов нуждает­ ся в указании отношения меж­ ду ее вершинами, что тоже воз­ можно осуществить в виде сло­ та. Семантические сети широко применяются в информатике, например, для операций поис­ ка по образцу, где в виде сетей представляется база данных. Ре­ зультат такого поиска можно изобразить графом. Использу­ ются сети и для графической иллюстрации системы отноше­ ний базы данных. Широко применяются сети для графического изображения различных логических схем в тео ­ рии автоматов, например схемы с памятью, у которых каждый узел F(i) — функция алгебры логики (см., например, рис. 7.2 и 7.3). Для формального описания совокупности процессов, проте­ кающих одновременно, используют сети Петри. Они представля­ ют собой ориентированные графы, состоящие из вершин двух видов: некоторых позиций и переходов, причем позиции изобра­ жают кружочками, а переходы —«планками» (рис. 2.22). Сети Петри предназначены для описания действия дискретных процессов во времени. Такие сети дают возможность моделировать ситуации протекания параллельных процессов, прослеживать возможные варианты их взаимодействия, выявлять нежелательные ситуации. Также в виде сетей изображаются схемы устройств, например р а ­ диоприемника или телевизора. 2.6. Применение графов и сетей Храни порядок, и порядок сохра­ нит тебя. Латинская формула Сети получили широкое практическое применение потому, что они являются естественным и удобным способом изображе­ ния и дальнейшего анализа различных сложных систем. Одним из первых применений сетевого изображения было создание ам е ­ риканскими учеными баллистических ракет «Поларис» для о с ­ нащения атомных подводных лодок военно-морского флота США. В реализации этого грандиозного проекта участвовали 600 фирм из 48 штатов. Сам сетевой граф содержал 10000 событий. В основе 91