Достоверные отношения частоты выполнения: различия между версиями
KEV (обсуждение | вклад) Нет описания правки |
KEV (обсуждение | вклад) Нет описания правки |
||
| Строка 1: | Строка 1: | ||
'''Достоверные отношения частоты выполнения''' (''[[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>{\ | '''Достоверные отношения частоты выполнения''' (''[[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>{\mathcal 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>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>. | ||
Версия от 16:37, 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{ {\mathcal 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]