Elasticity of algorithms.pdf Современная индустрия программного обеспечения и средств информационнойбезопасности компьютерных систем диктует необходимость развития специальных методованализа и классификации алгоритмов. В теории сложности вычислений классификацияалгоритмов традиционно осуществляется с точки зрения вычислительнойсложности - трудоемкости продуцируемых алгоритмами вычислительных процессов.При этом вычислительная сложность алгоритма формально описывается функциейвременной сложности t(n), отражающей максимальное количество элементарных шагов,которое необходимо алгоритму для достижения запланированного результата в зависимостиот n - длины входа алгоритма [1]. Обычно ограничиваются рассмотрениемповедения функций сложности в асимптотике при стремлении n к бесконечности, а изложениерезультатов ведется в терминах O-большое и о-малое [2]. До недавнего времениалгоритмы подразделяли на низкозатратные (полиномиальные) и высокозатратные(экспоненциальные). В сегодняшней программной инженерии используется пять слож-ностных классов алгоритмов. Выделены субполиномиальные (быстрые) алгоритмы изполиномиального класса, субэкспоненциальные и гиперэкспоненциальные алгоритмыиз экспоненциального класса. Субполиномиальные и субэкспоненциальные алгоритмы- область повышенного интереса современных криптографических систем [3]. Использованиенепосредственного асимптотического оценивания для распознавания всехпяти сложностных классов алгоритмов в большинстве случаев сопряжено с трудностямивычислительного характера.В данной работе в качестве меры вычислительной сложности алгоритмов взятаэластичность функций t(n). Относительно функций t(n) сделан ряд естественных допущений.Во-первых, полагается, что t(n) -монотонно неубывающие функции, областьюзначений которых выступает множество неотрицательных действительных чисел,а областью определения - множество неотрицательных целых чисел. Во-вторых, допускаетсяотступление от дискретности изменения n (с формальной заменой n на x),т. е. предположение о том, что аргумент x непрерывен, а необходимые значения t(n)вычисляются в целочисленных точках x = n. В-третьих, рассматриваемое множествофункций ограничивается семейством L - «по-существу положительных» логарифми-чески-экспоненциальных функций. Установление указанных границ рассматриваемогомножества функций обеспечивает существование эластичности и возможность сравнениялюбых двух функций сложности алгоритмов по скорости роста.Эластичный (греч. elastikos)-упругий, гибкий. С физической точки зрения эластичность- это свойство вещества оказывать механическое сопротивление силе, котораяна него воздействует, и принимать исходную форму после спада данной силы.Противоположность пластичности. Изучается в теории упругости. С экономическойточки зрения эластичность - это характеристика изменения одного показателя (например,спроса) к другому показателю (например, цене товара). Используется в эконометрикедля анализа производственных функций. С математической точки зрения эластичностьEx (y) - коэффициент пропорциональности между темпами роста величинy = t(x) и х - дифференциальная характеристика функции y = t(x), определяемаякак предел отношения относительного приращения этой функции к относительномуприращению аргумента:Ex(y) = lim ( -у : -x ) = x lim = x y = x(ln y)' = .Ax^0 ^ y x J y Ax^0 -x y (ln x)'Таким образом, если Ex(t) - эластичность функции временной сложности y = t(x),то это означает, что при повышении значения x (длины входа алгоритма) на один процентзначение t (время выполнения алгоритма) увеличится приблизительно на Ex(t)процентов.В работе [4] доказано, что семейство монотонно неубывающих, «по-существу положительных» L-функций можно разбить на классы Subpoly, Poly, Subexp, Exp, Hyperexp,для которых свойственно специфическое поведение эластичности на бесконечности.Это позволяет формально описать пять современных сложностных классов алгоритмов.Класс быстрых алгоритмов - множество алгоритмов с функциями сложностиt(x) Е Subpoly. Таким алгоритмам присуща тождественно нулевая или бесконечномалая эластичность. Класс полиномиальных алгоритмов - множество алгоритмовс t(x) Е Poly и асимптотически постоянной эластичностью Ex (t). Класс суб-экспоненциальных алгоритмов - алгоритмы, для которых t(x) Е Subexp. ЭластичностьEx(t) субэкспоненциального алгоритма - бесконечно большая величина, такая,что 1 -< Ex(t) -< x. Для подобного алгоритма темп роста времени выполнения значительновыше темпа роста длины входа. Класс экспоненциальных алгоритмов - этоалгоритмы с t(x) Е Exp. Для них эластичность Ex(t) = O(x) -бесконечно большаявеличина, асимптотически пропорциональная линейной функции. Функции с аналогичнойэластичностью описывают законы естественного роста: скорость увеличенияфункции прямо пропорциональна ей самой. Класс гиперэкспоненциальных алгоритмов- множество алгоритмов с t(x) Е Hyperexp и x -< Ex(t). Темп роста гиперэкспо-ненциальных функций настолько высок, что не укладывается в законы естественногороста. В настоящее время алгоритмы класса Hyperexp практически неосуществимыприбольшой длине входа.Классификация алгоритмов по асимптотике поведения эластичности функцийсложности не разрушает прежней, традиционной классификации с полиномиальнымии экспоненциальными алгоритмами, а лишь дополняет и уточняет ее. Свойстваэластичности позволяют без особого труда вычислять ее для любой L-функции.В экономических науках наибольший интерес вызывают эластичные и абсолютно(совершенно) эластичные зависимости. Функция временной сложности алгоритма описываетобратную зависимость, нежели производственная функция: если производственнаяфункция - это связь «ресурсы^- объем», то функция сложности алгоритма -«объем исходных данных^- ресурсы». Поэтому естественно то, что в теории сложностивычислений эффективными считают быстрые (совершенно неэластичные) и полиномиальные(эластичные) алгоритмы. Алгоритмы с функциями сложности из классовSubexp, Exp, Hyperexp целесообразно называть абсолютно эластичными. В асимптотикетемп роста времени выполнения абсолютно эластичных алгоритмов «взрывается»даже при небольших изменениях объема исходных данных, поступающих на вход алгоритмов.

Скачать электронную версию публикации