Достоверные отношения частоты выполнения: различия между версиями

Материал из WEGA
Перейти к навигации Перейти к поиску
(Создана новая страница размером '''Достоверные отношения частоты выполнения''' (''Reliable relations of execution frequency'') - П...)
 
Нет описания правки
Строка 1: Строка 1:
'''Достоверные отношения частоты выполнения''' (''Reliable relations of execution frequency'') -  
'''Достоверные отношения частоты выполнения''' (''[[Reliable relations of execution frequency]]'') - Пусть <math>G</math> --- некоторый ''[[уграф]]'' с начальной [[вершина|вершиной]] <math>p_0</math> и конечной <math>q_0</math>, <math>M</math> --- множество элементов (вершин и [[дуга|дуг]]) уграфа <math>G</math>, <math>M_1,M_2\subseteq M</math>, <math>{\cal N}</math> ---
Пусть <math>G</math> --- некоторый ''уграф'' с начальной вершиной
множество [[путь|путей]] по <math>G</math> от <math>p_0</math> до <math>q_0</math>, а <math>\mid P \cap M_1 \mid</math> --- количество вхождений элементов из <math>M_1 \subseteq M</math> в некоторый путь <math>P</math> по <math>G</math>.
<math>p_0</math> и конечной <math>q_0</math>, <math>M</math> --- множество элементов (вершин
и дуг) уграфа <math>G</math>, <math>M_1,M_2\subseteq M</math>, <math>{\cal N}</math> ---
множество путей по <math>G</math> от <math>p_0</math> до <math>q_0</math>, а <math>\mid P \cap M_1
\mid</math> --- количество вхождений элементов из <math>M_1 \subseteq
M</math> в некоторый путь <math>P</math> по <math>G</math>.


Говорят, что <math>M_1</math> и <math>M_2</math> ''достоверно выполняются
Говорят, что <math>M_1</math> и <math>M_2</math> ''достоверно выполняются одинаково часто'' в <math>G</math> (обозначается <math>M_1 \doteq M_2</math>), если для любого пути <math>P</math> из <math>{\mathcal N}</math> выполняется <math>\mid M_1 \cap P \mid = \mid M_2 \cap P \mid</math>. <math>M_1</math> ''достоверно выполняется "чаще"'', чем <math>M_2</math> (обозначается <math>M_1 <\!\! \cdot\ M_2</math>), если <math>\mid M_1 \cap P \mid \leq \mid M_2 \cap P \mid</math> для любого пути <math>P \in {\mathcal N}</math> и существует такой путь <math>P \in {\mathcal N}</math>, что <math>\mid M_1 \cap P \mid < \mid M_2 \cap P \mid</math>.
одинаково часто'' в <math>G</math> (обозначается <math>M_1 \doteq M_2</math>), если
для любого пути <math>P</math> из <math>{\cal N}</math> выполняется <math>\mid M_1 \cap
P \mid = \mid M_2 \cap P \mid</math>. <math>M_1</math> ''достоверно выполняется "чаще"'', чем
<math>M_2</math> (обозначается <math>M_1 <\!\! \cdot\ M_2</math>), если <math>\mid M_1 \cap P
\mid \leq \mid M_2 \cap P \mid</math> для любого пути <math>P \in {\cal
N}</math> и существует такой путь <math>P \in {\cal N}</math>, что <math>\mid M_1
\cap P \mid < \mid M_2 \cap P \mid</math>.


'''Д.о.ч.в.''' играют весьма важную роль при решении задачи
'''Д.о.ч.в.''' играют весьма важную роль при решении задачи ''[[оптимизация программ|оптимизации программы]]''. Целесообразность (оптимизационный эффект) ни одного из оптимизирующих преобразований нельзя гарантировать, если не обеспечены определенные '''Д.о.ч.в.''' между элементами преобразуемого
''оптимизации программы''. Целесообразность
им ''[[фрагмент|фрагмента]]''.
(оптимизационный эффект) ни одного из оптимизирующих
преобразований нельзя гарантировать, если не обеспечены
определенные '''Д.о.ч.в.''' между элементами преобразуемого
им ''фрагмента''.
==Литература==
==Литература==
[Касьянов/88]
[Касьянов/88]

Версия от 16:36, 15 октября 2009

Достоверные отношения частоты выполнения (Reliable relations of execution frequency) - Пусть [math]\displaystyle{ G }[/math] --- некоторый уграф с начальной вершиной [math]\displaystyle{ p_0 }[/math] и конечной [math]\displaystyle{ q_0 }[/math], [math]\displaystyle{ M }[/math] --- множество элементов (вершин и дуг) уграфа [math]\displaystyle{ G }[/math], [math]\displaystyle{ M_1,M_2\subseteq M }[/math], [math]\displaystyle{ {\cal N} }[/math] --- множество путей по [math]\displaystyle{ G }[/math] от [math]\displaystyle{ p_0 }[/math] до [math]\displaystyle{ q_0 }[/math], а [math]\displaystyle{ \mid P \cap M_1 \mid }[/math] --- количество вхождений элементов из [math]\displaystyle{ M_1 \subseteq M }[/math] в некоторый путь [math]\displaystyle{ P }[/math] по [math]\displaystyle{ G }[/math].

Говорят, что [math]\displaystyle{ M_1 }[/math] и [math]\displaystyle{ M_2 }[/math] достоверно выполняются одинаково часто в [math]\displaystyle{ G }[/math] (обозначается [math]\displaystyle{ M_1 \doteq M_2 }[/math]), если для любого пути [math]\displaystyle{ P }[/math] из [math]\displaystyle{ {\mathcal N} }[/math] выполняется [math]\displaystyle{ \mid M_1 \cap P \mid = \mid M_2 \cap P \mid }[/math]. [math]\displaystyle{ M_1 }[/math] достоверно выполняется "чаще", чем [math]\displaystyle{ M_2 }[/math] (обозначается [math]\displaystyle{ M_1 \lt \!\! \cdot\ M_2 }[/math]), если [math]\displaystyle{ \mid M_1 \cap P \mid \leq \mid M_2 \cap P \mid }[/math] для любого пути [math]\displaystyle{ P \in {\mathcal N} }[/math] и существует такой путь [math]\displaystyle{ P \in {\mathcal N} }[/math], что [math]\displaystyle{ \mid M_1 \cap P \mid \lt \mid M_2 \cap P \mid }[/math].

Д.о.ч.в. играют весьма важную роль при решении задачи оптимизации программы. Целесообразность (оптимизационный эффект) ни одного из оптимизирующих преобразований нельзя гарантировать, если не обеспечены определенные Д.о.ч.в. между элементами преобразуемого им фрагмента.

Литература

[Касьянов/88]