Архив WinRAR / Книги, блеать / Абрамов С.А. Вычислительная сложность алгоритмов (конспект лекций)

часовой стрелке, то нам непременно потребуется отсортировать начальные значения x1, x2 , ... , xn . Мы уже знаем, что Ω(nlog n) является асимптотической оценкой снизу

для алгоритмов сортировки, поэтому для алгоритмов построения выпуклой оболочки будет верна оценка Ω(nlog n) . Таким образом, если известно, что одна задача решается

медленно, то, сведя другую задачу к первой, можно показать, что она тоже решается медленно.

Рассмотрим две задачи: умножение булевых матриц и транзитивно-рефлексивное замыкание графа. Можно показать, что эти задачи являются эквивалентными. Таким образом, если мы

научимся находить транзитивное замыкание за O(n2 ) , то и булевые матрицы мы сможем умножать за O(n2 ) .

Действительно, если A — матрица смежности исходного графа (A порядка n), тогда матрица смежности транзитивно-рефлексивного замыкания графа будет равна

A* = I A A2 ... An = (I A)n		(максимальная длина пути — n)
Пусть у нас есть две матрицы: A и B. Построим по ним ещё одну матрицу по следующему
правилу:
0	A	0
	0
0		B
	0
0		0

и рассмотрим граф, для которого эта матрица будет являться матрицей смежности. Теперь посмотрим, что будет транзитивно-рефлексивным замыканием этого графа. Замыканием будет граф со следующей матрицей смежности:

I	A	AB
	I
0		B
	0	I
0

Тем самым, для получения произведения AB достаточно прочитать верхний правый угол получившейся матрицы.

Обычно для построения транзитивно-рефлексивного замыкания используют алгоритм Уоршела со сложностью O(n3 ), где за O скрывается совсем не большая константа (порядка 3), и ещё одним преимуществом алгоритма является небольшой расход памяти.

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

менее она должна допускать оценку O(nc ) , где c — некоторая константа. Вообще говоря,

оценка с O предполагает выполнение соответствующего неравенства начиная с некоторого n, но мы будем считать, что для всех n выполняется T (n) ≤ p(n) , где p(n) — полином.

Полиномиальной сложности алгоритмы — это искусство. Вопрос существования полиномиального алгоритма, решающего ту или иную задачу, отнюдь не праздный. От экспоненциальной сложности стараются перейти к полиномиальной. Сторонники получения какого-нибудь алгоритма не стремятся получить алгоритм с полиномиальной сложностью. Основной своей задачей они считают получение алгоритма, а снижение показателя сложности — это вопрос времени.

Рассмотрим следующий пример. В линейном программировании существует симплексметод, позволяющий решать задачи, сложность которого не является полиномиальной. Несколько лет назад был найден алгоритм решения задач линейного программирования с

51

полиномиальной сложностью, но коэффициенты полинома были настолько велики, что никакого продвижения не было. Симплекс-метод обладает субэкспоненциальной

сложностью: растёт медленнее, чем d n , но быстрее, чем любой полином. Например,

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

Сосредоточимся на задачах распознавания, т.е. задачах, ответом на которые является «да» или «нет». Более конкретно рассмотрим задачу распознавания языков, которая ставится следующим образом: есть некоторый алгоритм A, множество слов в алфавите A обозначим

через A* и выбирается их подмножество L A* — язык в алфавите A. Оговорим ещё одно допущение: что брать за размер входа? Для массивов мы брали число элементов, для квадратных матриц — порядок (что не то же самое, что число элементов). Здесь входом

будут слова x, а за размер входа возьмём его длину x — число букв в этом слове

(неотрицательное целое). Определимся с операциями. Т.к. любой конечный алфавит можно свести к A = {0, 1} (все слова в алфавите A можно кодировать последовательностями из

нулей и единиц). Тогда в качестве операций можно рассматривать битовые операции и битовую сложность. Не обязательно рассматривать двухсимвольный конечный алфавит, можно и более богатый, только операции в этом случае будут задаваться соответствующими таблицами. Примечательно, что таким способом суженная задача вызывает проблемы более осязаемые и более привычные.

