Презентация на тему "Современные проблемы информатики"

Содержание

• 
  Слайд 1

  Современные проблемы информатикиЛекция 2Алгебра поведений

• 
  Слайд 2
  

  2 Что такое поведение? (инвариант бисимуляционной эквивалентности) 1.Domain theory approach (S.Abramsky 1991) 2.ACP with recursion (J.A.Bergstra and J.W.Klop, 1984) 3.Coalgebraic approach (P.Aczel, 1988, later B.Jecobs and J.Rutten) 4.Continuous algebras (A.Letichevsky,D.Gilbert,1997) В теории автоматов: Автоматесть транзиционная система, размеченная парами вход/выход Поведение есть автоматное отображение Или Автоматесть настроенная транзиционная система, размеченная входными символами Поведениеесть язык

• 
  Слайд 3

  Алгебра поведений

  3 Два сорта: U – поведения A – действия Сигнатура: префиксингa.u недетерминированный выборu + v константы D, 0,^ отношение аппроксимации Аксиомы: аci для недетерминированного выбора 0 есть нейтральный элемент недетерминированного выбора есть отношение частичного порядка с наименьшим элементом ^ Обе операции монотонны и непрерывны (сохраняют наименьшие верхние грани) Дополнительные структуры: Действия:комбинация действий ´ , невозможное и нейтральное действия Атрибуты:функции на поведениях

• 
  Слайд 4

  Монотонность

  4

• 
  Слайд 5

  Непрерывность

  5 Направленное множество Наименьшая верхняя грань Непрерывность

• 
  Слайд 6
  

  6 Монотонность следует из непрерывности

• 
  Слайд 7

  Поведение есть элементалгебры поведений

  7 ^ D D D a a b a b a a a.(a+b+^)+b.a.(a+a.0) a. D = a

• 
  Слайд 8
  

  Как построить алгебру всех поведений произвольных систем над множеством действий А?

  8 ¥ ) ( ) ( ) ( A F A F A F fin fin Ì Ì Алгебра конечных поведений Алгебра поведений конечной высоты Алгебра бесконечных поведений

• 
  Слайд 9

  Алгебра конечных поведений Ffin(A)

  9 Порождается терминальными константами0, Состоит из выражений в сигнатуре +, (().()) Отношение аппроксимации: v1v2vn

• 
  Слайд 10

  Каноническая форма

  10 I – конечное множество индексов, Если все ai. ui различны и ui представлены в такой же форме, то представление u единственно с точностью до коммутативности недетерминированного выбора. Индукция по высоте терма h(u) uсходится, если ирасходится в противном случае

• 
  Слайд 11

  Критерий аппроксимации

  11 Индукция по высоте u

• 
  Слайд 12

  Ffin(A) есть инициальная алгебра поведений

  12 Антисимметричность (индукция) Свободные алгебры поведений Ffin(A,X)

• 
  Слайд 13

  Алгебра поведений конечной высоты

  13 Iпроизвольное множество (может быть пустое) Критерий аппроксимации – определение. Операции:

• 
  Слайд 14

  Полная алгебра поведений F(A)

  14 Элементы: классы эквивалентности направленных множеств поведений конечной высоты От классов к представителям. Предел направленного множества направленных множеств = их объединение. Бесконечные суммы:

• 
  Слайд 15

  Каноническая форма в алгебре F(A)

  15 Такое представление единственно, если все различны

• 
  Слайд 16

  Теорема о неподвижной точке

  16 Добавление переменных:

• 
  Слайд 17

  Следующая лекцияПоведение транзиционных систем

  17 Транзиционная система=> поведение=> транзиционная система