Методы анализа и разработки параметризированных алгоритмов тема диссертации и автореферата по ВАК РФ 05.13.17, доктор физико-математических наук Быкова, Валентина Владимировна

  • Быкова, Валентина Владимировна
  • доктор физико-математических наукдоктор физико-математических наук
  • 2012, Красноярск
  • Специальность ВАК РФ05.13.17
  • Количество страниц 257
Быкова, Валентина Владимировна. Методы анализа и разработки параметризированных алгоритмов: дис. доктор физико-математических наук: 05.13.17 - Теоретические основы информатики. Красноярск. 2012. 257 с.

Оглавление диссертации доктор физико-математических наук Быкова, Валентина Владимировна

Введение.

Глава 1. Предварительные обсуждения.

1.1. Алгоритмичность, конструктивность и вычислимость.

1.2. Концептуальные основы анализа алгоритмов.

1.3. Асимптотические обозначения, используемые в анализе алгоритмов.

1.4. Соглашения относительно функций сложности алгоритма. Характеризация класса логарифмически-экспоненциальных функций.

1.5. Графы и гиперграфы: основные понятия и обозначения.

Глава 2. Классическая и современная систематизации алгоритмов по сложности (одномерный случай).

2.1. Классическая систематизация алгоритмов по порядку роста функций сложности.

2.2. Эластичность и ее свойства.

2.3. Несколько вспомогательных утверждений.

2.4. Шесть классов £-функций.

2.5. Теорема о классификации ^-функций на основе эластичности.

2.6. Метод распознавания современных классов алгоритмов по асимптотике эластичности функций сложности.

2.7. Методика сравнения алгоритмов по асимптотике эластичности функций сложности.

2.8. Неэластичные, эластичные и суперэластичные алгоритмы.

Выводы.

Глава 3. Математические методы анализа рекурсивных алгоритмов

3.1. Проблемы анализа сложности рекурсивных алгоритмов.

3.2. Рекурсивные алгоритмы и рекуррентные соотношения.

3.3. Оценки решений специального типа рекуррентных соотношений, характерных для принципа «разделяй и властвуй».

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

Выводы.

Глава 4. Математический анализ параметризированных алгоритмов.

4.1. О классической сложностной дихотомии и подходах к решению трудноразрешимых задач.

4.2. Параметризация задач и алгоритмов. РРТ-разрешимость.

4.3. Проблемы параметризированной алгоритмики.

4.4. Классификация параметризированных алгоритмов по асимптотике частных эластичностей (двумерный случай).

4.5. Методика анализа воздействия параметра на вычислительную сложность параметризированного алгоритма.

4.6. Альтернативные характеризации РРТ-разрешимости.

Выводы.

Глава 5. Методы разработки ГРТ-алгоритмов на графах ограниченной древовидной ширины.

5.1. Специальные методы разработки РРТ-алгоритмов.

5.2. Дерево декомпозиции и древовидная ширина.

5.3. Метод динамического программирования по дереву декомпозиции.

5.4. Достаточные условия РРТ-разрешимости задач относительно древовидной ширины.

5.5. Вычислительная сложность метода и ее преодоление с помощью В&8-дерева.

5.6. Демонстрация решения задач выбора методом динамического программирования по В&Б-дереву.

Выводы.

Глава 6. Методы вычисления древовидной ширины.

6.1. Проблемы вычисления древовидной ширины.

6.2. Нижние оценки древовидной ширины и пути их уточнения.

6.3. Рекуррентный метод нижнего оценивания древовидной ширины, основанный на принципе «уменьшай и властвуй».

6.4. Рекуррентный метод верхнего оценивания древовидной ширины, основанный на принципе «разделяй и властвуй».

6.5. Алгоритмические аспекты применения минимальных сепараторов.

6.6. О верхнем оценивании древовидной ширины гиперграфа.

6.7. Уникальность разложения графа и гиперграфа на атомы кликовыми минимальными сепараторами.

Выводы.

Рекомендованный список диссертаций по специальности «Теоретические основы информатики», 05.13.17 шифр ВАК

Введение диссертации (часть автореферата) на тему «Методы анализа и разработки параметризированных алгоритмов»

Понятие алгоритма является не только одним из важнейших понятий математики, но одним из основных понятий современной науки. Чтобы ориентироваться в сегодняшнем мире алгоритмов, необходимо уметь сравнивать различные алгоритмы решения одних и тех же задач, причем не только по качеству выдаваемого решения, но и по характеристикам самих алгоритмов. Точный язык для обсуждения этих вопросов дает теория сложности вычислений. Ее результаты составляют теоретическую основу современной информатики и программной инженерии. Алгоритм как звено триады «задача-алгоритм-программа», с одной стороны, предопределяет производительность реализующей его программы, а, с другой стороны, способствует глубокому проникновению в решаемую задачу и нахождению эффективных методов ее решения.

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

Типичный уровень анализа - установление класса сложности и асимптотических оценок функции временной сложности исследуемого алгоритма с ориентацией на худший случай. Такие функции формально задают время выполнения алгоритма на равнодоступной адресной машине (РАМ) в зависимости от длины исходных данных (длины входа алгоритма). Полученные в результате анализа асимптотические оценки сложности алгоритма служат верхними оценками сложности решаемой задачи и согласно ГОСТ 28195-89 определяют производительность программы, реализующей этот алгоритм.

Необходимость исследований в области анализа и разработки эффективных (с точки зрения потребляемых ресурсов) алгоритмов обусловлена, прежде всего, тенденциями развития современных информационных технологий и особенностями подлежащих решению вычислительных задач. Задачи, возникающие в системах принятия решений, распознавания образов, компьютерной безопасности, искусственного интеллекта и биоинженерии, при создании и эксплуатации крупномасштабных информационных и телекоммуникационных систем, характеризуются, как правило, большой размерностью и высокой вычислительной сложностью. Сложность вычислений порой настолько высока, что с ней не могут справиться мощности современных компьютеров. Актуальность разработки теоретических основ создания программных систем для решения подобных задач отражена в приоритетных направлениях развития науки, технологий и техники (приказ президента РФ от 7 июля 2011 г. №899).

Широкий класс задач, возникающих в рамках современных информационных технологий, составляют задачи выбора. Отличительная особенность этих задач - поиск решения в конечной области. В них требуется найти одно из допустимых решений (в задачах удовлетворения ограничений) или оптимальное решение (в задачах комбинаторной оптимизации). Для ЫР-трудных задач выбора характерен стремительный рост числа допустимых решений с увеличением размерности задачи, что делает поиск решения полным перебором, алгоритмически неэффективным. Многие задачи выбора могут быть математически сформулированы как задачи на графах и гиперграфах. Именно ЫР-трудные задачи выбора, допускающие графовое и гиперграфовое представление, составляют класс рассматриваемых в диссертации задач.

Теория сложности вычислений сформировала фактический стандарт эффективной вычислимости задачи. Задачу считают эффективно (полиномиально) вычислимой, если существует алгоритм, время выполнения которого ограничено полиномом от длины входа. В то же время имеется большое число NP-трудных задач, для которых пока не получено эффективных алгоритмов. Справедливость гипотезы Р ^ NP означает, что таких алгоритмов вообще не существует. Выполнение этого неравенства предполагается в рамках всей диссертационной работы. В развитие классических основ теории сложности вычислений и анализа алгоритмов значительный вклад внесли А.Н. Колмогоров, A.A. Марков, Н.М. Нагорный, А.И. Мальцев, Г.С. Цейтин, Ю.И. Янов, JI.A. Левин, Ю.Л. Ершов, A.A. Разборов, А.Л. Семенов, В.А. Успенский, Б.А. Трахтенброт, Э.Л. Пост, A.M. Тьюринг, А. Черч, Р. Карп, С. Кук, М. Гэри, Д. Джонсон, Д. Кнут, Р. Тарьян, X. Пападимитриу, К. Стайглиц и многие другие российские и зарубежные ученые.

