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

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