Студопедия

КАТЕГОРИИ:

АстрономияБиологияГеографияДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРиторикаСоциологияСпортСтроительствоТехнологияФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника


Детерминизм




" i Î I $! r Î R [ i F+ r ] – глобальный детерминизм

" s Î S \ R $! s’ Î S \ I [ s F s’ ] – локальный детерминизм


34. Неэффективные процессы и проблема их анализа. Преобразование неэффективных процессов: формальная постановка задачи.

Неэффективный пр-сс – пр-сс, в котором есть циклы.

 

Говорим про св-во эффективности (и строгой эффективности).

 

Преобразование неэффективных пр-ссов – заменяем вершины, образующие цикл на одну вершину, соответствующую классу эквивалентности. Отношением эквивалентности в данном случае будет отношение Е:

1) si E sj, если si F+ sj & sj F+ si

2) для любого s из S: s E s

 

Это отношение позволяет построит фактор-множество мн-ва S.

 

Получаем т.о. грай без циклов.

 

Можно ещё поговорить про классы эквивалентности вообще…

По Варшавскому (но это Красюку говорит нельзя):

Эффективный АП – АП, удовлетворяющий условиям:

1) " s Î S \ R $ r Î R [ s F+ r ];

2) " s Î S \ I $ i Î I [ i F+ s ];

3) не $ si, sj [si Ï R & sj Ï R & si F+ sj & sj F+ si ]

 

Т.о.: все траектории из инициаторов ведут в результанты (из 1 и 3); каждая траектория, приводящая к результанту, начинается в инициаторе (из 1 и 2).

 

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

 

Рассмотрим АП P = <S, F, I, R>, S ={s1, …, s6}, для которого отношение F задаётся рисунком. Если для него I = {s1, s4}, R = {s5}, то АП не явл. эффективным, т.к. не выполняется св-во 1). Если I = {s1}, R = {s2, s3, s5, s6}, то не выполняется св-во 2). Если I = {s1, s4}, R = {s5, s6}, то не выполняется св-во 3). Заметим, что если I = {s1, s4}, R = s3, s5, s6}, то это ваще не АП: s3 F s2, но s3 Î R, а s2 Ï R; т.е. не выполняется ограничение на результанты: R – такие ситуации из S, для которых, если r F s, r Î R, то s Î R.

Следующий же вариант назначения иниц-ров и результантов даёт эффективный АП:
I = {s1, s4}, R = {s2, s3, s5, s6}.



Поделиться:

Дата добавления: 2015-04-05; просмотров: 70; Мы поможем в написании вашей работы!; Нарушение авторских прав





lektsii.com - Лекции.Ком - 2014-2024 год. (0.006 сек.) Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав
Главная страница Случайная страница Контакты