На сегодняшний день основными подходами к решению NP-трудных задач выбора являются [15, 45, 48, 57, 69, 99, 147]: сужение задачи с целью выделения легких частных случаев, сокращение перебора за счет «разумной» организации стратегии поиска, нахождение приближенных решений с гарантированной ошибкой, применение эвристик и метаэвристик, параметризация задачи. Параметризированный подход - сравнительно новый подход «борьбы» с трудноразрешимостью задач выбора. Основная идея этого подхода состоит в том, чтобы с помощью некоторого числового параметра структурировать и измерить конечное пространство поиска. Роль параметра - выделить основной источник неполиномиальной сложности NP-трудной задачи и показать, «комбинаторный взрыв» какой величины можно ожидать при ее решении на тех или иных исходных данных. Возникающие при этом алгоритмы называются параметризированными. Параметризированный алгоритм - основной объект исследования диссертационной работы.

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

Наибольший интерес представляют параметризации NP-трудных задач, приводящие к алгоритмам, время выполнения которых полиномиально зависит от длины входа и неполиномиальным образом - от значения параметра. Если такой параметр для рассматриваемой задачи существует, то задача называется FPT-разрешимой {Fixed-Parameter Tractable) относительно этого параметра, а соответствующий алгоритм - FPT-алгоритмом. С помощью FPT-алгоритмов можно решать задачи выбора большой размерности при малых фиксированных значениях параметра.

Параметризированный подход к оценке сложности вычислений был сформулирован в конце прошлого столетия Р. Дауни и М. Феллови [143]. Конечно, алгоритмы с функциями сложности от двух и более переменных встречались всегда. Параметризированный подход к сложности вычислений использован еще в теории графовых миноров Н. Робертсона и П. Сеймура [170, 171]. Однако только Р. Дауни и М. Феллови четко определили роль параметра и ввели понятие FPT-разрешимости задачи. Имеется большое число англоязычных научных изданий по параметризированному подходу [102-180]. В российской научной среде этот подход также известен и востребован. Его идеи и воплощения можно найти в публикациях российских ученых, работающих в области дискретной оптимизации и целочисленного программирования: Ю.И. Журавлева, И.В. Сергиенко, В.А. Емеличева, М.М. Ковалева, М.К. Кравцова, В.К. Леонтьева, B.JI. Береснева, Э.Х. Гимати, В.Г. Ви-зинга, С.В. Севастьянова, А.А. Колоколова, И.В. Романовского, Ю.А. Коче-това, И.Х. Сигала, А.В. Пяткина, В.В. Серваха, В.П. Ильева, В.Е. Алексеева, В.А. Бондаренко, О.А. Щербины и многих других.

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

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

1. В многочисленных работах по параметризированному подходу к анализу сложности вычислений традиционно применяются методы классической (одномерной) систематизации [102, 118-130, 136-148, 166]. Между тем классическая одномерность ограничивает глубину анализа параметризиро-ванных алгоритмов с функциями сложности двух и более переменных. Для исследования таких функций сложности нужны специальные инструменты анализа.

2. Для одномерного случая (когда функция сложности алгоритма зависит только от длины входа) также есть нерешенные проблемы. Суть одной из них состоит в отсутствии простых и удобных для практики математических средств распознавания современных сложностных классов алгоритмов. Сегодняшняя алгоритмическая практика уже давно вышла за рамки классической дихотомии (с классами полиномиальных и экспоненциальных алгоритмов) и оперирует пятью сложностными классами алгоритмов. Выделены субполиномиальные (быстрые) алгоритмы из полиномиального класса, субэкспоненциальные и гиперэкспоненциальные алгоритмы из экспоненциального класса. Быстрые и субэкспоненциальные алгоритмы - предмет повышенного интереса теоретических и прикладных исследований в области криптографии и информационной безопасности [10, 85, 95, 97, 98]. Использование непосредственного асимптотического оценивания в этих условиях, как правило, приводит к громоздким вычислениям. Известны попытки введения классификационного признака, позволяющего распознавать современные сложностные классы алгоритмов. Так, В.А. Головешкин и М.В. Ульянов предложили в качестве такого признака употреблять угловую меру асимптотического роста функций сложности [17]. Однако применение этой меры на практике зачастую ограничено трудностями вычислительного характера (она не просто находится для некоторых логарифмически-экспоненциальных функций) и сложностью ее обобщения на функции многих переменных. Другая проблема связана с анализом рекурсивных алгоритмов. В настоящее время основным инструментом анализа рекурсивных алгоритмов является метод рекуррентных соотношений [5, 16, 18, 19, 49, 58]. Идея этого метода состоит в построении и решении рекуррентного соотношения, которому удовлетворяет функция сложности анализируемого алгоритма. Как известно, общих правил решения рекуррентных соотношений пока не найдено. Поэтому всякий математический результат, дающий какой-либо общий подход к решению данной проблемы, интересен как теоретически, так и практически. К подобным результатам относятся методы решения линейных рекуррентных соотношений с постоянными коэффициентами, а также оценки Дж. Бентли, Д. Хакена, Дж. Сакса, полученные ими для времени выполнения рекурсивного алгоритма, организованного по принципу «разделяй и властвуй» [108]. Актуальны подобные оценки и для других широко употребляемых принципов организации рекурсии. Например, для принципа «уменьшай и властвуй», характерного для метода динамического программирования. В этом случае на каждом шаге рекурсии размерность задачи понижается на некоторую константу.

3. Параметризированный подход позволяет исследовать различные параметризации одной и той же задачи, каждая из которых может приводить или не приводить к FPT-алгоритмам. В настоящее время уже известны некоторые специальные методы конструирования FPT-алгоритмов. Наиболее универсальный метод разработки FPT-алгоритмов для задач выбора, пред-ставимых графами и гиперграфами, - метод динамического программирования по дереву декомпозиции, автором которого считается Г. Бодлаендер [124]. Пространство поиска здесь структурируется на основе специальной декомпозиции входного графа или гиперграфа и измеряется через числовой параметр, отражающий ширину этой декомпозиции. При всей теоретической привлекательности данного метода практическое его применение ограничивается двумя серьезными проблемами. Первая проблема связана с высокими потребностями в памяти получаемых FPT-алгоритмов, а вторая - с решением NP-трудной задачи - с вычислением древовидной ширины графа.

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

Достижение заявленной цели предполагает решение следующих задач исследования.

1. Изучение вопросов систематизации алгоритмов по вычислительной сложности и параметризированного подхода к оценке сложности вычислений. Разработка удобных для широкой алгоритмической практики математических инструментов анализа параметризированных алгоритмов.

2. Исследование проблемы анализа рекурсивных процессов и ее решение для класса рекурсивных алгоритмов, организованных по принципу «уменьшай и властвуй».

3. Исследование проблем создания РРТ-алгоритмов и практической применимости метода динамического программирования по дереву декомпозиции. Разработка методов решения этих проблем для МР-трудных задач выбора, представимых графами и гиперграфами.

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

Научная новизна и выносимые на защиту положения. Все результаты диссертации являются новыми. Укажем наиболее существенные.

1. Разработаны математические инструменты анализа вычислительной сложности параметризированных алгоритмов:

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

- метод двумерной классификации параметризированных алгоритмов на основе частных эластичностей.

2. Введены и изучены новые понятия: эластичность алгоритма; неэластичные, эластичные и суперэластичные алгоритмы.

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

