Дасгупты, Пападимитриу, Вазирани «Алгоритмы»

С. Дасгупта, Х. Пападимитриу, У. Вазирани

Алгоритмы

DRAFTПеревод с английского А. С. Куликова под редакцией А. Шеня

Москва Издательство МЦНМО 2014

УДК 510.5 ББК 22.18я73

Д20
Д20	Дасгупта С. и др.
	Алгоритмы / С. Дасгупта, Х. Пападимитриу, У. Ва-
	зирани; Пер. с англ. под ред. А. Шеня. –– М.: МЦНМО,
	2014. –– 320 с.
DRAFT
	ISBN 978-5-4439-0236-4
	В этой книге, предназначенной для студентов математических и
	программистских специальностей (начиная с младших курсов), по-
	дробно разбираются основные методы построения и анализа эффек-
	тивных алгоритмов. Она основана на лекциях авторов в универси-
	тетах Сан-Диего и Беркли. Выбор материала не вполне стандартный
	(скажем, о сортировке и структурах данных, связанных с хранени-
	ем упорядоченных множеств в сбалансированных деревьях, не гово-
	рится, зато обсуждаются линейное программирование и даже кван-
	товые вычисления). Авторы старались выделить основные идеи и из-
	лагать доказательства наглядно, не злоупотребляя формализмом, но
	и не жертвуя математической строгостью; оригинальный подход ав-
	торов делает книгу интересной не только студентам, но и опытным
	преподавателям. Каждый раздел снабжён упражнениями.
		ББК 22.18я73
	Thanslation from the English language edition:
Algorithms by Sanjoy Dasgupta, Christos Papadimitriou, and Umesh Vazirani
	Copyright ffi 2006 McGraw-Hill
	All Rights Reserved
ISBN 978-0073523408 (англ.)		ffi McGraw-Hill, 2006.
ISBN 978-5-4439-0236-4		ffi МЦНМО, перевод на русск. яз., 2014.

Оглавление

DRAFT
Предисловие . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Глава 0. Пролог . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
0.1.	Книги и алгоритмы . . . . . . . . . . . . . . . . . . . . . . . . . .
0.2.	Вычисление чисел Фибоначчи . . . . . . . . . . . . . . . . . . .
0.3.	O-символика . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Упражнения . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Глава 1. Числовые алгоритмы . . . . . . . . . . . . . . . . . . . . . . . .
1.1.	Элементарная арифметика . . . . . . . . . . . . . . . . . . . . .
1.2.	Арифметика сравнений . . . . . . . . . . . . . . . . . . . . . . .
1.3.	Проверка чисел на простоту . . . . . . . . . . . . . . . . . . . .
1.4.	Криптография . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
1.5.	Универсальное хеширование . . . . . . . . . . . . . . . . . . .
Упражнения . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Глава 2. Метод «разделяй и властвуй» . . . . . . . . . . . . . . . . . .
2.1.	Умножение чисел . . . . . . . . . . . . . . . . . . . . . . . . . . .
2.2.	Рекуррентные соотношения . . . . . . . . . . . . . . . . . . . .
2.3.	Сортировка слиянием . . . . . . . . . . . . . . . . . . . . . . . .
2.4.	Медианы . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2.5.	Умножение матриц . . . . . . . . . . . . . . . . . . . . . . . . . .
2.6.	Быстрое преобразование Фурье . . . . . . . . . . . . . . . . . .
Упражнения . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Глава 3.	Декомпозиция графов . . . . . . . . . . . . . . . . . . . . . . .
3.1.	Откуда берутся графы . . . . . . . . . . . . . . . . . . . . . . . .
3.2.	Поиск в глубину в неориентированных графах . . . . . . . .
3.3.	Поиск в глубину в ориентированных графах . . . . . . . . .
3.4.	Компоненты сильной связности . . . . . . . . . . . . . . . . .
Упражнения . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Глава 4. Пути в графах . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
4.1.	Расстояния в графе . . . . . . . . . . . . . . . . . . . . . . . . . .
4.2.	Поиск в ширину . . . . . . . . . . . . . . . . . . . . . . . . . . . .
4.3.	Длины рёбер . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
4.4.	Алгоритм Дейкстры . . . . . . . . . . . . . . . . . . . . . . . . .

