Роль этого параметра – учесть информацию о структуре исходных данных алгоритма и выделить основной источник неполиномиальной сложности NP-трудной задачи. <...> . Разработкой точного языка для обсуждения этих вопросов призвана заниматься теория сложности вычислений (метрическая теория алгоритмов) область исследований, лежащая на стыке дискретной математики и математической кибернетики. <...> Это собственно сложность вычислений раздел, включающий в себя анализ сложности задач (нахождение нижних оценок времени решение задач), классическую дихотомию задач (классы сложности P, NP) и теорию NP-полноты. <...> Анализ задач, конечно же, опирается на анализ алгоритмов и направлен на определение оценок ресурсов, необходимых для любого алгоритма, решающего исследуемую задачу. <...> Во-вторых, наблюдается большой разброс в неполиномиальной сложности алгоритмов решения различных NP-полных задач. <...> Можно ли с помощью отдельных параметров входной информации выделить «ядро» источник неполиномиальной сложности NPполной задачи, чтобы затем выявить для нее эффективно разрешимые случаи? <...> Ответы на эти вопросы пытается дать параметризированная теория сложности. <...> Роль этого параметра – учесть информацию о структуре исходных данных алгоритма и выделить основной источник неполиномиальной сложности NP-полной задачи. <...> При параметризированном подходе возникают двумерные функции сложности алгоритмов (функции, зависящие от n и k), поэтому параметризированную теорию сложности называют также двумерной теорией сложности вычислений. <...> Поэтому именно их в настоящее время считают основоположниками параметризированной теории сложности вычислений. <...> Параметризированная теория сложности вычислений развивается по нескольким направлениям: определение иерархии классов сложности параметризированных задач, установление условий FPT-разрешимости, выявление взаимосвязи между параметризированной сложностью и классами приближенных алгоритмов <...>
Теоретические_основы_анализа_параметризированных_данных.pdf
МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ
РОССИЙСКОЙ ФЕДЕРАЦИИ
СИБИРСКИЙ ФЕДЕРАЛЬНЫЙ УНИВЕРСИТЕТ
В.В. Быкова
ТЕОРЕТИЧЕСКИЕ ОСНОВЫ АНАЛИЗА
ПАРАМЕТРИЗИРОВАННЫХ АЛГОРИТМОВ
Красноярск
СФУ
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
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