Реферат Курсовая Конспект
Редукция процесса - раздел Философия, ТЕОРИЯ ВЫЧИСЛИТЕЛЬНЫХ ПРОЦЕССОВ Операция Редукции Состоит В Сведении Данного Ап К Боле...
|
Операция редукции состоит в сведении данного АП к более простому.
Такая операция необходима тогда, когда из полного описания процесса хочется выделить некоторую его часть, рассмотрение которой интересно по тем или иным причинам.
Пусть задан неприведенный АП Р = <S, F, I, R>, ситуации которого структурированы по 2-му способу, т.е. множество S представимо упорядоченной тройкой
S = (X,Y,Z), где X,Y,Z - соответственно множества значений входной, выходной компоненты и компоненты, не являющейся ни входной ни выходной.
Образуем р-блочное разбиение множества S процесса Р, в ситуациях каждого блока которого входная компонента принимает фиксированное значение xj, 1≤j≤p.
Выберем r < p различных значений входной компоненты и составим множество X*Ì X.
Ситуации, входящие в те блоки разбиения, которые соответствуют выбранным значениям входной компоненты, обозначим S*, S*Ì S.
Для каждого инициатора siÎI постоим множество ситуаций S(si), встречающихся на траекториях процесса Р, ведущих из указанного инициатора.
Образуем множество S(X*) как объединение тех множеств S(si), для которых справедливо S(si) Í S*, т.е. в S(X*) включаем те ситуации из S*, для которых существуют траектории, начинающиеся в инициаторах:
S(X*) =
Постоим также F(X*) = F Ç (S(X*)´S(X*))
I(X*) = I Ç S(X*), R(X*) = R Ç S(X*).
Определение 1.13. Назовем процесс P(X*) = <S(X*), F(X*), I(X*), R(X*)> редукцией неприведенного процесса P = <S, F, I, R> по выбранному множеству Х* значений входной компоненты.
Аналогично определяется редукция P(Y*) неприведенного процесса по выбранному множеству Y* значений выходной компоненты.
Пример: построим возможную редукцию неприведенного асинхронного процесса работы лазерного принтера. Используем, описанное выше структурирование ситуаций АП по входным компонентам, и построим редукцию процесса по выбранному множеству Х* значений входных компонент.
Множество входных компонент: Х = {10, 11}.
х = (М Р), где М – память,P – бумага для печати;
S1 = (1,0,0,0,0,0,0)
S2 = (1,1,0,0,0,0,1)
S3 = (1,0,0,0,0,0,1)
S4 = (1,1,1,0,1,0,0)
S5 = (1,1,0,1,1,0,0)
S6 = (1,1,0,0,1,1,0)
S7 = (1,1,0,0,1,0,1)
Выберем значения входных компонент для построения редукции: Х* = {11}.
Такой выбор означает, что необходимо выделить подпроцесс непосредственной печати, когда все внешние условия выполнены.
Тогда множество S* будет включать следующие ситуации:
S* = {s2, s4, s5, s6, s7}.
Рассмотрим траектории АП, начинающиеся в инициаторах процесса:
S(s1) :
S(s2) :
Очевидно, что все ситуации S* принадлежат траектории s2 M s7 и, следовательно, S(X*) = S*.
Таким образом, редукцией данного АП по выбранному множеству Х* значений входных компонент является асинхронный процесс
P(X*) = <S(X*), F(X*), I(X*), R(X*)> , где
S(X*) = {s2, s4, s5, s6, s7},
F(X*) = {(s2, s4), (s4, s5), (s5, s6), (s6, s7)},
I(X*) = {s2},
R(X*) = {s7}.
Конец примера.
Репозиция редукции
Рассмотрим теперь репозицию редукции Р(Х*) процесса Р.
Образуем р-блочное разбиение ситуации S’ процесса Р’, каждый блок которого соответствует фиксированному значению xj, 1≤j≤p, входной компоненты.
Образуем множество S’* как объединение тех блоков, в ситуациях которых xjÎХ*.
Далее для каждого инициатора ij’ÎR(X*) процесса Р’ и каждого результанта rm’ÎI(X*) рассмотрим множество ситуаций Sk’(ij’,rm’), принадлежащих каждой траектории ij’ в rm’.
Построим:
1) множество S’(X*) =
2) отношение F’(X*), задающее следование ситуаций на этих траекториях
F’(X*) = F’ Ç (S’(X*)´S’(X*))
3) множества I’(X*) = I’ Ç S’(X*), R’(X*) = R’ Ç S’(X*).
Процесс P’(X*) = <S’(X*), F’(X*), I’(X*), R’(X*)> и будет искомой репозицией редукции Р(Х*) процесса Р.
Аналогично, по репозиции Р’ процесса Р строится репозиция редукции Р(Y*) по выходным компонентам.
Пример: построим возможную репозицию редукции АП, соответствующего работе лазерного принтера. Построенная выше репозиция имеет вид:
P’=<S’, F’, I’, R’>,
где S’ = {s1, s2, s3, s7, s8Д, s9Д}, {s1, s2, s3, s7} Í S,
F’ = {(s7, s1), (s7, s2), (s7, s9),(s9,s1),(s3, s8),(s8, s2)}
I’ = {s3, s7 },
R’ = {s1, s2}.
Граф отношения F’:
Рис.10
s1 = (1,0,0,0,0,0,0)
s2 = (1,1,0,0,0,0,1)
s3 = (1,0,0,0,0,0,1)
s7 = (1,1,0,0,1,0,1)
s8 = (1,1,0,0,0,0,0)
s9 = (0,0,0,0,0,0,0)
Образуем 3-блочное разбиение ситуации S’ процесса Р’, каждый блок которого соответствует фиксированному значению xj, j=1,2,3 входной компоненты:
s1 = (1,0,0,0,0,0,0) s2 = (1,1,0,0,0,0,1) s9 = (0,0,0,0,0,0,0)
s3 = (1,0,0,0,0,0,1) s7 = (1,1,0,0,1,0,1)
s8 = (1,1,0,0,0,0,0)
Выберем Х*={11}.
Образуем S*={s2, s7, s8}.
Рассмотрим траектории репозиции:
s7 ® s1
s7 ® s9 ® s1
s7 ® s2
s3 ® s8 ® s2
Тогда искомая репозиция редукции будет иметь вид:
S’(X*) = {s2, s7}
F’(X*) = F’ Ç (S’(X*)´S’(X*)) = {( s7, s2)}
I’(X*) = I’ Ç S’(X*) = {s7},
R’(X*) = R’ Ç S’(X*) = {s2}.
Рис.11
Конец примера.
Редукция приведенного процесса Рп строится по редукции неприведенного процесса Р и репозиции редукции Р’(X*).
Очевидны следующие утверждения:
1. Редукция неэффективного процесса может быть эффективным процессом.
2. Редукция эффективного процесса (если она существует) - всегда эффективный процесс.
3. Редукция управляемого процесса (если она существует) - всегда управляемый процесс.
4. Редукция частично приведенного процесса может быть полностью приведенным процессом, а редукция полностью приведенного процесса может оказаться частично приведенным и даже неприводимым процессом.
ЗАМЕЧАНИЕ. Из правил построения редукции следует, что редукция Р(Х*) процесса Р может быть определена не на всем множестве Х*, а на некотором подмножестве Х**, Х**Ì Х*, так как при построении редукции из исходного процесса исключаются не отдельные ситуации, а пучки траекторий. При этом Р(Х**)=Р(Х*).
– Конец работы –
Эта тема принадлежит разделу:
ПО РЫБОЛОВСТВУ... ФЕДЕРАЛЬНОЕ ГОСУДАРСТВЕННОЕ ОБРАЗОВАТЕЛЬНОЕ... УЧРЕЖДЕНИЕ ВЫСШЕГО ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ МУРМАНСКИЙ ГОСУДАРСТВЕННЫЙ ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ...
Если Вам нужно дополнительный материал на эту тему, или Вы не нашли то, что искали, рекомендуем воспользоваться поиском по нашей базе работ: Редукция процесса
Если этот материал оказался полезным ля Вас, Вы можете сохранить его на свою страничку в социальных сетях:
Твитнуть |
Новости и инфо для студентов