4. Разработаны теоретические положения и алгоритмические решения проблем, возникающих при построении РРТ-алгоритмов методом динамического программирования по дереву декомпозиции. В их число входят:

- теоретические и алгоритмические аспекты применения бинарного сепараторного дерева в решении проблемы памяти;

- два рекуррентных и полиномиальных по времени метода вычисления верхних и нижних оценок древовидной ширины графа и гиперграфа.

Личный вклад автора. В список положений выносимых на защиту включены лишь те результаты, которые получены соискателем лично.

Достоверность и обоснованность результатов подтверждаются математическими доказательствами и строгими аргументациями.

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

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

2. Решена проблема анализа класса рекурсивных алгоритмов, организованных по принципу «уменьшай и властвуй».

3. Разработаны и математически обоснованы методы, способствующие развитию и практическому применению специального метода конструирования РРТ-алгоритмов (метода динамического программирования по дереву декомпозиции).

4. Совокупность представленных в диссертации математических методов составляет теоретическую основу параметризированной алгоритмики и позволяет исследовать и создавать РРТ-алгоритмы для решения широкого спектра ЫР-трудных задач выбора, возникающих в рамках новых информационных технологий.

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

1. Методика сравнения алгоритмов по асимптотике поведения эла-стичностей функций сложности.

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

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

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

Публикации. По материалам диссертации автором опубликовано 39 работ, включая монографию [181], 17 статей в ведущих рецензируемых журналах и журналах из перечня ВАК [182-198]), 3 свидетельства о государственной регистрации комплексов программ [220-222].

Структура и объем работы. Диссертация состоит из введения, шести глав, заключения, библиографического списка и трех приложений. Изложение иллюстрируется 41 рисунком и двумя таблицами. Общее число страниц диссертации - 257, в том числе приложения - 25 страниц.

Похожие диссертационные работы по специальности «Теоретические основы информатики», 05.13.17 шифр ВАК

Заключение диссертации по теме «Теоретические основы информатики», Быкова, Валентина Владимировна

Выводы

1. Использование дерева декомпозиции графа и гиперграфа ограниченной древовидной ширины при решении 1МР-трудных задач выбора - один из современных подходов преодоления их вычислительной сложности с помощью РРТ-алгоритмов. Между тем, сама задача вычисления древовидной ширины является ЫР-трудной. Хотя на сегодняшний день известен широкий спектр точных, приближенных и эвристических алгоритмов решения этой задачи, вопрос ее алгоритмического обеспечения нельзя считать закрытым. Необходимость практического решения данной задачи в условиях большой размерности и для произвольного вида графов и гиперграфов требует новых алгоритмов и подходов.

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

3. Первый из этих методов реализует принцип «уменьшай и властвуй» и основан на свойствах хордальных графов и ациклических гиперграфов. Метод позволяет выполнять полиномиальное по времени редуцирование исходного графа или гиперграфа (без потери оптимальности) и получать нижние оценки древовидной ширины. Для хордальных графов и ациклических гиперграфов он определяет схему рекурсивного процесса вычисления древовидной ширины. Доказательства лемм 6.5, 6.6 и утверждения 6.7 служат теоретическим обоснованием этого метода.

4. Второй предложенный метод предобработки действует по принципу «разделяй и властвуй» и основан на свойствах сепараторов. Лемма 6.18 и утверждения 6.9, 6.13, 6.19 - теоретическое обоснование метода. Доказано, что целесообразные сепараторы позволяют разбивать граф и гиперграф на части и вычислять их древовидную ширину через значения этого параметра для частей разложения. Установлено, что целесообразными сепараторами являются минимальные кликовые и почти кликовые сепараторы. Показано, что такие сепараторы всегда можно найти за полиномиальное время. Именно этот факт обеспечивает эффективность всего процесса разложения и получения верхней оценки древовидной ширины рассматриваемого графа и гиперграфа.

5. Результат разложения графа и гиперграфа на части целесообразными сепараторами, вообще говоря, зависит от порядка выбора этих сепараторов, поскольку допустимы разделяющие друг друга сепараторы. Между тем, если разложение выполнять только с помощью кликовых минимальных сепараторов, то результат уникален. Уникальность такого разложения применительно к графам была установлена Г. Лаймером в 1993 г. В настоящей диссертационной работе показано, что уникальность сохраняется и для гиперграфов (утверждение 6.20). Такое обобщение открывает дополнительные вычислительные возможности приложений гиперграфовых моделей систем, поскольку атомарное разложение гиперграфа может быть использовано не только в аспекте древовидной ширины, но в других задачах, базирующихся на отношениях смежности вершин гиперграфа.

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

7. Следует отметить, что в российских изданиях тематика древовидной ширины графов представлена скромно. Имеются работы по исследованию структуры сепараторов в многосвязных графах [40, 41]. Частично введена соответствующая терминология в словарь по теории графов [27]. Изучаются хордальные графы [83]. Имеются работы по успешному применению древовидной ширины графа в решении разреженных задач дискретной оптимизации [101]. В зарубежных научных изданиях проблема вычисления древовидной ширины графа широко освещается и исследуется в многочисленных работах. Наиболее значимые из этих работ приведены в библиографическом списке. Полученные в шестой главе результаты вносят определенный теоретический и алгоритмический вклад в решение проблемы вычисления древовидной ширины. Они позволяют на практике вычислять и оценивать значения древовидной ширины для графов и гиперграфов, возникающих во многих реальных задачах выбора.

ЗАКЛЮЧЕНИЕ

В диссертационной работе на основе проведенных автором исследований получены следующие основные результаты.

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

2. Разработаны математические инструменты анализа параметризиро-ванных алгоритмов: метод двумерной классификации параметризированных алгоритмов по сложности на основе частных эластичностей; методика установления степени воздействия параметра на сложность параметризированно-го алгоритма с помощью коэффициента замещения одного аргумента функции другим; две альтернативные формы представления функции сложности РРТ-алгоритма (утверждение 4.1).

3. Получены верхние и нижние оценки времени выполнения рекурсивных алгоритмов, построенных путем аддитивного уменьшения размера задачи на некоторую константу (теорема 3.3 и следствия 3.4-3.7).

4. Доказано, что проблему высоких потребностей в памяти РРТ-алгоритмов, образующихся при применении метода динамического программирования по дереву декомпозиции, можно решать с помощью бинарного сепараторного дерева декомпозиции (утверждение 5.11).

5. Разработаны и математически обоснованы два рекуррентных и полиномиальных по времени метода вычисления верхних и нижних оценок древовидной ширины графа и гиперграфа (леммы 6.5, 6.6 и утверждение 6.7; лемма 6.18 и утверждения 6.9, 6.13, 6.19).

6. Доказано, что гиперграф уникальным образом разлагается на части минимальными кликовыми сепараторами (утверждение 6.20).

11 Ф

Представленные в диссертации теоретические результаты и практические решения расширяют и углубляют научные основы современных информационных технологий на базе использования средств вычислительной техники. Их применение в алгоритмической практике и программной инженерии будет способствовать созданию эффективных (с точки зрения объема потребляемых вычислительных ресурсов) программных и информационных систем различного назначения.

Список литературы диссертационного исследования доктор физико-математических наук Быкова, Валентина Владимировна, 2012 год

1. Список цитируемой литературы

2. Алексеев О.Г. Комплексное применение методов дискретной оптимизации / О.Г. Алексеев. М.: Наука, 1987. - 248 с.

3. Ахо А. Построение и анализ вычислительных алгоритмов / А. Ахо, Дж. Хопкрофт, Дж. Ульман. М.: Мир, 1979. - 536 с.

