Виды порождающих систем

Лекция 17

4.18 Виды порождающих систем

системы с поведением

1. базовые-

a. уравнение (4.12)—нейтральные;

b. уравнение (4.28)—направленные;

2. порождающие:

a. уравнение (4.19)—нейтральные;

Рекомендуемые материалы

b. уравнение (4.32)—направленные;

ST-системы

1. базовые:

a. уравнение (4.66) —нейтральные,

b. уравнение (3.93)—направленные;

2. порождающие:

a. уравнение (4.86) — нейтральные;

b. уравнение (4.87)—направленные.

Как было показано, любая ST-система может быть преобразована в изоморфную систему с поведением, в то время как обратное преобразование возможно только при определенном типе масок. Следовательно, системы с поведением более общие, чем ST-системы.

Два основных недостатка ST-систем очевидны: ограниченность из-за использования только компактных масок и собственная из­быточность, проистекающая из наложения текущего и следующего состояний.

ST-системы, когда они применимы, представляют для исследователей определенные преимущества. По-видимому, ST-функции понятнее человеку, чем аналогичные функции поведения.

Для порождающих систем выделены различные отличия. Это отличия, выделенные для систем более низких уровней, и некоторые новые. Среди первых наиболее существенны­ми являются:

1. упорядоченность   параметрического  множества,  что  позволяет ввести важное понятие маски;

2. упорядоченность множеств состояний, что играет существенную роль в упрощении процедур для порождающих систем и при работе с не полностью определенными наборами данных;

3. отличие четких и нечетких каналов наблюдения, дающих соот­ветственно четкие или нечеткие данные и требующих применения различных методов обработки данных;

4. отличие между нейтральными и направленными системами, с которыми следует обращаться по-разному.

Отличиями, относящимися к порождающим системам, но не к системам данных и исходным системам, явля­ются:

1. детерминированность и недетерминированность систем;

2. по используемой маске различаются порождающие системы без памяти и системы, зависящие от прошлого.   

Разумеется, эти методологические отличия характеризуют и си­стемы более высоких  уровней.

4.19 Упрощение порождающих систем

            На некотором этапе обработки заданной системы данных ча­сто желательно бывает упростить соответствующие этой системе данных порождающие системы.

Существует два основных метода одновременного упрощения систем данных и соответствующих порождающих систем:

1) упрощение за счет исключения некоторых переменных из со­ответствующей подобной системы;

2) упрощение за счет определения классов эквивалентности со­стояний некоторых переменных.

 Пусть множество переменных порождающей системы V со­стоит из п переменных и любое подмножество V, за исключением пустого множества, представляет содержательное упрощение пер­вого рода. Следовательно, имеется  нетривиальных упроще­ния первого рода. Они частично упорядочены по отношению «под­множество». Если для удобства включить исходное множество V и пустое множество, то множество упрощений с частичным упо­рядочением образует решетку. Назовем эту решетку решеткой переменных или V-решеткой и обозначим . Понятно, что V -решетка может быть описана или как

или как                                                           (4.88)

Обозначим через f_B функцию поведения заданной системы с по­ведением с переменными, составляющими множество V. При упро­щении этой системы с помощью сокращения множества V до под­множества  новая (упрощенная) функция поведения f_B опреде­ляется проекцией

,(4.89)

определенной уравнением (4.57).

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

 (4.90)

где — заданное множество состояний (переменной ); — упрощенное (сокращенное) множество состояний той же перемен­ной; — новое состояние, присвоенное исходному состоянию , а — это идентификаторы, с помощью которых различаются раз­ные функции вида (4.90), примененные к множеству состояний од­ной и той же переменной. Если , то состояния х и у изпри упрощении оказываются неразличимыми. Функция (4.90) должна быть голоморфна относительно всех математичес­ких свойств исходного множества V_i , которые считаются сущест­венными с точки зрения рассматриваемой задачи. Будем функцию (4.90), являющуюся гомоморфизмом в описанном выше смысле, называть упрощающей функцией.

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

Разрешающие формы, определенные на каком-то множестве состояний , могут быть упорядочены с помощью обычного отношения уточнения, определенного на разбиениях данного множе­ства. Хорошо известно, что такое отношение уточнения является отношением частичного порядка и образует решетку. Для двух заданных разбиений, скажем X и У, определенных на одном и том же множестве, будем говорить, что X является уточненным раз­биением Y тогда и только тогда, когда для любой группы х из X существует группа у из У, такая, что . Если X, уточняющее разбиение У, то У называется укрупненным разбиением X. Решет­ку разрешающих форм, определенных на множестве состояний , будем называть разрешающей решеткой и обозначать . Любая разрешающая решетка множества состояний может быть опре­делена или в виде                                                     

(4.91)

или в виде                                         

(4.92)

где  и  обозначают соответственно произведение и сумму раз­биений.

Если рассматриваемое множество состояний не обладает мате­матическими свойствами, которые должны быть сохранены, то в качестве разрешающей формы приемлемо любое разбиение.

В этом случае разрешающая решетка содержит все разбиения, которые могут быть определены на этом множестве состояний. Если мно­жество состояний состоит из m состояний, то число разрешающих форм в решетке, определяется формулой

  (4.93)

Ниже показано огромное число разрешающих форм даже для не­большого числа состояний:

