В.Б. Алексеев - Введение в теорию сложности алгоритмов

Московский государственный университет имени М. В. Ломоносова Факультет вычислительной математики и кибернетики В. Б. Алексеев ВВЕДЕНИЕ В ТЕОРИЮ СЛОЖНОСТИ АЛГОРИТМОВ Учебное пособие по курсу "Сложность алгоритмов" Москва 2002 Э'ДН Омквхшю. Ык ББК 22.12:22.18 А 47 Алексеев В. Б. "Введение в теорию сложности алгоритмов" (учебное пособие для студентов) — Мс Издательский отдел ф-та ВМиК МГУ (лицензия ИЛ Х 05899 от 24.09.2001), 2002 г. — 82 с. Курс "Сложность алгоритмов" входит как основной курс в учебный план для студентов кафедры математической кибернетвхн факультета ВМиК МГУ, а также может служить спецкурсом для студентов других кафедр. Ланное учебное пособие призвано помочь студентам в изучении этого курса. В учебном пособии рассматриваются общие утверждения о сложности задач, методы построения быстрых алгоритмов (метод динамического программмирования, ".разделяй и властвуй", метод расширения модели) и примеры их применения с оленками сложности, основные классы задач относительно их сложности, примеры универсальных задач в этих классах.

Репензенты: Лупанов О. Б., чл.-корр. РАН, профессор Ложкин С. А., д. ф.-м. н., профессор Печатается по решению Редакционно-издательского совета факультета вычислительной математики и кибернетики МГУ им. М. В. Ломоносова. БВХ 5-89407-137-2 Ос Издательский отдел факультета вычислительной математики и кибернетики МГУ им. М. В. Ломоносова, 2002 ОГЛАВЛЕНИЕ 1. Введение .....4 1.1.

Поиск в упорядоченном массиве ..4 1.2. Сортировка . .7 2. Рекуррентные методы построения алгоритмов........... 10 2.1. Метод динамического программирования....................... 10 2.2. Метод "разделяй и властвуй" . 14 2.3. Алгоритм Карелубы для умножения чисел......,.......,...... 16 2.4. Алгоритм Тоома дпя умножения чисел......................... 18 2.5. Апюритм Штрассена для умножения матрип.................. 20 3. Метод расширения модели 22 3.1. Алгоритмы умножения 0-1-матриц 22 3.2. Транзитивное замыкание графов . 24 3.3. Распознавание принадлежности булевых функций предпопным классам Поста 25 3.4.

Распознавание сохранения двухместных преднкатов............ 27 3.5. Классы Р 29 4. Общая теория сложности задач . .. 33 4.1. Машины Тьюринга 33 4.2. Существование сложных задач 34 4.3. Метод следов. Распознавание симметрии....................... 38 4.4. Регулярные языки 42 4.5. Классы Р н ИР . 46 4.6. Теорема Кука .. .49 4.7. Сложность задач о выполнимости . 54 4.8.

Некоторые МР-полные задачи на графах....................... 58 5. Задачи оптимизапии................,......................... 65 5.1. Задача о кратчайшем остовном дереве......................... 65 5.2. Приближенные алгоритмы .. 67 5.3. Задача коммивояжера 70 5.4. Задача о максимальной клике 73 6. Классы РЯРАСЕ и РЬОС . . 76 Литература 81 1.

Введение Каждый алгоритм А характеризуется тем, что на его вход могут поступать различные входяые данные х, которые он преобразует в некоторые вмходкые данвьье у. При этом процесс работы А на входных данных х можно охарактеризовать некоторыми сложвостлвыми харакглерпсльвками Ья(х) (чйсло'1пагов алгоритма, объем используемой па' мяти и др.). Однако дать явное представление фувтшии Ья(х) для всех х обы шо не прццставляется 'возможным. Лаже поведение Ья(х) как функции от х обычно трудно'описать; Поэтому при анализе сложности ' алгоритмов часто рассматривают более грубые характеристики. Наиболее распространенным является сле)зумкций подход. Входные данные характеризуются некоторым натуральным параметром п их сложности (чаще всего п — длина представления входных данных некоторым заданным слособом). Палее изучается фувхция Ья(п), определяемая как максимум Ья(х) по всем х с параметром п (сложносльь в худтиеиь случае) илн как некоторое'среднее Ья(х) по всем х с параметром п (средняя сложность).

В этих случэлх уже удается получать интересные результаты. В данном пособии мы будем рассматривать только одну сложвостную характеристику алгоритмов — время, нли число шагов, работы алгоритма. При этом мы до1икны четко определять, что такое шаг алгоритма. Если же мы хотим получать утверждения типа идля любого алгоритма", то мы также должны четко описать весь класс алгоритмов, которые мы рассматриваем. Мы поясним это вначале примерами. 1.1. Поиск в упорндоченном массиве. Пусть имеется упорядоченный массив элементов из некоторого линейно упорядоченного множества а1 < аз « ... а„. На вход алгоритма будет поступать некоторый элемент а, совпадающий с одним из элементов а1, а2,..., а„.

