Задача анализа свойств состояний: различия между версиями
KEV (обсуждение | вклад) Нет описания правки |
KEV (обсуждение | вклад) Нет описания правки |
||
| Строка 1: | Строка 1: | ||
'''Задача анализа свойств состояний''' (''[[Data flow analysis problem]]'') | '''Задача анализа свойств состояний''' (''[[Data flow analysis problem]]'') — Рассматривается полурешетка свойств <math>(L,\sqcap)</math>, не содержащая бесконечных [[цепь|цепей]], множество преобразователей свойств <math>F</math> и функция <math>M</math>, ставящая в соответствие каждой [[дуга|дуге]] <math>u</math> анализируемого ''[[уграф|уграфа]]'' <math>G=(V,U)</math> функцию эффекта дуги <math>M(u)\in F</math>. | ||
Прямая ''' | Прямая '''задача анализа свойств состояний''' формулируется как задача нахождения так называемой ''[[полная разметка|полной разметки]]'' — такой функции <math>A:V\rightarrow L</math>, что | ||
<math>A(p)=\sqcap\{f_{\alpha} | :::::<math>A(p)=\sqcap\{f_{\alpha} (a_0):\alpha \mbox{ --- }</math> путь от начальной вершины до <math> p\},</math> | ||
(a_0):\alpha \mbox{ --- путь от начальной вершины до | |||
где <math>a_0</math> | где <math>a_0</math> — некоторое свойство, сопоставляемое с начальной [[вершина|вершиной]] | ||
уграфа, а <math>f_{\alpha}</math> | уграфа, а <math>f_{\alpha}</math> — функция ''эффекта [[путь|пути]]'', полученная композицией функций эффектов составляющих его дуг. Указанная задача алгоритмически неразрешима и допускает эффективное решение лишь для узких своих подклассов таких, как, например, ''дистрибутивные'' | ||
''' | '''задачи анализа свойств состояний''', в которых <math>F</math> состоит только из дистрибутивных функций. Поэтому обычно | ||
рассматриваются алгоритмы нахождения приближенных решений задачи, связанных с нахождением ''корректных разметок'' | рассматриваются алгоритмы нахождения приближенных решений задачи, связанных с нахождением ''корректных разметок'' — таких <math>B:V\rightarrow L</math>, что <math>B(p)\sqsubseteq f_{\alpha}(a_0)</math> для любых вершины <math>p</math> и пути <math>\alpha</math> из <math>a_0</math> в <math>p</math>. | ||
В отличие от прямой ''обратная'' ''' | В отличие от прямой ''обратная'' '''задача анализа свойств состояний''' предполагает известными начальное свойство для конечной вершины уграфа и обратное направление применения функций эффектов дуг. | ||
В общей постановке с каждой дугой уграфа могут связываться функции ее эффектов как в прямом, так и в обратном направлении. | В общей постановке с каждой дугой уграфа могут связываться функции ее эффектов как в прямом, так и в обратном направлении. | ||
Другие названия | Другие названия — ''[[Задача потокового анализа]]'' и ''[[Задача глобального анализа потока данных]]''. | ||
==Литература== | ==Литература== | ||
* Касьянов В.Н. Оптимизирующие преобразования программ. — М.: Наука, 1988. | |||
* Котов В.Е., Сабельфельд В.К. Теория схем программ. — М.: Наука, 1991. | |||
Версия от 18:08, 9 февраля 2011
Задача анализа свойств состояний (Data flow analysis problem) — Рассматривается полурешетка свойств [math]\displaystyle{ (L,\sqcap) }[/math], не содержащая бесконечных цепей, множество преобразователей свойств [math]\displaystyle{ F }[/math] и функция [math]\displaystyle{ M }[/math], ставящая в соответствие каждой дуге [math]\displaystyle{ u }[/math] анализируемого уграфа [math]\displaystyle{ G=(V,U) }[/math] функцию эффекта дуги [math]\displaystyle{ M(u)\in F }[/math].
Прямая задача анализа свойств состояний формулируется как задача нахождения так называемой полной разметки — такой функции [math]\displaystyle{ A:V\rightarrow L }[/math], что
- [math]\displaystyle{ A(p)=\sqcap\{f_{\alpha} (a_0):\alpha \mbox{ --- } }[/math] путь от начальной вершины до [math]\displaystyle{ p\}, }[/math]
где [math]\displaystyle{ a_0 }[/math] — некоторое свойство, сопоставляемое с начальной вершиной уграфа, а [math]\displaystyle{ f_{\alpha} }[/math] — функция эффекта пути, полученная композицией функций эффектов составляющих его дуг. Указанная задача алгоритмически неразрешима и допускает эффективное решение лишь для узких своих подклассов таких, как, например, дистрибутивные задачи анализа свойств состояний, в которых [math]\displaystyle{ F }[/math] состоит только из дистрибутивных функций. Поэтому обычно рассматриваются алгоритмы нахождения приближенных решений задачи, связанных с нахождением корректных разметок — таких [math]\displaystyle{ B:V\rightarrow L }[/math], что [math]\displaystyle{ B(p)\sqsubseteq f_{\alpha}(a_0) }[/math] для любых вершины [math]\displaystyle{ p }[/math] и пути [math]\displaystyle{ \alpha }[/math] из [math]\displaystyle{ a_0 }[/math] в [math]\displaystyle{ p }[/math].
В отличие от прямой обратная задача анализа свойств состояний предполагает известными начальное свойство для конечной вершины уграфа и обратное направление применения функций эффектов дуг.
В общей постановке с каждой дугой уграфа могут связываться функции ее эффектов как в прямом, так и в обратном направлении.
Другие названия — Задача потокового анализа и Задача глобального анализа потока данных.
Литература
- Касьянов В.Н. Оптимизирующие преобразования программ. — М.: Наука, 1988.
- Котов В.Е., Сабельфельд В.К. Теория схем программ. — М.: Наука, 1991.