Пусть алгоритмы распознавания языков, имеющие полиномиальную сложность, образуют класс P. В некоторых изданиях к P относят все алгоритмы с полиномиальной сложностью, что было бы не совсем правильным. Класс полиномиальных алгоритмов правильнее было бы обозначить через Poly. Вернёмся к нашему определению класса P, как классу алгоритмов распознавания имеющих полиномиальную сложность. Задача определения принадлежности алгоритма к классу P является достаточно сложной.

Нас будут интересовать предикаты, определённые на словах. Можно говорить не о «задачах» из класса P, а о предикатах.

Рассмотрим наряду с P другой класс алгоритмов — NP.

Определение. Будем говорить, что предикат (задача) u(x) NP , если существуют такие полиномы p и q и такой предикат R(x, y) , что u(x) = y A* , y ≤p(x )R(x, y) и предикат R(x, y) имеет полиномиальную временную сложность, ограниченную q(x + y ).

Соотношение для u(x) можно записать и в другой форме: y A* (y ≤ p(x ) R(x, y)).

Обозначение NP происходит от non deterministic polynomer. Слово y в этом случае называется сертификатом x (в некоторой литературе — «подсказкой»).

Класс NP замечателен тем, что легко проверить принадлежность к нему. Рассмотрим это на примерах. Но для начала мы должны определится с тем, как будем записывать слова в нашем алфавите. Эти способы, вообще говоря, могут быть весьма разнообразными. Для примера рассмотрим ситуацию, когда алфавитом являются целые положительные числа. В этом случае для их записи мы можем использовать палочную систему (рисовать столько палочек, какое число мы хотим изобразить) или позиционную систему счисления. Сложность в разных случаях будет различной.

Рассмотрим задачу определения, является ли заданный граф гамильтоновым. Гамильтоновым называю граф, если в нём существует путь, проходящий через все вершины ровно по одному разу. Когда мы рассматриваем произвольный граф и хотим определить, является ли он гамильтоновым, мы можем записать граф матрицей смежности (при

52

необходимости разделяя строчки некоторым разделителем). Не трудно видеть, что сформулированная задача распознавания гамильтонового графа принадлежит классу NP. Чтобы доказать это достаточно указать сертификат, в качестве которого в данном случае можно взять сам гамильтонов путь. Уж как-нибудь за не очень большое (полиномиальное) время проверить, является ли он путём и является ли он гамильтоновым, мы вполне сможем.

Задача определения составного числа так же принадлежит классу NP. Сертификатом в этом случае будет делитель. Очевидно, что за короткое время мы сможем проверить, является ли он делителем или нет.

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

Важным понятием является понятие полиномиальной сводимости.

Определение. Будем говорить, что задача (предикат) u1 полиномиально сводится к задаче u2 , если существует функция f : A* → A* , применимая к любому слову из A* , время вычисления которой ограничено p0 (x ) , и такая, что истинность u1(x) эквивалентна истинности u2 (f (x)).

Обозначение: u1 ≤P u2

Необходимо отметить важный момент: если u1 полиномиально сводится к задаче u2 и u2 P , тогда u1 P . В этом утверждение есть одна тонкость: новый аргумент f (x) может

иметь другую длину, нежели x , но она тоже будет ограничена полиномиально (т.к. время вычисления ограничено полиномиально).

Возникает проблема: верно ли, что P = NP ?

Важными понятиями являются NP-трудный и NP-полный предикаты.

Определение. NP-трудным называется предикат, к которому полиномиально сводится любой предикат из NP.

Определение. NP-полным называется NP-трудный предикат, принадлежащий классу NP.

Вырисовывается очень удобный путь для решения обозначенной проблемы в положительном смысле: нужно найти NP-трудную задачу и предложить для неё полиномиальный алгоритм.

Доказано, что NP-полной задачей является задача определения выполнимости булевой формулы. Формула является выполнимой, если существует такой набор значений переменных, входящих в формулу, что результатом формулы является истина. Всего

различных наборов для n переменных будет 2n . До сих пор не известно, существует ли алгоритм, который за полиномиальное время позволяет установить выполнимость, но известно, что задача является NP-полной, а значит NP-трудной.

