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

§ 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