1. Понятие дискретной динамической системы

• Название: 1. Понятие дискретной динамической системы
• Дата: 23.11.2018
• Размер: 0.51 Mb.
• Имя файла: tmp_4118-Otvety_k_ekzamenu_po_predmetu_Teoria_vychislitelnykh_pr.docx
• Тип: Документы; #57412
• страница: 5 из 15

14.Редукция диаграммы переходов.

Редукцию ДП можно осуществить по множеству ситуаций, порожденному теми или иными компонентами ситуаций.

В этом случае сначала из всего множества ситуаций S оставляют те, входные компоненты которых попали в выделенное множество значений входной компоненты X*. Таким образом, получаем множество ситуаций S*. Далее редукция строится по полученному множеству ситуаций S*.

Первые два элемента вектора полного состояния выберем в качестве входных компонент, последние два – в качестве выходных компонент.

15. Основная идея теории комплектов, сравнение с теорией множеств. Свойства комплектов.

В теории СП комплект - набор элементов из некоторой конечной области D (аналогично множеству).

Множества не допускают присутствие нескольких экземпляров одного и того же элемента.	комплекты допускают присутствие нескольких экземпляров одного и того же элемента.
отношение включения (определяет, какие элементы являются членами каких множеств)	функция числа экземпляров #(x,B) (читается «число x в комплекте B»).
Если ограничить число экземпляров каждого элемента в комплекте 0#(x, B)1, то комплект совпадает с множеством.

Свойства комплектов

Пусть х и B: #(х,В)0.

Если #(х,В)>0, то обозначается: хB. Если #(х,В)=0, то обозначается: хВ. Пустой комплект:.

• 
  Мощность |B| - общее число экземпляров в комплекте:
  

• 
  Комплект A - подкомплект комплекта В (обозначение: AB), если #(х, A)#(х, В) для всех хB. Из AB следует: |A||B|.
  
• 
  Комплект А строго включен в комплект В (обозначение: АВ), если АВ и АВ.
  
• 
  Два комплекта A и В равны (обозначение: А=В), если #(х,А)=#(х,В) или AB и ВА для всех хD. Из A=B следует: |A|=|B|.
  

16. Операции над комплектами. Пространство комплектов.

Пусть А и В – комплекты. Определим для них операции:

• 
  объединение комплектов АВ: #(х, АВ)=max(#(х, А), #(х, B));
  
• 
  пересечение комплектов АВ: #(х, АВ)=min(#(х, А), #(х, B));
  
• 
  сумма комплектов А+В: #(х, А+В)=#(х, А)+#(х, B);
  
• 
  разность комплектов А-В: #(x, A-B)=
  

Нетрудно видеть, что:

АВ А АВ; А-В А А+В

|АВ||A|+|B|; |А+В|=|A|+|B|.

Пространство комплектов Dⁿ – множество всех таких комплектов, что элементы их принадлежат D, и ни один элемент не входит в комплект более n раз.

Таким образом, для любого комплекта ВDⁿ имеем:

1) если хВ, то хD,

2) для хВ: #(х, В)n.

Множество D^∞ - множество всех комплектов над областью D без каких-либо ограничений на число экземпляров элемента в комплекте.

Если D={d₁, d₂, ..., d_m}, то существует естественное соответствие между каждым комплектом B над D и m-мерным вектором f=(f₁, f₂, ..., f_m) по правилу f_i=#(d_i,B). Это соответствие называется отображением Париха.