Как уже было сказано, задача о гамильтоновом графе является NP-полной. Это наводит на мысль, что P ≠ NP (что, вообще говоря, не доказано и по сей день).

Если вы трудитесь над какой-то проблемой и пытаетесь найти для её решения полиномиальный алгоритм, но вдруг узнаёте, что она является NP-трудной (известная NP- задача полиномиально сводится к вашей), тогда лучше считать, что для вашей задачи нет полиномиального алгоритма.

53

Для задачи распознавания простоты числа, если входом считать m =ν(n) — битовую длину n, 3 года назад был предложен Индийский алгоритм (разработанный тремя индийскими математиками) с полиномиальной сложностью, допускающий оценку O(m13 ). Только для

решения означенной проблемы этот результат ровным счётом ничего не даёт. Если бы им удалось доказать обратное, что не существует полиномиального алгоритма распознавания простоты числа, тогда сразу следовало бы, что P ≠ NP , т.к. задача определения простоты числа полиномиально сводится к задаче распознавания составного числа, которая принадлежит классу NP.

Уместно будет заметить, что мы разнесли задачи распознавания простоты числа и распознавания составного числа, хотя эти задачи являются обратными. Если для задачи определения составного числа мы можем показать, что она принадлежит классу NP, то для обратной задачи распознавания простоты числа мы этого показать не можем (какой тут сертификат?). Следует отметить, что не обязательно из того, что u(x) NP следует, что u

(обратная задача к u ) NP . Поэтому будем говорить, что предикаты, отрицание которых принадлежит классу NP, принадлежат классу Co-NP.

Отметим, что многие из утверждения, которые мы сделали недавно, доказываются при помощи машины Тьюринга (МТ). Но какое это имеет отношение к нам? А может быть так, когда мы имеем дело с МТ, полиномиального алгоритма нет из-за перемещений по ленте. В равнодоступной адресной машине (РАМ) таких затрат нет и кажется, что существование полиномиальных алгоритмов на РАМ более вероятно. Но это не так, потому как путешествия по ленте не очень сильно удлиняют вычисления (в худшем случае сложность возведётся в квадрат, но изначально полиномиальная сложность полиномиальной же и останется). Следовательно, если нет полиномиального алгоритма для МТ, то и для РАМ его тоже нет.

Более подробно про алгоритмы полиномиальной сложности и найти более подробные доказательства сформулированных утверждений можно найти в книге М.Гэри и Д.Джонсона «Вычислительные машины и трудно решаемые задачи».

В заключение приведём несколько примеров NP-полных задач.

Примеры.

1.«Задача редактирования слова». Имеется алгоритм A, два слова x, y A* и k N .

Алгоритм заключается в определении, можно ли из x получить y не более, чем за k операций, в качестве которых допустимыми являются вычеркивание символа и перестановка двух соседних символов. Доказано, что эта задача NP-полная.

2.Имеется квадратная матрица порядка n из нулей и единиц и натуральное число k. Алгоритм заключается в определении, можно ли все единицы покрыть не более чем k прямоугольниками, не покрывая при этом ни одного нуля. Эта задача тоже является NP-полной.

3.«Задача о рюкзаке». Задано конечное множество U. Для каждого u U определён размер s(u) и цена v(u) . Заданы b, k N , и спрашивается, можно ли выбрать подмножество U ′ U такое, что

∑s(u) ≤ b , ∑v(u) ≥ k .

u U′ u U′

Эта задача тоже является NP-полной.

54

4. Задан набор пар целых чисел (ai , bi ) Z2 , i =1, 2, ... , n , bi ≥ 0 . Рассматривается

n

полином вида ∑ai zbi и спрашивается, есть ли у него корень в комплексной

i=1

плоскости, лежащий на единичной окружности ( z =1 ). Эта задача является NP- трудной, но принадлежность её к классу NP, не установлена.

55

Задачи

1. Доказать равенства:

n			n			, n N
n =	2		+	2

a = − −a , a R

Решение.				1) В			случае чётного n
n			n			= k	+ k = 2k = n . Если
	2		+	2
n			n			= k	+ k +1 = 2k +1 = n .
			+	2
	2

