Аноним

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

Материал из WEGA
нет описания правки
(Создана новая страница размером '''Задача анализа свойств состояний''' (''Data flow analysis problem'') - Рассматривается п...)
 
Нет описания правки
Строка 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}
<math>A(p)=\sqcap\{f_{\alpha}
(a_0):\alpha \mbox{ --- путь от начальной вершины до } p\},</math>
(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], [Котов-Сабельфельд]
[Касьянов/88], [Котов-Сабельфельд]