Один шаг алгоритма состоит в сравнении а с некоторым а;, получении одного из двух ответов а < а; или а > а, и анализе этого ответа. Алгоритм должен выдать номер 1 того элемента а, для которого а = а . Рассмотрим, например, алгоритм, который сравнивает а по очереди со всеми элементами от а1 до а„, Тогда если а = а1, он может вьшать ответ уже после 1-го шага. Однако, если а = а„1 или а = а„, то алгоритм будет делать и — 1 шагов.

В среднем, если считать, что а совпадает с любым а, с вероятностью -„, число 1 шаюв будет 1+2+...+и-1 +п-1 и+1 1 и 2 и' В дальнейшем мы будем алгоритмы считать детерминированными. Так, например, для любого алгоритма поиска элемента в упорядоченном массиве на первом шаге однозначно определяется номер т элемента, с которым сравнивается а. Этот номер не зависит от входа а. В зависимости от ответа (а < ат или а > аз) однозначно определяется следующий номер элемента, с которым сравнивается а, и т.д. Татсим образом всякий алгоритм поиска (из указанного выше класса) можно представить корневым бинарным деревом, в котором каждой вершине, отличной от листьев, приписан некоторый номер элемента, с которым сравнивается а, а каждому листу приписан номер элемента; равного а. Определение. Сложностаью (в худшем случае) Ъл(п) алгоритма поиска в упорядоченном массиве из и элементов называется максимальное число сравнений элемента а с элементами массива до получения ответа.

Средней сложностью Ь„о(п) алгоритма поиска А в упорядоченном массиве нз и элементов называется величина Ьл" (и) =- -"1,. 1Ьл(а,), гле Ьл(ат) — число шагов алгоритма, если вход а = ао Если тт — действительное число, то через ]а] и ]те] мы будем обозначать наибольшее (соответственно, наименьшее) целое число„не большее (соответственно, не меньшее), чем а. Часто ]тз] обозначают [а] н называют целой частпью числа ст. Теорема 1.1.

Сушествуеот алгоритм А поиска в упорядоченном массиве, для котпорого Ьл(п) = (1обз и]. Доказаотельсптво. Доказывать существование алгоритма с нужными свойствами обычно легко — достаточно явно предъявить такой алгоритм. Требуемому в теореме условию удовлетворяет следующий алгоритм, называемый "бинарным поиском", и описываемый рекуррентно.

Если и = 1, то выдать ответ а = ап Если и > 2, то вычислить й = '1з] и сравнить а с аю Если а < ам то рехуррентно (тем же алгоритмам) осуществить поиск а в массиве ат < аз « ... аь. Если а > ам то осуществить (рекуррентно) поиск а в массиве ае Ы < аь+з «... а„.

В любом случае длина получаемого массива не превосходит и— '1з] = ] з], и, следовательно, Ьл(п) = 1+Ел(] 'з]). Кроме того Дл(1) = О. Докажем индукцней по та, что для всех натуральных п, таких, что 2ю т < и < 2, выполняется Дл(п) = тп. При пт = О получаем и = 1 и Ьл(1) = О = тп. Пусть утверждение верно для тп = р и 2" < и < 2тт+т.

Тогда 2~ ~ < ] з] < 2э н по пРедположению индУкции Ьл(Я]) = Р. Отсюда Тл(п) = 1+ Бл(] з]) = р+ 1, то есть утверждение верно для т = р+ 1. По индукдии получаем, что утверждение верно для всех и, то есть Ел(п) = пз = !!обэп~!. Теорема доказана. Следствие. Для алгоритма А бинарного поиска Ьл (и) < ср !'1обз 1. , Доказать утверждение типа "для любого алгоритма" обычно существенно труднее, чем утверждение типа "существует алгоритм".

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

Высотой Ь(Р) дерева Р будем называть гаахЬ(х), где максимум берется по всем листьям дерева Р. Средней вьюотой Ьср(Р) дерева Р будем называть среднее арифметическое величин Ь(х) по всем листьям дерева Р. Лемма 1.1. Для любого бинарного дерева с п листьями вмполняютаг неравенства: 1) Ь(Р) > !'1обз и!, г) Ьср(Р) >!айги.

Доказательство. 1) Любое бинарное дерево высоты Ь можно достроить до полного бинарного дерева высоты Ь (в котором все пути от хорна до листьев содержат по Ь ребер). Для этого достаточно к каждому листу х высоты Ь(х) подклеить полное бинарное дерево высоты Ь вЂ” Ь(х). При этом число листьев не уменьшится. Поскольку в полном бинарном дереве высоты Ь число листьев равно 2", то для числа и листьев в исходном дереве выполняется неравенство и ( 2, ь или Ь ) 1обг п. Так как Ь вЂ” натургльное число, то Ь ) т!1обз п~,.