4635
правок
Схема с разметкой: различия между версиями
Материал из WikiGrapp
нет описания правки
KVN (обсуждение | вклад) |
KEV (обсуждение | вклад) Нет описания правки |
||
| Строка 1: | Строка 1: | ||
'''Схема с разметкой''' (''[[Data flow analysis frameworks]]'') | '''Схема с разметкой''' (''[[Data flow analysis frameworks]]'') — | ||
модель [[схема программ|(схемы) программы]], ориентированная на извлечение | модель [[схема программ|(схемы) программы]], ориентированная на извлечение | ||
свойств потока данных в программе (в схеме программы), | свойств потока данных в программе (в схеме программы), — | ||
решение ''[[задача анализа свойств состояний|задачи анализа свойств состояний]]''. | решение ''[[задача анализа свойств состояний|задачи анализа свойств состояний]]''. | ||
'''Схема с разметкой''' | '''Схема с разметкой''' — это пятерка <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>\,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>. | ||
Другое название | Другое название — ''[[Схема свойств состояний]]''. | ||
==См. также == | ==См. также == | ||
''[[Задача анализа свойств состояний]].'' | * ''[[Задача анализа свойств состояний]].'' | ||
==Литература== | ==Литература== | ||
* Касьянов В.Н. Оптимизирующие преобразования программ. — М.: Наука, 1988. | |||
[[Категория: Теория схем программ]] | [[Категория: Теория схем программ]] | ||
[[Категория: Потоковый анализ программ]] | [[Категория: Потоковый анализ программ]] | ||
