Файл: Алферова, З. В. Математическое обеспечение экономических расчетов с использованием теории графов.pdf

вым символам. .

При раздельном подсчете объемов алфавитной и цифровой ин­ формации в документе параметры /,-, соответствующие однотипной информации, снабжаются признаками, указывающими вид инфор­ мации. Если же U характеризует реквизит, представляющий сме­ шанную информацию, то он соответственно состоит из двух частей,

образом, объем в алфавитных символах и объем в цифровых сим­

либо непосредственно по структурным графам документа, либо по соответствующей матрице смежности. Процесс определения путей

ляющего структурный граф документа с измененным направлени­

цы, сумма элементов строк в которых равна нулю. Выходу графа G'(X, Г) будет соответствовать строка, сумма элементов столбцов которой равна нулю. Таким образом, для определения входов и выходов графа необходимо подсчитать сумму элементов в каждой строке и в каждом столбце матрицы смежности этого графа.

Для расчета объемов информации по путям выделяются пути, ведущие от входных вершин к выходной. С этой целью из матрицы смежности выбираются вершины, соответствующие входам графа, определяются номера столбцов матрицы, содержащих эти верши-

58

ны. Номера столбцов указывают вершины начала путей. Затем просматриваются строки матрицы с номерами, равными номерам выбранных столбцов, до появления элементов, отличных от нуля. Значения этих элементов фиксируются (они соответствуют пара­ метрам т ( ) , после чего проверяется, не является ли концом пути столбец с номером, соответствующим ненулевому элементу строки. Если это не конец пути, то следующей рассматривается строка матрицы с номером, равным номеру выбранного столбца. Процесс продолжается до тех пор, пока не будет определен конец пути.

Перемножая значения зафиксированных при поиске пути эле­ ментов матрицы, отличных от нуля, и значение параметра /,г соответствующее данной начальной вершине, получаем объем ин­ формации по конкретному пути. Суммируя объем информации по всем путям, получаем объем информации по документу.

59

Рассматривая столбец с суммами элементов строк, устанавли­

должения пути обращаемся к строке матрицы с номером Х\. Бэтой строке первым элементом, не равным нулю, является элемент, стоящий в столбце с номером х0. Фиксируем значение этого эле­ мента, равное единице. Проверяем номер столбца на соответствие

и переходим к определению объема информации по данному пути,

60

§ 3. 1. ЭКВИВАЛЕНТНОСТЬ АЛГОРИТМОВ И ПРОГРАММ

Теоретического описания алгоритма, дающего реше­ ние некоторой задачи, еще недостаточно для получения ее реше­ ния. После того как алгоритм записан в виде последовательности элементарных актов и условий, возникает вопрос о его реализации.

Один и тот же алгоритм допускает различные способы реали­ зации в зависимости от используемых средств, квалификации ис­ полнителя и т. д. Кроме того, для одной и той же задачи можно составить различные алгоритмы, выделяя различные систе­ мы элементарных актов. Так, один алгоритм может получиться более универсальным, но менее выгодным для данной задачи, а другой — более узким, но более выгодным для данной задачи.

Для выбора наиболее выгодного алгоритма нужно уметь пере­ водить алгоритмы из одной формы в другую — тождественно их преобразовывать; необходимость в изучении различных способов тождественного или эквивалентного преобразования алгоритмов возникает и при реализации алгоритмов на вычислительных ма­ шинах.

Программирование для электронных вычислительных машин представляет собой один из вариантов эквивалентного преобразо­ вания алгоритма. В процессе программирования алгоритм, пред­ ставленный на языке математических описаний или на каком-либо алгоритмическом языке, преобразуется в алгоритм на языке ма­ шины, т. е. в программу. Таким образом, сам процесс программи­ рования содержит в качестве своей составной части эквивалент­ ное преобразование алгоритма, заданного на одном языке, в алго­ ритм, заданный на другом языке.

Заметим, что при ручном программировании преобразования алгоритма обычно производятся в уме. При автоматическом про­ граммировании преобразования выполняются специальной про­ граммой, называемой транслятором. Для этого алгоритм должен

62