. . .	6
. . .	7
. . .	7
. . .	8
. . .	10
. . .	12
. . .	15
. . .	15
. . .	19
. . .	27
. . .	34
. . .	38
. . .	42
. . .	49
. . .	49
. . .	52
. . .	54
. . .	56
. . .	59
. . .	61
. . .	74
. . .	83
. . .	83
. . .	85
. . .	89
. . .	92
. . .	96

. . . 105

. . . 105

. . . 106

. . . 108

. . . 108

4	Оглавление
4.5.	Реализации очередей с приоритетами . . . . . . . . . . . . . . . .	113
4.6.	Кратчайшие пути и отрицательные веса . . . . . . . . . . . . . . .	114
4.7.	Кратчайшие пути в ациклических графах . . . . . . . . . . . . . .	119
Упражнения . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .		120
Глава 5. Жадные алгоритмы . . . . . . . . . . . . . . . . . . . . . . . . . . . .		127
5.1.	Покрывающие деревья . . . . . . . . . . . . . . . . . . . . . . . . . .	127
5.2.	Кодирование Хаффмана . . . . . . . . . . . . . . . . . . . . . . . . . .	139
5.3.	Формулы Хорна . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .	143
DRAFT
5.4.	Покрытие множествами . . . . . . . . . . . . . . . . . . . . . . . . . .	146
Упражнения . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .		148
Глава 6. Динамическое программирование . . . . . . . . . . . . . . . . .		156
6.1.	Ещё раз о кратчайших путях в ориентированных ациклических
	графах . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .	156
6.2.	Наибольшая возрастающая подпоследовательность . . . . . . . .	157
6.3.	Расстояние редактирования . . . . . . . . . . . . . . . . . . . . . . .	158
6.4.	Задача о рюкзаке . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .	162
6.5.	Произведение матриц . . . . . . . . . . . . . . . . . . . . . . . . . . .	167
6.6.	Кратчайшие пути . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .	170
6.7.	Независимые множества в деревьях . . . . . . . . . . . . . . . . . .	174
Упражнения . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .		175
Глава 7. Линейное программирование и сводящиеся к нему задачи		184
7.1.	Введение в линейное программирование . . . . . . . . . . . . . .	184
7.2.	Потоки в сетях . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .	193
7.3.	Паросочетания в двудольных графах . . . . . . . . . . . . . . . . .	200
7.4.	Принцип двойственности . . . . . . . . . . . . . . . . . . . . . . . . .	201
7.5.	Игры с нулевой суммой . . . . . . . . . . . . . . . . . . . . . . . . . .	205
7.6.	Симплекс-метод . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .	209
7.7.	Эпилог: вычисление значения схемы . . . . . . . . . . . . . . . . .	217
Упражнения . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .		220
Глава 8. NP-полные задачи . . . . . . . . . . . . . . . . . . . . . . . . . . . . .		230
8.1.	Задачи поиска . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .	230
8.2.	NP-полные задачи: определения и примеры . . . . . . . . . . . . .	241
8.3.	Свед´ения . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .	244
Упражнения . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .		260
Глава 9. Решение NP-полных задач . . . . . . . . . . . . . . . . . . . . . . .		267
9.1.	Оптимизация перебора . . . . . . . . . . . . . . . . . . . . . . . . . .	268
9.2.	Приближённые алгоритмы . . . . . . . . . . . . . . . . . . . . . . . .	271
9.3.	Эвристики локального поиска . . . . . . . . . . . . . . . . . . . . . .	280
Упражнения . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .		287
Глава 10. Квантовые алгоритмы . . . . . . . . . . . . . . . . . . . . . . . . .		291
10.1. Кубиты, суперпозиция, измерения . . . . . . . . . . . . . . . . . . .		291

