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

На правах рукописи

Быкова Валентина Владимировна

МЕТОДЫ АНАЛИЗА И РАЗРАБОТКИ ПАРАМЕТРИЗИРОВАННЫХ АЛГОРИТМОВ

05.13.17 — теоретические основы информатики

АВТОРЕФЕРАТ диссертации на соискание ученой степени доктора физико-математических наук

- -8 КОЯ 2012

Красноярск - 2012

005054614

005054614

Работа выполнена на базовой кафедре вычислительных и информационных технологий ФГАОУ ВПО «Сибирский федеральный университет»

Научный консультант:

доктор технических наук, профессор Потапов Виктор Ильич

Официальные оппоненты:

доктор физико-математических наук, профессор Колоколов Александр Александрович, Омский филиал ФГБУН Института математики им. С.Л. Соболева СО РАН, лаборатория дискретной оптимизации, заведующий лабораторией

доктор технических наук, профессор Агибалов Геннадий Петрович, ФГБОУ ВПО «Национальный исследовательский Томский государственный университет», кафедра защиты информации и криптографии, заведующий кафедрой

доктор физико-математических наук, профессор Сафонов Константин Владимирович, ФГБОУ ВПО «Сибирский государственный аэрокосмический университет им. академика М.Ф. Решетнева», кафедра прикладной математики, заведующий кафедрой

Ведущая организация:

ФГБОУ ВПО «Национальный исследовательский Томский политехнический университет»

Защита состоится 2 ноября 2012 г. в 14 часов на заседании диссертационного совета Д 212.099.11 при Сибирском федеральном университете по адресу: г. Красноярск, ул. Киренского, 26, ауд. УЛК 115.

С диссертацией можно ознакомиться в библиотеке Сибирского федерального университета.

Автореферат разослан « — ^^ 2012 года. Ученый секретарь

диссертационного совета

Покидышева Людмила Ивановна

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

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

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

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

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

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

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

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

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

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

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

1Flum J., Grohe М. Parameterized complexity theory. - Berlin, Heidelberg: Springer-Verlag, 2006.

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

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

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

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

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

2. Для одномерного случая (когда функция сложности алгоритма зависит только от длины входа) также есть нерешенные проблемы. Суть одной из них состоит в отсутствии простых и удобных для практики математических средств распознавания современных сложностных классов алгоритмов. Сегодняшняя алгоритмическая практика уже давно вышла за рамки классической дихотомии (с классами полиномиальных и экспоненциальных алгоритмов) и оперирует пятью сложностными классами алгоритмов. Выделены субполиномиальные (быстрые) алгоритмы из полиномиального класса, субэкспоненциальные и гиперэкспоненциальные алгоритмы из экспоненциального класса. Использование непосредственного асимптотического оценивания в этих условиях, как правило, приводит к громоздким вычислениям. Известны попытки введения классификационного признака, позволяющего распознавать современные сложностные классы алгоритмов. Так, В.А. Головешкин и М.В. Ульянов предложили в качестве такого признака употреблять угловую меру асимптотического роста функций сложности4. Однако применение этой меры на практике зачастую ограничено трудностями вычислительного характера (она не просто находится для некоторых логарифмически-экспоненциальных функций) и сложностью ее обобщения на функции многих переменных. Другая

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

проблема связана с анализом рекурсивных алгоритмов. В настоящее время основным инструментом анализа рекурсивных алгоритмов является метод рекуррентных соотношений. Идея этого метода состоит в построении и решении рекуррентного соотношения, которому удовлетворяет функция сложности анализируемого алгоритма. Как известно, общих правил решения рекуррентных соотношений пока не найдено. Поэтому всякий математический результат, дающий какой-либо общий подход к решению данной проблемы, интересен как теоретически, так и практически. К подобным результатам относятся методы решения линейных рекуррентных соотношений с постоянными коэффициентами, а также оценки Дж. Бентли, Д. Хакена, Дж. Сакса, полученные для времени выполнения рекурсивного алгоритма, организованного по принципу «разделяй и властвуй»5. Актуальны подобные оценки и для других широко употребляемых принципов организации рекурсии. Например, для принципа «уменьшай и властвуй», характерного для метода динамического программирования. В этом случае на каждом шаге рекурсии размерность задачи понижается на некоторую константу.

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

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

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

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

Задачи исследования:

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Использование результатов диссертации. Результаты диссертационной работы переданы и используются: в Институте вычислительного моделирования СО РАН (г. Красноярск) при выполнении проекта «Разработка интеллектуальных вычислительных комплексов для поддержки принятия решений при конструировании и эксплуатации сложных технических систем и объектов» в рамках Программы Президиума РАН, а также темы «Разработка и исследование методов компьютерного моделирования и обработки данных для информационно-управляющих систем поддержки принятия решений по повышению уровня пожарной безопасности зданий» в рамках междисциплинарного интеграционного проекта СО РАН; в филиале ОАО «РЖД» (г. Красноярск) для управления терминально-складской и транспортно-экспедиционной логистикой грузоперевозок; в ОАО «РУСАЛ-Ачинск» для разработки программ и мероприятий, направленных на совершенствование управления производством и повышение информационной безопасности компьютерных систем предприятия. Результаты диссертации применяются в учебном процессе Института математики Сибирского федерального университета (г. Красноярск) для подготовки бакалавров и магистров направления «Математика. Компьютерные науки», а также Института информатики и телекоммуникаций Сибирского государственного аэрокосмического университета им. академика М.Ф. Решетнева (г. Красноярск) для под-

готовки бакалавров направления «Прикладная математика» и магистров направления «Теоретическая информатика». Имеются акты об использовании.

