Составители:
Рубрика:
Глава 6. ПРЕДСТАВЛЕНИЕ И РЕАЛИЗАЦИЯ
АЛГОРИТМОВ
§ 1. Программы реализации алгоритмов
1.1. Условия реализуемости алгоритмов
Реализация алгоритма на вычислительной системе — это ре-
ализация базовой программы эквивалентным способом. Поэтому
(явно или неявно) должны быть определены:
— функция, устанавливающая взаимно однозначное соответ-
ствие между вершинами графа алгоритма и отдельно срабатыва-
ниями функциональных устройств вычислительной системы;
— потоки информации между функциональными устройства-
ми системы;
— моменты включения функциональных устройств.
Имеются две основные стратегии при решении этих задач:
— статическая;
— динамическая.
При статической стратегии решение принимается заранее на
основе анализа алгоритма и вычислительной системы, а при дина-
мической стратегии решение принимается в процессе реализации.
Динамическая стратегия характеризует так называемые пото-
ковые линии. Иногда используют смешанные стратегии.
Принято на этой стадии исследования идеализировать ситуа-
цию, предполагая, что система не может сработать и выдать непра-
вильный результат (т.е. результат, относящийся к другому алгорит-
му): либо система срабатывает и реализует алгоритм, либо систе-
ма не срабатывает. Этот подход на самом деле во многих случа-
ях весьма далек от истины: например, при решении той или иной
вычислительной задачи обычно предполагается, что указанные в
алгоритме арифметические действия выполняются точно; однако,
при реальных вычислениях компьютерная система реализует "ма-
шинную арифметику", так что результат фактически относится к
реализации другого алгоритма (причем реализуемый алгоритм, как
правило, остается неизвестным).
Соответствие, которое устанавливает упомянутая выше функ-
ция между алгоритмом и срабатываниями системы, чрезвычай-
но важна: ее неудачный выбор может оказаться первой причиной
несрабатывания алгоритма. Важно также, чтобы класс "удачных"
75
Страницы
- « первая
- ‹ предыдущая
- …
- 72
- 73
- 74
- 75
- 76
- …
- следующая ›
- последняя »
