Кузюрин Н.Н. Фомин С.А. Эффективные алгоритмы и сложность вычислений

Подождите немного. Документ загружается.

Версия от 11 декабря 2009 г.

Эта книга написана по материалам двух спецкурсов, чи-

тавшихся авторами в течение нескольких лет для студентов

4-го и 6-го курсов Московского физико-технического институ-

та. Она знакомит читателей как с классическими результатами

в разработке эффективных алгоритмов для решения вычисли-

тельно трудных задач, полученными еще в 1960-1970-х годах,

так и с новыми результатами, полученными в последние годы.

Именно в рассмотрении современных подходов к решению вы-

числительно трудных задач и заключается основное отличие

данного пособия от традиционных книг по разработке и ана-

лизу эффективных алгоритмов.

Рассмотренные темы составляют основу современных на-

учных исследований сложности вычислительных задач и алго-

ритмов и могут быть использованы для создания наукоемкого

программного обеспечения и инноваций в сфере информацион-

ных технологий.

Для студентов факультетов управления и прикладной ма-

тематики, нанотехнологий и информатики, инноваций и высо-

ких технологий Московского физико-технического института.

Рекомендуется также студентам и аспирантам других ВУЗов,

изучающих информатику, теорию алгоритмов и сложность вы-

числений.

Свежая версия этой книги всегда доступна на странице

http://discopal.ispras.ru/ru.book-advanced-algorithms.htm и

распространяется по лицензии OPL (http://www.opencontent.

org/openpub/). Это означает, что текст данной книги может

использоваться свободно в любых целях, за исключением ком-

мерческих, и нельзя менять авторство.

Свяжитесь с нами (mailto:fomin@ispras.ru), если вы на-

шли ошибку или у вас есть конструктивное замечание/предло-

жение — мы будем рады.

Оглавление

Предисловие 7

Введение 9

Глава 1. Алгоритмы и их сложность 17

1.1. Примеры задач и алгоритмов . . . . . . . . . . . 17

1.1.1. Теоретико-числовые задачи:



НОД





факториал





возведение в степень





дискретный логарифм



. . . . . . . . . . 17

1.1.2. Задачи на графах:



Коммивояжер





Кратчайшие пути





Остовные деревья



1.1.3. Приближенные алгоритмы:



Составление

расписаний



. . . . . . . . . . . . . . . . . 40

1.1.4.



Сортировка слиянием



. . . . . . . . . . 44

1.1.5.



Быстрая сортировка



. . . . . . . . . . . 47

1.2. Формально об алгоритмах. Несложно о сложности 52

1.2.1.



RAM



: машины с произвольным доступом 52

1.2.2. Сложность в худшем случае . . . . . . . . 59

1.2.3. Сложность в среднем . . . . . . . . . . . . 61

1.2.4. Полиномиальные алгоритмы . . . . . . . . 61

1.2.5. Полиномиальность и эффективность . . . 65

Глава 2. Аппроксимация с гарантированной точно-

стью 68

2.1. Алгоритмы с оценками точности . . . . . . . . . 68

4 Оглавление

2.1.1. Жадные алгоритмы для



Покрытия мно-

жеств



. . . . . . . . . . . . . . . . . . . . 70

2.1.2. Приближенные алгоритмы для



Вершинного

покрытия



. . . . . . . . . . . . . . . . . . 75

2.1.3. Жадный алгоритм для



Рюкзака



. . . . 84

2.1.4. Алгоритм Кристофидеса . . . . . . . . . . 88

2.2. Аппроксимация с заданной точностью . . . . . . 96

2.2.1.



Рюкзак



: динамическое программиро-

вание . . . . . . . . . . . . . . . . . . . . . 96

2.2.2. Полностью полиномиальная приближен-

ная схема для



Рюкзака



. . . . . . . . . 104

Глава 3. Вероятностный анализ алгоритмов 112

3.1. Сложность и полиномиальность в среднем . . . 112

3.2. Задача упаковки . . . . . . . . . . . . . . . . . . . 115

3.3. Выполнимость КНФ . . . . . . . . . . . . . . . . 122

3.4. Точность алгоритма для почти всех входов . . . 130

3.5.



Рюкзак



: полиномиальность в среднем . . . . . 136

Глава 4. Вероятностные алгоритмы и их анализ 145

4.1. Вероятностная проверка тождеств . . . . . . . . 145

4.2. Вероятностные методы

в перечислительных задачах . . . . . . . . . . . . 149

4.3. Вероятностные методы

в параллельных вычислениях . . . . . . . . . . . 157

4.3.1. Максимальное по включению независи-

мое множество в графе . . . . . . . . . . . 157

