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

ЯЭ о о о о о о о о о о о о о о о о о »—< о о о о о о о о о

чэ о о о о о о о о о о о о о о « о о о о о о => о о о о о

2Л о о о о о о о о о о о о о о о о о о о о о о о о о

ZA о о о о о о о о о о о < о о о о о о о о с о о о о о

II

12ft

Глава V О Ц Е Н К А С Л О Ж Н О С Т И

А Л Г О Р И Т М О В

§ 5. 1. ОЦЕНКА с л о ж н о с т и с п о м о щ ь ю СИГНАЛИЗИРУЮЩИХ ФУНКЦИЙ

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

В качестве меры сложности алгоритма рассматривается функ­ ционал, соотносящий каждому из алгоритмов Л = {Ль Л 2 , . . . } не-

.которое число М (Лг-), характеризующее его громоздкость, напри­ мер число команд в Л*, длину записи или какой-либо другой пара­ метр, характеризующий объем информации, содержащейся в Л*.

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

В качестве меры сложности вычислений рассматривается функ­

характеризует сложность работы алгоритма Л* применительно к исходным данным задачи 3* до выдачи соответствующих резуль­ татов.

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

128

Поскольку для каждого алгоритма Л* однозначно определен класс задач 3,, который он решает, то в качестве меры сложности работы алгоритма (вычисления) можно принять некоторый опе­ ратор, сопоставляющий с каждым алгоритмом Л» соответствую­

работе Б. А. Трахтенброта [70]. Б. А. Трахтенброт ввел специаль­ ные функции, измеряющие объем памяти, необходимый для вы­ полнения заданных вычислений, и назвал их сигнализирующими функциями.

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

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

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

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

восстановить слово X.

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

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

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

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

\Р\<П

130