Апробация работы. Основные результаты исследования докладывались и обсуждались на следующих конференциях и семинарах международного, всероссийского и региональных уровней: Всероссийских конференциях «Проблемы оптимизации и экономические приложения» (Омск, Россия, 1997, 2012); VI-VII Всероссийских конференциях по финансово-актуарной математике и смежным вопросам (Красноярск, Россия, 2007, 2008); V-VI Всесибир-ских конгрессах женщин-математиков (Красноярск, Россия, 2008, 2010); 9-11 Сибирских научных школах-семинарах с международным участием «Компьютерная безопасность и криптография» (Тюмень, Россия, 2010; Томск, Россия, 2011; Иркутск, Россия, 2012); XIV Международной конференции по эвентологической математике и смежным вопросам (Красноярск, Россия, 2010); XII Всероссийской научно-практической конференции «Проблемы информатизации региона» (Красноярск, Россия, 2011); IX-X Международных конференциях по финансово-актуарной математике и эвентоконвер-генции технологий (Красноярск, Россия, 2010, 2011); The Third International Conference «Problems of cybernetics and informatics» (Baku, Azerbaijan, 2010); The Third IASTED International Multi-Conference on Automation, Control, and Information Technology, ACIT-CDA2010 (Novosibirsk, Russia, 2010); The Conference devoted to 20 anniversary of independence of the Republic Uzbekistan «Modern Mathematics Problems» (Karshi, Uzbekistan, 2011); The 14th Applied Stochastic Models and Data Analysis International Conference, ASMDA2011 (Rome, Italy, 2011).

Публикации. По материалам диссертации автором опубликовано 39 работ, включая монографию [1], 35 печатных работ в журналах и сборниках (из них 17 статей в ведущих рецензируемых журналах и журналах из перечня ВАК [2-18]), 3 свидетельства о государственной регистрации комплексов программ [37-39].

Личный вклад автора. Результаты диссертации получены соискателем самостоятельно. В соавторстве выполнены работы [23, 27, 28, 30, 32, 37-39], в которых вклады авторов равнозначны.

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

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

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

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

В диссертации под словом «задача» подразумевается массовая задача П. Там, где речь идет об индивидуальной задаче I, применяются словосочетания «экземпляр I задачи П», «I — вход алгоритма, решающего задачу П» и т.п. Следуя классическим традициям и позициям параметризированной теории сложности вычислений, функция вычислительной сложности алгоритма поставлена в центр внимания исследования: вначале в главах 2 и 3 как функция ¿(п) одной переменной п, а затем в главах 4-6 как функция ¿(п, к) двух аргументов пик. Эта функция представляет время выполнения алгоритма (в худшем случае применительно к РАМ) в зависимости от длины входа п—\1\ и значения числового параметра к (если он учитывается). Сравнение алгоритмов осуществляется по порядку роста их функций сложности. При этом используются традиционные асимптотические обозначения:

— ¿1 (п) -< £2(п), или ¿1 (п) = о^г(тг)]. Функция ^(п) меньше функции ¿2(п) по порядку роста;

— ¿2(п) =<! £х(п), или tl(n) = П[4г(га)]. Функция ¿1 (гг) не меньше функции ¿2 (п) по порядку роста;

— <х(гг) ^(гс), или ¿1 (п) = О^г(п)]. Функция ¿1 (п) не больше функции £2(п) по порядку роста;

— ¿х(тг) х ¿2(п), или ¿1 (гг) = в [¿г (га)]. Функция Ь\(п) равна функции £2(п) по порядку роста.

На функции сложности накладываются отдельные ограничения. Во-первых, полагается, что областью значений этих функций выступает множество неотрицательных действительных чисел Е+, а областью определения — множество целых положительных чисел (или 2+ X К), где N — множество натуральных чисел. Во-вторых, при необходимости дискретные пик формально заменяются непрерывными х и у, а. нужные значения вычисляются в целочисленных точках х = п и у = к. В этом случае вместо Ь(п) или t(n, к) используется запись г(х) или г(х,у) соответственно. В-третьих, предполагается, что функции сложности принадлежат семейству £ — рекурсивно

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

Функция г(х) считается «по существу положительной», если существует х0 такое, что г(х) > 0 для всех х > х0. Известно, что каждая функция из £ (далее просто ¿-функция) непрерывна и дифференцируема в той области, где она определена. Кроме того, если ^(х), г2(х) е С, то при х -> со либо 21(1) -< г2(х), либо г2(х) г^х), либо гх(х) ж г2(х)7. Поэтому любые две С-функции асимптотически сравнимы между собой по порядку роста, а значит, сравнимы между собой по сложности соответствующие им алгоритмы.

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

Вторая глава состоит из восьми параграфов и посвящена классификации алгоритмов по вычислительной сложности. Установление класса сложности алгоритма — один из этапов анализа алгоритма. В данной главе предложен новый метод систематизации алгоритмов, базирующийся на асимптотике поведения эластичности функций сложности. Теоретическое обоснование метода — теорема 2.10. Здесь анализ ограничивается одномерным случаем (когда функция сложности г(х) зависит только от непрерывного аргумента х — длины входа алгоритма).

В параграфе 2.1 исследована классическая систематизация алгоритмов. Отмечено, что данная систематизация — это дихотомия, которая выделяет низкозатратные (полиномиальные) и высокозатратные (экспоненциальные) алгоритмы. Причем эти классы определены с точностью до полиномиальных преобразований длины входов алгоритмов и традиционно устанавливаются путем непосредственного асимптотического оценивания порядка роста функций сложности алгоритмов. Классическая систематизация алгоритмов лежит в основе классификации задач по сложности. Соответственно выделены классы полиномиально разрешимых и трудноразрешимых задач, а для задач разрешения определены классы Р, № и класс полных задач. В современной алгоритмической практике используют пять сложностных классов алгоритмов (с субполиномиальным, полиномиальным, субэкспоненциальным, экспоненциальным и гиперэкспоненциальным порядком роста функций сложности). В диссертации доказано, что все эти пять классов математически точно и достаточно просто устанавливаются исходя из такой дифференциальной характеристики функций сложности алгоритмов, как эластичность.

В параграфах 2.2 и 2.3 исследуются свойства эластичности ¿-функций. Под эластичностью Ех(г) функции г = г(х) принято понимать предел отношения относительного приращения этой функции к относительному прира-

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

щению аргумента:

„ , . /Az Ах\ х Az х , . ,

EJz) = lim — :- = - lim — = -z' = x{\az)'. (1)

; Дх-+0 \ z x ) z Дх-Ю Ах z

Согласно (1) эластичности присущи свойства, сходные со свойствами операций логарифмирования и дифференцирования, поэтому она легко определяется для всякой £-функции. Кроме того, при малых Да; справедливо приближение

z x

которое задает подходящую для анализа алгоритмов интерпретацию эластичности: Ex(z) — коэффициент пропорциональности между темпами роста величин z их. Справедливо

