Составители:
Рубрика:
алгоритм за минимальное время.
1.2. О времени выполнения алгоритмов
Рассмотрим теперь любую упорядоченную последовательность
вершин графа алгоритма, в которой для каждой пары последова-
тельных вершин следующая вершина либо связана дугой с преды-
дущей, либо обе операции, соответствующие этим вершинам, вы-
полняются на одном функциональном устройстве. Ясно, что опе-
рации для этой последовательности вершин могут выполняться
лишь последовательно. Значит, при фиксированном соответствии
графа алгоритма и соответствующих срабатываниях функциональ-
ного устройства время реализации алгоритма не меньше, чем ми-
нимальное время выполнения (на избранной системе и при том же
соответствии) последовательности упомянутых операций.
Определение 1.1. Последовательности с максимальным из
минимальных времен выполнения называются максимальными по-
следовательностями.
Благодаря теореме 1.2 легко устанавливаем следующее утвер-
ждение
Теорема 1.3. Пусть установлена функция соответствия
между вершинами графа алгоритма и срабатываниями, при ко-
торых алгоритм выполним. Тогда минимальное для этой функ-
ции время реализации алгоритма равно времени выполнения мак-
симальных последовательностей.
Следствие 1.1. Для того чтобы режим включения функци-
ональных устройств обеспечивал минимальное время реализации
алгоритма при данной функции соответствия между вершина-
ми графа алгоритма и срабатывания функциональных устройств,
необходимо и достаточно, чтобы время реализации алгоритма
было равно минимальному времени выполнения при этой функции
соответствия хотя бы одной упорядоченной последовательности
операций, каждая из которых либо получает аргумент предыду-
щей, либо выполняется вместе с предыдущей на одном функцио-
нальном устройстве.
Д о к а з а т е л ь с т в о очевидно.
Сформулированное следствие полезно при установлении того,
что режим включения обеспечивает минимальное время реализа-
ции алгоритма: для этого достаточно найти цепочку указанного
рода, минимальное время выполнения которой совпадает со време-
78
Страницы
- « первая
- ‹ предыдущая
- …
- 75
- 76
- 77
- 78
- 79
- …
- следующая ›
- последняя »
