FPT-алгоритмы и их классификация на основе эластичности | ПДМ. 2011. № 2(12).

FPT-алгоритмы и их классификация на основе эластичности

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

FPT-algorithms and their classification on the basis of elasticity.pdf С позиции классической теории сложности большинство задач, имеющих важноепрактическое значение, NP-трудные [1]. Классическая теория сложности анализируети классифицирует задачи и алгоритмы по объему ресурса (преимущественно времени),необходимого для достижения требуемого результата, и потому оперирует функциямивычислительной сложности t(n), зависящими от одной переменной n - длины входаалгоритма. Такая одномерность и ориентация в анализе алгоритмов на худший слу-чай зачастую делает задачи сложнее, чем они есть на самом деле. Для практическогорешения NP-трудных задач были предложены многие подходы, среди которых при-ближенные и параметризированные алгоритмы. Цель приближенных алгоритмов -найти за полиномиальное время решение, близкое к оптимальному. Заметный классприближенных алгоритмов составляют полностью полиномиальные схемы приближе-ний [2]. Параметризированные алгоритмы направлены на поиск точных решений NP-трудных задач, когда параметр k решаемой задачи мал по сравнению с длиной входаалгоритма. Роль этого параметра - учесть информацию о структуре входных данныхалгоритма и выделить основной источник неполиномиальной сложности NP-труднойзадачи. В параметризированной теории используются двумерные функции сложностиалгоритмов (функции, зависящие от n и k), поэтому ее называют двумерной теориейсложности вычислений [3]. Параметризированная теория сложности создает основудля анализа и детальной классификации задач, которые труднорешаемые в классиче-ском понимании, а также для развития новых методов анализа и разработки эффек-тивных алгоритмов решения NP-трудных задач. Идея параметризированного подходак оценке сложности алгоритмов и задач была предложена в 90-х годах прошлого сто-летия [4]. За последние два десятилетия эта идея нашла применение в различных обла-стях компьютерных наук, таких, как криптография [5], искусственный интеллект [6],вычислительная биология [7], теория баз данных [8].1. Параметризированные задачи и алгоритмыПриведем основные положения теории параметризированной сложности, исполь-зуя обозначения и понятия, введенные в работах [3, 4]. Параметризированная задача Псостоит в том, что для заданных языка L(n) С Е* х N, где Е - некоторый конечныйалфавит и N - множество всех неотрицательных целых чисел, и пары (I,k) Е Е* х Nтребуется определить, является ли (I, k) элементом L(n). Для алгоритма а, решающе-го данную задачу, (I,k) называют входом, I - его основной частью, n = |11 -длинойвхода и число k - параметром задачи. Алгоритм а называют параметризированнымалгоритмом, если его вычислительная сложность, определяемая количеством времениисполнения, оценивается с точки зрения длины входа |11 = n и значения параметра k.Таким образом, функция вычислительной сложности параметризированного алгорит-ма, определяющая время его работы, - функция двух переменных t(n, k).Параметризированная задача П считается разрешимой с фиксированным парамет-ром, или FPT-разрешимой (Fixed-Parameter Tractable), если она может быть решенанекоторым параметризированным алгоритмом за времяt(n,k) = O(nO(1) f (k)) (1)для функции f, зависящей только от параметра k. Порядок роста функции f (k) неограничивается. Так, возможно f (k) = 2o(k) или f (k) = 2O(k). Важно, что исключают-ся функции вида f (n, k), например f (n, k) = nk. Класс всех разрешимых с фикси-рованным параметром задач обозначается FPT. Соответствующие параметризирован-ные алгоритмы, решающие такие задачи, называются FPT-алгоритмами.Примером FPT-разрешимой задачи может служить задача о вершинном покры-тии графа, когда параметром выступает размер покрытия. В самом деле, вершинноепокрытие размера k в графе G с n вершинами можно определить за время O(n 2k). Ес-ли в данной задаче в качестве параметра взять древовидную ширину tw(G) графа G,то метод динамического программирования способен отыскать наибольшее вершин-ное покрытие за время O(n 2tw(G)) [9]. Следовательно, параметризация данной задачиотносительно tw(G) вновь приводит к FPT-разрешимости. Примером задачи, котораяне принадлежит FPT, является задача о k-раскраске n-вершинного графа с парамет-ром k.Очевидно, что в FPT лежат все полиномиально разрешимые задачи. Однако наи-больший интерес с точки зрения теории и практики представляют FPT-разрешимыезадачи, являющиеся NP-трудными. С теоретической точки зрения все эти задачи мо-гут быть решены за полиномиальное время при каждом фиксированном значении па-раметра. Реально это удается осуществить в большинстве случаев лишь при малыхзначениях параметра (все зависит от вида функции f(k)). Уже имеются сборникипараметризированных задач, включая FPT-разрешимые задачи. Наиболее конкрет-ным на данный момент времени является сборник М. Чезати [10]. Теория параметри-зированной сложности развивается по нескольким направлениям: определение иерар-хии классов сложности параметризированных задач, установление условий FPT-раз-решимости, выявление взаимосвязи между параметризированной сложностью и клас-сами приближенных алгоритмов (в частности, полностью полиномиальными схемамиприближений), развитие параметризированной алгоритмики (методов анализа и раз-работки параметризированных алгоритмов) [3]. Последнее направление - это преиму-щественно область прикладных исследований. Здесь имеется ряд открытых вопросов.2. Некоторые вопросы параметризированной алгоритмикиАнализ сборника параметризированных задач [10] показывает, что одна и та жезадача может иметь различные параметризации (различные параметризированныеформулировки) относительно разнообразных параметров. Так, в задаче о вершинномпокрытии параметрами могут быть размер покрытия, число вершин, число ребер, дре-вовидная ширина, наибольшая степень вершин графа и др. Закономерны вопросы:1) Что может служить в качестве параметра для NP-трудной задачи?2) Как следует выбирать параметр, чтобы задача стала FPT-разрешимой?3) Существуют ли специальные методы разработки FPT-алгоритмов?4) Как сравнивать между собой различные FPT-алгоритмы, предназначенные длярешения одной и той же NP-трудной задачи?На некоторые из этих вопросов пока нет исчерпывающих ответов. Например, напервые два вопроса параметризированная теория сложности отвечает следующим об-разом.Бывают параметры внутренние и внешние. Параметр считается явным внутрен-ним, если он непосредственно появляется в основной части экземпляра (I, k) парамет-ризированной задачи П и его значение ограничено полиномом от |11 = n. Для за-дачи о вершинном покрытии подобными параметрами являются размер покрытия,число вершин или число ребер графа. Имеются стандартные параметры. Они наи-более популярны. Так, в задачах минимизации в роли стандартного параметра все-гда выступает величина, которая минимизируется. Для задачи о вершинном покры-тии - это размер покрытия. Если k = n, то k становится тривиальным парамет-ром, и параметризированный алгоритм вырождается в обычный алгоритм. Параметрявляется неявным внутренним, если его значение ограничено полиномом от |11 = nи информация о нем неявно скрыта в I. Типичным примером неявного внутреннегопараметра является древовидная ширина графа (значение этой величины никогда непревосходит числа вершин графа). В целом, все внутренние параметры характеризу-ют некоторым образом структуру входных данных алгоритма. Наконец, существуютвнешние параметры, которые никак не связаны с |11 или связаны с |11 неполиномиаль-ным образом. Информация о таких параметрах задается дополнительно к I, так каксчитается, что ее нет в I.С теоретической точки зрения в качестве параметра может выступать любая частьвхода алгоритма. На практике для получения хорошей параметризации (например, от-носящейся к FPT) рекомендуется выбирать ту часть входа, которая обычно принимаетмалые значения по сравнению с |11 = n. В конечном счете, все зависит от приложе-ния. Для различных приложений могут быть приемлемы различные параметризацииодной и той же NP-трудной задачи. Относительно ряда NP-трудных задач доказа-но, что некоторые их параметризации не могут быть реализованы FPT-алгоритмами.В частности, такой задачей является задача о k-раскраске n-вершинного графа с па-раметром k. Для некоторых NP-трудных задач найдены FPT-алгоритмы лишь при-менительно к отдельным параметрам. Например, для многих оптимизационных задачна графах древовидная ширина оказалась таким параметром, который, как правило,приводит к FPT-алгоритмам [9-11].Что касается третьего из перечисленных выше вопросов, то в настоящее время ужепредложены и апробированы несколько специальных методов конструирования FPT-алгоритмов. Прежде всего, это метод динамического программирования на основе де-рева декомпозиции для графов с ограниченной древовидной шириной [11]. Другимизвестным методом построения FPT-алгоритмов является параметрическая редукция(kernelization) [4]. Параметрическая редукция - это полиномиальное по времени пре-образование каждого экземпляра (/, k) параметризированной задачи П в экземпляр(/',k') параметризированной задачи П' так, что k! < k. После выполнения редукциик экземпляру (/', k'), называемому ядром, применяется полный перебор. Например,для задачи о вершинном покрытии со стандартным параметром k (размером покры-тия) редукция сводится к многократному применению двух правил: удаление изоли-рованной вершины без изменения значения параметра k; удаление вершины, степенькоторой больше k, и уменьшение параметра k на единицу. Следует отметить, что ме-тод параметрической редукции в сочетании с полным перебором не всегда приводит кFPT-алгоритму. Между тем доказано, что если параметризированная задача принад-лежит к FPT, то данный метод неизменно дает FPT-алгоритм [4].Четвертый вопрос теоретически открыт: в многочисленных работах по параметри-зированной теории сложности для анализа и сравнения параметризированных алго-ритмов применяются методы классической (одномерной) теории сложности [12-14].Между тем классическая одномерность ограничивает глубину анализа параметризиро-ванных алгоритмов, для которых вычислительная сложность описывается функциейот двух переменных t(n, k). В настоящей работе предлагается мера вычислительнойсложности алгоритма, с помощью которой можно исследовать темп роста функциймногих переменных, анализировать степень влияния структуры входных данных па-раметризированного алгоритма на его вычислительную сложность, сравнивать междусобой FPT-алгоритмы решения NP-трудных задач. Этой мерой является частная эла-стичность функции вычислительной сложности (далее просто функции сложности)алгоритма. Представленные в статье результаты являются обобщением и расширени-ем результатов автора, опубликованных в [15- 17] применительно к одномерной теориисложности вычислений.3. Соглашения относительно функций сложностиФормальный подход к анализу параметризированных алгоритмов требует уточне-ния свойств их функций сложности t(n, k). Относительно функций t(n, k) мы сделаемнесколько естественных допущений, которые выполнимы для большинства реальныхалгоритмов: полагаем, что t(n,k) -монотонно неубывающие функции по обоим аргументам,областью значений функций выступает множество неотрицательных действитель-ных чисел, а областью определения - множество N х N; допускаем возможность отступления от дискретности изменения n и k (с формаль-ной заменой n на x и k на у), т. е. считаем, что аргументы функции t(n, k) непрерыв-ны, а необходимые значения вычисляются в целочисленных точках x = n и у = k.Руководствуясь данным допущением, ниже вместо t(n,k) будем писать z(x,y); предполагаем, что рассматриваемое множество функций ограничивается семейст-вом L «по-существу положительных», логарифмически-экспоненциальных функ-ций. Функция z(x,y) считается «по-существу положительной», если существуюттакие значения x0, уо, что z(x, у) > 0 для всех x > x0, у > уо. Семейство L опреде-лено рекурсивно, и всякая функция z(x^) Е L представима в виде z(x^) = ew(x ' y),где и ^ у ) Е L [18]. Известно, что каждая такая функция непрерывна и диффе-ренцируема в той области, где она определена.Данные предположения являются гарантией существования эластичности для функ-ций сложности параметризированных алгоритмов.4. Эластичность функции как мера вычислительной сложности алгоритмаПод эластичностью Ex(z) функции z = z(x) принято понимать предел отношенияотносительного приращения этой функции к относительному приращению аргумента:^ . . (Az Ax\ dz dx dz x ,xEx(z) = lim : = - : - = = z ' - = x(lnz)'. (2)Д х ч ^ z x ) z x d x z zОтметим несколько важных особенностей эластичности L-функции. Для всякойL-функции z = z(x) всегда существует эластичность и Ex(z) ^ 0. В [15] показано,что при x ^ то эластичность L-функции - тождественно постоянная, или бесконеч-но малая, или бесконечно большая логарифмически-экспоненциальная функция, длякоторойzln xПоследняя оценка означает, что при x ^ то поведение эластичности инвариантноотносительно полиномиального преобразования, заключающегося в умножении этойфункции на константу c > 0 и возведении в положительную и отделенную от нулястепень m > 0. Хорошо известно [18], что две произвольные L-функции zi(x), z2 (x)всегда сопоставимы между собой по порядку роста: если z1(x), z2(x) G L, то при x ^ товерно одно из трех отношений:z1(x) - z2(x), z2(x) - z1(x), z1 (x) = O(z2(x)).Кроме того, доказано, что иерархия эластичностей порождает идентичную иерар-хию L-функций [17], т.е. если (z1) - Ex(z2), то z1(x) - z2(x). Заметим, что здесьотношение - интерпретируется так: z1(x) - z2(x) тогда и только тогда, когдаz1(x) = °(z2(x)). O-большое обозначает асимптотическую пропорциональность функ-ций: z1(x) = O(z2(x)) тогда и только тогда, когда z1(x) ~ cz2(x), c > 0. Согласно (2),при достаточно малых Ax справедливо приближениеAz Ax- w Ex(z) ,z xкоторое указывает, что Ex(z) - коэффициент пропорциональности между темпами ро-ста переменных z и x. Поскольку Ex(z) = Eax(bz) для любых констант а > 0, b > 0, тоэластичность - безразмерная величина.Все перечисленные выше особенности эластичности позволяют использовать еев качестве меры измерения вычислительной сложности алгоритма, поскольку онаудовлетворяет ряду необходимых требований, таких, как сопоставимость, интерпре-тируемость и вычислимость. Сопоставимость обеспечивают безразмерность и инвари-антность относительно модели вычислений: ведь переход от одной модели к другойменяет вычислительную сложность алгоритма лишь полиномиальным образом. Эла-стичность имеет отчетливую интерпретацию: если z = z(x) - функция сложности ал-горитма, то это означает, что при повышении значения x (длинывхода алгоритма)на один процент значение z (время выполнения алгоритма) увеличивается приблизи-тельно на Ex(z) процентов. Вычислимость также имеет место: эластичность существу-ет для всякой L-функции и всегда может быть определена непосредственно из (2) исвойств эластичности. Эластичности присущи свойства, сходные со свойствами опера-ций логарифмирования и дифференцирования [16], поэтому она легко определяетсядля логарифмически-экспоненциальных функций. Простота вычисления - это основ-ное достоинство эластичности по сравнению с другими мерами сложности вычислений.Важно отметить, что эластичность - локальная характеристика функции: ее зна-чения в общем случае изменяются при переходе от одного значения аргументак другому. Между тем при больших значениях аргумента в поведении эластичностиL-функций наблюдаются определенные закономерности: разным (по скорости роста)классам L-функций свойственно принципиально различное поведение эластичности, инаоборот, по асимптотике поведения эластичности можно однозначным образом опре-делить класс, к которому относится L-функция. Это утверждает следующая теорема.Теорема 1 (о классификации L-функций) [15]. Разбиение семейства монотоннонеубывающих «по-существу положительных» L-функций на классы SUBPOLY, POLY,SUBEXP, EXP, HYPEREXP в соответствии с порядком их роста эквивалентно надле-жащему разбиению по асимптотике эластичности этих функций на бесконечности:SUBPOLY = {z(x) : z(x) X eO ( l n x ) } = {z(x) : E^z) = o(1)}; (3)POLY = {z(x) : z(x) = O ( e O ( l n x ) ) } = {z(x) : Ea(z) = O(1)}; (4)SUBEXP = {z(x) : eO(lnx) X z(x) X eO ( x ) } = {z(x) : 1 X Ex(z) X x}; (5)EXP = {z(x) : z(x) = O (eO ( x ) )} = {z(x) : Ex(z) = O(x)}; (6)HYPEREXP = {z(x) : eO(x) X z(x)} = {z(x) : x X E*(z)}. (7)Данная теорема порождает пять сложностных классов алгоритмов (субполино-миальных, полиномиальных, субэкспоненциальных, экспоненциальных и гиперэкспо-ненциальных соответственно), которые полностью отвечают современной классифи-кации алгоритмов. Класс быстрых алгоритмов составляют алгоритмы с функциямисложности z(x) Е SUBPOLY. Таким алгоритмам присуща тождественно нулевая илибесконечно малая эластичность. Класс полиномиальных алгоритмов - множество ал-горитмов с z(x) Е POLY и асимптотически постоянной эластичностью Ex(z). Класссубэкспоненциальных алгоритмов - алгоритмы, для которых z(x) Е SUBEXP. Элас-тичность Ex(z) субэкспоненциального алгоритма - бесконечно большая величина, та-кая, что 1 X Ex (z) X x. Класс экспоненциальных алгоритмов - это алгоритмы, длякоторых z(x) Е EXP. Для них эластичность Ex(z) = O(x) - бесконечно большая ве-личина, асимптотически пропорциональная линейной функции. Класс гиперэкспонен-циальных алгоритмов - это алгоритмы, для которых z(x) Е HYPEREXP и x X Ex(z).Эквивалентности (3) - (7) обеспечивают «прозрачность» сложностных классов алго-ритмов, ведь эластичности согласно (3) - (7) представляются более простыми по видуфункциями, чем соответствующие им L-функции. Понятие эластичности легко рас-пространяется на функции многих переменных. Это дает возможность использоватьданную дифференциальную характеристику функции в анализе параметризирован-ных алгоритмов.Под частной эластичностью Ex(z) функции z = z(x, у) по аргументу x понимаетсяэластичность переменной z, которая рассматривается как функция только от x и припостоянных значениях у. Частная эластичность Ex(z) связана с частной производнойфункции z = z(x, у) по x соотношениемxEx(z) = zX z = x(lnz)X. (8)Аналогично определяется частная эластичность Ey(z) функции z = z(x,y) по аргу-менту у:Ey (z) = zy ^ = у(ln z)y. (9)Поскольку всякая L-функция z = z(x, y) непрерывна и дифференцируема в той об-ласти, где она определена, то для нее в этой области всегда существуют частные эла-стичности. Выражения (8), (9) аналогичны формуле (2). Поэтому частные эластично-сти Ex(z),Ey (z) обладают всеми основными свойствами эластичности функции однойпеременной [16]. Укажем наиболее важные из этих свойств и запишем их примени-тельно к Ex(z):1) Если z = z(x,y) не зависит от x, то Ex(z) = 0.2) Безразмерность: Ex(z) = Eax(bz) для любых констант а > 0, b > 0.3) Частная эластичность произведения (отношения) функций z1 = z1(x,y) иz2 = z2(x,y) равна сумме (разности) их частных эластичностей:Ex(z1 z2) = Ex(z1) + Ex(z2), Ex(z1/z2) = Ex(z1) - Ex(z2).Частным эластичностям свойственна отчетливая интерпретация. Пусть z = z(n, k)является функцией сложности параметризированного алгоритма, где n - длина вхо-да, а k - параметр этого алгоритма. После формальной замены n на x и k на y имеемz = z(x,y) G L. Тогда Ex(z) -коэффициент пропорциональности между темпом роставремени работы алгоритма и темпом роста его длины входа x. Аналогично Ey(z) - ко-эффициент пропорциональности между темпом роста времени выполнения алгоритмаи темпом роста параметра y.5. Двумерная классификация FPT-алгоритмов по сложностиВ общем случае частные эластичности Ex(z),Ey(z) являются функциями, завися-щими от двух аргументов x и y. Однако ситуация значительно упрощается, если учестьтот факт, что для большинства параметризированных алгоритмов время работы ал-горитма описывается L-функцией видаz ( x , y ) = q ( x ) / (У) ' (10)где q(x) G L - количественная компонента, а /(y) G L - параметрическая компонентафункции z(x,y). Мультипликативная форма представления (10) характерна для ал-горитмов с параметрически зависимым циклом, выполняющим полный перебор всехвозможных вариантов при различных значениях параметра, тогда как в теле этогоцикла выполняется проверка текущего варианта и время проверки зависит только отдлины входа алгоритма. Именно такие алгоритмы порождает метод параметрическойредукции. Заметим, что формула (1), определяющая время работы FPT-алгоритма,также имеет мультипликативную форму записи:z(x,y) = O(xO(1) /(y)). (11)Пусть z(x,y) = q(x) /(y) G L. Тогда, исходя из свойств эластичности 1 и 3, част-ные эластичности Ex(z), (z) вырождаются в обычные эластичности функции одногоаргумента:Ex(z) = Ex(q(x) /(y)) = Ex(q(x)) + .л(/(y)) = Ea(q(x)); (12)Ey(z) = Ey(q(x) /(y)) = Ey(q(x)) + Ey(/(y)) = Ey(/(y)). (13)Теперь Ex(z) зависит лишь от x, а Ey(z) - только от y. Поскольку q(x), /(y) G L,то каждая из этих функций принадлежит только одному сложностному классу изK = {SUBPOLY, POLY, SUBEXP, EXP, HYPEREXP}. Обозначим через Fx класссложности функции z(x,y) по аргументу x, а через Fy - класс сложности по ар-гументу y. Тогда всякому параметризированному алгоритму с функцией сложностиz(x,y) = q(x) f (у) Е L соответствует пара(Fx,Fy) Е K х K,характеризующая сложность данного алгоритма как по длине входа x, так и по значе-нию параметра у. Таким образом, мы приходим к двумерной классификации парамет-ризированных алгоритмов по сложности. При двумерном подходе более отчетливуюи общую формулировку получает определение FPT-алгоритма и условие (11): пара-метризированный алгоритм называется FPT-алгоритмом, если время его исполнениязадается функцией z ( x ^ ) = q(x) f (у) Е L, для которой(Fx,Fy) Е {SUBPOLY, POLY} х K.Когда параметризированная задача не только FPT-разрешима, но и полиномиальноразрешима, то для нее существуют FPT-алгоритмы, сложность которых соответствуетпарам(Fx,Fy) Е {SUBPOLY, POLY} х {SUBPOLY, POLY}. (14)Подобные параметризированные алгоритмы естественно назвать полиномиальнымиFPT-алгоритмами. Алгоритмы, сложность которых отвечает парам(Fx,Fy) Е {SUBPOLY, POLY} х {SUBEXP}, (15)(Fx,Fy) Е {SUBPOLY, POLY} х {EXP}, (16)(Fx,Fy) Е {SUBPOLY, POLY} х {HYPEREXP}, (17)целесообразно определить как субэкспоненциальные, экспоненциальные и гипер-экспоненциальные FPT-алгоритмы соответственно. Такие FPT-алгоритмы присущиNP-трудным задачам.Введенная двумерная классификация FPT-алгоритмов не противоречит понятиям,используемым в настоящее время в параметризированной теории сложности примени-тельно к FPT-алгоритмам, а лишь формально их уточняет и расширяет. При желаниив декартовом произведении K х K всегда можно выделить более мелкие подмножествапар (Fx, Fy) и, как следствие, определить более детальную классификацию параметри-зированных алгоритмов, чем (14) - (17). При тривиальной параметризации у = x соот-ношения (12), (13) принимают единый видEx(z) = Ex(q(x) f (x)) = Ex(q) + Ex(f).В этом частном случае приходим к одномерной классификации алгоритмов. Анало-гичный случай возникает, когда f (у) -тождественная константа.ЗаключениеПараметризированная теория сложности дала толчок к разработке новых подходовконструирования алгоритмов (алгоритмов решения задач, разрешимых с фиксирован-ным параметром). Одновременно с этим, данная теория породила ряд проблем. Однаиз них - отсутствие простых и удобных инструментов анализа параметризированныхалгоритмов,когда их функции сложности зависят от многих переменных. В настоя-щей работе предложен показатель, с помощью которого можно измерять темп ростафункций многих переменных, сравнивать между собой FPT-алгоритмы, анализиро-вать степень влияния параметра на вычислительную сложность параметризирован-ного алгоритма. Этим показателем является частная эластичность. Для мультипли-кативной формы представления функций сложности в работе предложена двумер-ная классификация параметризированных алгоритмов, точно определен класс FPT-алгоритмов, выделены подклассы полиномиальных, субэкспоненциальных, экспонен-циальных и гиперэкспоненциальных FPT-алгоритмов. Допустимо дальнейшее разви-тие предложенного подхода в части увеличения числа параметров и анализа другихформ представления функций сложности.

