Детерминизм

" 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) не $ s_i, s_j [s_i Ï R & s_j Ï R & s_i F⁺ s_j & s_j F⁺ s_i ]

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

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

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

Следующий же вариант назначения иниц-ров и результантов даёт эффективный АП:
I = {s₁, s₄}, R = {s₂, s₃, s₅, s₆}.