ВУЗ:
Составители:
34
Лекция 3
Модели вычислительных процессов и систем
3.1 Понятие графа алгоритма и его свойства
Для описания информационных зависимостей алгоритмов решения задач
широко используют модель в виде ациклического ориентированного графа [1-
3], называемую графом алгоритма. В этой модели множество операций алго-
ритма и существующие между операциями информационные зависимости
описываются двойкой:
G = (V, E), (3.1)
где V = {1,...,|V|} – множество вершин графа, представляющих операции алго-
ритма, а E – множество дуг графа, устанавливающих частичный порядок опе-
раций. Дуга E
i, j
= (i, j) принадлежит графу только в том случае, если операция j
использует результат выполнения операции i. Свойство ацикличности графа
алгоритма состоит в том, что никакая величина не может определяться через
саму себя.
Описанная выше модель является направленным графом. Если дугам графа
приписать веса
Njic
ij
,1,, , отражающие интенсивность информационного
обмена между i-й и j- ветвями программы, такой граф называется взвешенным
направленным графом. В общем случае граф алгоритма есть мультиграф, т.е.
две вершины могут быть связаны несколькими дугами [2]. При этом в качестве
разных аргументов одной операции используется одна и та же величина. Коли-
чество вершин графа (не считая вершин ввода) далее будем обозначать
V
.
Путь максимальной длины в графе называют критическим.
Для ориентированного ациклического графа с n вершинами существует
число s<n , для которого все вершины графа можно так пометить одним из ин-
дексов 1,2,…,s, что если дуга из вершины с индексом i идет в вершину с ин-
дексом j, то i<j. Покажем это [2].
Страницы
- « первая
- ‹ предыдущая
- …
- 32
- 33
- 34
- 35
- 36
- …
- следующая ›
- последняя »
