Cтраница 2
Из вышесказанного видно, что фрагменту программы, внутри которого при оптимизации можно применить те же принципы ис-ключения возможности внесения ошибок в программу, которые используются при оптимизации линейного участка, в графе хода выполнения программы соответствует такой подграф с единственной входной вершиной, каждая вершина которого, кроме входной вершины, имеет только один единственный непосредственный предшественник. Такой подграф графа хода выполнения программы часто называют расширенным линейным участком. [16]
При выполнении условий а) - г) 3.8 каждая вершина графа G представляет собой один интервал. Следовательно, на основании теоремы 3.6 граф хода выполнения программы является несокращаемым. [17]
Умножая матрицу смежности С саму на себя два раза, получаем матрицу С3, каждый элемент которой с3 [ i, / ] указывает число путей длиной 3 от вершины щ к вершине tij. Аналогично элементы матрицы Ck, полученной в результате умножения матрицы смежности С на себя k раз, представляют собой число путей длиной k между вершинами графа хода выполнения программы. [18]
Может показаться, что в принципах, гарантирующих исключение возможности внесения ошибок в программу при оптимизации, из результатов анализа логических связей используются только отношения доминирования между линейными участками программы. Так как анализ и установление информационных связей произведены в контексте графа хода выполнения программы и его производных графов, то, фактически, в процессе нумерации значений неявно используется вся информация, которая выявляется во время анализа логических связей в программе. [19]
Допустим, что производный граф Gft) для несокращаемого графа G содержит две вершины. Тогда эти вершины в любом случае будут вхо. G ( fe 1), состоящий из одной единственной вершины. Таким образом, если граф Gft содержит только две вершины, то граф хода выполнения программы будет обязательно сокращаемым. [20]