Теоретические основы анализа параметризированных алгоритмов
Покупка
Основная коллекция
Издательство:
Сибирский федеральный университет
Год издания: 2011
Кол-во страниц: 180
Дополнительно
Вид издания:
Монография
Уровень образования:
ВО - Магистратура
ISBN: 978-5-7638-2488-9
Артикул: 617512.01.99
Книга посвящена анализу параметризированных алгоритмов - современному направлению теории сложности вычислений. Параметризированные алгоритмы направлены на поиск точных решений NP-полных задач, когда параметр решаемой задачи мал по сравнению с длиной входа алгоритма. Роль этого параметра - учесть информацию о структуре исходных данных алгоритма и выделить основной источник неполиномиальной сложности NP-трудной задачи. В работе представлена классификация параметризирован-ных алгоритмов по вычислительной сложности на основе эластичностей функций сложности, описывающих потребности алгоритмов в необходимых ресурсах. С помощью эластичностей исследовано влияние параметра на время выполнения параметризированного алгоритма. Развиты методы анализа рекурсивных алгоритмов. Для специалистов в области разработки, анализа и исследования алгоритмов, а также для студентов, аспирантов, научных работников, преподавателей высших учебных заведений.
Скопировать запись
Фрагмент текстового слоя документа размещен для индексирующих роботов
МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ СИБИРСКИЙ ФЕДЕРАЛЬНЫЙ УНИВЕРСИТЕТ В.В. Быкова ТЕОРЕТИЧЕСКИЕ ОСНОВЫ АНАЛИЗА ПАРАМЕТРИЗИРОВАННЫХ АЛГОРИТМОВ Красноярск СФУ 2011
УДК 510.52+004.051 ББК 22.18 Б 952 Рецензенты: Б.С. Добронец, зав. кафедрой «Информационные системы» ИКИТ СФУ, доктор физико-математических наук, профессор; Л.Ф. Ноженкова, зав. отделом прикладной информатики ИВМ СО РАН, доктор технических наук, профессор. Быкова, В.В. Б 952 Теоретические основы анализа параметризированных алгоритмов: моногра фия / В.В. Быкова. – Красноярск: Сиб. федер. ун-т, 2011. – 180 с. ISBN 978-5-7638-2488-9 Книга посвящена анализу параметризированных алгоритмов – современному на правлению теории сложности вычислений. Параметризированные алгоритмы направлены на поиск точных решений NP-полных задач, когда параметр решаемой задачи мал по сравнению с длиной входа алгоритма. Роль этого параметра – учесть информацию о структуре исходных данных алгоритма и выделить основной источник неполиномиальной сложности NP-трудной задачи. В работе представлена классификация параметризированных алгоритмов по вычислительной сложности на основе эластичностей функций сложности, описывающих потребности алгоритмов в необходимых ресурсах. С помощью эластичностей исследовано влияние параметра на время выполнения параметризированного алгоритма. Развиты методы анализа рекурсивных алгоритмов. Для специалистов в области разработки, анализа и исследования алгоритмов, а также для студентов, аспирантов, научных работников, преподавателей высших учебных заведений. УДК 510.52+004.051 ББК 22.18 Сибирский федеральный университет, 2011 ISBN 978-5-7638-2488-9 В.В. Быкова, 2011
ВВЕДЕНИЕ Сведения о том, что может и что не может быть эффективно вычислено или математически формализовано, должны иметь глубочайшее влияние на математику и, более того, на наше понимание математических методов. Джурис Хартманис «Алгоритм – это, прежде всего, вычисления, которые реально осуществимы». Э. Арман Борель Понятие алгоритма является не только одним из главных понятий ма тематики, но одним из основных понятий современной науки. Чтобы ориентироваться в современном мире алгоритмов, необходимо уметь сравнивать различные алгоритмы решения одних и тех же задач, причем не только по качеству выдаваемого решения, но и по характеристикам самих алгоритмов (времени выполнения, расходу памяти и др.). Разработкой точного языка для обсуждения этих вопросов призвана заниматься теория сложности вычисле ний (метрическая теория алгоритмов) область исследований, лежащая на стыке дискретной математики и математической кибернетики. Ее результаты составляют теоретическую основу современной информатики и программной инженерии. В теории сложности вычислений выделяют два специальных раздела. Это собственно сложность вычислений раздел, включающий в себя анализ сложности задач (нахождение нижних оценок времени решение задач), классическую дихотомию задач (классы сложности P, NP) и теорию NP-полноты. Анализ алгоритмов раздел, в котором основным объектом исследования является алгоритм, его качество и сложность с различных точек зрения, но главным образом с точки зрения ресурсов, необходимых для его исполнения. Анализ задач, конечно же, опирается на анализ алгоритмов и направлен на определение оценок ресурсов, необходимых для любого алгоритма, решающего исследуемую задачу. Изучение алгоритмов позволяет более глубоко вникнуть в задачу и порой может подсказать наиболее эффективные методы ее решения.
Анализ алгоритмов предполагает очень многогранную область иссле дований: поиск критериев сравнения алгоритмов, нахождение асимптотических оценок сложности, классификацию алгоритмов по сложности и выработку рекомендаций по построению эффективных алгоритмов. При этом под сложностью алгоритма традиционно понимают время исполнения вычислительного процесса, порождаемого алгоритмом, то есть ресурсную или вычислительную сложность алгоритма. Успех в достижении глубины уровня анализа во многом зависит от решаемой задачи, выбранного метода решения и, конечно, от самого исследователя. Наиболее типичный уровень детализации – анализ алгоритма с установлением класса сложности и асимптотических оценок для функции временной сложности исследуемого алгоритма. Такие функции формально задают время исполнения алгоритма в зависимости от n длины исходных данных. Подобный уровень анализа характерен для широкой алгоритмической практики. Настоящее издание посвящено анализу параметризированных алгорит мов – современному направлению теории сложности вычислений, которое обращено к методам исследования и классификации параметризированных алгоритмов. В последние годы наблюдается растущий интерес к разработке и ана лизу параметризированных алгоритмов. Этот интерес имеет много причин. Во-первых, принято считать, что P NP, и что алгоритмы субэкспоненци альной сложности это лучшее, на что можно надеяться при решении NPполных задач. Во-вторых, наблюдается большой разброс в неполиномиальной сложности алгоритмов решения различных NP-полных задач. Классической дихотомии с классами P и NP уже недостаточно. Существует ли закономерность в алгоритмических возможностях NP-полных задач? Можно ли как-то классифицировать NP-полные задачи, чтобы выявить, насколько близ ко мы подошли к потенциально наилучшим алгоритмам для заданной NP полной задачи? Можно ли с помощью отдельных параметров входной ин формации выделить «ядро» источник неполиномиальной сложности NP полной задачи, чтобы затем выявить для нее эффективно разрешимые случаи? Ответы на эти вопросы пытается дать параметризированная теория сложности.
Параметризированные алгоритмы направлены на поиск точных реше ний NP-полных задач, когда параметр k решаемой задачи мал по сравнению с n длиной входа (исходных данных) алгоритма. Роль этого параметра – учесть информацию о структуре исходных данных алгоритма и выделить основной источник неполиномиальной сложности NP-полной задачи. При параметризированном подходе возникают двумерные функции сложности алгоритмов (функции, зависящие от n и k), поэтому параметризированную теорию сложности называют также двумерной теорией сложности вычислений. Идея параметризированного подхода к оценке сложности алгоритмов и задач была предложена в конце прошлого столетия Р. Дауни и М. Феллови. Они ввели понятие FPT-разрешимости задачи (Fixed-Parameter Tractable) относительно некоторого параметра. Поэтому именно их в настоящее время считают основоположниками параметризированной теории сложности вычислений. За последние два десятилетия эта теория нашла применение в различных областях компьютерных наук. Параметризированная теория сложности вычислений развивается по нескольким направлениям: определение иерархии классов сложности параметризированных задач, установление условий FPT-разрешимости, выявление взаимосвязи между параметризированной сложностью и классами приближенных алгоритмов (в частности, полностью полиномиальными схемами приближений), развитие методов анализа и разработки параметризированных алгоритмов. В многочисленных работах по параметризированному подходу к анализу сложности алгоритмов применяются методы классической (одномерной) систематизации. Между тем классическая одномерность ограничивает глубину анализа параметризированных алгоритмов, для которых вычислительная сложность описывается функциями от двух и более переменных. В настоящем издании систематизированы некоторые результаты ис следований автора, касающиеся анализа параметризированных алгоритмов. Предложена мера вычислительной сложности алгоритма, с помощью которой можно исследовать темп роста функций многих переменных, анализировать степень влияния структуры исходных данных параметризированного алгоритма на его вычислительную сложность, сравнивать между собой FPTалгоритмы решения NP-трудных задач. Этой мерой является частная эластичность функции сложности алгоритма. С помощью эластичности можно
классифицировать и обычные алгоритмы (алгоритмы с функцией сложности одной переменной n). Эластичность выделяет все пять классов алгоритмов (субполиномиальной, полиномиальной, субэкспоненциальной, экспоненциальной и гиперэкспоненциальной сложности), широко используемых в современной алгоритмической практике. В работе развиты методы анализа рекурсивных алгоритмов. Предложена методика асимптотического анализа итерационных алгоритмов. Все затронутые в книге вопросы практически важны для разработчиков программного обеспечения и специалистов в области теоретической информатики. Они дают ясное понимание того, как можно на практике решать прикладные задачи большой размерности, что можно и чего нельзя делать с помощью современных компьютеров. Книга написана на доступном математическом языке и мотивировками из информатики. Книга состоит из четырех разделов, трех приложений и библиографи ческого списка. Раздел 1 носит вводный характер. Здесь определяются необходимые понятия из теории алгоритмов. Вводятся и обсуждаются концептуальные основы анализа сложности алгоритмов. Приводятся асимптотические обозначения и свойства класса логарифмически-экспоненциальных функций, применяемые в последующих разделах. Раздел 2 посвящен классификации алгоритмов по сложности. Вначале рассматривается классическая дихотомия алгоритмов по сложности (полиномиальные и экспоненциальные алгоритмы). Затем исследуются пять современных сложностных классов алгоритмов. Поскольку непосредственное асимптотическое оценивание для распознавания всех пяти сложностных классов алгоритмов в большинстве случаев сопряжено с трудностями вычислительного характера, то предлагается простой и удобный для практики математический метод распознавания этих сложностных классов на основе асимптотики эластичности функций сложности. Здесь доказана теорема, устанавливающая особенности асимптотического поведения эластичности для различных (по порядку роста) логарифмически-экспоненциальных функций. Рассмотрение ограничивается одномерным случаем (когда функция сложности исследуемого алгоритма зависит только от одного аргумента – длины входа), что отвечает тривиальной параметризации. Предложенный подход
обобщается далее в разделе 4 на двумерный случай при рассмотрении параметризированных алгоритмов, которым свойственны в общем случае функции сложности многих переменных. В разделе 3 применительно к одномерным функциям сложности рас сматривается методика анализа итерационных алгоритмов, основанная на поэтапном исследовании структуры описания алгоритма с привлечением математического аппарата асимптотического анализа функций. Значительная часть раздела 3 отведена анализу рекурсивных алгоритмов и выработке рекомендаций по их эффективной организации. Анализ сложности рекурсивных алгоритмов – очень трудная и до конца нерешенная проблема теории сложности вычислений. Поэтому всякий математический результат, дающий какой-либо общий подход решения проблемы анализа рекурсивных алгоритмов, интересен как теоретически, так и практически. Здесь приведена и доказана теорема, позволяющая находить верхние и нижние асимптотические оценки времени выполнения рекурсивного алгоритма, построенного путем аддитивного уменьшения размера задачи на некоторую константу. Эта теорема теоретически дополняет известную ранее теорему Дж. Бентли, Д. Хакена и Дж. Сакса о решении рекуррентных соотношений, характерных для рекурсивных алгоритмов, организованных по принципу «разделяй и властвуй». Данные теоремы представляют пусть не универсальное, но достаточно мощное средство асимптотической оценки сложности рекурсивных алгоритмов, построенных определенным образом. Раздел 4 посвящен параметризированной алгоритмике. Вначале кратко обсуждаются традиционные классы сложности задач, концепция NP-полноты и современные подходы к решению трудноразрешимых задач. Эти сведения затрагивают алгоритмические возможности задач и нужны для введения в параметризированную алгоритмику. Затем освещаются основные идеи параметризированного подхода к сложности вычислений, вводится частная эластичность функции сложности многих переменных как мера вычислительной сложности параметризированного алгоритма. На основе частных эластичностей в условиях мультипликативной формы представления функций сложности и в границах семейства логарифмически-экспоненциальных функций излагается математический метод двумерной сложностной классификации FPT-алгоритмов. Также приводится методика установления степени воздей
ствия параметра на вычислительную сложность параметризированного алгоритма, основанная на применении частных эластичностей и коэффициента замещения одного аргумента другим для функций многих аргументов. Приложение 1 носит справочный характер. Оно содержит краткий спи сок формул, которые часто употребляются при математическом анализе алгоритмов. Приложение 2 включает краткое изложение методов решения линей ных рекуррентных соотношений с постоянными коэффициентами, которые позволяют выполнять анализ сложности обширного класса рекурсивных алгоритмов. Здесь также представлены результаты анализа, как начальные условия рекуррентного соотношения влияют на сложность рекурсивного алгоритма. Приложение 3 демонстрирует методы математического анализа алго ритмов на основных задачах линейной алгебры: нахождение определителя и ранга матрицы, обращение невырожденной матрицы, решение неоднородной системы линейных уравнений, построение треугольного разложения невырожденной квадратной матрицы. Приведен анализ сложности алгоритма Штрассена быстрого умножения матриц и схемы исключения Гаусса. Показана полиномиальная разрешимость основных задач линейной алгебры и их полиномиальная сводимость к задаче умножения матриц. Библиографический список содержит 126 наименований. В него вклю чены также работы автора, отвечающие содержанию и тематике настоящего издания. Теоремы, утверждения, леммы, следствия, рисунки и таблицы нумеру ются двумя числами: первое из них – это номер раздела, а второе – их порядковый номер, причем нумерация сквозная внутри раздела. Конец доказатель ства отмечается символом . Часть используемой символики является обще принятой в математике и информатике. В указателе обозначений приводятся некоторые специфические обозначения.
1. ПРЕДВАРИТЕЛЬНЫЕ ОБСУЖДЕНИЯ Данный раздел предваряет последующие разделы. Здесь определяются необходимые понятия из теории алгоритмов, такие как алгоритм, данные, конструктивный объект, массовая задача, вычислимая функция, алгоритмическая система. Вводятся и обсуждаются концептуальные основы анализа сложности алгоритмов. Приводятся асимптотические обозначения и свойства класса логарифмически-экспоненциальных функций, применяемые в последующих разделах. 1.1. Алгоритмичность и конструктивность Как и все прикладные разделы математики, теория алгоритмов кроме точного (формального) определения основного объекта изучения и исследования – алгоритма – использует и неформальное его определение. Многие компьютерные науки (теория автоматов, теория кодирования, математическая лингвистика, теория распознавания образов и др.), составляющие, как и теория алгоритмов, теоретическую основу современной информатики, в основном оперируют интуитивным определением алгоритма, основанным на интуиции и практическом опыте. Приведем несколько наиболее известных интуитивных определений. Определение А.Н. Колмогорова: алгоритм – всякая система вычисле ний, выполняемых по строго определенным правилам, которая после какоголибо числа шагов заведомо приводит к решению поставленной задачи [56]. Определение А.А. Маркова: алгоритм – это точное предписание, оп ределяющее вычислительный процесс, идущий от варьируемых исходных данных к искомому результату [68]. Математический энциклопедический словарь дает такую трактовку по нятия алгоритма: алгоритм – предписание исполнителю (человеку или автомату) выполнить точно определенную последовательность действий, направленных на достижение заданной цели или решение поставленной задачи [71].
Дональд Кнут в книге «Искусство программирования для ЭВМ» [53] отмечает, что современное толкование понятия алгоритма очень схоже со значением слов «метод», «способ», «процедура», «программа», но имеет свой дополнительный смысловой оттенок. Уточнение смысла выливается в постулирование ряда свойств, которыми должен обладать любой алгоритм. Приведем перечень наиболее важных свойств, которые раскрывают ин туитивную трактовку понятия алгоритма [2, 53, 93]. 1. Каждый алгоритм имеет дело с данными (исходными, промежуточ ными, результирующими). В качестве данных могут выступать необязательно числа, это могут быть самые разнообразные объекты (тексты, формулы, матрицы, графы и пр.) – объекты, построенные из элементов какого-либо множества по определенным правилам (алгоритму). Такое толкование данных открывает возможность широкой трактовки алгоритма. Можно говорить об алгоритмах управления техническими системами, алгоритмах распознавания образов, алгоритмах редактирования текстовой информации и т.п. 2. Для размещения данных алгоритму необходима память. Память считается однородной и дискретной, то есть состоящей из одинаковых ячеек. 3. Описание алгоритма должно быть конечным и дискретным, то есть состоять из конечного числа отдельных шагов, которые выполняются в дискретные моменты времени. 4. Каждый шаг должен быть элементарным (ограниченной сложно сти). Элементарность шага предполагает, что выполняемый объем работы на шаге мажорируется некоторой константой, зависящей от исполнителя, но не зависящей от исходных и промежуточных данных. 5. Последовательность шагов алгоритма детерминирована, то есть по сле каждого шага либо указывается, какой шаг выполнять дальше, либо дается команда остановки, после чего работа алгоритма считается законченной. 6. Алгоритм должен быть результативным, то есть для заданного на бора исходных данных последовательность шагов обязана приводить к выдаче вполне определенного результата. 7. Конечность действий (или финитность) алгоритма – для достижения результата алгоритм должен выполнить конечное число шагов, при этом требуемое количество шагов зависит только от исходных данных.