рефераты конспекты курсовые дипломные лекции шпоры

Реферат Курсовая Конспект

Редукция процесса

Редукция процесса - раздел Философия, ТЕОРИЯ ВЫЧИСЛИТЕЛЬНЫХ ПРОЦЕССОВ   Операция Редукции Состоит В Сведении Данного Ап К Боле...

 

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

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

Пусть задан неприведенный АП Р = <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. Редукция частично приведенного процесса может быть полностью приведенным процессом, а редукция полностью приведенного процесса может оказаться частично приведенным и даже неприводимым процессом.

 

ЗАМЕЧАНИЕ. Из правил построения редукции следует, что редукция Р(Х*) процесса Р может быть определена не на всем множестве Х*, а на некотором подмножестве Х**, Х**Ì Х*, так как при построении редукции из исходного процесса исключаются не отдельные ситуации, а пучки траекторий. При этом Р(Х**)=Р(Х*).

 

– Конец работы –

Эта тема принадлежит разделу:

ТЕОРИЯ ВЫЧИСЛИТЕЛЬНЫХ ПРОЦЕССОВ

ПО РЫБОЛОВСТВУ... ФЕДЕРАЛЬНОЕ ГОСУДАРСТВЕННОЕ ОБРАЗОВАТЕЛЬНОЕ... УЧРЕЖДЕНИЕ ВЫСШЕГО ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ МУРМАНСКИЙ ГОСУДАРСТВЕННЫЙ ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ...

Если Вам нужно дополнительный материал на эту тему, или Вы не нашли то, что искали, рекомендуем воспользоваться поиском по нашей базе работ: Редукция процесса

Что будем делать с полученным материалом:

Если этот материал оказался полезным ля Вас, Вы можете сохранить его на свою страничку в социальных сетях:

Все темы данного раздела:

Тема 1.1. Понятие вычислительного процесса. Основные свойства
Современные системы управления содержат важный подкласс систем – управляющие устройства, осуществляющие координацию процессов с конечном множеством состояний. Работа таких устройств описыв

Репозиция процесса
В рамках введенных выше понятий и определений не уточнялся механизм перехода от результантов к инициаторам. Между тем, описание такого механизма необходимо для получения эффекта возобновления АП, е

Композиция процессов
Рассмотрим два АП: процесс P1 = <S1, F1, I1, R1> (необязательно приведенный) и приведенный процесс P2п = <S

Модельная интерпретация асинхронного процесса с помощью сети Петри
Ситуациями в сети является начальная разметка М0 и все разметки, достижимые от М0, т.е. МÎR(À). Ситуация-инициатор – начальная разметка, результанты – множество к

Свойства сетей Петри
Свойства условий: ограниченность и безопасность Из определения правил срабатывания переходов сети следует, что для реализации события достаточно, чтобы каждое его входное условие им

Дерево достижимости
Дерево достижимости (другое название покрывающее дерево) представляет все достижимые маркировки сети Петри, а также – все возможные последовательности запусков её переходов. Для любой сети

Анализ безопасности и ограниченности
Утверждение 1. Сеть Петри ограниченна тогда и только тогда, когда символ w отсутствует в её дереве достижимости. Краткое обоснование. Присутствие символа w в дереве достижимо

Матричные уравнения
Другой подход к анализу сетей Петри основан на матричном представлении сетей Петри и решении матричных уравнений. Альтернативным по отношению к определению сети Петри À в виде пятерки <P,

Блокировка памяти
Все вычислительные машины и системы имеют такое средство для организации взаимного исключения, как блокировка памяти. Это средство запрещает одновременное использование двух (и более) команд

Понятие тупика. Модель Холта
При параллельном исполнении процессов могут возникать ситуации, при которых два или более процесса все время находятся в заблокированном состоянии. Самым простым является случай, когда каждый из дв

Методы борьбы с тупиками
Проблема тупиков является чрезвычайно серьезной и сложной. В настоящее время разработано несколько подходов и методов разрешения этой проблемы, однако ни один из них нельзя считать панацеей. В неко

Стандартные схемы программ
Определение 5.4. Стандартная схема – это схема программ с памятью, называемая также алголоподобной или операторной схемой.   Исследование стандартных схем соста

Хотите получать на электронную почту самые свежие новости?
Education Insider Sample
Подпишитесь на Нашу рассылку
Наша политика приватности обеспечивает 100% безопасность и анонимность Ваших E-Mail
Реклама
Соответствующий теме материал
  • Похожее
  • Популярное
  • Облако тегов
  • Здесь
  • Временно
  • Пусто
Теги