4.3.2. Протокол византийского соглашения . . . 166

4.4. Вероятностное округление . . . . . . . . . . . . . 171

4.4.1. Вероятностное округление

для задачи «MAX-SAT» . . . . . . . . . . 171

4.4.2. Максимальный разрез в графе . . . . . . 177

Глава 5. Методы дерандомизации 187

5.1. Метод условных вероятностей . . . . . . . . . . . 187

Оглавление 5

5.2. Метод малых вероятностных пространств . . . . 193

Глава 6. Основы теории сложности вычислений 198

6.1. Сложность вычислений . . . . . . . . . . . . . . . 198

6.1.1. Машины Тьюринга и вычислимость . . . 198

6.1.2. Классы DT IME, DSPACE . . . . . . . . 216

6.2. Полиномиальные сводимости и N P-полнота . . 221

6.2.1. Сводимость по Куку . . . . . . . . . . . . 221

6.2.2. Недетерминированные алгоритмы . . . . 223

6.2.3. Сводимость по Карпу . . . . . . . . . . . . 229

6.3. Вероятностные вычисления . . . . . . . . . . . . 240

6.3.1. Классы RP/coRP.



Односторонние ошиб-

ки



. . . . . . . . . . . . . . . . . . . . . . 243

6.3.2. Класс BPP.



Двусторонние ошибки



. . 249

6.3.3. Класс PP . . . . . . . . . . . . . . . . . . . 253

6.3.4. Класс ZPP.



Алгоритмы без ошибок



. 257

6.3.5. Вероятностно проверяемые доказательства 259

6.3.6. PCP и неаппроксимируемость . . . . . . . 267

6.3.7. Класс APX . Сводимости, сохраняющие

аппроксимации . . . . . . . . . . . . . . . . 274

6.4. Схемы и схемная сложность . . . . . . . . . . . . 284

6.5. Коммуникационная сложность . . . . . . . . . . 292

6.6. Диаграмма классов сложности . . . . . . . . . . 298

Глава 7. Приложения 301

7.1. Введение в Python . . . . . . . . . . . . . . . . . . 301

7.2. Глоссарий . . . . . . . . . . . . . . . . . . . . . . . 306

Глава 8. Сборник упражнений (ИСПРАН-2008-

весна) 308

Список литературы 327

Списки иллюстраций 343

6 Оглавление

Список алгоритмов 346

Предисловие

Настоящее учебное пособие написано по материалам двух

спецкурсов, читавшихся авторами в течение нескольких

лет для студентов 4-го и 6-го курсов Московского физико-

технического института — «Сложность комбинаторных алго-

ритмов» и «Эффективные алгоритмы». Основная цель пособия

заключается в ознакомлении читателей как с классически-

ми результатами в разработке эффективных алгоритмов для

решения вычислительно трудных задач, полученными еще

в 1960-1970-х годах, так и с новыми результатами, полученны-

ми в последние годы. Именно в рассмотрении вычислительно

трудных задач и современных подходов к их решению и за-

ключается основное отличие данного пособия от традиционных

книг по разработке и анализу эффективных алгоритмов (на-

пример: [79, 99a]).

Пособие можно разбить на три основные части соответ-

ственно уровням сложности изложения материала. В первой

(глава 1) популярно излагаются примеры алгоритмов, и ана-

лизируется их сложность для ряда широко известных задач.

Вторая часть (главы 2–5) посвящена методам разработ-

ки и анализа алгоритмов решения конкретных задач. В гла-

ве 2 рассматриваются приближенные алгоритмы с гарантиро-

ванными оценками точности для нескольких N P-трудных за-

дач. Глава 3 посвящена вероятностным методам анализа детер-

минированных алгоритмов. В ней демонстрируется, что для

некоторых N P-трудных задач существуют алгоритмы, кото-

рые являются полиномиальными «в среднем» или точными

8 Предисловие

«для почти всех входов». В главе 4 рассматриваются методы

построения вероятностных приближенных алгоритмов. В гла-

ве 5 представлены методы дерандомизации — преобразования

вероятностных алгоритмов в приближенные детерминирован-

ные. В этой части к результатам, которые не освещены в отече-

ственной литературе, можно отнести полиномиальные в сред-

нем алгоритмы для ряда N P-трудных задач (например, для

задачи о рюкзаке), вероятностные приближенные алгоритмы

для ряда задач и методы их дерандомизации: метод условных

вероятностей и метод малых вероятностных пространств.

Третья часть (глава 6) посвящена теории сложности, вклю-

чающей в себя классические понятия сложности вычисле-

ний, классов сложности, теорию N P-полноты. Из новых ре-

зультатов, представленных в этой части, хочется отметить