"Утверждение 2.1. Для любой С-функции z = z(x) всегда существует эластичность, и Ex(z) > 0, Ex(z) = o{z/ lnx). Асимптотическое поведение эластичности С-функции z = z(x) при х оо инвариантно относительно полиномиального преобразования, заключающегося в умножении этой функции на константу с > 0 и возведении в положительную и отделенную от нуля степень т> О, то есть Ex(czm) = 0[.Ex(z)].

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

1) CONST = {z{x) I z(x) = в(1)} — асимптотические константы;

2) SUBPOLY = {z(x) I 1 z(x) -< ee(bl)} — функции субполиномиального порядка роста;

3) POLY = {z(x) I z(x) x ee(lnl'} — функции полиномиального порядка роста;

4) SUBEXP = {z(x) I ee(Ini) z(x) -< ee(l)} — функции субэкспоненциального порядка роста;

5) EXP = {z(x) I z(x) ж eeM} — функции экспоненциального порядка роста;

6) HYPEREXP = {z(x) I eeW -< z(x)} — функции гиперэкспоненциального порядка роста.

В параграфе 2.5 доказана теорема 2.10 о классификации ^-функций на основе эластичностей. Доказательство базируется на утверждении 2.1 и леммах 2.4—2.9, справедливость которых математически обоснована в диссертации.

Согласно этим леммам разным (по порядку роста) классам £-функций свойственно принципиально различное поведение эластичности и, наоборот, по асимптотике поведения эластичности можно определить класс, к которому относится эта функция. При этом данное соответствие однозначно, если объединить CONST, SUBPOLY в один класс SUBPOLY.

Теорема 2.10. Разбиение семейства монотонно неубывающих, шо существу положительных» С-функций на классы SUBPOLY, POLY, SUBEXP, EXP, HYPEREXP в соответствии с порядком их роста эквивалентно надлежащему разбиению по асимптотике эластичности этих функций на бесконечности:

SUBPOLY - [z(x) I z(x) -< ee(lni)} = {z{x) \ Ex(z) = o(l)}; (2)

POLY = {z(x) I z(x) e®} = {z(x) I ад x 1}; (3)