решение тривиально: n = 2k n2 = n2

n нечётно, т.е.	n			= k;
	n = 2k +1	2

= n = k2

n = k +12

2) Если a Z , то очевидно, что a = a; −a = −a , что доказывает равенство. Если a не

является целым, то найдется такое целое число n и такое 0 < ε <1 , что a = n +ε . Тогда

a = n +ε = n +1, −a = −n −ε = −n −1 a = − −a . 2. Доказать равенство:

k, n N, k >1 logk n +1 = logk (n +1)

Решение. Не трудно видеть, что для данного n всегда найдётся такое целое число m, что выполняется оценка: k m ≤ n < k m+1 . Тогда logk n = m . Так как k целое, то

km < n +1 ≤ km+1 , откуда m < logk (n +1) ≤ m +1 logk (n +1) = m +1 что и доказывает равенство.

3.Считая в алгоритме сортировки простыми вставками операцию обмена a ↔ b реализованной следующим образом: с := a; a := b; b := c, определить, чему равны TI1 и TI2 .

4.Имеется железнодорожный разъезд с тупиком (см. рис.), в одной части которого находятся 2n вагонов двух типов: n белых и n чёрных. Порядок вагонов не определён. Имеется 3 операции перемещения вагонов: 1) МИМО, 2) В (в тупик) и 3) ИЗ (из тупика). Требуется привести алгоритм сортировки вагонов, в результате работы которого с другой стороны будет составлена последовательность из 2n вагонов, цвета которых чередуются.

МИМО

ИЗ В 2n

Решение. Требуется переправить вагоны справа на лево, изменив их порядок так, чтобы цвета вагонов чередовались. Предлагаемый алгоритм заключается в следующем: если цвет первого вагона формируемого состава не имеет значения, то первый вагон просто проходит МИМО. Если цвет первого вагона важен, то с помощью тупика это всегда можно сделать. Далее, пока имеются вагоны справа, проверяем на совпадение цветов последний вагон слева с первым вагоном справа. Если их цвета не совпадают,

56

выполняем операцию МИМО, после чего проверяем наличие вагонов в тупике. Если в тупике имеются вагоны, то выполняем операцию ИЗ и переходим к следующему вагону справа. При совпадении цветов, отправляем очередной вагон в тупик операцией

В.

На псевдокоде предлагаемый алгоритм выглядит следующим образом: исходный состав справа обозначен массивом ai, каждый элемент которого принимает значения чёрный или белый. Операция not меняет значение цвета с белого на чёрный и наоборот, z — текущее количество вагонов в стеке, k — цвет последнего вагона формируемого состава слева. Основная идея алгоритма заключается в том, что в тупике в один момент времени не могут находиться вагоны разных цветов и в конце каждой итерации цикла если в тупике есть вагоны, то цвет их совпадает с цветом последнего вагона формируемого состава.

z := 0; k := a1; for i = 2 to 2n do

if k = ai then

В;

z := z + 1; else

МИМО;

k := ai;

if z > 0 then

ИЗ;

z := z – 1; k := not k;

fi

fi

od

Не трудно видеть, что сложность представленного алгоритма по количеству операций МИМО, В, ИЗ T = O(n) , но из постановки задачи ясно, что сложность любого

алгоритма, решающего задачу, есть Ω(n) , следовательно, сложность представленного алгоритма T = Θ(n) .

5.Путник стоит перед бесконечной стеной в обе стороны. Известно, что на расстоянии n шагов в одну из сторон находится дверь. Требуется привести алгоритм нахождения двери путником, сложность которого по числу шагов составляла бы O(n) .

Решение. Очевидный алгоритм заключается в следующем: путник на первой итерации делает один шаг в одну из сторон, затем возвращается и делает один шаг уже в другую сторону и снова возвращается. На второй итерации ситуация повторяется, но уже совершается по два шага в обе стороны. На третьей итерации — три шага и т.д. пока не будет обнаружена дверь. Сложность такого алгоритма составляет

2 (1+ 2 +...+ n) = n(n +1) = O(n2 ) , в связи с чем, данный алгоритм не подходит.