4. Ахо А. Структуры данных и алгоритмы / А. Ахо, Дж. Хопкрофт, Дж. Ульман. М.: Изд. дом «Вильяме», 2007. - 400 с.

5. Баранов В.И. Экстремальные комбинаторные задачи и их приложения / В.И. Баранов, Б.С. Стечкин. М.: ФИЗМАТЛИТ, 2004. - 240 с.

6. Баррон Д. Рекурсивные методы в программировании / Д. Баррон. М.: Мир, 1974.-79 с.

7. Батищев Д. И. Многоуровневая декомпозиция гиперграфовых структур / Д.И. Батищев, Н.В. Старостин, A.B. Филимонов // Информационные технологии. Прил. 2008. - № 5. - С. 1-31.

8. Беллман Р. Прикладные задачи динамического программирования / Р. Беллман, Р. Дрейфус. М.: Наука, 1965. - 457 с.1

9. Бондаренко В.А. Геометрические конструкции и сложность в комбинаторной оптимизации / В.А. Бондаренко, А.Н. Максименко. М.: Изд-во ЛКИ, 2008.-184 с.

10. БулосДж. Вычислимость и логика / Дж. Булос, Р. Джеффри. М.: Мир, 1994.-396 с.

11. Василенко О.Н. Теоретико-числовые алгоритмы в криптографии / О.Н. Василенко. М.: МЦНМО, 2006. - 336 с.

12. Власова Е.А. Ряды / Е.А. Власова. М.: Изд-во МГТУ им. Н.Э. Баумана, 2000.-612 с.

13. ВиртН. Алгоритмы и структуры данных / Н. Вирт. СПб.: Невский проспект, 2001. - 352 с.

14. Всемирное М.А. Алгоритмы для пропозициональной выполнимости и верхние оценки их сложности / М.А. Всемирнов, Э.А. Гирш, Е.Я. Дан-цин, C.B. Иванов // Зап. научн. сем. ТОМИ. 2001. - 277. - С. 14-46.

15. Гашков С.Б. Арифметика. Алгоритмы. Сложность вычислений / С.Б. Гашков, В.Н. Чубариков. М.: Высш. шк., 2000. - 320 с.

16. Гладков JI.A. Генетические алгоритмы / Л.А.Гладков, В.В. Курейчик, В.М. Курейчик. М.: ФИЗМАТЛИТ, 2006. - 320 с.

17. Головешкин В.А. Теория рекурсии для программистов / В.А. Головеш-кин, М.В. Ульянов. М.: ФИЗМАТЛИТ, 2006. - 296 с.

18. Головешкин В.А. Метод классификации вычислительных алгоритмов по сложности на основе угловой меры асимптотического роста функций / В.А. Головешкин, М.В. Ульянов // Вычислительные технологии. -2006. Т. 11. - № 1. - С. 52-62.

19. Головешкин В.А. Аналитическое решение специального класса рекуррентных соотношений в целях анализа рекурсивных алгоритмов / В.А. Головешкин, М.В. Ульянов // Вестник СамГУ. Естественнонаучная серия. 2008. - № 3(62). - С. 96-107.

20. Грин Д. Математические методы анализа алгоритмов / Д. Грин, Д. Кнут. М.: Мир, 1987. - 120 с,

21. Грэхем Р. Конкретная математика. Основание информатики / Р. Грэхем, Д. Кнут, О. Паташник. М.: Мир, 2006. - 703 с.

22. Гудман С. Введение .в разработку и анализ алгоритмов / С. Гудман, С. Хидетниеми. М.: Мир, 1981. - 368 с.

23. Гуц А.К. Математическая логика и теория алгоритмов / А.К. Гуц. -Омск: Изд-во Наследие. Диалог-Сибирь, 2003. 108 с.

24. Гэри М. Вычислительные машины и труднорешаемые задачи / М. Гэри, Д. Джонсон. М.: Мир, 1982. - 416 с.

25. Де Брёйн Н.Г. Асимптотические методы в анализе / Н.Г. Де Брёйн. -М.: ИЛ, 1961.-247 с.

26. Джонс М.Т. Программирование искусственного интеллекта в приложениях / М.Т. Джонс. М.: ДМК Пресс, 2004. - 312 с.

27. Доугерти К. Введение в эконометрику / К. Доугерти. М.: ИНФРА-М, 2001.-402 с.

28. Евстигнеев В.А. Словарь по графам в информатике / В.А. Евстегнеев, В.Н. Касьянов. Новосибирск: ООО «Сибир. научн. изд-во», 2000. -300 с.

29. Егорычев Г.П. Интегральные представления и вычисление комбинаторных сумм / Г.П. Егорычев. Новосибирск, Наука, 1977. - 285 с.

30. Емеличев В.А. Многогранники, графы, оптимизация (комбинаторная теория многогранников) / В.А. Емеличев, М.М. Ковалев, М.К. Кравцов. М.: Наука, 1981.-344 с.

31. Ершов А.П. Введение в теоретическое программирование / А.П. Ершов. М.: Наука, 1977. - 288с.

32. Ершов Ю.Л. Определимость и вычислимость / Ю.Л. Ершов. Новосибирск: Научная книга, 1996. - 286 с.

33. Журавлев Ю.И. Избранные научные труды / Ю.И. Журавлев. М.: Магистр, 1998. - 420 с.

34. Задирака В.К. Оптимизация алгоритмов быстрого умножения больших чисел. I / В.К. Задирака, С.С. Мельникова, А.Н. Терещенко // УСиМ. -2006. -№3.- С. 13-21.

35. Задирака В.К. Оптимизация алгоритмов быстрого умножения больших чисел. II / В.К. Задирака, С.С. Мельникова, А.Н. Терещенко // УСиМ. -2006. № 4. - С. 23-32.

36. Зыков A.A. Гиперграфы / A.A. Зыков // УМН. 1974. - Т. 29. - Вып. 6. -С. 89-154.

37. Ильичев А.П. Полиномиальные алгоритмы вычисления перманентов некоторых матриц / А.П. Ильичев, Г.П. Коган, В.Н. Шевченко // Дискретная математика. 1997. - Т. 9. - Вып. 3. - С. 96 -100.

38. Карацуба A.A. Умножение многозначных чисел на автоматах/A.A. Ка-рацуба Ю.П. Офман // ДАН. 1961. - Т. 145. - № 2. - С. 293-294.

39. Карацуба A.A. Сложность вычислений / A.A. Карацуба // Труды Матем. института РАН. 1995. - Т. 211. - С. 186-203.

40. Карп P.M. Сводимость комбинаторных проблем / P.M. Карп // Киб. сборник. Новая серия. М.: Мир, 1975. - С. 16-38.

41. Карпов Д.В.О структуре ^-связного графа / Д.В. Карпов, A.B. Пастор // Зап. научн. семин. ПОМИ. 2000. - Т. 266. - С. 76-106.

42. Карпов Д.В. Разделяющие множества в Ar-связном графе / Д.В. Карпов // Зап. научн. семин. ПОМИ. 2006. -Т. 340. - С. 33-60.

43. Кнут Д. Искусство программирования. Т. 1. Основные алгоритмы / Д. Кнут. М.: Мир, 2000. - 712 с.

44. Кнут Д. Искусство программирования. Т. 2. Получисленные алгоритмы / Д. Кнут. М.: Мир, 2000. - 828 с.

45. Кнут Д. Искусство программирования. Т. 3. Сортировка и поиск / Д. Кнут. М.: Мир, 2007. - 832 с.

46. КоеалевМ.М. Дискретная оптимизация (целочисленное программирование) / М.М. Ковалев. М.: УРСС, 2003. - 192 с.

47. Колмогоров А.Н. Теория информации и теория алгоритмов / А.Н. Колмогоров. М.: Наука, 1987. - 303 с.

