Достоверные отношения частоты выполнения: различия между версиями
Glk (обсуждение | вклад) (Создана новая страница размером '''Достоверные отношения частоты выполнения''' (''Reliable relations of execution frequency'') - П...) |
KEV (обсуждение | вклад) Нет описания правки |
||
| Строка 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>{\ | |||
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 {\ | |||
N}</math> и существует такой путь <math>P \in {\ | |||
\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]