Быкова В.В. Теоретические основы анализа параметризированных алгоритмов

Теоретические основы анализа параметризированных алгоритмов......Page 1 1.1. Алгоритмичность и конструктивность......Page 10 1.2. Алгоритмичность и вычислимость......Page 15 1.3. Концептуальные основы анализа сложности алгоритмов......Page 22 1.4. Асимтотические обозначения и их использование при анализе алгоритмов......Page 31 1.5. Соглашения относительно функций сложности алгоритма. Характеризация класса логарифмически- экспоненциальных функций......Page 36 Резюме......Page 40 2.1. Классическая систематизация алгоритмов по скорости роста функций сложности......Page 43 2.2. Эластичность и ее свойства......Page 50 2.3. Несколько вспомогательных утверждений......Page 53 2.4. Шесть классов L-функций......Page 54 2.5. Теорема о классификации L-функций на основе эластичности......Page 58 2.6. Современная классификация алгоритмов по асимптотике эластичности функций сложности......Page 65 2.7. Методика сравнения алгоритмов по асимптотике эластичности......Page 68 2.8. Неэластичные, эластичные и суперэластичные алгоритмы......Page 71 Резюме......Page 72 3.1. Основные приемы анализа сложности итерационных алгоритмов......Page 75 3.2. Проблемы анализа сложности рекурсивных алгоритмов......Page 80 3.3. Рекурсивные алгоритмы и рекуррентные соотношения......Page 82 3.4. Метод оценки решений специального типа рекуррентных соотношений, характерных для принципа «разделяй и властвуй»......Page 86 3.5. Метод оценки решений специального типа рекуррентных соотношений, характерных для аддитивного уменьшения размерности задачи......Page 90 Резюме......Page 100 4. МАТЕМАТИЧЕСКИЙ АНАЛИЗ ПАРАМЕТРИЗИРОВАННЫХ АЛГОРИТМОВ......Page 103 4.1. О классической сложностной дихотомии и подходах к решению трудноразрешимых задач......Page 104 4.2. Параметризация задач и алгоритмов как путь управления сложностью вычислений. FPT-разрешимость......Page 111 4.3. Проблемы параметризированной алгоритмики......Page 114 4.4. Классификация параметризированных алгоритмов на основе асимптотики частных эластичностей функций сложности (двумерный случай)......Page 117 4.5. Методика анализа воздействия параметра на сложность параметризированного алгоритма......Page 122 4.6. Альтернативные характеризации FPT-разрешимости......Page 130 РЕЗЮМЕ......Page 131 ПРИЛОЖЕНИЕ 1. ФОРМУЛЫ, ПРИМЕНЯЕМЫЕ ПРИ АНАЛИЗЕ АЛГОРИТМОВ......Page 135 ПРИЛОЖЕНИЕ 2. КРАТКИЕ СВЕДЕНИЯ О РЕКУРРЕНТНЫХ СООТНОШЕНИЯХ С ПОСТОЯННЫМИ КОЭФФИЦИЕНТАМИ......Page 137 ПРИЛОЖЕНИЕ 3. РЕКУРСИЯ В ВЫЧИСЛИТЕЛЬНЫХ ЗАДАЧАХ ЛИНЕЙНОЙ АЛГЕБРЫ......Page 149 БИБЛИОГРАФИЧЕСКИЙ СПИСОК......Page 167 УКАЗАТЕЛЬ ОБОЗНАЧЕНИЙ......Page 178 СОДЕРЖАНИЕ......Page 179