Предыдущий алгоритм базировался на арифметической прогрессии, что и дало квадратичную сложность. Попробуем оценить сложность подобного алгоритма, базирующегося на геометрической прогрессии. Пусть по прежнему на первой итерации совершается по одному шагу в одну и другую сторону, тем самым первый член прогрессии будет равен 1. Выберем произвольное q N, q >1 и на каждой k-й

итерации будем совершать qk−1 шагов в обе стороны. Исходя из этих данных, получаем, что количество требуемых алгоритму итераций не превзойдёт logq n +1 ,

57

тогда суммарное количество шагов не превзойдёт 2	qlogq n+1 −1	= 2	qn −1	= O(n) , что и
	q −1		q −1
требовалось.

6. Доказать асимптотику сложности алгоритма пробных делений (TD), приняв за размер

входа битовую длину n: T *		2	m
	(m =ν(n))= Θ		2 .
TD

Решение. При фиксированной длине числа n, равной m, получаем ограничение на значения n: 2m−1 ≤ n < 2m . Согласно постулату Бертрана, в интервале (2m−1, 2m ) найдётся простое число n, для определения простоты которого алгоритму пробных делений потребуется в точности n −1 делений. Следовательно, получаем оценки на TTD* (m) :

2m−1 −1 < TTD* (m) < 2m −1										2m−1 −2 < TTD* (m) < 2m −1
1		m			m				m
	2	2 −2 < T *		(m) < 2	2 −1 T *			2
							(m) = Θ		2 .
2			TD			TD

7.f (n) = amnm +... + a1n + a0 , am ≠ 0 . Доказать утверждения:

1)f (n) = O(nk ) k ≥ m ;

2)f (n) = Ω(nk ) k ≤ m ;

3)f (n) = Θ(nk ) k = m .

Решение.

a.

f (n) = O(nk ) C > 0 : f (n) ≤ Cnk 0 ≤ lim

f (n)

≤ C k ≥ m .

nk

n→∞

b.

f (n) = Ω(nk ) C > 0 : f (n) ≥ Cnk 0 ≤ lim

nk

≤

1

k ≤ m .

f (n)

n→∞

C

c.

f (n) = Θ(nk ) c

,c

> 0 : c nk ≤ f (n) ≤ c

nk c

≤ lim

f (n)

≤ c

k = m .

1

2

1

2

1

n→∞

nk

2

8. Аддитивной цепочкой называется последовательность вида n1 < n2

< ... < nk , для которой

выполнены два условия: 1)

n1 =1 ; nk = n

и 2) i :1 < i ≤ k

s,t :1 ≤ t ≤ s < i такие, что

nt + ns = ni . Через l(n) обозначим минимальную длину аддитивной цепочки.

Доказать: l(ab) ≤ l(a) +l(b) −1,

a,b N .

Решение. Рассмотрим минимальную аддитивную цепочку, последним элементом

которой является a: 1 = n1′ < ... < nl′(a) = a .

Минимальная аддитивная цепочка для b в

свою очередь выглядит следующим образом: 1 = n1′′< ... < nl′′(b) = b . Помножим каждый

элемент цепочки для b на a и получим ещё одну цепочку, которая, вообще говоря, не является аддитивной: a = n1′′′< ... < nl′′(′b) = ab . Не трудно видеть, что последний элемент

	′			′′′		′	′′′
цепочки {n } равен первому элементу цепочки {n }, т.е.						nl(a)	= n1 . Составим из первой
и	третьей	цепочек	одну,	объединив	их	по	равному	элементу:
		l (b)
		64474448
1 = n1′ < ... < nl′(a) = n1′′′< ... < nl′′(′b) = ab .				Не трудно	видеть,		что так	составленная

1442443

l (a)

58

последовательность является аддитивной цепочкой, но не обязательно является минимальной. Откуда следует, что l(ab) ≤ l(a) +l(b) −1.

9. Дан некоторый отрезок и число n >1. Требуется привести алгоритм построения отрезка

1n от данного со сложностью O(log n) .

Решение. Пусть дан отрезок AB. Для деления отрезка на n воспользуемся теоремой Фалеса. Для этого из одного конца данного отрезка выпустим луч и отложим на нём n раз отрезок произвольной длины (пробный отрезок). Получим набор точек A1, A2 , ..., An .