SUBEXP = {z(x) I ee(ln*> z(x) ~< e9«} = {z(x) | 1 -< Ex{z) -< x}; (4) EXP = [z{x) I z{x) x в9«} = {z(x) I Ex(z) x x} ; (5)

HYPEREXP = [z{x) I e®W -< z(i)} ее {z{x) | x < Ex{z)}. (6)

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

Из теоремы 2.10 и свойств эластичности вытекают важные следствия.

Следствие 2.11. Разбиение С-функций на указанные в теореме 2.10 классы инвариантно относительно следующего полиномиального преобразования: если и(х) 6 POLY и z(x) S К, К е { SUBPOLY, POLY, SUBEXP, EXP, HYPEREXP}, mo u(z(x)) e K.

Следствие 2.12. Класс SUBPOLY замкнут относительно суперпозиции (композиции) С-функций: если z(x), и(х) е SUBPOLY, то u(z(x)) £ SUBPOLY.

Следствие 2.13. Класс POLY замкнут относительно суперпозиции С - функций: если z(x),u(x) е POLY, то u(z(x)) £ POLY.

Следствие 2.14. Класс HYPEREXP замкнут относительно суперпозиции С-функций: если z(x),u(x) е HYPEREXP, то u(z(x)) € HYPEREXP.

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

Если г{х) — время выполнения алгоритма при длине входа х, то Ех(г) — эластичность этого алгоритма. Эластичность алгоритма — это коэффициент пропорциональности между темпом роста времени выполнения алгоритма и темпом роста его длины входа. С учетом этой интерпретации полученные в теореме 2.10 эквивалентности (2)-(6) порождают пять соответствующих сложностных классов, которые полностью отвечают современной детальной классификации алгоритмов. Класс субполиномиальных (быстрых) алгоритмов образуют алгоритмы, которым свойственна тождественно нулевая или бесконечно малая эластичность. Класс полиномиальных алгоритмов — это множество алгоритмов, для которых эластичность есть асимптотически постоянная величина. Класс субэкспоненциальных алгоритмов — алгоритмы, для которых эластичность есть бесконечно большая величина с порядком роста ниже линейной функции. Класс экспоненциальных алгоритмов состоит из алгоритмов, для которых эластичность — бесконечно большая величина, асимптотически равная (по порядку роста) линейной функции. Класс гиперэкспоненциальных алгоритмов образуют алгоритмы, для которых эластичность есть бесконечно большая величина с порядком роста выше линейной функции.

В параграфе 2.8 предложено более крупное разбиение алгоритмов на классы: выделены и определены неэластичные, эластичные, суперэластичные алгоритмы — алгоритмы с бесконечно малой, асимптотически постоянной и бесконечно большой эластичностью соответственно. Неэластичные и эластичные алгоритмы практически значимые, так как эффективные. Суперэластичные алгоритмы очень чутко реагируют на изменение длины входа и с этой точки зрения хорошо управляемые по сложности через эту величину.

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

Третья глава диссертации состоит из четырех параграфов и посвящена анализу сложности рекурсивных алгоритмов. В этой главе установлены и теоретически обоснованы верхние и нижние оценки времени выполнения рекурсивного алгоритма, построенного на основе принципа «уменьшай и властвуй», то есть путем аддитивного уменьшения размера задачи на некоторую константу (теорема 3.3). Здесь анализируются функции сложности 1(п) от

одного дискретного аргумента п — длины входа алгоритма.

В параграфе 3.1 раскрыты проблемы анализа рекурсивных алгоритмов. В параграфе 3.2 представлены рекуррентные соотношения, которые характерны для прямой рекурсии, организованной по принципам «разделяй и властвуй» и «уменьшай и властвуй». Указаны наиболее распространенные случаи, когда эти соотношения могут быть решены: постоянное число подзадач, создаваемых на каждом шаге рекурсии, и полиномиальная трудоемкость рекурсивного перехода.

В параграфе 3.3 исследованы оценки Дж. Бентли, Д. Хакена, Дж. Сакса, полученные ими для времени выполнения рекурсивного алгоритма, организованного по принципу «разделяй и властвуй». Этот широко известный результат уже давно применяется при анализе и разработке эффективных алгоритмов. Согласно нему рекурсивная реализация принципа «разделяй и властвуй» всегда приводит к быстрым и полиномиальным алгоритмам.

В параграфе 3.4 сформулирована и доказана теорема 3.3. Данная теорема позволяет находить верхние и нижние асимптотические оценки времени выполнения рекурсивного алгоритма, построенного путем аддитивного уменьшения размера задачи на некоторую константу к Є N. Такие алгоритмы, например, порождает рекурсивная реализация метода динамического программирования.

Теорема 3.3. Пусть дано рекуррентное соотношение

!с, если 0 < п < к — 1,

(7)

at(n — к) + ЬпТ, если тг> к,

где а > 0, к > 1 — целые константы, b > О, с > 0, т > 0 — вещественные константы. Тогда при п = km, т Є Z+ ипчоо верны оценки

i(n) = П(п), t(n) = О (nT+1) , а = 1, Ь > 0; (8)

t{n) = Vt{an'k), t{n) = О (птап, а > 1, b > 0; (9)

i(n) = Є(1), а =1,6 = 0; (10)

t(n) = Є (а"'*) , а > 1, Ь = 0. (11)

В рекуррентном соотношении (7) константа а трактуется как число подзадач, порождаемых рекурсивной ветвью алгоритма, а степенная функция Ьпт определяет трудоемкость рекурсивного перехода. Оценки (10) и (11) отвечают случаю «бесплатного» рекурсивного перехода. В работе установлены

другие частные случаи, когда из (8), (9) вытекают ©-оценки. Они отражены в следствиях 3.4-3.7.

Следствие 3.4. В предположениях теоремы 3.3 при т = 0 решением рекуррентного соотношения (7) является функция

Ъ

с + —п, если а = 1,

к

t(n) =

ап/к _ ^

ап/кс + b-, если а > 1.

а — 1

Следствие 3.5. При т = 0, любых значениях b > О, с > 0 и п —» оо для решения рекуррентного соотношения (7) верны оценки

{Э(п), если а = 1, b > О, в (ап/А) , если а > 1, Ъ > 0.

Следствие 3.6. Для решения рекуррентного соотношения (7) при а = 1, с > 0, Ъ > 0, целых положительных т и п —> оо справедлива оценка

t{n) = 9 (nT+1) .

Следствие 3.7. Для решения рекуррентного соотношения (7) при а > 1, с > 0, 6 > 0 и целых положительных т верна оценка

t{n) = 0 (Va"^) .

Из оценок теоремы 3.3 и следствий 3.4-3.7 вытекают важные для практики положения: рекурсивные алгоритмы, образованные аддитивным уменьшением размера задачи на некоторую константу, могут быть быстрыми, полиномиальными и экспоненциальными. Быстрый алгоритм возможен только в тривиальной ситуации (при одной подзадаче и нулевых затратах на рекурсивный переход). Полиномиальные алгоритмы возникают лишь в случае, когда исходная задача сводится к одной подзадаче меньшего размера. При числе подзадач а > 1 рекурсивный алгоритм, построенный путем аддитивного уменьшения размера задачи на некоторую константу, всегда экспоненциальный по времени и никакие усовершенствования процедуры разбиения и объединения подзадач не способны изменить класс его сложности. Причина этого кроется в возникновении на каждом шаге рекурсии перекрывающихся подзадач. Данные положения служат математическим обоснованием тому факту, что метод динамического программирования для большинства задач

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

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

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

В параграфе 4.1 кратко обсуждаются традиционные классы сложности задач, концепция NP-полноты и современные подходы к решению трудноразрешимых задач. В параграфах 4.2 и 4.3 диссертации исследуется параметри-зированный подход к оценке сложности вычислений, вводится необходимый понятийный аппарат.

Параметризованная задача П (в распознавательной формулировке) — язык, определяемый как 1,(П) С Е* х N, где Е — некоторый конечный алфавит, Е* — множество всех слов в данном алфавите, N — множество натуральных чисел. Каждая пара значений (I, к) е £(П) выступает в качестве экземпляра параметризированной задачи П и входа алгоритма, решающего данную задачу. При этом величина п = \1\ задает длину входа алгоритма, к — значение параметра. Если параметризированная задача П может быть решена некоторым алгоритмом за время, не более чем

"0(1) • т, (12)

то ее называют FPT-разрешимой относительно параметра к, а соответствующий алгоритм — FPT-алгоритмом8. Примечательно, что в (12) функция f(k) зависит только от к. Соотношение (12) определяет верхнюю асимптотическую оценку времени выполнения FPT-алгоритма и свидетельствует о том, что при каждом фиксированном к данный алгоритм полиномиальный относительно п. В этом смысле i(n, к) = О (п°М ■ /(к)).

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

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

мально дискретные ть и к заменяются на непрерывные х и у соответственно, и вместо t(n,k) используется запись z(x,y).

Частная эластичность Ex(z) функции г = z(x,y) по аргументу х — эластичность переменной z, которая рассматривается как функция только от х и при постоянных значениях у. Аналогичным образом определяется частная эластичность Ey(z) функции z = z(x, у) по аргументу у.

Если функция z(x, у) отражает время работы параметризированного алгоритма при длине входа х и значении параметра у, то Ex(z) — коэффициент пропорциональности между темпом роста времени выполнения этого алгоритма и темпом роста длины входа (при постоянном значении параметра). Аналогично Ey(z) — коэффициент пропорциональности между темпом роста времени выполнения параметризированного алгоритма и темпом роста параметра у (при постоянной длине входа).

В общем случае частные эластичности Ex(z), Ey(z) являются функциями, зависящими от х и у. Однако ситуация значительно упрощается, если время работы параметризированного алгоритма описывается ¿-функцией, имеющей мультипликативную форму записи: z(x,y) = q(x) ■ f(y), где q(x) £ ¿ — количественная компонента, a f(y) £ ¿ — параметрическая компонента функции z{x,y). Так, условие FPT-разрешимости (12) традиционно определяется именно через мультипликативную форму записи функции сложности параметризированного алгоритма.

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

Рассмотрим функцию z(x, у) = д(х) • f(y) £ ¿. Согласно свойствам эла-стичностей величины Ex(z) и Ey(z) вырождаются в обычные эластичности функции одного аргумента:

Ex{z) = Ex[q(x) ■ f(y)} = Ex[q{x)] + Ex[f(y)] = Ex[q(x)], (13)

Ey(z) = Ey[q(x) ■ f(y)] = Ey[q(x)] + Ey\f(y)] = Ey[f(y)}. (14) Теперь Ex{z) зависит лишь от x, a Ey(z) зависит только от у. По теореме 2.10 каждая из функций q(x), f(y) принадлежит только одному сложностному классу (по надлежащему аргументу) из множества

К. = {SUBPOLY, POLY, SUBEXP, EXP, HYPEREXP}.

Пусть Кх — класс сложности функции д(х) по аргументу х, и Ку — класс сложности функции f(y) по аргументу у. Пусть эти классы определены исходя из теоремы 2.10 и соответствующих частных эластичностей (13)-(14). Тогда всякому параметризированному алгоритму с функцией сложности z(x,y) = q(x) ■ f(y) £ ¿ отвечает пара (КХ,КУ) € К х К. Эта пара

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

При двумерном подходе отчетливую формулировку получает определение FPT -алгоритма. Параметризированный алгоритм является FPT-алгоритмом, если время его работы задается функцией z(x, у) = д(х) ■ f(y), для которой

(КХ,КУ) е {SUBPOLY, POLY} х К.

В параграфе 4.4 диссертации FPT-алгоритмы систематизированы по сложности относительно параметра у. Алгоритмы, вычислительная сложность которых соответствует парам

(КХ,КУ) е {SUBPOLY, POLY} х {SUBPOLY, POLY} ,

(КХ,КУ) е {SUBPOLY, POLY} х {SUBEXP} ,

(КХ,КУ) е {SUBPOLY,POLY} x {EXP},

(Kx,Ky) G {SUBPOLY, POLY} x {HYPEREXP} ,

определены как полиномиальные, субэкспоненциальные, экспоненциальные и гиперэкспоненциальные FPT-алгоритмы соответственно. Субэкспоненциальные, экспоненциальные и гиперэкспоненциальные FPT-алгоритмы присущи NP-трудным задачам. Они суперэластичные по параметру (при постоянной длине входа).

Анализ параметризированных алгоритмов предполагает не только определение класса сложности алгоритма, но и установление степени влияния параметра на время выполнения алгоритма. В параграфе 4.5 диссертации разработана методика, позволяющая проводить такие исследования. Она основана на коэффициенте замещения одного аргумента функции другим аргументом. Этот коэффициент определяется и интерпретируется следующим образом. Пусть z(x, у) S £. Тогда величина

dx xEJz)

= = м О»)

есть коэффициент замещения одного аргумента функции другим, при условии, что значения функции постоянные (отвечают некоторой линии уровня). Формулу (15) можно записать так:

Соотношение (16) дает следующее толкование коэффициенту замещения: при некотором постоянном значении 2 (реально осуществимой нормы времени исполнения алгоритма) уменьшение значения параметра у на Ду = 1 позволяет увеличить х — длину входа алгоритма — примерно на М, то есть регулировать вычислительные возможности алгоритма на входах большой длины.

Для определения РРТ-алгоритма традиционно применяется мультипликативная форма представления функции сложности алгоритма. В параграфе 4.6 диссертации предложены аддитивная и смешанная формы представления, доказана их эквивалентность мультипликативной форме в смысле РРТ. Этот результат отражает

"Утверждение 4.1. Пусть задана задана П, параметризированная относительно параметра у. Следующие высказывания эквивалентны.

1) Для задачи П существует ¥РТ-алгоритм со временем работы С%(х) • /(у)], где q(x) — функция полиномиального или субполиномиального порядка роста от длины входа х.