Ключевые слова

elasticity of algorithms, parameterized algorithms, computation complexity, эластичность алгоритмов, анализ алгоритмов, параметризированные алгоритмы, сложность вычислений

Авторы

ФИООрганизацияДополнительноE-mail
Быкова Валентина ВладимировнаСибирский федеральный университет, г. Красноярскдоцент, кандидат технических наук, профессор Института математикиbykvalen@mail.ru
Всего: 1

Ссылки

Грэхем Р., Кнут Д., Поташник О. Конкретная математика. М.: Мир; Бином. Лаборатория знаний, 2006.
Bykova V. V. Complexity and elasticity of the computation // Proc. of the 3-rd IASTED International Multi-Conference on Automation, Control, and Information Technology (ACITCDA 2010). Anaheim-Calgary-Zurich: ACTA Press, 2010. P. 334-340.
Быкова В. В. Эластичность алгоритмов // Прикладная дискретная математика. 2010. №2(8). С. 87-95.
Быкова В. В. Метод распознавания классов алгоритмов на основе асимптотики эластич- ности функций сложности // Журн. СФУ. Математика и физика. 2009. №2(1). С. 46-61.
Быкова В. В. Математические методы анализа рекурсивных алгоритмов // Журн. СФУ. Математика и физика. 2008. №1(3). С. 236-246.
Грин Д., Кнут Д. Математические методы анализа алгоритмов. М.: Мир, 1987.
Кормен Т., Лейзерсон Ч., Ривест Р. Алгоритмы: построение и анализ. М.: МЦНМО, 1999.
Gottlob G., PichlerR., and Wei F. Abduction with bounded treewidth: From theoretical tractability to practically efficient computation // Proc. of the Twenty-Third AAAI Conf. on Artificial Intelligence. Menlo Park: AAAI Press, 2008. P. 1541-1546.
Niedermeier R. Invitation to fixed-parameter algorithms: Oxford Lecture series in mathematics and its applications. Oxford: University Press, 2006.
CesatiM. Compendium of parameterized problems. http://bravo.ce.uniroma2.it/home/ cesati/research/compendium - 2006.
Papadimitriou C. and Yannakakis M. On the complexity of database queries / / J . Comput. System Scien. 1999. V. 58. P. 407-427.
Bodlaender H., Downey R., Fellows M., et al. Parameterized complexity analysis in computational biology // Comput. Appl. Bioscien. 1995. V. 11. P. 49-57.
Gottlob G., Scarcello F., and Sideri M. Fixed-parameter complexity in AI and Nonmonotonic reasoning // Artific. Intellig. 2002. V. 138. P. 55-86.
Downey R. and Fellows M. Parameterized complexity. New York: Springer Verlag, 1999.
Fellows M. and Koblitz N. Fixed-parameter complexity and cryptography // Technical Report DCS-207-IR, Department of Comput. Science, University of Victoria, 1992.
Flum J. and Grohe M. Parameterized complexity theory. Berlin; Heidelberg: Springer Verlag, 2006.
Ausiello G., Crescenzi P., Gambosi G., et al. Complexity and approximation, combinatorial optimization problems and their approximability properties. New York: Springer Verlag, 1999.
Гэри M., Джонсон Д. Вычислительные машины и труднорешаемые задачи. М.: Мир, 1982.
 FPT-алгоритмы и их классификация на основе эластичности | ПДМ. 2011. № 2(12).

FPT-алгоритмы и их классификация на основе эластичности | ПДМ. 2011. № 2(12).

Полнотекстовая версия