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

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

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

им ''[[фрагмент|фрагмента]]''.

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