Задача анализа свойств состояний: различия между версиями

Версия от 16:14, 20 октября 2009

Задача анализа свойств состояний (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{ --- путь от начальной вершины до } 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].

В отличие от прямой обратная З.а.с.с. предполагает известными начальное свойство для конечной вершины уграфа и обратное направление применения функций эффектов дуг.

В общей постановке с каждой дугой уграфа могут связываться функции ее эффектов как в прямом, так и в обратном направлении.

Другие названия --- Задача потокового анализа и Задача глобального анализа потока данных.

Литература

[Касьянов/88], [Котов-Сабельфельд]

@@ Строка 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>(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:V\rightarrow L</math>, что
 <math>A(p)=\sqcap\{f_{\alpha}
 (a_0):\alpha \mbox{ --- путь от начальной вершины до } p\},</math>
-где <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>.
-полученная композицией функций эффектов составляющих его
-дуг. Указанная задача алгоритмически
-неразрешима и допускает эффективное решение лишь для узких
-своих подклассов таких, как, например, ''дистрибутивные''
-'''З.а.с.с.''', в которых
-<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>.
-В отличие от прямой ''обратная'' '''З.а.с.с.'''
+В отличие от прямой ''обратная'' '''З.а.с.с.''' предполагает известными начальное свойство для конечной вершины уграфа и обратное направление применения функций эффектов дуг.
-предполагает известными
-начальное свойство для конечной вершины уграфа и обратное
-направление применения функций эффектов дуг.
-В общей
+В общей постановке с каждой дугой уграфа могут связываться функции ее эффектов как в прямом, так и в обратном направлении.
-постановке с каждой дугой уграфа могут связываться функции
-ее эффектов как в прямом, так и в обратном направлении.
-Другие названия --- ''Задача потокового анализа'' и
+Другие названия --- ''[[Задача потокового анализа]]'' и ''[[Задача глобального анализа потока данных]]''.
-''Задача глобального анализа потока данных''.
 ==Литература==
 [Касьянов/88], [Котов-Сабельфельд]

Задача анализа свойств состояний: различия между версиями

Версия от 16:14, 20 октября 2009

Литература

Навигация

Поиск