После чего проведём прямую, параллельную An B , через точку A2 , тогда, согласно теореме, она отсечёт на отрезке AB требуемый отрезок.

An

...An−1

A2

A1

AB 1n AB

Если откладывать пробный отрезок по одному n раз, то сложность такого алгоритма будет порядка n, и он нам не подойдёт. Чтобы добиться логарифмической сложности следует поступить следующим образом: после отложения 2-х пробных отрезков сразу находим A4 , отложив от A2 отрезок AA2 . Затем сразу можно найти A8 , отложив два

раза отрезок AA4 и т.д. по степеням двойки. Отсюда получаем логарифмическую сложность, и оценка O(log n) будет верна.

10.Используя оценку функции Эйлера π(n) > 13 lnnn доказать, что сложность в среднем алгоритма пробных делений TTD не является полиномиальной.

11.Найти сложность в среднем по количеству обменов для алгоритма сортировки выбором, исключая обмены вида xk ↔ xk .

12.Дан массив x1,..., xn . Алгоритм нахождения минимального элемента выглядит следующим образом:

m:=x1;

for i=2 to n do

if xi<m then m:=xi fi

od

Найти сложность в среднем по числу присваиваний.

Решение. Разложим Πn следующим образом:

Πn = An1 +... + Ann ,

59

где событие Ai заключается в том, что минимальный элемент массива располагается на

n

i-м месте. Не трудно видеть, что P

(Ai

) =

(n −1)!

= 1 . Введём случайную величину ξ

n

,

n

n

n!

n

E(ξn

Ani )Pn (Ani ) . Если событие

показывающую затраты алгоритма,

n

тогда T

(n) = Eξn = ∑

Ani имеет место,

то ξn при этом

i=1

ξn = i E(ξn

Ani )= i

принимает

значение

T (n) = Eξn = 1 ∑i = n +1 .

n

n i=1

2

13. Имеются кости домино, которые можно класть либо рядом, либо строить навес:

...

l

Какой максимальной длины можно построить навес?

14.Дан массив. Описать алгоритм нахождения m-го минимального алгоритма с использованием операции разбиения и исследовать его сложность.

15.Доказать, что количество пар (i, j) , попадающих в стек в алгоритме быстрой сортировки (отложенные задачи), меньше длины начального массива n .

16.Доказать, что если считать сложность рандомизированного алгоритма быстрой сортировки в количестве обращений к генератору случайных чисел, то она равна Θ(n) .

Решение. Если воспользоваться формулировкой алгоритма быстрой сортировки с разрезальщиком, то за каждое разрезание он будет брать ровно 1 рубль, и для

1

n

2 n−1

′

∑(Eχi−1

+Eχn−i )=1+

сложности

в

среднем

= Eχn

=1+

∑χk .

получаем: TQS (n)

n

i=1

n k=0

Обозначим

′

(n) = Eχn

= f (n) , тогда получим:

TQS

f (n) =1+

n−1

2 ∑ f (k)

n k=0

n−1

nf (n) = n + 2∑ f (k)

k=0

n−2

(n −1) f (n −1) = n −1+ 2∑ f (k)

k=0

Вычитаем из первого второе и получим: nf (n) −(n +1) f (n −1) =1

f (n)

−

f (n −1)

=

1

. Введём функцию

ϕ(x) =

f (x)

, тогда предыдущее выражение

n

n(n +1)

1+ x

n +1

перепишется в виде: ϕ(n) −ϕ(n −1) =

1

, ϕ(0) = 0

n(n +1)

n

1

n 1

1

1

1

ϕ(n) = ∑

= ∑

−

=1−

, откуда

f (n) = (1+ n) 1−

= n = Θ(n) .

k +1

n +

1

n +1

k =1 k(k +1)

k =1 k

17.Как реализовать генератор случайных чисел (ГСЧ), чтобы вероятность выпадения числа 0 ≤ k ≤ N −1 была αk (на базе стандартного ГСЧ выдающего числа из (0,1) с

равномерным распределением).

60