PCP-теорему и ее следствия для доказательства неаппрокси-

мируемости ряда задач, а также понятия сводимостей, сохра-

няющих аппроксимации.

Несколько слов о форме описания. Обычно при описании

алгоритмов опускают вопросы конкретной программной реа-

лизации, и алгоритмы описываются либо неформально, либо

на наиболее примитивном, алголоподобном языке (псевдоко-

де). Чтобы избежать неясностей, свойственных псевдоописани-

ям (т.к. псевдокод не «верифицирован» компьютером), мы ре-

ализовали часть алгоритмов на языке Python (см. раздел 7.1).

Этот язык признан удачным выбором для преподавания ин-

форматики и курсов по алгоритмам.

Также в конце книги приведен глоссарий с элементарными

определениями, используемыми в тексте книги. Эти определе-

ния обычно знакомы студентам старших курсов, поэтому мы

не даем их в основном тексте книги, но иногда требуется осве-

жить эти определения в памяти — для этого и предназначен

глоссарий.

Введение

С понятием алгоритма были знакомы еще ученые древних ци-

вилизаций. Алгоритм Евклида нахождения наибольшего обще-

го делителя двух целых чисел был описан в книге VII «Начал»

Евклида, датирующейся 330-320 гг. до н.э. Прообраз метода ис-

ключения Гаусса был описан в китайском источнике «Девять

книг по арифметике» (202 г. до н.э. — 9 г.н.э.). Эратосфен

(приблиз. 276–194 гг. до н.э.) предложил алгоритм проверки

простоты числа, получивший впоследствии название решета

Эратосфена.

Тем не менее, различные формализации понятия алгорит-

ма были предложены только в середине 30-х годов прошлого

столетия, когда и стала складываться современная теория ал-

горитмов. Ее возникновение связано с точным математическим

определением такого, казалось бы, интуитивно ясного понятия

как алгоритм. Потребность в этом определении была вызва-

на внутренними тенденциями развития математики, посколь-

ку некоторые открытые проблемы заключались в выяснении

существования (или несуществования) алгоритма для реше-

ния конкретных задач. Например, знаменитая 10-я проблема

Гильберта заключалась в вопросе о существовании процедуры

нахождения целочисленных корней произвольного многочлена

от нескольких переменных с целыми коэффициентами

Именно потенциальная возможность несуществования ал-

горитмов решения некоторых проблем потребовала формаль-

В 1970 году Ю.В. Матиясевич доказал, что эта проблема алгоритми-

чески неразрешима.

10 Введение

ного определения алгоритма. Почти одновременно в 30-х

годах XX в. независимо (и в разных формах) рядом круп-

ных математиков того времени — А. Тьюрингом ([Tur36]),

А. Черчем ([Chu36]), Э. Постом ([Pos36]), К. Геделем, С. Клини

и др. — было формализовано понятие вычислимости. Э. Пост

и А. Тьюринг определили алгоритм как вычисление на аб-

страктных машинах. При этом вычислимость функции пони-

малась как вычислимость на машинах Тьюринга. К. Гедель,

А. Черч и С. Клини определили понятие вычислимости по-

другому, на языке введенных ими арифметических функций,

которые теперь называются частично рекурсивными функци-

ями. Позднее А.А. Марков ввел понятие нормального алгориф-

ма

. Однако выяснилось, что все эти определения, совершенно

различные по форме, описывают некое единое математическое

понятие — понятие алгоритма.

Доказательство алгоритмической неразрешимости многих

известных задач и получение ряда других отрицательных ре-

зультатов послужило хорошим стимулом развития классиче-

ской теории алгоритмов. По-видимому, не случайно эти иссле-

дования непосредственно предшествовали появлению первых

компьютеров в 40-х годах прошлого века, поскольку теория

алгоритмов явилась теоретическим фундаментом для созда-

ния и использования вычислительных машин. В рамках клас-

сической теории алгоритмов задаются вопросами о разрешимо-

сти различных задач, при этом вычислительная сложность ал-

горитмов принципиально не исследуется. Однако многие дис-

кретные задачи, очевидно, алгоритмически разрешимы с помо-

щью переборных алгоритмов. Такие прямые переборные алго-

ритмы уже при небольших исходных параметрах вынуждены

просматривать огромное (обычно экспоненциальное) число ва-

Именно алгорифмы Маркова, а не алгоритмы Маркова. Так назвал

их А.А.Марков, подчеркивая арабо-греческую этимологию слова. К тому

же в дореволюционных российских энциклопедиях и учебниках исполь-

зовалось слово алгориφм. В настоящее время слово алгорифм иногда ис-

пользуют математики так называемой «питерской школы».