Алгоритмы параллельных вычислений и программирование. Бурова И.Г - 50 стр.

UptoLike

ВУЗ: 

СПбГУ | Санкт-Петербург

Составители: 

Рубрика: 

3) все дуги, исходящие из вершин последнего яруса, являются
ребрами с одной вершиной (лежащей в последнем ярусе);
4) высота параллельной формы на единицу больше критиче-
ского пути графа;
5) произведение высоты параллельной формы на ее ширину не
меньше числа вершин графа.
В силу предыдущих рассуждений эти свойства представляются
достаточно очевидными.
Замечание.На первый взгляд может показаться, что отыскание
параллельной формы не требует большого числа операций. Дей-
ствительно, при топологической сортировке требуется число дей-
ствий по меньшей мере порядка n
2
(ибо на каждом шаге прихо-
дится делать сравнения со всеми оставшимися вершинами), и это
кажется приемлемым с точки зрения сложности алгоритмов (закон
полиномиальный и даже весьма малой степени — квадратичный).
Однако в реальных алгоритмах общее число n операций велико и
потому даже линейная зависимость от n для отыскания параллель-
ной формы обычно недопустима (ибо в наших обстоятельствах, как
правило, не получится никакой экономии). Поэтому нужны более
эффективные методы отыскания параллельных форм.
§ 7. Направленные графы и параллельные формы
Пусть задан ациклический ориентированный граф алгоритма,
вершины которого расположены в некотором арифметическом про-
странстве R
s
(т.е. в некотором евклидовом пространстве конечной
размерности s).
Теорема 7.1. Пусть в R
s
существует ось l (т.е. направ-
ленная прямая) такая, что ортогональная проекция графа на нее
имеет следующее свойство: ненулевые проекции всех его дуг име-
ют положительное значение. Тогда длина критического пути гра-
фа не превосходит суммы длин критических путей его подграфов,
проектирующихся в точки, и длины критического пути проекции
графа.
Д о к а з а т е л ь с т в о. Рассмотрим критический путь графа. Те
его части, которые имеют ненулевые проекции на ось, в сумме не
превосходят критического пути графа на оси. Те же его части, кото-
рые находятся в подграфах на ортогональных плоскостях, не пре-
восходят критических путей упомянутых подграфов. Складывая
51

Страницы