В.В. Быкова
ТеореТические осноВы
анализа
парамеТризироВанных
алгориТмоВ
Монография
Институт математики
Стр.1
МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ
РОССИЙСКОЙ ФЕДЕРАЦИИ
СИБИРСКИЙ ФЕДЕРАЛЬНЫЙ УНИВЕРСИТЕТ
В.В. Быкова
ТЕОРЕТИЧЕСКИЕ ОСНОВЫ АНАЛИЗА
ПАРАМЕТРИЗИРОВАННЫХ АЛГОРИТМОВ
Красноярск
СФУ
2011
Стр.2
УДК 510.52+004.051
ББК 22.18
Б 952
Рецензенты:
Б.С. Добронец, зав. кафедрой «Информационные системы» ИКИТ СФУ,
доктор физико-математических наук, профессор;
Л.Ф. Ноженкова, зав. отделом прикладной информатики ИВМ СО РАН,
доктор технических наук, профессор.
Быкова, В.В.
Б 952 Теоретические основы анализа параметризированных алгоритмов: монография
/ В.В. Быкова. – Красноярск: Сиб. федер. ун-т, 2011. – 180 с.
ISBN 978-5-7638-2488-9
Книга посвящена анализу параметризированных алгоритмов – современному направлению
теории сложности вычислений. Параметризированные алгоритмы направлены
на поиск точных решений NP-полных задач, когда параметр решаемой задачи мал по
сравнению с длиной входа алгоритма. Роль этого параметра – учесть информацию о
структуре исходных данных алгоритма и выделить основной источник неполиномиальной
сложности NP-трудной задачи. В работе представлена классификация параметризированных
алгоритмов по вычислительной сложности на основе эластичностей функций сложности,
описывающих потребности алгоритмов в необходимых ресурсах. С помощью эластичностей
исследовано влияние параметра на время выполнения параметризированного
алгоритма. Развиты методы анализа рекурсивных алгоритмов.
Для специалистов в области разработки, анализа и исследования алгоритмов, а
также для студентов, аспирантов, научных работников, преподавателей высших учебных
заведений.
УДК 510.52+004.051
ББК 22.18
ISBN 978-5-7638-2488-9
Сибирский федеральный
университет, 2011
В.В. Быкова, 2011
Стр.3
ВВЕДЕНИЕ
Сведения о том, что может и что не может быть эффективно
вычислено или математически формализовано, должны иметь
глубочайшее влияние на математику и, более того, на наше понимание
математических методов.
Джурис Хартманис
«Алгоритм – это, прежде всего, вычисления, которые реально
осуществимы».
Э. Арман Борель
Понятие алгоритма является не только одним из главных понятий математики,
но одним из основных понятий современной науки. Чтобы ориентироваться
в современном мире алгоритмов, необходимо уметь сравнивать
различные алгоритмы решения одних и тех же задач, причем не только по
качеству выдаваемого решения, но и по характеристикам самих алгоритмов
(времени выполнения, расходу памяти и др.). Разработкой точного языка для
обсуждения этих вопросов призвана заниматься теория сложности вычислений
(метрическая теория алгоритмов) область исследований, лежащая на
стыке дискретной математики и математической кибернетики. Ее результаты
составляют теоретическую основу современной информатики и программной
инженерии.
В теории сложности вычислений выделяют два специальных раздела.
Это собственно сложность вычислений раздел, включающий в себя анализ
сложности задач (нахождение нижних оценок времени решение задач), классическую
дихотомию задач (классы сложности P, NP) и теорию NP-полноты.
Анализ алгоритмов
раздел, в котором основным объектом исследования
является алгоритм, его качество и сложность с различных точек зрения, но
главным образом с точки зрения ресурсов, необходимых для его исполнения.
Анализ задач, конечно же, опирается на анализ алгоритмов и направлен на
определение оценок ресурсов, необходимых для любого алгоритма, решающего
исследуемую задачу. Изучение алгоритмов позволяет более глубоко
вникнуть в задачу и порой может подсказать наиболее эффективные методы
ее решения.
Стр.4
4
Анализ алгоритмов предполагает очень многогранную область исследований:
поиск критериев сравнения алгоритмов, нахождение асимптотических
оценок сложности, классификацию алгоритмов по сложности и выработку
рекомендаций по построению эффективных алгоритмов. При этом под
сложностью алгоритма традиционно понимают время исполнения вычислительного
процесса, порождаемого алгоритмом, то есть ресурсную или вычислительную
сложность алгоритма. Успех в достижении глубины уровня анализа
во многом зависит от решаемой задачи, выбранного метода решения и,
конечно, от самого исследователя. Наиболее типичный уровень детализации
– анализ алгоритма с установлением класса сложности и асимптотических
оценок для функции временной сложности исследуемого алгоритма. Такие
функции формально задают время исполнения алгоритма в зависимости от n
длины исходных данных. Подобный уровень анализа характерен для широкой
алгоритмической практики.
Настоящее издание посвящено анализу параметризированных алгоритмов
– современному направлению теории сложности вычислений, которое
обращено к методам исследования и классификации параметризированных
алгоритмов.
В последние годы наблюдается растущий интерес к разработке и анализу
параметризированных алгоритмов. Этот интерес имеет много причин.
Во-первых, принято считать, что P NP, и что алгоритмы субэкспоненциальной
сложности это лучшее, на что можно надеяться при решении NPполных
задач. Во-вторых, наблюдается большой разброс в неполиномиальной
сложности алгоритмов решения различных NP-полных задач. Классической
дихотомии с классами P и NP уже недостаточно. Существует ли закономерность
в алгоритмических возможностях NP-полных задач? Можно ли
как-то классифицировать NP-полные задачи, чтобы выявить, насколько близко
мы подошли к потенциально наилучшим алгоритмам для заданной NPполной
задачи? Можно ли с помощью отдельных параметров входной информации
выделить «ядро» источник неполиномиальной сложности NPполной
задачи, чтобы затем выявить для нее эффективно разрешимые случаи?
Ответы на эти вопросы пытается дать параметризированная теория
сложности.
Стр.5
178
СОДЕРЖАНИЕ
Введение………………………………………………………………….
1. Предварительные обсуждения……………………………………..
1.1. Алгоритмичность и конструктивность…………………………..
1.2. Алгоритмичность и вычислимость……………………………….
1.3. Концептуальные основы анализа сложности алгоритмов……...
1.4. Асимптотические обозначения и их использование
при анализе алгоритмов………………………………………………..
1.5. Соглашения относительно функций сложности алгоритма.
Характеризация класса логарифмически-экспоненциальных
функций…………………………………………………………………
Резюме……………………………………………..................................
2. Классическая и современная систематизации алгоритмов
по сложности (одномерный случай) ………………………………..
2.1. Классическая систематизация алгоритмов по скорости роста
функций сложности…………………………………………………..
2.2. Эластичность и ее свойства………………………………………
2.3. Несколько вспомогательных утверждений……………….…….
2.4. Шесть классов L-функций……………………………………….
2.5. Теорема о классификации L-функций на основе
эластичности…………………………………………………………..
2.6. Современная классификация алгоритмов по асимптотике
эластичности функций сложности……………………………………
2.7. Методика сравнения алгоритмов по асимптотике
эластичности…………………………………………………………
2.8. Неэластичные, эластичные и суперэластичные алгоритмы.........
Резюме………………………………………………………………….
3. Математические методы анализа алгоритмов ………………..
3.1. Основные приемы анализа сложности итерационных
алгоритмов……………………………………………………………...
3.2. Проблемы анализа сложности рекурсивных алгоритмов………
3
9
9
14
21
30
35
39
42
42
49
52
53
57
64
67
70
71
74
74
79
Стр.179
179
3.3. Рекурсивные алгоритмы и рекуррентные соотношения………..
3.4. Метод оценки решений специального типа рекуррентных
соотношений, характерных для принципа «разделяй
и властвуй»……………………………………………………………..
3.5. Метод оценки решений специального типа рекуррентных
соотношений, характерных для аддитивного уменьшения
размерности задачи…………………………………………………….
Резюме………………………………………………………………….
4. Математический анализ параметризированных алгоритмов
4.1. О классической сложностной дихотомии и подходах
к решению трудноразрешимых задач………………………………..
4.2. Параметризация задач и алгоритмов как путь управления
сложностью вычислений. FPT-разрешимость…….....………………
4.3. Проблемы параметризированной алгоритмики………………...
4.4. Классификация параметризированных алгоритмов на основе
асимптотики частных эластичностей функций сложности
(двумерный случай)…………………………………………………..
4.5. Методика анализа воздействия параметра на сложность
параметризированного алгоритма…………………………………..
4.6. Альтернативные характеризации FPT-разрешимости…………
Резюме…………………………………………………………………
Приложение 1. Формулы, применяемые при анализе
алгоритмов…………………………………………………………….
П.1.1. Оценки некоторых формул суммирования…………………..
П.1.2. Комбинаторные числа и их оценки……………………………
П.1.3. Оценки для экспонент и логарифмов…………………………
П.1.4. Формулы округления снизу и сверху…………………………
Приложение 2. Краткие сведения о рекуррентных
соотношениях с постоянными коэффициентами………………..
П.2.1. Методы решения однородных линейных рекуррентных
соотношений…………………………………………………………..
П.2.2. Чувствительность порядка роста функции сложности
к начальным условиям рекуррентного соотношения………………
П.2.3. Методы решения неоднородных линейных рекуррентных
соотношений…………………………………………………………..
81
85
89
99
102
103
110
113
116
121
129
130
134
134
135
135
135
136
136
140
141
Стр.180
180
Приложение 3. Рекурсия в вычислительных задачах линейной
алгебры ………………………………………………………………..
П.3.1. Быстрое умножение квадратных матриц по принципу
«разделяй и властвуй»……………………………………………….
П.3.2. Реализация схемы исключения Гаусса путем аддитивного
уменьшения размерности задачи……………………………………..
П.3.3. Полиномиальная разрешимость и сводимость
основных задач линейной алгебры…………………………………
Библиографический список ……………………………………….
Указатель обозначений………………………………………………
148
148
151
159
166
177
Стр.181