Оглавление

5

10.2. План действий . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 296 10.3. Квантовое преобразование Фурье . . . . . . . . . . . . . . . . . . . 297 10.4. Периодичность . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 299 10.5. Квантовые схемы . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 301 10.6. Периодичность и разложение на множители . . . . . . . . . . . . 305 10.7. Квантовый алгоритм разложения на множители . . . . . . . . . . 306 Упражнения . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 309

Исторические замечания и книги для дальнейшего чтения . . . . . .	312
DRAFT
Указатель имён и терминов . . . . . . . . . . . . . . . . . . . . . . . . . . . .	314

Предисловие

DRAFTЭта книга возникла из записок лекций, которые авторы читали в последние десять лет [английское издание вышло в 2008 году] в университетах Беркли и Сан-Диего для студентов младших курсов. За это время курс сильно изменился. Отчасти это было связано с тем, что студенты редко имеют опыт строгих рассуждений и нам пришлось с этим считаться, отчасти –– с эволюцией самого предмета лекций. Выбор материала определялся логикой рассказа, и мы не претендуем на энциклопедичность и отступили от традиций, включив некоторые темы. Мы старались выделять идеи, лежащие в основе доказательств, и не злоупотреблять формализмом –– в надежде, что это сделает математическую строгость более привлекательной.

Следуя истории, мы решили начать курс (часть I) с алгоритмов, работающих с числами. Начав со знакомых понятий (простота, разложение на множители), мы затем рассматриваем алгоритмы умножения, сортировки и поиска медианы, основанные на приёме «разделяй и властвуй». Также мы рассматриваем алгоритм быстрого преобразования Фурье. Далее (часть II) мы переходим к традиционным темам вводного курса: структурам данных и графам. Здесь мы стремимся показать, как совсем короткие алгоритмы (несколько строк кода) позволяют решать довольно сложные задачи. При желании следовать традиционной схеме курса можно начать с части II (которая не зависит от предыдущего материала, не считая «Пролога») и отложить материал части I «на потом» (если останется время).

В частях I и II мы излагаем некоторые приёмы, полезные для задач определённых классов («разделяй и властвуй», жадные алгоритмы). В части III мы переходим к более общим методам и разбираем динамическое программирование (постаравшись изложить его более понятно, чем это часто делается) и линейное программирование (симплекс-метод, двойственность, представление комбинаторных задач в виде задач линейного программирования). Наконец, в части IV мы обсуждаем алгоритмически трудные задачи (NP-полно- та, эвристические алгоритмы, квантовые вычисления). В итоге мы замыкаем круг, вернувшись к задаче разложения на множители и разобрав квантовый алгоритм Шора.

Параллельные основному тексту врезки посвящены истории развития области, практическим приложениям (особенно связанным с интернетом) и математическим отступлениям.

Глава 0

Пролог

DRAFTКуда ни посмотри –– везде компьютеры. Торговля, развлечения, производство, медицина –– всё это выглядело бы совсем иначе без компьютеров. Даже генералы и президенты понемногу учатся ими пользоваться. Из двух технологических прорывов, сделавших все эти чудеса возможными, один очевиден –– это колоссальный прогресс в области технологии разработки и производства микросхем, которые становятся меньше, быстрее и экономичнее с каждым годом.

Но наша книга посвящена другому прорыву –– изобретению эффективных алгоритмов. Он не столь заметен, но не менее важен и не менее увлекателен, так что бросайте свои дела –– и вперёд, за нами!

0.1. Книги и алгоритмы

В 1448 году в немецком городе Майнце ювелир по имени Иоганн Гутенберг придумал, что можно печатать книги, набирая текст из отдельных литер. Мрачному средневековью пришёл конец, науки и искусства расцвели, затем началась индустриальная революция и всё такое. Многие историки видят в этом заслугу Гутенберга –– и действительно, мир был бы совсем другим, если книги нужно было бы переписывать вручную. Но другие отводят главную роль менее заметному изобретению –– возникновению алгоритмов.

