Составители:
Рубрика:
Рис. 10. Решетчатый граф.
Следствие 7.2. Если одноименные координаты (т.е. ко-
ординаты с одним номером) дуг либо отрицательные, либо поло-
жительные, то граф является строго направленным, а в каче-
стве направления можно взять вектор с ненулевыми координа-
тами, знаки которых совпадают со знаками соответствующих
одноименных координат дуг.
Теорема 7.4. Пусть все вершины графа алгоритма нахо-
дятся в узлах прямоугольной целочисленной решетки и принад-
лежат замкнутому прямоугольному параллелепипеду с ребрами
длиной d
1
, d
2
, . . . , d
s
. Пусть дуги графа имеют неотрицательные
координаты. Тогда высота h алгоритма удовлетворяет неравен-
ству
h ≤
m
X
i=1
d
i
+ 1. (7.2)
Д о к а з а т е л ь с т в о. Очевидно, рассматриваемый граф явля-
ется строго направленным, и в качестве оси можно взять вектор
с единичными компонентами. Согласно следствию 7.1 высота ал-
горитма равна числу проекций на ось, а их число не превосходит
правой части неравенства (7.2). Теорема доказана.
Определение 7.2. Граф, вершины которого лежат в узлах
целочисленной решетки, называется решетчатым.
Пример. Рассмотрим задачу вычисления произведения A =
BC двух квадратных матриц B = (b
ik
), C = (c
kj
), i, j, k =
1, . . . , n. Пусть A = (a
ij
) i, j, k = 1, . . . , n. Определим алгоритм
формулами a
(k)
ij
= a
(k−1)
ij
+ b
ik
c
kj
, где a
(0)
ij
= 0. Операцию a + bc
будем считать базовой.
53
Страницы
- « первая
- ‹ предыдущая
- …
- 50
- 51
- 52
- 53
- 54
- …
- следующая ›
- последняя »
