Аноним

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

Материал из 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]