2) Для задачи П существует РРТ-алгоритм со временем работы 0[и(х) + го(у)], где и(х) — функция полиномиального или субполиномиального порядка роста от длины входа х.

3) Для задачи П существует РРТ-алгоритм со временем работы О[(?:(х) • /1 (у) + <й(ж) • /г(у)]> гдед^х), 52(2) — функции полиномиального или субполиномиального порядка роста от длины входа х.

Утверждение 4.1 расширяет область применимости разработанных в главе 4 математических средств анализа параметризированных алгоритмов.

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

В параграфе 5.1 дан краткий обзор основных методов разработки РРТ-алгоритмов. Отмечено, что в настоящее время уже предложены и апробированы несколько специальных методов конструирования РРТ-алгоритмов, наиболее универсальный из них — метод динамического программирования по дереву декомпозиции. Этот метод ориентирован на параметризированные

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

В параграфе 5.2 приводятся определения и известные свойства дерева декомпозиции и древовидной ширины графа9. Пусть G = (V,E) — связный неориентированный граф, |V| > 1 и |£| > 1. Дерево декомпозиции графа G = {V,E) представляет собой пару (MG,TG), задающую разбиение множества вершин и множества ребер графа G, где MG = [X{\i е IG} — семейство подмножеств множества V, называемых «мешками», аТс = (IG) W) — дерево, узлам которого сопоставлены эти «мешки». Вершины дерева TG принято называть узлами, чтобы избежать путаницы с вершинами графа G. Семейство MG и множество W ребер дерева TG такие, что справедливы условия:

1) объединение множеств вершин, образующих «мешки» Xit г € IG, дает множество V;

2) для всякого ребра графа G обязательно имеется хотя бы один «мешок», содержащий обе вершины этого ребра;

3) для любой вершины v графа G множество узлов {г € IG | v € Xi}, «мешки» которых содержат эту вершину, индуцирует связный подграф, являющийся поддеревом дерева TG.

Ширина дерева декомпозиции (MG,TG) равна наибольшей вместимости его «мешка», уменьшенной на единицу:

шах{|Х;|-1}.

гб 1а

Древовидная ширина (treewidth) графа G определяется как наименьшая ширина всех допустимых его деревьев декомпозиции и обозначается через tw(G). Дерево декомпозиции (MG,TG) ширины tw(G) называется оптимальным, а без кратных и вложенных «мешков» — фундаментальным. Для tw(G) верны естественные границы: 1 < tw(G) < ¡i/| - 1. Пусть к — некоторая заданная целая положительная константа, и к < Если tw(G) < к, то говорят, что граф G обладает ограниченной (значением к) древовидной шириной.

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