48. Колоколов A.A. Исследование одного алгоритма решения задач целочисленного линейного программирования / A.A. Колоколов, Т.Г. Орловская //Тр. ИММ УрО РАН. -2010.-16:3. -С. 140-145

49. Компьютер и задачи выбора / Э.Н. Гордеев, В.К. Леонтьев, П.П. Кольцов. М.: Наука, 1989. - 208 с.

50. Кормен Т. Алгоритмы: построение и анализ / Т. Кормен, Ч. Лейзерсон, Р. Ривест. М.: МЦНМО, 1999. - 960 с.

51. Корн Г. Справочник по математике / Г. Корн, Т. Корн. М.: Наука, 1973. - 832 с.

52. Королев JI.H. Об эволюционных алгоритмах, нейросетевых вычислениях, генетическом программировании математические проблемы / Л.Н. Королев // Автоматика и телемеханика. - 2007. - № 5. - С. 71-83.

53. Кристофидес Н. Теория графов. Алгоритмический подход / Н. Кри-стофидес. М.: Мир, 1978. - 432 с.

54. Левитин A.B. Алгоритмы: введение в разработку и анализ / A.B. Левитин. -М.: Изд. дом «Вильяме», 2006. 576 с.

55. Лежнев A.B. Динамическое программирование в экономических задачах / A.B. Лежнев. -М.: Бином. Лаб. знаний, 2006. 174 с.

56. Лейнартас Е.К. Асимптотика многомерных разностных уравнений / Е.К. Лейнартас, М. Пассаре, А.К. Цих // УМН. 2005. - Т. 60. -№5(365).-С. 171-172.

57. Лекции по теории графов / В.А. Емеличев, О.И. Мельников, В.И. Сарванов, Р.И. Тышкевич М.: Наука, 1990. - 384 с.

58. ЛеонтьевВ.К. Дискретная оптимизация / В.К.Леонтьев // ЖВМ и МФ. 2007. - 47. - С. 338-352.

59. Макконелл Дж. Анализ алгоритмов. Вводный курс / Дж. Макконелл. -М.: Техносфера, 2002. 304 с.

60. Мальцев А.И. Алгоритмы и рекурсивные функции / А.И. Мальцев. М.: Наука, 1986.-367 с.

61. Марков А.А. Теория алгоритмов / А.А. Марков, Н.М. Нагорный. М.: Наука, 1984.-432 с.

62. Мартин-Лёф 77. Очерки по конструктивной математике / П. Мартин-Лёф. М.: Мир, 1975. - 136 с.

63. Марченков С. С. Рекурсивные функции / С.С. Марченков. М.: ФИЗ-МАТЛИТ, 2007. - 62 с.

64. Матиясевич Ю.В. Диофантовы множества / Ю.В. Матиясевич // УМН. 1972. - Т. 27. - № 5. - С. 185-222.

65. Мейер Д. Теория реляционных баз данных / Д. Мейер. М.: Мир, 1987.-608 с.

66. Миллер Р. Последовательные и параллельные алгоритмы: общий подход / Р. Миллер, Л. Боксер. М.: Бином. Лаб. знаний, 2006. - 406 с.

67. Мельников О.И. Реализации гиперграфа деревьями минимального диаметра / О.И. Мельников // Дискретная математика. 1997. — Т. 9. -Вып. 4.-С. 91-97.

68. Ноден 77. Алгебраическая алгоритмика / П. Ноден, К. Китке. М.: Мир, 1999.-720 с.

69. Олвер Ф. Асимптотика и специальные функции / Ф. Олвер. М.: Наука, 1990. - 528 с.

70. Пападимитриу X. Комбинаторная оптимизация. Алгоритмы и сложность / X. Пападимитриу, К. Стайглиц. М.: Мир, 1985. - 510 с.

71. Проблемы Гильберта / Под ред. П.С. Александрова. М.: Мир, 1969. -239 с.

72. Рейнгольд Э. Комбинаторные алгоритмы. Теория и практика / Э. Рейнгольд, Ю. Нивергель?, Н. Део. М.: Мир, 1980. - 478 с.

73. РиорданДж. Комбинаторные тождества / Дж. Риордан. М.: Наука, 1982.-255 с.

74. Саати Т. Целочисленные методы оптимизации и связанные с ними экстремальные проблемы / Т. Саати. М.: Мир, 1973. - 302 с.

75. Сергиенко И.В. Приближенные методы решения задач дискретной оптимизации / И.В. Сергиенко. Киев: Наукова думка, 1980. - 275 с.

76. Сергиенко И.В. Задачи дискретной оптимизации: проблемы, методы решения, исследования / И.В. Сергиенко, В.П. Шило. К.: Наукова думка, 2003. - 264 с.

77. Сигал И.Х. Введение в прикладное дискретное программирование: модели и вычислительные алгоритмы / И.Х. Сигал, А.П. Иванова. М.: ФИЗМАТЛИТ, 2004. - 304 с.

78. Сигал И.Х. Оценки параметров алгоритмов ветвей и границ для задач дискретной оптимизации большой размерности / И.Х. Сигал // Известия РАН. Теория и системы управления. 2005. - № 4. - С. 96-101.

79. Солодовников A.C. Математика в экономике: учебник/ A.C. Солодовников, В.А. Бабайцев, A.B. Браилов, И.Г. Шандра. М.: Финансы и статистика, 2001. - 376 с.

80. Схрейвер А. Теория линейного и целочисленного программирования: в 2-х т. Т. 1 / А. Схрейвер. М.: Мир, 1991. - 360 с.

81. Схрейвер А. Теория линейного и целочисленного программирования: в 2-х т. Т. 2 / А. Схрейвер. М.: Мир, 1991.-342 с.

82. ТраубДж. Общая теория оптимальных алгоритмов / Дж. Трауб, X. Вожьняковский. М.: Мир, 1983. - 382 с.

83. Трахтенброш Б.А. Алгоритмы и вычислительные автоматы / Б.А. Трах-тенброт. М.: Сов. радио, 1974. - 200 с.

84. Турсунбай кызы Ы. Деревья клик хордального графа и деревья подграфов / Турсунбай кызы Ы // Конструирование и оптимизация программ. Новосибирск: Институт систем информатики СО РАН. 2008. -Вып. 16.-С. 314-321.

85. Тыугу ЭХ. Концептуальное программирование / Э.Х. Тыугу. М.: Наука, 1984. - 255 с.

86. Уильяме X. Проверка чисел на простоту с помощью вычислительных машин / X. Уильяме // Киб. сборник. 1986. - Вып. 23. - С. 51-99.

87. Ульянов М.В. Ресурсйо-эффективные компьютерные алгоритмы. Разработка и анализ / М.В. Ульянов. М.: ФИЗМАТЛИТ, 2008. - 304 с.

88. Успенский В.А. Теория алгоритмов: основные открытия и приложения / В.А. Успенский, А.Л. Семенов. М.: Наука, 1987. - 288 с.

89. Фалевич Б.Я. Теория алгоритмов / Б.Я. Фалевич. М.: Машиностроение, 2004.-160 с.

90. Финкелыитейн Ю.Ю. Приближенные методы и прикладные задачи дискретного программирования / Ю.Ю. Финкелыитейн. М.: Наука, 1976.-264 с.

91. Фомичев В.М. О сложности метода формального кодирования при анализе генератора с полноцикловой функцией переходов / В.М. Фомичев // Прикладная дискретная математика. 2009. - № 3(12). - С. 21-28.

92. ХардиГ.Х. Курс чистой математики / Г.Х. Харди. М.: ИЛ, 1949. -512 с.

