Схема с разметкой — различия между версиями

Материал из WikiGrapp
Перейти к:навигация, поиск
(Литература)
 
Строка 1: Строка 1:
'''Схема с разметкой''' (''[[Data flow analysis frameworks]]'') -
+
'''Схема с разметкой''' (''[[Data flow analysis frameworks]]'')
 
модель [[схема программ|(схемы) программы]], ориентированная на извлечение
 
модель [[схема программ|(схемы) программы]], ориентированная на извлечение
свойств потока данных в программе (в схеме программы), -
+
свойств потока данных в программе (в схеме программы),
 
решение ''[[задача анализа свойств состояний|задачи анализа свойств состояний]]''.
 
решение ''[[задача анализа свойств состояний|задачи анализа свойств состояний]]''.
  
'''Схема с разметкой''' - это пятерка <math>(G,L,F,M,a_0)</math>, где <math>G</math> -
+
'''Схема с разметкой''' это пятерка <math>\,(G,L,F,M,a_0)</math>, где <math>\,G</math>
[[уграф]]; <math>L</math> - полурешетка свойств --- множество пометок с
+
[[уграф]]; <math>\,L</math> полурешетка свойств множество пометок с
 
отношением порядка <math>\sqsubseteq</math>, не содержащее бесконечных
 
отношением порядка <math>\sqsubseteq</math>, не содержащее бесконечных
[[цепь|цепей]] и являющееся полурешеткой с  <math>0</math> и  <math>1</math>
+
[[цепь|цепей]] и являющееся полурешеткой с  <math>\,0</math> и  <math>\,1</math>
относительно пересечения <math>\sqcap</math>; <math>F</math> - множество так
+
относительно пересечения <math>\sqcap</math>; <math>\,F</math> множество так
 
называемых [[преобразователь|преобразователей]] [[пометка|пометок]] (свойств), которое
 
называемых [[преобразователь|преобразователей]] [[пометка|пометок]] (свойств), которое
 
состоит из монотонных функций <math>f: L \rightarrow L</math> и
 
состоит из монотонных функций <math>f: L \rightarrow L</math> и
 
является замкнутым относительно композиции функций и
 
является замкнутым относительно композиции функций и
 
содержит тождественную функцию и для любого <math>a\in L</math> такую
 
содержит тождественную функцию и для любого <math>a\in L</math> такую
функцию <math>f \in F</math>, что <math>a=f(0)</math>; <math>a_0\in L</math> - начальная
+
функцию <math>f \in F</math>, что <math>\,a=f(0)</math>; <math>\,a_0\in L</math> начальная
 
пометка;
 
пометка;
<math>M</math> - функция, ставящая в соответствие каждой [[дуга|дуге]] <math>u</math>
+
<math>\,M</math> функция, ставящая в соответствие каждой [[дуга|дуге]] <math>\,u</math>
анализируемого уграфа <math>G</math>
+
анализируемого уграфа <math>\,G</math>
 
функцию эффекта дуги <math>M(u)\in F</math>.
 
функцию эффекта дуги <math>M(u)\in F</math>.
 
'''Схема с разметкой''' ''хорошо определена'', если существуют
 
'''Схема с разметкой''' ''хорошо определена'', если существуют
 
[[алгоритм|алгоритмы]], позволяющие для любых <math>a,b\in L</math> и <math>f\in F</math>
 
[[алгоритм|алгоритмы]], позволяющие для любых <math>a,b\in L</math> и <math>f\in F</math>
вычислять элементы <math>a\sqcap b</math> и  <math>f(a)</math>.
+
вычислять элементы <math>a\sqcap b</math> и  <math>\,f(a)</math>.
  
Другое название --- ''[[Схема свойств состояний]]''.
+
Другое название ''[[Схема свойств состояний]]''.
  
 
==См. также ==
 
==См. также ==
''[[Задача анализа свойств состояний]].''
+
* ''[[Задача анализа свойств состояний]].''
 
==Литература==
 
==Литература==
[Касьянов/88]
+
* Касьянов В.Н. Оптимизирующие преобразования программ. — М.: Наука, 1988.
 +
 
  
 
[[Категория: Теория схем программ]]
 
[[Категория: Теория схем программ]]
 
[[Категория: Потоковый анализ программ]]
 
[[Категория: Потоковый анализ программ]]

Текущая версия на 11:53, 12 сентября 2011

Схема с разметкой (Data flow analysis frameworks) — модель (схемы) программы, ориентированная на извлечение свойств потока данных в программе (в схеме программы), — решение задачи анализа свойств состояний.

Схема с разметкой — это пятерка \,(G,L,F,M,a_0), где \,Gуграф; \,L — полурешетка свойств — множество пометок с отношением порядка \sqsubseteq, не содержащее бесконечных цепей и являющееся полурешеткой с \,0 и \,1 относительно пересечения \sqcap; \,F — множество так называемых преобразователей пометок (свойств), которое состоит из монотонных функций f: L \rightarrow L и является замкнутым относительно композиции функций и содержит тождественную функцию и для любого a\in L такую функцию f \in F, что \,a=f(0); \,a_0\in L — начальная пометка; \,M — функция, ставящая в соответствие каждой дуге \,u анализируемого уграфа \,G функцию эффекта дуги M(u)\in F. Схема с разметкой хорошо определена, если существуют алгоритмы, позволяющие для любых a,b\in L и f\in F вычислять элементы a\sqcap b и \,f(a).

Другое название — Схема свойств состояний.

См. также

Литература

  • Касьянов В.Н. Оптимизирующие преобразования программ. — М.: Наука, 1988.