Утверждение 5.6. Всякое дерево декомпозиции (МН,ТН) связного гиперграфа Н есть дерево декомпозиции графа lP\H) и наоборот, любое дерево декомпозиции графа Ь(2)(Я) задает дерево декомпозиции гиперграфа Н.

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

Кроме того, древовидная ширина гиперграфа Н равна древовидной ширине графа L^{H).

Таким образом, с точки зрения древовидной ширины граф L(2'(ff), отражающий отношение смежности вершин гиперграфа Н, полностью определяет этот гиперграф. Поэтому гиперграфовое описание задач выбора, хотя и не вносит ничего существенного в метод динамического программирования по дереву декомпозиции в сравнении с представлением таких задач графами, зато позволяет привлекать для его реализации свойства ациклических гиперграфов. Ограниченная древовидная ширина исходного графа и гиперграфа — это условие применимости данного метода. Чем меньше древовидная ширина, тем меньше вычислительных ресурсов нужно FPT-алгоритму, реализующему динамическое программирование по дереву декомпозиции.

В параграфе 5.3 дано описание метода динамического программирования по дереву декомпозиции. Указаны рекурсивные правила выделения подзадач. В параграфе 5.4 исследованы достаточные условия FPT-разрешимости задач выбора относительно древовидной ширины, устанавливаемые теоремой Курселя10. Согласно теореме Курселя, данный метод приводит к FPT-алгоритму со временем работы 0(\V\-f(k)), если решаемая задача может быть сформулирована в виде конечной формулы монадической логики второго порядка и входной граф G = (V, Е) имеет tw(G) < к.

Динамическое программирование по дереву декомпозиции по своей сути — рекурсивный метод. Число подзадач, возникающих на каждом шаге рекурсии, определяется арностью дерева, которая в общем случае больше единицы. По теореме 3.3 рекурсивная реализация метода неминуемо приводит к неполиномиальному времени вычислений относительно длины входа. Для получения FPT-алгоритма требуется этот метод реализовывать с помощью табличной техники. Однако данная техника порождает проблему памяти для размещения создаваемых таблиц динамического программирования: сколько узлов содержит дерево декомпозиции, столько таблиц возникает; размер всякой таблицы экспоненциально зависит от арности и ширины применяемого дерева декомпозиции. В частности, если в методе динамического программирования исходить из бинарного дерева декомпозиции графа G = (У, Е) ширины к и с 0(|У|) узлами, то общая потребность соответствующего алгоритма в памяти и времени составит 0{\V\ ■ к - q3k), где q — число состояний, в которых может находиться вершина графа к допустимому решению. Таким образом, проблема памяти — серьезное препятствие применимости этого метода на практике.

Для решения проблемы памяти применяют различные преобразования де-

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

рева декомпозиции11. Наиболее известное в этом отношении — Kbks-дерево12. Данное дерево дает возможность удерживать размер всякой таблицы динамического программирования в пределах оценки 0(к ■ qk). Между тем это достигается за счет увеличения числа таблиц примерно в к раз. В параграфе 5.5 предложено бинарное сепараторное дерево декомпозиции (В&Э-дерево), которое обеспечивает компромисс между размером и числом таблиц динамического программирования.

В диссертации В&Б-дерево определено следующим образом. Корневое дерево декомпозиции (Ma,TG), MG = {Xt \ г в IG}, TG = (IG,W), связного графа G = (V, Е) называется В&Б-деревом, если в нем каждый узел имеет не более двух прямых потомков и относится к одному из четырех типов узлов:

1) узел-лист — узел, у которого нет потомков;

2) узел-сепаратор — узел s с одним прямым потомком j и узлом г в роли родителя. Всегда Xs — сепаратор (разделяющее множество вершин) графа GnXs=XinXj^ 0, С Хи Xs С Xj-

3) узел-расширение — узел i с одним прямым потомком s. В данном случае Xs С Xi\

4) узел-соединение — узел г с двумя прямыми потомками I и j Здесь Xi U Xj С X,-.

В параграфе 5.5 доказано

Утверждение 5.11. Всякое фундаментальное дерево декомпозиции (MG,TG) графа G = (V, Е), где MG = {Х{ \ i 6 IG}, TG = (IG, W), имеющее ширину k и 0(\V\) узлов, может быть преобразовано за время 0(|V|) в B&iS-depeeo, которое обладает той же шириной и 0(|У|) узлами.

Показаны и теоретически обоснованы следующие достоинства B&S-дерева. Переход от бинарного корневого дерева декомпозиции к B&S-дереву увеличивает число таблиц не более чем в два раза (за счет добавления узлов-сепараторов). B&S-дерево удерживает размер всякой таблицы динамического программирования в тех же пределах, что и Kloks-дерево. Для вычисления таблиц динамического программирования по BfeS-дереву возможно привлечение аппарата реляционной алгебры и свойств ациклических баз данных. Это способствует алгоритмической конкретизации метода и сокращению числа строк в промежуточных таблицах (за счет применения монотонного плана соединения и программы полусоединений таблиц).

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

12Kloks T. TVeewidth. Computations and Approximations. - Springer-Verlag LNCS 842, 1994.

В параграфе 5.6 показано применение метода динамического программирования по В&Б-дереву при решении оптимизационных задач (на примере задачи о вершинном покрытии) и задач удовлетворения ограничений (на примере задачи SAT, Satisfiability). Для задач удовлетворения ограничений употреблено гиперграфовое описание.

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

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

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

В параграфе 6.1 представлен краткий обзор популярных на сегодняшний день методов вычисления древовидной ширины графа. В параграфе 6.2 приведены известные нижние границы значений древовидной ширины графа G = (V,E), связывающие tw(G) с другими числовыми параметрами этого графа. Отмечено, что наиболее существенные из этих оценок трудновычис-ляемые и потому актуальны различные способы предобработки, снижающие размерность задачи вычисления древовидной ширины. В параграфе 6.3 разработан и теоретически обоснован рекуррентный метод, позволяющий редуцировать входной граф и гиперграф и вычислять нижние оценки его древовидной ширины. Метод реализует принцип «уменьшай и властвуй» и опирается на свойства хордальных графов и ациклических гиперграфов. Обоснованием метода служат доказанные в диссертации следующие положения.

Лемма 6.5. Если v е V — симплициалъная вершина графа G = (V,E) степени deg(v), то

tw(G) = max{de5(t>), tw(G - «)}. (17)

Лемма 6.6. Всякая висячая вершина гиперграфа Н = (X, U) — симплициалъная вершина графа lS2\H).

