Достоверные отношения частоты выполнения

Достоверные отношения частоты выполнения (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{ {\cal 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 {\cal N} }[/math] и существует такой путь [math]\displaystyle{ P \in {\cal N} }[/math], что [math]\displaystyle{ \mid M_1 \cap P \mid \lt \mid M_2 \cap P \mid }[/math].

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

Литература

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