93. Хачиян Л.Г. Полиномиальный алгоритм в линейном программировании / Л.Г. Хачиян //Докл. АН СССР. 1979. - Т. 244. - № 5. - С.1093-1096.

94. Хачиян Л.Г. Полиномиальные алгоритмы в линейном программировании / Л.Г. Хачиян // ЖВМ и МФ. -1980. Т. 20. - № 1. - С. 51-69.

95. Хачиян Л.Г. Сложность задач линейного программирования / Л.Г. Хачиян. М.: Знание, 1987. - 32 с.

96. Хооли К. Применение методов решета в теории чисел / К. Хооли. М.: Наука, 1987.-134 с.

97. Хопкрофт Дж. Введение в теорию автоматов, языков и вычислений / Дж. Хопкрофт, Р. Мотовани, Дж. Ульман. М.: Изд. дом «Вильяме», 2002. - 528 с.

98. Черемушкин A.B. Лекции по арифметическим алгоритмам в криптографии / A.B. Черемушкин. М.: МЦНМО, 2002. - 104 с.

99. Чмора А.Л. Современная прикладная криптография / А.Л. Чмора. М.: Гелиос АРВ, 2001. - 256 с.

100. Штовба СД. Муравьиные алгоритмы: теория и применение / С.Д. Штовба // Программирование. 2005. - № 4. - С. 3-18.

101. Шенхаге А. Быстрое умножение больших чисел / А. Шенхаге,

102. B. Штрассен // Киб. сборник. Новая серия. Вып. 10. М.: Мир, 1973.1. C. 87-98.

103. Щербина О.А. Локальные элиминационные алгоритмы решения разреженных дискретных задач / О.А. Щербина // ЖВМ и МФ. 2008. -Т. 48.-№ 1.-С. 159-175.

104. AlberJ. Fixed parameter algorithms for Dominating Set and related problems on planar graphs / J. Alber, H.L. Bodlaender, H. Fernau, T. Kloks, R. Niedermeier // Algorithmica. 2002. - 33(4). - P. 461-493.

105. AlberJ. Improved tree decomposition based algorithms for domination-like problems / J. Alber, R. Niedermeier // Proc. 5th LATIN 2002, SpringerVerlag LNCS 2286, 2002. P. 613-627.

106. Amir E. Efficient approximations for triangulation of minimum treewidth / E. Amir // Proc. of the 17Th Conference on Uncertainty in Artificial Intelligence, 2001.-P. 7-15.

107. ArnborgS. An algebraic theory of graph reduction / S. Arnborg, B. Courcelle, A. Proskurowski, D. Seese // J. ACM. 1993. - 40(5). - P. 11341164.

108. ArnborgS. Complexity of finding embeddings in a £-tree / S. Arnborg,

109. D.G. Corneil, A. Proskurowski // SIAM J. Alg. Disc. Meth. 1987. - 8. -P. 277-284.

110. Aspvall В. Memory requirements for table computations in partial k-tree algorithms / B. Aspvall, A. Proskurowski, J.A. Telle // Algorithmica. -2000. 27(3). - P. 382-394.

111. Bentley J.L. A general method for solving divide-and-conquer recurrences / J.L. Bentley, D. Haken, J.B. Saxe // SIGACT News. 1980. - № 12(3). -P. 36-44.

112. Berry A. A wide range algorithm for minimal triangulation from an arbitrary ordering / A. Berry, J.P. Bordât, P. Heggernes, G. Simonet, Y. Villanger // J. Algorithms. 2006. - 58(1). - P. 33-66.

113. Berry A. Maximum cardinality search for computing minimal triangulations of graphs / A. Berry, J.R.S. Blair, P. Heggernes, B.W. Peyton // Algorithmi-ca. 2004. - 39. - P. 287-298.

114. Berry A. A vertex incremental approach for dynamically maintaining chordal graphs / A. Berry, P. Heggernes, Y. Villanger // Algorithms and Computation (ISAAC'2003). Springer Verlag, 2003. P. 47-57.

115. Berry A. The minimum degree heuristic and the minimal triangulation process / A. Berry, P. Heggernes, G. Simonet // Proc. of the 29th Workshop on Graph Theoretic Concepts in Computer Science, 2003. P. 58-70.

116. Berry A. Generating all the minimal separators of a graph / A. Berry, J.P. Bordât, O. Cogis // International Journal of Foundations of Computer Science.- 2000. 11. - P. 397-^04.

117. Berry A. A wide-range efficient algorithm for minimal triangulation /

118. A. Berry // Proc. of the Tenth Annual ACM-SIAM (SODA'99), 1999. -P. 860-861.

119. BetzlerN. Tree decompositions of graphs: Saving memory in dynamic programming / N. Betzler, R. Niedermeier, J. Uhlmann // Electronic Notes in Discrete Mathematics. 2004. - 17. - P. 57-62.

120. Blair J.R.S. An introduction to chordal graphs and clique trees / J.R.S. Blair,

121. B. Peyton // Graph theory and sparse matrix computation. New York, Springer, 1993.-P. 1-29.

122. Bodlaender H.L. On exact algorithms for treewidth / H.L. Bodlaender, A. Grigoriev, A.M.C.A. Koster // Proc. 14Th Annual European Symposium on Algorithms ESA, 2006, V. 4168.- P. 672-683.vk i if

123. Bodlaender H.L. Discovering treewidth / H.L. Bodlaender // Proc. of the 31st Conference SOFSEM 2005, Springer-Verlag LNCS 3381, 2005.1. P. 1-16.

124. Bodlaender H.L. Tree decompositions with small cost / H.L. Bodlaender, F.V. Fomin // Discrete Applied Mathematics. 2005. - 145(2).1. P. 143-154.

125. Bodlaender H.L. Computing the treewidth and the minimum fill-in with the modular decomposition / H.L. Bodlaender, U. Rotics // Algorithmica. -2003. -V. 36. P. 375—408.

126. Bodlaender H.L. Parallel algorithms for series parallel graphs and graphs with treewidth two / H.L. Bodlaender, B. Fluiter // Algorithmica. 2001. -V. 29. - P. 543-559.

127. Bodlaender H.L. Some classes of graphs with bounded treewidth / H.L. Bodlaender // Technical Report RUU-CS-76-22, Dept. Computer Science, Univ. Utrecht, 1998.

128. Bodlaender H.L. A partial k-arboretum of graphs with bounded treewidth / H.L. Bodlaender // Theoretical Computer Science. 1998. - V. 209.1. P. 1-45.

129. Bodlaender H.L. Treewidth: Algorithmic techniques and results / H.L. Bodlaender // Proc. 22nd MFCS, Springer-Verlag LNCS 1295, 1997.1. P. 19-36.

130. Bodlaender H.L. Treewidth for graphs with small chordality / H.L. Bodlaender, D.M Thilikos // Disc. Appl. Math. 1997. - V. 79. - P. 45-61.

131. Bodlaender H.L. Efficient and constructive algorithms for the pathwidth and treewidth of graphs / H.L. Bodlaender, T. Kloks // J. Algorithms. 1996. -21.-P. 358-402.

132. Bodlaender H.L. Parameterized complexity analysis in computational biology / H. Bodlaender, R. Downey, M. Fellows, M. Hallett, H. Wareham // Computer Applications in the Biosciences. 1995.- V. 11. - P. 49-57.

133. Bodlaender H. L. A linear-time algorithm for finding tree decompositions of small treewidth / H.L. Bodlaender // SIAM J. Comput. 1995.- 25(6). -P. 1305-1317.

134. Bodlaender H.L. A tourist guide through treewidth / H.L. Bodlaender // Acta Cybernetica. 1993. - 11. - P. 1-21.