Утверждение 6.7. Пусть х € X является висячей вершиной гиперграфа Н = (X,U) степени d (для нее в обозначениях теории гиперграфов13: х е Х(и), U{x) = {и} и d = |X(u)| - 1). Пусть гиперграф Н' = Hß(X - х) получен из Н слабым удалением вершины х с последующей минимизацией (удалением кратных и вложенных ребер). Тогда

tw{H) = max{d, tw(H')}. (18)

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

В параграфах 6.4-6.6 изложен и теоретически обоснован рекуррентный метод верхнего оценивания древовидной ширины. Этот метод основан на свойствах сепараторов. Он воплощает принцип «разделяй и властвуй» (разбивая исходный граф или гиперграф на части) и потому всегда имеет полиномиальную относительно числа вершин рекурсивную реализацию при условии, что применяемые сепараторы полиномиально вычисляемые. Изложим суть данного метода применительно к графам.

Говорят, что множество вершин S С V разделяет несмежные вершины о и Ь связного графа G = (V,E), если в графе G(V \ S) вершины а и Ъ принадлежат различным компонентам связности. Множество S при этом называется (а, 6)-сепаратором и минимальным (а, Ь)-сепаратором, если S есть (а, 6)-сепаратор, и в нем нет собственного подмножества, являющегося (а, Ь)-сепаратором. Сепаратор S называется минимальным, если в графе G существует такая пара вершин о и Ъ, что S — минимальный (а, 6)-сепаратор.

Пусть A(G) — множество сепараторов связного графа G = (V, Е) и S е А(G). Обозначим через Уь У2, ..., YT области связности графа G(V\S).

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

Части Gi, G2, GT графа G, выделенные в результате его разделения сепаратором S, определим следующим образом:

Gi = G(Yi U S) U K(S),

где К (S) — полный граф на множестве вершин S, г Є Is = {1,2,..., г}. В частности, если S — точка сочленения графа G, то G\, G2, ■ • •, GT — блоки этого графа. Сепаратор S графа G назовем целесообразным относительно tw(G), если справедливо равенство

tw{G) = max{iw(G;) | і Є Is}- (19)

Данное равенство определяет рекуррентное соотношение для вычисления древовидной ширины графа через его части, полученные разделением G сепаратором S. В параграфе 6.4 доказаны утверждения 6.9, 6.13, согласно которым кликовые сепараторы и минимальные почти кликовые сепараторы гарантируют справедливость (19). Кликовый сепаратор — сепаратор графа G, образующий в G клику. Сепаратор S графа G считается почти кликовым, если существует вершина и Є S такая, что множество S \ {и} — клика графа G.

В параграфе 6.5 исследуются минимальные кликовые и минимальные почти кликовые сепараторы. Показано, что такие сепараторы всегда можно извлечь за полиномиальное время из минимальной триангуляции графа. Напомним, что триангуляцией графа G = (V, Е) называется хордальный граф G' = (V,E'), который содержит граф G в качестве остовного подграфа (Е С Е'). Триангуляция G' минимальная, если для G не существует другой триангуляции, которая образует собственный подграф графа G'. Известно, что всякий минимальный сепаратор S минимальной триангуляции G' = {V, Е') — минимальный сепаратор исходного графа G = (V, Е), Е Ç Е', а для вычисления минимальной триангуляции G' = (V, Е') достаточно 0(|У|3) времени14.

В параграфе 6.5 также дано описание рекурсивного алгоритма разложения заданного графа на части минимальными кликовыми и минимальными почти кликовыми сепараторами и вычисления верхней оценки древовидной ширины этого графа с использованием формулы (19). Верхние оценки для частей графа вычисляются на основе неравенств tw(Gi) < tw(G'i), где G- — соответствующие минимальные триангуляции. В параграфе 6.6 предложенный метод обобщен на гиперграфы (лемма 6.18, утверждение 6.19). Указаны правила формирования частей разложения.

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

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

Пусть Я = (X, U) — связный гиперграф без кратных и вложенных ребер и Y С X — это максимальное по включению подмножество вершин такое, что гиперграф H(Y) связен и не содержит минимальных кликовых сепараторов. Гиперграф H(Y) назовем атомом гиперграфа Я. Заметим, что H(Y) — часть гиперграфа Я = (X, U), индуцированная множеством Y С X. Пусть Д(Я) — множество минимальных кликовых сепараторов, Ф (Я) — множество частей гиперграфа Я, полученных рекурсивным разложением этого гиперграфа сепараторами из Д(Я), при этом каждая часть — некоторый гиперграф H(Yt) с областью связности Yi(i е /я).

Утверждение 6.20. Разложение Ф(Я) = {H(Yi) | i & 1н} определяет уникальное для заданного гиперграфа Я множество атомов.

Эта уникальность означает следующее. Результат разложения не зависит от порядка выбора минимальных кликовых сепараторов. Каждый из гиперграфов H(Yi) е Ф(Я) — атом гиперграфа Я, и никакой из атомов этого гиперграфа не утерян при разложении. Состав атомов, образующих Ф(Я), не зависит от минимальных триангуляций, используемых для нахождения минимальных кликовых сепараторов.

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

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

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

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

ОСНОВНЫЕ РЕЗУЛЬТАТЫ

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).

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

ПУБЛИКАЦИИ АВТОРА ПО ТЕМЕ ДИССЕРТАЦИИ

Монография

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

Статьи в журналах, рекомендованных ВАК РФ

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

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

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

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

- № 5. - С. 5-10.

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

- С. 101-106.

7. Быкова В.В. Вычислительные аспекты древовидной ширины графа // Прикладная дискретная математика. - 2011. - № 3(13). - С. 65-79.

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

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

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

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

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

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

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

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

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

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

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

Материалы конференций, статьи в сборниках

19. Быкова В.В. FPT-алгоритмы и их классификация на основе эластичности // Материалы 10 Сибирской научной школы-семинара «Компьютерная безопасность и криптография» (SIBECRYPT'll), 5-10 сентября 2011 г., Томск. - Прикладная дискретная математика. - 2011. - Приложение № 4. - С. 58-60.

20. Быкова B.B. Вычислительные аспекты древовидной ширины графа // Материалы 10 Сибирской научной школы-семинара «Компьютерная безопасность и криптография» (SIBECRYPT'll), 5-10 сентября 2011 г., Томск. - Прикладная дискретная математика. - 2011. - Приложение № 4 - С. 85-87.

21. Быкова В.В. Комбинаторно-геометрическое моделирование задач выбора // Материалы XII Всероссийской научно-практической конференции «Проблемы информатизации региона» (ПИР-2011), 22-23 ноября 2011 г., Красноярск. - Красноярск: СФУ, 2011. - С. 47-51.

22. Быкова В.В. Подходы и проблемы нахождения точных решений NP - трудных задач: обзор // Труды Десятой Международной конференции по финансово-актуарной математике и эвентоконвергенции технологий (ФАМЭБ 2011), 23-24 апреля 2011 г., Красноярск. - Красноярск: НИИППБ, СФУ, КГТЭИ, 2011. - С. 65-73.

23. Быкова В.В., Никульская H.A. Сравнительный анализ эвристик построения триангуляции графа для древовидной ширины // Труды Десятой Международной конференции по финансово-актуарной математике и эвентоконвергенции технологий (ФАМЭБ 2011), 23-24 апреля 2011 г., Красноярск. - Красноярск: НИИППБ, СФУ, КГТЭИ, 2011. - С. 79-82.

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

25. Быкова В.В. Комбинаторно-геометрический анализ задачи динамического программирования // Труды IX Международной конференции по финансово-актуарной математике и эвентоконвергенции технологий (ФАМЭТ 2010), 23-25 апреля 2010 г., Красноярск. - Красноярск: КГТЭИ, СФУ, 2010. - С. 83-88.

26. Быкова В.В. Эластичность алгоритмов // Материалы 9 Сибирской научной школы-семинара «Компьютерная безопасность и криптография» (SIBECRYPT'10), 6-11 сентября 2010 г., Тюмень. - Прикладная дискретная математика. - 2010. - Приложение № 3. - С. 76-78.

27. Быкова В.В., Никульская H.A. Алгоритмические аспекты минимальных триангуляций графа // Труды XIV Международной конференции по эвентологической математике и смежным вопросам (ЭМ'2010), 18-19 декабря 2010 г., Красноярск. - Красноярск: КГТЭИ, СФУ, 2010. - С. 26-32.

28. Быкова В.В., Трубникова К.С. Алгоритмы построения оптимального дерева декомпозиции ациклического гиперграфа // Труды XIV Международной конференции по эвентологической математике и смежным вопросам (ЭМ'2010), 18-19 декабря 2010 г., Красноярск. - Красноярск: КГТЭИ, СФУ, 2010. - С. 33-40.

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

30. Быкова В.В., Портнягина Т.П. Исследование угловой меры асимптотического роста функций сложности алгоритмов // Труды VII Всероссийской конференции по финансово-актуарной математике и смежным вопросам (ФАМ'2008), 29 февраля-4 марта 2008 г., Красноярск. 4.2. - Красноярск: ИПК СФУ, 2008. - С. 49-57.

31. Быкова В.В. Асимптотическая оценка сложности рекурсивных алгоритмов с аддитивным уменьшением размерности задачи // Труды VI Всероссийской конференции по финансово-актуарной математике и смежным вопросам (ФАМ'2007) 2-4 марта 2007 г., Красноярск. Ч. 2. - Красноярск: ИВМ СО РАН, СФУ, КГТЭИ, СИБУП, Изд-во «Гротеск», 2007. - С. 17-25.

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

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

34. Bykova V.V. On the level impact of parameter on the time execution of parameterized algorithms // The Conference devoted to 20 anniversary of independence of the Republic Uzbekistan «Modern Mathematics Problems» (MMP'2011). Karshi, Uzbekistan, 22-23 April 2011, P. 275-279.

35. Bykova V.V. Complexity and elasticity of the computation // Proc. of the Third IASTED International Multi-Conference on Automation, Control, and Information Technology (ACIT-CDA 2010) in cooperation with the Russian Academy of Sciences, 15-18 June 2010, Novosibirsk, Russia. ACTA Press Anaheim | Calgary | Zurich, P. 334-340.

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

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

37. Быкова В.В., Никульская Н.А. Комплекс программ TreeDec для нахождения дерева декомпозиции и вычисления верхней оценки древовидной ширины графа: Свидетельство о государственной регистрации № 17338 от 19.07.2011 (ИНИМ РАО, ОФЕРНиО) - Инв. номер ВНТИЦ 50201151063 от 26.07.2011.

38. Быкова В.В., Болховец В.О. Комплекс программ SafeDec для безопасного разложения графа минимальными сепараторами: Свидетельство о государственной регистрации №17337 от 19.07.2011 (ИНИМ РАО, ОФЕРНиО) - Инв. номер ВНТИЦ 50201151064 от 26.07.2011.

39. Быкова В.В., Свинцов Ю.А. Комплекс программ B&STree для преобразования дерева декомпозиции в бинарное сепараторное дерево: Свидетельство о государственной регистрации № 17983 от 01.03.2012 (ИНИПИ РАО, ОФЕРНиО) - Инв. номер ВНТИЦ 50201250289 от 01.03.2012.

Подписано в печать Формат 60x84/16. Усл. печ. л. 1,84.. Тираж 100 экз. Заказ №9227

Отпечатано полиграфическим центром Библиотечно-издательского комплекса Сибирского федерального университета 660041 Красноярск, пр. Свободный, 82а Тел/факс (391)206-26-67,206-26-49 E-mail: print_sfu@mail.ru; http://lib.sfu-kras.ru

Введение.

Глава 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. Уникальность разложения графа и гиперграфа на атомы кликовыми минимальными сепараторами.

Выводы.

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

В теории сложности вычислений выделяют два специальных раздела. Это собственно сложность вычислений - раздел, включающий в себя анализ сложности задач (нахождение нижних оценок времени решение задач), классическую дихотомию задач (классы сложности Р, 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 страниц.

Выводы

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 Ф

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

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. Свидетельства о регистрации программных комплексов