книги из ГПНТБ / Алферова, З. В. Математическое обеспечение экономических расчетов с использованием теории графов

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

время его обработки. Затем среди всех этих времен берется мак­

мо достаточное для обработки слова р длиной п, а с другой сто­ роны, необходимое, так как среди слов длиною п имеется хотя бы

\Р\<П

130

§ 5. 2. АКСИОМАТИЧЕСКИЙ ПОДХОД К ОЦЕНКЕ СЛОЖНОСТИ

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

Блюм предлагает аксиоматический подход к характеристике сложности вычислимых функций. Выбранные аксиомы служат ос­ новой для определения того, что является, а что не является за­ конной мерой функциональной сложности. Наиболее известны такие меры оценки сложности, как число шагов, необходимых для вычисления функции, размер памяти, необходимый машине для вычисления. Эти меры удовлетворяют предложенным аксиомам.

ваемую сигнализирующей функцией, которую можно понимать как число шагов или размер памяти, используемой машиной Mi, при заданном р (в качестве машины Mi Блюм подразумевает машину Тьюринга).

Теперь аксиомы могут быть сформулированы следующим об­

Аксиома 2. Мера вычисления М принимает значения

Таким образом, функция М равна единице, если машина Mi перерабатывает входное слово р точно за т шагов, в противном случае М равна нулю.

132

В качестве т может рассматриваться также число ячеек па­ мяти.

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

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

Тем самым доказывается существование бесконечно оптимизи­ руемых в смысле сложности классов функций.

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

Теорема сжатия представляет собой обращение теоремы уско­ рения. Эта теорема показывает, что для некоторых весьма слож­ ных функций число шагов, необходимых для их вычисления, мож­ но «сжать» между двумя достаточно близкими границами. Несмот­ ря на то, что аксиоматический подход к оценке сложности явля­ ется чисто теоретическим, он имеет большое практическое значе­ ние. Это значение состоит прежде всего в том, что четко определи­ лись направления дальнейшего развития как теории, так и практики. Теория оценки сложности является тем практическим аппаратом, на основе которого осуществляется разработка раз­ личных методов эквивалентных преобразований алгоритмов и программ, обеспечивающих их оптимизацию. В результате акси­

разом, теория и практика оптимальных преобразований должны

практике, но они носили скорее интуитивный, а не теоретический характер. Аксиоматическая теория дала обоснование и доказа­ тельство правомерности таких оценок. Хотя практическое получе­

другие не могут дать положительного результата.

133

§ 5. 3. ОЦЕНКА СЛОЖНОСТИ С ИСПОЛЬЗОВАНИЕМ ГРАФОВ

Несмотря на то, что в настоящее время в теории алгоритмов оценкам сложности уделяется большое внимание, исследования в этой области в большинстве своем остаются чисто теоретически­

При этом X означает множество исходных данных, а У— мно­ жество промежуточных результатов, получаемых в процессе вы­ полнения функциональных операторов Ф,.

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

На рис. 25а приведена граф-схема для алгоритма, определяе­

134

135

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

Если представить алгоритм вычислений в виде графа, то, ис­ пользуя аналитический аппарат теории графов, можно выполнить расчет ряда характеристик алгоритма, например, вектор встречае­ мости операций, относительные частоты использования отдельных операций,склонность к распараллеливанию и др.

время выполнения алгоритма на конкретной машине. Объем ин­ формации связан с объемом памяти, необходимой машине для реализации этого алгоритма.

Число операций связано прямой зависимостью с временем вы­ числения алгоритма {Т — ф (N)). Но выполнение различных опе­ раций требует различного времени. Так, операции сложения и вы­ читания, как наиболее простые, требуют меньшего машинного вре­ мени для своего выполнения. Отюда следует, что для определения сложности алгоритма необходимо знать не только общее количест­ во операций, но также и количество используемых в алгоритме типов операций и количество операций каждого типа в отдельно­ сти.

Количество операций для заданного алгоритма определяется следующим образом.

На основании анализа графа получаем вектор встречаемости операций в алгоритме

#={<?ь Q 2 . - - - , Q v , Q r } , где Qi — количество операций i-ro типа;

г — количество операций в исследуемом классе задач и отно­ сительные частоты операций:

Pi= при Л/ = 2 Qi •

Умножая время выполнения каждой операции на количество этих операций и суммируя результаты по всем операциям, полу­ чим время реализации алгоритма

Т= i Qi-ti • i = l

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

136

^Na

АЛГЭК. В результате работы по этой программе определяется частота использования следующих групп операций:

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

Желательно иметь такой метод оценки сложности алгоритмов, который позволял бы оценить алгоритм до его представления в алгоритмическом языке. Это необходимо и на этапе проектирова­ ния механизированной обработки информации, и на этапе проекти­ рования АСУ, и на этапе проектирования вычислительных центров.

137

В данной работе для определения числа операций и, в частно­ сти, вектора встречаемости операций в алгоритме без записи его на алгоритмическом языке предлагается использовать аппарат графов.

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

Как известно, в любом алгоритме можно выделить два вида элементов: операционные элементы и решающие элементы. Опе­ рационным элементам соответствуют отдельные операции или по­ следовательности операций, не прерываемые условной передачей управления. Решающим элементам соответствуют логические опе­ рации, вызывающие условные передачи управления. В качестве такой операции в большинстве случаев используется операция сравнения.

При построении графа алгоритма каждой элементарной опе­ рации (сложение, вычитание, умножение, деление, переадресация, сравнение и т. п.) сопоставляется вершина графа G(X,U). Вер­ шина графа Xi соединяется с вершиной Xi+\ в том и только в том случае, если операция, соответствующая вершине х%+\, выполняет­ ся непосредственно после операции х\. Таким образом, в графах, отражающих алгоритм, из каждой вершины, соответствующей операционному элементу, будет исходить точно по одной дуге, а из каждой вершины, соответствующей решающему элементу, — точно по две дуги.

Алгоритм строится с учетом циклов, отражающих процесс об­ работки информации. Циклы обработки должны быть строго вло­

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

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

Число операций для каждой из вершин графа G (X, U) опре­ деляется в результате умножения значения параметра mit соот­ ветствующего данной вершине, на произведение параметров 1} по пути, ведущему от заданной вершины к конечной:

Ni~miY\lj >

138

где / соответствует номерам тех дуг, которые ведут из вершины Xi в конечную вершину.

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

Рассмотрим расчет числа операций на примере составления сводки о реализации фондов в отделе строительных материалов. Граф алгоритма этой задачи, построенный с учетом изложенных требований, представлен на рис. 26.

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

Рис. 26. Граф алгоритма для расчета числа операций

139