135. Borie R. Automatic generation of linear-time algorithms from predicate calculus descriptions of problems on recursively constructed graph families / R.B. Borie, R.G. Parker, C.A. Tovey // Algorithmica. 1992. - 7. -P. 555-581.

136. Bouchitte V. On treewidth approximations / V. Bouchitte, D. Kratsch, H. Muller, I. Todinca // Disc. Appl. Math. 2004. - V. 6. - P. 183-196.

137. Broersma H. A generalization of AT-free graphs and a generic algorithm for solving triangulation problems / H. Broersma, T. Kloks, D. Kratsch, H. Muller // Algorithmica. 2002. - V. 32. - P. 594-610.

138. Broersma H. A linear time algorithm for minimum fill-in and tree width for distance hereditary graphs / H. Broersma, E. Dahlhaus, T. Kloks // Disc. Appl. Math. 2000. - V. 99. - P. 367^100.

139. CaiL. On the existence of sub-exponential time parameterized algorithms / L. Cai, D. Juedes // Journal of Computer and System Sciences. 2003. -V. 67. - P. 789-807.

140. CesatiM. Compendium of parameterized problems / M. Cesati . 2006. Доступ: http://bravo.ce.uniroma2.it/home/cesati/research/compendium/ (дата обращения: 20.05.2012).

141. Clautiaux F. Heuristic and meta-heuristic methods for computing graph treewidth / F. Clautiaux, A. Moukrim, S. Negre, J. Carlier // RAIRO Oper. Res. 2004. - V. 38. - P. 13-26.

142. Courcelle B. The monadic second-order logic of graphs. XVI. Canonical graph decompositions / B. Courcelle // Logical Methods in Computer Science. 2006. - V. 2. - (2:2). - P. 1-46.

143. Courcelle В. The monadic second-order logic of graphs. III. Tree decompositions, minors and complexity issues / B. Courcelle // RAIRO Inform. Theor. Appl. 1992. - 26(3). - P. 257-286.

144. Courcelle В. The Monadic Second-Order Logic of Graphs. I. Recognizable Sets of Finite Graphs / B. Courcelle // Information and Computation. -1990.-85.-P. 12-75.

145. Dahlhaus E. Minimal elimination ordering inside a given chordal graph / E. Dahlhaus // Graph Theoretical Concepts in Computer Science-WG'97. Springer Verlag, 1997.-P. 132-143.

146. Dirac G.A. On rigid circuit graphs / G.A. Dirac // Abh. Math. Sem. Univ. Hamburg. 1961. - 25.- P. 71-76.

147. Downey R. Parameterized complexity / R.Downey, M. Fellows. New York, Springer-Verlag, 1999.

148. Eppstein D. Diameter and treewidth in minor-closed families / D. Eppstein // Algorithmica. 2000. - V. 27. - P. 275-291.•n 111

149. Fellows M. Fixed-parameter complexity and cryptography / M. Fellows, N. Koblitz // Technical Report DCS-207-IR. Department of Comput. Science, University of Victoria, 1992.

150. FernauH. Parameterized algorithms. A graph-theoretic approach: Habilitationsschrift / H. Fernau. Germany: Universität Tubingen, 2005.

151. FlumJ. Parameterized complexity theory / J. Flum., M. Grohe. Berlin, Heidelberg: Springer-Verlag, 2006.

152. FlumJ. Parameterized complexity and subexponential time / J. Flum, M. Grohe // Bull. Eur. Assoc. Theoiy Computer Sciences EATCS. 2004. -V. 84.-P. 71-100.

153. Fomin F. V. Exact (exponential) algorithms for treewidth and minimum fill-in / F.V. Fomin, D. Kratsch, I. Todinca // Automata, Languages and Programming (ICALP). Springer Verlag LNCS 3142, 2004. P. 568-580.

154. Fulkerson D.R. Incidence matrices and interval graphs / D.R. Fulkerson, O.A. Gross // Pacific Journal of Math. 1965. - 15. - P. 835-855.

155. Guo J. Improved algorithms and complexity results for power domination in graphs / J. Guo, R. Niedermeier, D. Raible // Proc. 15th FCT, SpringerVerlag LNCS 3623, 2005. P. 172-184.

156. Guo J. A structural view on parameter zing problems: distance from triviality / J. Guo, F. Hüffner, R. Niedermeier // Proc. of International Workshop on Parameterized and Exact Computation IWPEC, Springer LNCS 3162, 2004.-P. 162-173.

157. GogateV. A complete anytime algorithm for treewidth / V. Gogate, R. Dechter I I Proc. 20Th Conference on Uncertainty in Artificial Intelligence. Arlington, Virginia, USA: AUAI Press, 2004. P. 201-208.

158. Gottlob G. Fixed-parameter complexity in AI and Nonmonotonic reasoning / G. Gottlob, F. Scarcello, M. Sideri // Artificial Intelligence. 2002. -V. 138.-P. 55-86.

159. GroheM. The parameterized complexity of database queries / M. Grohe // Proceedings of the 20th ACM Symposium on Principles of Database Systems, 2001.-P. 82-92.

160. Heggernes P. Computing minimal triangulations in time 0(nalogn) = o(n 376) / P. Heggernes, J.A. Telle, Y. Villanger // SIAM Journal on Discrete Math. 2005. - 19(4). - P. 900-913.

161. Hirsch E.A. New worst-case upper bounds for SAT / E.A. Hirsch // Journal of Automated Reasoning. 2000. - 24(4). - P. 397-420.

162. Impagliazzo R. Complexity of k-SAT / R. Impagliazzo, R. Paturi // J. of Computer and System Sciences. 2001. - 62. - P. 367-375.

163. Kloks T. Treewidth. Computations and Approximations / T. Kloks. Springer-Verlag LNCS 842, 1994.

164. Kloks T. Computing treewidth and minimum fill-in: All you need are the minimal separators / T. Kloks, H.L. Bodlaender, H. Muller, D. Kratsch // Algorithms-ESA, Springer-Verlag, 1993. P. 260-271.

165. Köster A.M. C.A. Solving partial constraint satisfaction problems with tree decompositions / A.M.C.A. Koster, S.P.M. van Hoesel, A.W.J. Kolen // Networks. 2002. - 40(3). - P. 170-180.

166. Kulimann O. New methods for 3-SAT decision and worst case analysis / O. Kullmann // Theoretical Computer Science. 1999. - 223. - P. 1-72.

167. Leimer H.G. Optimal decomposition by clique separators / H.G. Leimer // Discrete Mathematics. 1993. - 113. - P. 99-123.

168. Manouvrier J.F. Resolving the network reliability problem with a tree decomposition of the graph / J.F. Manouvrier, C. Lucet // Proc. 1st OPODIS, Hermes, 1997. P. 193-204.

169. Niedermeier R. A general method to speed up fixed-parameter-tractable algorithms / R. Niedermeier, P. Rossmanith // Information Proc. Letters. -2000.-V. 73.-P. 125-129.

170. Niedermeier R. Invitation to fixed-parameter algorithms: Oxford Lecture series in mathematics and its applications. V. 31 / R. Niedermeier. Oxford University Press, 2006.

171. Papadimitriou C. On the complexity of database queries / C. Papadimitriou, M. Yannakakis I I Journal of Computer and System Sciences. 1999. -V. 58.-P. 407-427.

172. ParraA. Characterizations and algorithmic applications of chordal graph embeddings / A. Parra, P. Scheffle // Disc. Appl. Math. 1997. - V. 79. -P. 171-188.

173. Parter S. The use of linear graphs in Gauss elimination / S. Parter. I I SI AM Review. 1961.-3.-P. 119-130.

