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

Материал из WikiGrapp
Перейти к навигации Перейти к поиску
(Создана новая страница размером '''Достоверные отношения частоты выполнения''' (''Reliable relations of execution frequency'') - П...)
 
Нет описания правки
 
(не показаны 2 промежуточные версии этого же участника)
Строка 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>{\mathcal 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]
* Касьянов В.Н. Оптимизирующие преобразования программ. — М.: Наука, 1988.

Текущая версия от 16:31, 7 февраля 2011

Достоверные отношения частоты выполнения (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].

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

Литература

  • Касьянов В.Н. Оптимизирующие преобразования программ. — М.: Наука, 1988.