Сейчас все с младых ногтей приучены к десятичной системе. А между тем Гутенберг записал бы 1448 год как MCDXLVIII. Сможете ли вы вычислить сумму MCDXLVIII+DCCCXII? а произведение этих чисел? Скорее всего Гутенберг, как человек умный и образованный, мог складывать и вычитать небольшие числа на пальцах; для более серьёзных вычислений он должен был бы обратиться к специалистам, умеющим считать на абаке.

Десятичная система, изобретённая в Индии около 600 года н. э., произвела революцию в технологии вычислений: она позволила с помощью всего лишь десяти символов компактно записывать большие числа и выполнять арифметические операции как последовательность простых шагов. Несмотря на все эти преимущества, десятичная система распространилась по миру не сразу –– как всегда, сказались расстояния, языковые и культурные барьеры. Большую роль в её распространении сыграла книга, написанная по-арабски в IX веке. Её автор жил в Багдаде, звали его аль-Хорезми, и в ней он описал методы сложения, умножения и деления в десятичной системе (и даже вычисления квадратных корней и цифр числа ). Методы эти требовали аккуратного («механического») выполнения чётко описанных действий и гарантировали

8 Глава 0. Пролог

получение правильного результата –– короче говоря, они были алгоритмами, как мы сказали бы сейчас. Но само слово алгоритм появилось много лет спустя и произошло как раз от имени аль-Хорезми.

С этого времени десятичная система и основанные на ней численные алгоритмы играют центральную роль. Без них не было бы ни науки, ни техники, ни быстрого развития промышленности и торговли. А когда появились компьютеры, позиционная система (правда, двоичная, а не десятичная) легла в основу представления чисел в их памяти. Новые алгоритмы самого раз-

ного рода появляются каждый год, всё больше расширяя возможности ком- DRAFTпьютеров –– и меняя наш мир до неузнаваемости.

0.2. Вычисление чисел Фибоначчи

В последовательности Фибоначчи

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, ‌

каждый член равен сумме двух предыдущих:
Fn =	81,n 1 +	F	n 2	,	n = 1,
	F				n > 1,
	<0,				n = 0.
	:

Это одна из самых знаменитых последовательностей –– почти как последовательность степеней двойки. Числа Фибоначчи растут почти так же быстро, как степени двойки: например, F30 больше миллиона, а в десятичной записи F100 уже 21 цифра. Число Fn равно примерно 20,694n (см. упражнение 0.3).

Как вычислять числа Фибоначчи?

Экспоненциальный алгоритм

Буквально следуя рекурсивному определению, получаем следующий алгоритм.

функция Fib1(n)

если n = 0: вернуть 0

если n = 1: вернуть 1

вернуть Fib1(n 1) + Fib1(n 2)

Написав алгоритм, мы должны спросить себя: 1. Корректен ли он?

2. Каково время его работы (в зависимости от n)? 3. Существует ли более быстрый алгоритм?

В нашем случае первый вопрос не имеет особого смысла, поскольку алгоритм повторяет определение. Для ответа на второй вопрос обозначим через T (n) время работы (число операций) алгоритма Fib1 на входе n. Ясно, что для n ¶1 значение T (n) не больше двух, а далее T (n) = T (n 1) + T (n 2) + 3

0.2. Вычисление чисел Фибоначчи

9

(два рекурсивных вызова, две проверки значения n и сложение). Сравнив это неравенство с определением Fn, мы видим, что T (n) ¾ Fn. Таким образом, время работы алгоритма растёт экспоненциально с ростом n, что означает, что он практически бесполезен на практике. Например, для вычисления F200 понадобится около 2138 операций. На это даже суперкомпьютеру, выполняющему 40 триллионов операций в секунду, понадобится 292 секунд.