174. Robertson N. Graph minors. XX. Wagner's conjecture / N.Robertson, P.D. Seymour // J. Comb. Theory. Ser. B. 2004. - № 92(2). - P. 325-357.

175. Robertson N. Graph minors. II. Algorithmic aspects of treewidth / N. Robertson, P.D. Seymour // J. Algorithms.- 1986. V. 7. - P. 309-322.

176. RoseD. Algorithmic aspects of vertex elimination on graphs / D.Rose, R.E. Tarjan, G. Lueker // SIAM J. Comput. 1976. - V. 5. - P. 146-160.

177. Rose D.J. On simple characterizations of £-trees / D.J. Rose // Discrete Math. 1974. - 7. - P. 317-322.

178. Rose D.J. Triangulated graphs and the elimination process / D.J. Rose // J. Math. Anal. Appl. 1970. - 32. - P. 597-609.

179. Tarjan R.E. Decomposition by clique separators / R.E. Tarjan // Discrete Mathematics. 1985. - 55. - P. 221-232.

180. Tarjan R.E. Simple linear-time algorithms to test chordality of graphs, test acyclicity of hypergraphs, and selectively reduce acyclic hypergraphs / R.E. Tarjan, M. Yannakakis. // SIAM J. Comput. 1984. - 13. - P. 566-579.

181. Yannakakis M. Computing the minimum fill-in is NP-complete / M. Yannakakis // SIAM J. Alg. Disc. Meth. 1981. - 2. - P. 77-79.

182. Woeginger G.J. Exact algorithms for NP-hard problems: A survey / G.J. Woeginger // Combinatorial Optimization-Eureka, You Shrink! 5th International Workshop, Springer-Verlag LNCS 2570, 2001. P. 185-208.

183. Wolle T. A framework for network reliability problems on graphs of bounded treewidth / T. Wolle // Proc. 13th ISAAC 2002, Springer-Verlag LNCS 2518, 2002. P. 137-149.

184. Публикации автора по теме диссертации

185. Быкова В.В. Теоретические основы анализа параметризированных алгоритмов: монография / В.В. Быкова. Красноярск: СФУ, 2011. - 180 с.

186. Быкова В.В. FPT-алгоритмы на графах ограниченной древовидной ширины // Прикладная дискретная математика. 2012. - № 2(16). -С. 65-78.

187. Быкова В.В. О разложении гиперграфа кликовыми минимальными сепараторами /В.В. Быкова // Журнал СФУ. Математика и физика. -2012.-№ 1(5). -С. 36-45.

188. Быкова В.В. Анализ воздействия параметра на вычислительную сложность параметризированного алгоритма /В.В. Быкова // Омский научный вестник. Приборы, машины и технологии. 2012. - № 1(107). -С. 283-287.

189. Быкова В.В. Рекуррентные методы вычисления древовидной ширины гиперграфа /В.В. Быкова // Известия Томского политехнического университета. Управление, вычислительная техника и информатика. -2011.-Т. 318.-№5.-С. 5-10.

190. Быкова В.В. Программирование задач на графах ограниченной древовидной ширины / В.В. Быкова // Программные продукты и системы. -2011.-№4(96).-С. 101-106.

191. Bykova V.V. Analysis parameterized algorithms on the bases of elasticity to functions complexity / V.V. Bykova // Journal of Siberian Federal University. Mathematics & Physics. 2011. - № 4(2). - P. 195-207.

192. Быкова В.В. Вычислительные аспекты древовидной ширины графа /

193. B.В. Быкова // Прикладная дискретная математика. 2011. - № 3(13).1. C. 65-79.> I

194. Быкова В.В. РРТ-алгоритмы и их классификация на основе эластичности / В.В.Быкова // Прикладная дискретная математика. 2011. -№2(12). -С. 40-48.

195. Быкова В.В. Алгоритм построения дерева декомпозиции гиперграфа на основе ацикличности /В.В. Быкова // Программные продукты и системы. 2011. - № 1(93). - С. 64-69.

196. Быкова В.В. Сложность и эластичность вычислений / В.В.Быкова // Омский научный вестник. Приборы, машины и технологии. 2011. -№ 1(97).-С. 10-14.

197. Быкова В.В. Асимптотические свойства решений специального типа рекуррентных соотношений / В.В. Быкова // Омский научный вестник. Приборы, машины и технологии. 2011. - № 1(97). - С. 153-157.

198. Быкова В.В. М-ациклические и древовидные гиперграфы / В.В. Быкова // Известия Томского политехнического университета. Математика и механика. Физика. 2010. - Том 317. - № 2. - С. 25-30.

199. Быкова В.В. Эластичность алгоритмов / В.В.Быкова // Прикладная дискретная математика. 2010. - № 2(8). - С. 87-95.

200. Быкова В.В. Метод распознавания классов алгоритмов на основе асимптотики эластичности функций сложности /В.В. Быкова // Журнал СФУ. Математика и физика. 2009. - № 2(1). - С. 48-62.

201. Быкова В.В. Полиномиальные достаточные условия реализуемости гиперграфа на плоскости /В.В. Быкова // Известия Томского политехнического университета. Математика и механика. Физика. 2009. -Т. 314.-№2.-С. 15-20.

202. Быкова В.В. Математические методы анализа рекурсивных алгоритмов / В.В. Быкова // Журнал СФУ. Математика и физика. 2008. - № 1(3). -С. 236-246.

203. Быкова В.В. Полиномиальные достаточные условия бихроматичности гиперграфа / В.В. Быкова // Вестник КрасГУ. Серия физ.-мат. науки. -2006. -№7-С. 98-106.

204. Bykova V.V. Parameterized complexity and elasticity of the algorithms / V.V. Bykova // The 14th Applied Stochastic Models and Data Analysis International Conference (ASMDA2011), 6-10 June 2011, Rome, Italy, 2011.-P. 219-225.

205. Быкова В.В. Графоаналитический метод анализа сложности алгоритмов / В.В. Быкова // Материалы VI Всесибирского конгресса женщин-математиков (в день рождения С.В. Ковалевской), 15-17 января 2010 г. Красноярск: РИЦ СибГТУ, 2010. - С. 43-47.

206. Bykova V.V. Asymptotic properties of solutions of a special type of recurrence relations / V.V. Bykova // The Third International Conference «Problems of cybernetics and informatics» (Pci'2010), 6-8 September 2010, Baku, Azerbaijan, 2010. P. 341-344.

207. Быкова В.В. Математические методы анализа рекурсивных алгоритмов / В.В. Быкова // Материалы V Всесибирского конгресса женщин-математиков (в день рождения С.В. Ковалевской), 15-18 января 2008 г., Красноярск. Красноярск: РИО СФУ, 2008. - С. 75-78.

208. Быкова В.В. Сравнительный анализ М-ациклических и комплектных гиперграфов / В.В. Быкова, Т.В. Куприянова // Проблемы оптимизации и экономические приложения: Тезисы доклада Международной конференции. Омск: Омский гос. ун-т, 1997. - С. 31.

209. Быкова В.В. Комплекс программ TreeDec для нахождения дерева декомпозиции и вычисления верхней оценки древовидной ширины графа / В.В. Быкова, H.A. Никульская // Навигатор в мире науки и образования. 2011- № 1(9). - С. 21-25.

210. Доступ: http://ofernio.ru/portal/daidiest.php (дата обращения: 20.05.2012).

211. Свидетельства о регистрации программных комплексов

Обратите внимание, представленные выше научные тексты размещены для ознакомления и получены посредством распознавания оригинальных текстов диссертаций (OCR). В связи с чем, в них могут содержаться ошибки, связанные с несовершенством алгоритмов распознавания. В PDF файлах диссертаций и авторефератов, которые мы доставляем, подобных ошибок нет.