Поскольку наименьшая уточненная разрешающая форма (все со­стояния в одном блоке) смысла не имеет, а наибольшее уточне­ние дает упрощения, то число осмысленных упрощений равно.

Если множество состояний полностью упорядочено и требуется сохранить эту упорядоченность при упрощениях, то число разре­шающих форм существенно меньше числа, задаваемого формулой. Пусть — это состояния и . Тогда для любого и или объединяются в одну группу или нет. Только эти решения определяют конкрет­ное разбиение. Таким образом, для т состояний принимается m—1 бинарное решение. Следовательно, для полностью упорядо­ченных множеств состояний

(4.94)

Очевидно, что эта решетка для m состояний изоморфна булевской решетке для упорядочения подмножеств любого множества из m—1 элемента. В следующей таблице приводятся значения , вычисленные по формуле (3.94); в этом случае число разрешаю­щих форм существенно меньше, чем в случае неупорядоченных множеств состояний:

Число содержательных упрощений снова равно

Пример 4.7. Рассмотрим переменную, состояниями которой являются цвета светофора: красный, желтый, зеленый. Поскольку они не упорядочены, все разбиения множества состояний прием­лемы в качестве разрешающих форм. Диаграмма Хассе для этой решетки приведена на рис. 4.13. Буквы к, ж, з означают соответ­ственно красный, желтый и зеленый цвета. Группам в отдельных разрешающих формах показаны черточками над соответствующими буква­ми. Стрелка на диаграмме указывают направление уточнения разби­ений. Для упрощения исходной системы нужно двигаться в на­правлении, обратном стрелкам.

Рис. 4.13. Решетки разрешающих форм.

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

 Пусть — множества элементов отдельных разрешающих решеток выбранных переменных, а X — множество эле­ментов соответствующей разрешающей решетки. Понятно, что общее число элементов объединен­ной разрешающей решетки равно произведению числа элементов отдельных разрешающих решеток, т. е.

(4.95)

однако только некоторые из них являются содержательными упро­щениями. В частности, любая комбинация, в которую входит наи­меньшая уточненная разрешающая форма (разбиение на одну группу) одной из разрешающих решеток, является бессмыслен­ной. Комбинация всех наиболее уточненных разрешающих форм также не представляет упрощения. Следовательно, общее число элементов объединенной решетки, представляющих содержатель­ные упрощения, определяется по формуле

 (4.96)

В частном случае, когда все отдельные решетки одинаковы и каж­дая состоит из разрешающих форм, мы получаем

 (4.97)

Более того, если все разрешающие решетки построены на пол­ностью упорядоченном множестве с т состояниями, то

 (4.98)

               

Требования, упрощающие порождающие системы:

1)   чтобы системы были как можно проще;

2)   чтобы степень порождающей нечеткости систем была как можно меньше.

Будем называть требование 1 требованием простоты, а требо­вание 2 требованием четкости.

Чтобы конкретизировать требование простоты для систем с по­ведением следует задать определенную меру сложности. Пусть, например, сложность системы с поведением оценивается числом реальных состояний системы, т. е. числом состояний, имеющих ненулевые вероятности или возможности. Это очень простая мера, но, воз­можно, наиболее содержательная.

Алгоритмы формализации порождающих систем

Системы с поведением

1. Определяется правило сдвига  (Если параметрическое множество полностью упорядочено ).
2. Определяются выборочные переменные , где .  обозначает состояние выборочной переменной  при значении пара­метра w, а  — состояние переменной   при значении па­раметра .
3. Определяется маска . Для введения выборочных переменных определяется функция .
4. Определяется функция поведения , где . , если состояние с имеет место быть, и  в противном случае.
5. Определяется система с поведением .

Порождающие системы с поведением

1. Определяются подмаски  и  маски М. Порождаемая подмаска и порождающая подмаска .  - маска порождения.
2. Для удобства определяются функции . Множества состояний  и  соответственно порождаемых и порождающих переменных
3. Определяется порождающая функция поведения .
4. Определяется порождающая система с поведением .

Для недетерминированных систем с поведением

Функция поведения принимает вид  закона распределения вероятностей. В случае порождающих систем с поведением .

Направленные системы с поведением

1. Определяются подмаски  и  маски  М. Пусть подмаска   определяет выборочные переменные, задаваемые сре­дой, а подмаска   — остальные.  - маска направленной системы с поведением.
2. Для удобства определяются функции. Также .
3. Определяется функция поведения .
4. Определяется направленная система с поведением .

Информация в лекции "25 - Обмен энергии и терморегуляция" поможет Вам.

Направленные порождающие системы с поведением

1. Порождающая маска для направленной системы с поведением .  рассматривается как разбиение .
2. Определяется функция поведения .
3. Определяется направленная порождающая система с поведением .

Системы с изменяющимися состояниями

1. Определяются функциигде  — это вероятность состояния , следующего непосредственно за со­стоянием  (согласно выбранному порядку порождения); где  — условная вероятность того, что при текущем состоянии  следующим состоянием будет состояние.

2. Определяются аналоги нейтральных систем с поведением, ST-система  , и порождающая ST-система . Где , и имеют тот же смысл, что в системах с поведением.

К.Р. № 17

Для некоторой порождающей системы приведите примеры возможных упрощений.