Есть такое наблюдение, называемое законом Мура: каждый год компьютеры становятся быстрее примерно в 1,6 раз. Представим себе, что такое продлится ещё некоторое время и посмотрим, много ли чисел Фибоначчи нам удастся вычислить. Время работы алгоритма Fib1 растёт примерно как 20,694n 1,6n. Если сегодня компьютер позволяет вычислить F100, то через год мы вычислим F101, через два года –– F102. И так далее, по одному числу в год.

Итак, наш алгоритм корректен, но безнадёжно неэффективен. Существует ли более быстрый алгоритм?

Полиномиальный алгоритм

Попытаемся понять, почему же алгоритм Fib1 такой медленный. На рис. 1 показано дерево рекурсивных вызовов. Видно, что алгоритм много раз вычисляет одно и то же. Разумнее было бы сохранять промежуточные результаты (значения F0, F1, ‌, Fn 1):

	функция Fib2(n)
	если n = 0: вернуть 0
	создать массив		f [0‌n]
	f [0] 0, f [1]		1
	для i от 2 до n:
	f [i]	f [i 1] + f [i 2]
	вернуть	f [n]
	Рис. 1. Дерево рекурсивных вызовов
					Fn
			Fn 1				Fn 2
		Fn 2		Fn 3		Fn 3		Fn 4
	F	F	F	F	F	F	F	F
DRAFTn 3 n 4 n 4 n 5 n 4 n 5 n 5 n 6
					.

10	Глава 0. Пролог

Как и в случае предыдущего алгоритма, корректность здесь очевидна. Каково же время работы? Цикл повторяется n 1 раз, и время работы алгоритма Fib2 линейно по n. Переход от экспоненциального к полиномиальному (в данном случае линейному) времени работы радикально меняет дело. Теперь F200 и даже F200000 можно вычислить без труда1: секрет успеха –– в правильном алгоритме.

Более детальный анализ

DRAFTДо сих пор мы оценивали число операций в алгоритме и неявно предполагали, что все операции занимают одно и то же время. Это удобно, хотя на деле каждая операция разбивается процессором на ещё более мелкие шаги и количество и длительность этих шагов могут быть разными.

Есть в нашем анализе и более существенное упрощение: мы считали сложение за один шаг, не учитывая размеры слагаемых. Это разумно, если числа помещаются в один регистр (32 или 64 бита). Однако в двоичной записи n-го числа Фибоначчи около 0,694n битов, и они очень скоро перестают помещаться. Арифметические операции на числах произвольной длины не могут быть выполнены за один шаг. Поэтому нужно более детально оценить время работы алгоритма.

В главе 1 мы увидим, что сложение двух n-битовых чисел требует времени, пропорционального n (сложение в столбик). Значит, алгоритм Fib1, выполняющий около Fn сложений, требует около nFn элементарных операций. Для алгоритма Fib2 время пропорционально n2, что по-прежнему не так много.

Может быть, есть ещё более быстрый алгоритм? Оказывается, что да: см. упражнение 0.1.

0.3. O-символика

Оценивая примерное время работы алгоритма, важно понимать, чем мы пренебрегаем, а за чем следим (чтобы не пропустить главное и не копаться в несущественных деталях). Распространённый подход –– оценивать время работы алгоритма (как функцию от размера входа) с точностью до ограниченных множителей. При этом ошибка в два раза или даже в тысячу раз считается допустимой, в то время как разница между n и n2 считается существенной.

При таком подходе нет надобности разбираться в длительности элементарных операций, хотя в реальных процессорах разные команды разлагаются в последовательность микрокоманд разной длины и занимают разное время. Важно только, что время любой операции ограничено некоторой константой. Другое следствие того же подхода: если, скажем, алгоритм выполняет 5n3 + 4n + 3 элементарных операций на входе размера n, мы можем отбросить слагаемые 4n и 3 (которые при больших´ n малы по сравнению с 5n3). Более того, мы можем отбросить и множитель 5 в старшем слагаемом (через несколько лет компьютеры станут в пять раз быстрее) и сказать, что время

1О разнице между полиномиальным и экспоненциальным ростом см. историю в главе 8.