книги / Математическая логика и теория алгоритмов. Анализ алгоритмов

Докажем обратное, что если граф G – связный, то все элементы массива A равны true. Рассмотрим две произвольные вершины vx и vy. Поскольку граф связный, между vx и vy есть путь.

1)Если этот путь не содержит других промежуточных вершин (то есть vx и vy напрямую соединены ребром), то A[x,y] становится равно true в строке 7.

2)Пусть теперь путь из vx в vy проходит через промежуточные вершины. Обозначим за s максимальный из номеров этих промежуточных вершин. Докажем, что после завершения s-й итерации цикла в строке 8 (k=s) элемент A[x,y] будет равен

true. Доказательство выполним по индукции по параметру s. База индукции: s=1. Это означает, что путь имеет вид

vx – v1 – vy (других промежуточных вершин быть не может, так как тогда максимальный из номеров был бы больше 1). Тогда при выполнении алгоритма в строке 11 при k=1, i=x, j=y получим:

if (A[x,1]&A[1,y]) then A[x,y] true.

Как было показано выше, в силу наличия ребер (vx,v1)

и(v1,vy), A[x,1]=true и A[1,y]=true. Следовательно,

иA[x,y] примет значение true.

Индукционный переход. Предположим, утверждение справедливо для всех путей, проходящих через промежуточные вершины с номерами <s. Пусть путь из vx в vy проходит через промежуточные вершины, максимальный из номеров которых равен s. Значит, путь имеет вид vx – … – vs – … – vy, при этом на путях vx – … – vs и vs – … – vy все промежуточные вершины имеют номера <s. По предположению индукции это означает, что к моменту начала s-й итерации цикла в строке 8 A[x,s]=A[s,y]=true. Тогда при выполнении алгоритма в строке 11 при k=s, i=x, j=y получим:

if (A[x,s]&A[s,y]) then A[x,y] true.

131

Учитывая полученное ранее равенство A[x,s]=A[s,y]= true, получаем, что A[x,y] примет значение true, что и требовалосьдоказать.

Итак, алгоритм isConnected имеет полиномиальную сложность и корректно решает рассматриваемую задачу T. Следовательно, T P. Учитывая, что P NP, можно также утверждать, что T NP.

Ответ: задача T принадлежит классам сложности P и NP.

Задачи для коллективного решения у доски

9. Боря и Коля только что получили премию за инновационную устремлённость. У них есть мешок денег, которые нужно разделить. В мешке лежит n предметов (монет, купюр, чеков). Для начала Боря и Коля хотят определить, возможно ли разделить деньги точно поровну. В каждом из описанных ниже сценариев определить класс получаемой задачи. В каждом случае в качестве входных данных выступает список, состоящий из n чисел, равных стоимости содержащихся в мешке предметов. Объемом входных данных считается число n. На выходе необходимо получить ответ «да» (деньги можно разделить точно поровну) либо «нет» (нельзя).

а) В мешке n монет двух различных номиналов: одни монеты стоят x долларов, а другие – y долларов (то есть во входном списке присутствуют только числа x и y).

б) В мешке n монет произвольного количества различных номиналов, но при этом каждый номинал является неотрицательной целой степенью двойки, то есть возможны номиналы 1, 2, 4 доллара и т.д.

в) В мешке n чеков, по невероятному совпадению выписанных на имя «Боря или Коля». Сумма в каждом чеке может быть любой.

132

Задачи для самостоятельной работы на занятии

10. Подмножество V вершин графа называется вершинным покрытием, если каждое ребро графа инцидентно хотя бы одной из вершин, принадлежащих V . Рассмотрим задачу T: «Даны граф G = (V, E) и число k. Определить, существует ли в графе G вершинное покрытие, состоящее из k вершин». Доказать, что задача T является NP-полной.

Задачи для самостоятельной работы дома

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

изаканчиваться в одной и той же комнате. В каждом из описанных ниже сценариев определить класс задачи, которую хочет решить директор. В каждом случае в качестве входных данных выступают число k и матрица n*n, описывающая все существующие в музее переходы (если элемент матрицы x в i-й строке

иj-м столбце положительный, значит, переход из комнаты i в комнату j существует и его длина равна x; если же элемент равен 0, то перехода нет). Объемом входных данных считается число n. На выходе необходимо получить ответ «да» (искомый маршрут существует) либо «нет» (не существует).

а) Экспонаты музея располагаются в комнатах, поэтому маршрут должен проходить через все комнаты ровно по 1 разу.

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

133

ОТВЕТЫИСОВЕТЫ

ПРАКТИЧЕСКОЕ ЗАНЯТИЕ № 3 АНАЛИЗ СЛОЖНОСТИ ЗАДАЧ

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

ккоторому относится рассматриваемая задача. К основным классам сложности относятся классы P, EXP, NP, NPC.

2.Класс P (от англ. Polynomial – полиномиальный) – это класс задач полиномиальной сложности. Задача T принадлежит классу P, если существует алгоритм α, решающий данную зада-

чу T такой, что его функция сложности tα (x) ограничена полиномом, то есть существует полином P (x) такой, что tα (x) ≤ P (x).

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

3.Класс EXP (от англ. Exponential – экспоненциальный) – это класс задач экспоненциальной сложности. Задача T принад-

лежит классу EXP, если T P, но существует алгоритм α, ре-

134

шающий данную задачу T такой, что его функция сложности

tα (x) ограничена экспонентой, то есть существует константа c такая, что tα (x) ≤ cx.

Любая экспонента растёт быстрее, чем полином, поэтому задачи из класса EXP существенно сложнее задач из класса P, так как требуют для решения существенно больше времени.

4. Класс NP (от англ. Non-deterministic Polynomial – неде-

терминированный полиномиальный) – это класс задач, которые могут быть решены за полиномиальное время на недетерминированной машине Тьюринга. Задача T принадлежит классу NP, если существует алгоритм α для недетерминированной машины Тьюринга, решающий данную задачу T такой, что время его работы на входных данных x tα (x) ограничено полиномом, то есть существует полином P (x) такой, что tα (x) ≤ P (x).

Любой детерминированный алгоритм может рассматриваться как частный случай алгоритма для недетерминированной машины Тьюринга, поэтому если задача принадлежит классу P, то она автоматически принадлежит и NP, то есть P NP. Вопрос о том, является ли это включение строгим или же P = NP, до сих пор является открытой проблемой. Однако большинство учёных и специалистов считают, что, скорее всего, включение является строгим, то есть P NP.

Если рассматриваемая задача T является задачей принятия решения (то есть ответом на задачу является одно логическое значение – true или false), то справедливо также второе определение класса NP: задача принятия решения T принадлежит классу NP, если она представима в форме

T (x) = y:(|y| Q (|x|)) & R (x, y),

где y имеет смысл «дополнительных данных», |x| и |y| – объемы входных данных и дополнительных данных соответственно, Q () – полином, а задача R P. Иными словами, задача T NP, если существуют такие дополнительные данные, знание кото-

135

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

5.Говорят, что задача T1:X1 Y1 полиномиально сводима

кзадаче T2:X2 Y2, если существуют такие алгоритмы :X1 X2

и:Y2 Y1, что:

1)x X1: (T2 ( (x))) = T1 (x),

2)сложность алгоритмов и ограничена полиномом, то

В случае если T1 и T2 являются задачами принятия решения (то есть Y1 = Y2 = {true,false}), определение немного упрощается, поскольку алгоритм преобразования выходных данных не требуется. То есть задача принятия решения

T1:X1 {true,false} полиномиально сводима к задаче при-

нятия решения T2:X2 {true,false}, если существует алгоритм :X1 X2 такой, что:

1)x X1: T2 ( (x)) = T1 (x),

2)сложность алгоритма ограничена полиномом, то есть

существует полином P такой, что t (x) P (x).

Если задача T1 полиномиально сводима к задаче T2 будем обозначать это следующим образом: T1 T2.

Основные свойства полиномиальной сводимости:

1)если T1 T2 и T2 P, то T1 P;

2)если T1 T2 и T2 NP, то T1 NP;

3)если T1 T2 и T2 T3, то T1 T3.

6. Класс NPС (от англ. Non-deterministic Polynomial Complete – NP-полный) – это класс «наиболее трудных» задач в классе NP. Задача T принадлежит классу NPC, если T NP и при этом любая задача T из класса NP полиномиально сводима к T, то есть

T NPC = (T NP) & ( T NP: T T).

136

Непосредственно из определения следует, что NPC NP. Также можно отметить, что если хотя бы для одной задачи T из класса NPC будет найден алгоритм полиномиальной сложности (то есть окажется, что T P), то в силу свойств полиномиальной сводимости это будет означать, что T NP: T P, то есть это будет означать, что P = NP = NPC. На настоящий момент ни одной такой задачи не известно, но также не доказано, что их нет. Большинство учёных и специалистов считают, что, скорее всего, P NP. В этом случае P NPC = ,

иP NPC = NP.

7.Известными задачами из класса NPC являются:

1)Задача «Выполнимость» и её модификация, задача «k-выполнимость» при k 3. Дано: булева функция f в виде КНФ (в модификации на функцию накладывается дополнительное ограничение: в каждый дизъюнкт входит ровно k литералов). Определить: выполнима ли функция f, то есть существует ли такой набор значений переменных, на которых функция принимает значение «1».

2)Задача «О клике». Дано: граф G, число k. Определить: существует ли в G полный подграф, содержащий k вершин.

3)Задача «О гамильтоновом цикле». Дано: граф G. Определить: существует ли в G гамильтонов цикл.

4)Задача «О сумме подмножества». Дано: множество натуральных чисел S = {s1, s2, …, sn} и натуральное число t. Опре-

делить: существует ли подмножество S множества S такое, что сумма его элементов равна t.

8. Пусть известна задача T0 NPC.

Если задача T NP и задача T0 полиномиально сводима к T, то T NPC.

137

ОТВЕТЫ НА ЗАДАЧИ

9.

а) Задача принадлежит классам P, NP.

Совет. Можно просто перебирать все возможные варианты, сколько монет достоинством x отдать Боре. Для каждого варианта следует пытаться добавить монеты достоинством y, чтобы получилась ровно половина от общей суммы. Если это оказалось возможно – ответ «да», если для всех вариантов оказалось невозможно – ответ «нет». Такой алгоритм не самый эффективный, но даже он имеет полиномиальную сложность.

б) Задача принадлежит классам P, NP.

Совет. Можно предложить такой алгоритм: вначале максимально поровну распределить самые дорогие монеты, затем – следующие по номиналу и т.д. Если в итоге удалось распределить монеты поровну – ответ «да». Если не удалось, то в силу особого характера номиналов монет это означает, что распределение поровну вообще невозможно – ответ будет «нет». Такой алгоритм имеет полиномиальную сложность.

в) Задача принадлежит классам NP, NPC.

Совет. Для доказательства принадлежности задачи классу NP в качестве «дополнительных данных» можно взять номера чеков, составляющих в сумме ровно половину общей суммы. Для доказательства принадлежности классу NPC в качестве «базовой» NP-полной задачи нужно взять задачу «о сумме подмножества».

10. Совет. В качестве «базовой» NP-полной задачи нужно взять задачу «о независимом подмножестве», рассмотренную в примере (задача 1).

11.

а) Совет. Рассмотреть задачу «О гамильтоновом цикле». б) Совет. Воспользоваться известным критерием сущест-

вования эйлерова цикла в графе.

138

ПРАКТИЧЕСКОЕ ЗАНЯТИЕ № 4 ПРАКТИЧЕСКАЯ РАБОТА ПО ИССЛЕДОВАНИЮ И СРАВНЕНИЮ СЛОЖНОСТИ АЛГОРИТМОВ

Цели занятия: закрепить навыки теоретической и экспериментальной оценки сложности алгоритмов; получить навык оценки сложности реальных, используемых на практике алгоритмов.

Контрольные вопросы

1.В чем суть теоретической и экспериментальной оценки сложности алгоритма? Почему для полноценного исследования алгоритма необходимо выполнять оба вида оценки сложности?

2.Какие задачи называются задачами оптимизации? Приведите пример NP-полной задачи оптимизации.

3.Какие существуют универсальные подходы к приближенному решению NP-полных задач?

4.В чём заключается задача об оптимальной одномерной упаковке («об упаковке в контейнеры»)? Какие есть алгоритмы для ее решения?

5.В чём заключается задача «о рюкзаке»? Какие есть алгоритмы для ее решения?

6.В чём заключается задача о правильной раскраске графа

вминимальное количество цветов? Какие есть алгоритмы для ее решения?

7.Даны две функции: f1 (n) = 16 n4 + 3 n + 8; f2 (n) = 3 2n + + 9 n log n. Определите порядок роста каждой из функций. У ка-

кой из этих функций порядок роста выше?

8. Пусть даны три алгоритма, функции сложности которых имеют следующий порядок роста: f 1 (n) = O (n6); f 2 (n) = = O (n log n); f 3 (n) = O (2n). Какой из этих алгоритмов является

139

наиболее эффективным, а какой – наименее эффективным? Можно ли утверждать, что наиболее эффективный алгоритм всегда (на любых входных данных) будет работать быстрее, чем наименее эффективный?

Методика решения задач

В данном занятии одна большая задача. Необходимо реализовать заданные алгоритмы решения заданной задачи в виде законченной компьютерной программы, составить отчет, подготовить презентацию и выступить с докладом о полученных результатах. Задание выполняется в группах по 2–3 человека. Участники группы распределяют роли в группе самостоятельно.

Подробное описание задания.

1.Получить задание (номер варианта) у преподавателя.

Программная часть

2.Реализовать указанные алгоритмы в виде компьютерной программы на одном из языков программирования высокого уровня (Pascal, Delphi, C, C++, C#, Java, Python). Рекомендуемый формат входных и выходных данных указан в задании (изменения возможны при согласовании с преподавателем). Проверок на корректность входных данных не требуется (считать, что все входные данные корректны). Все алгоритмы должны быть реализованы в одном проекте, но отдельные алгоритмы должны быть структурно выделены (в виде отдельных модулей, подпрограмм, классов и т.п.).

3.Дополнить программу автоматическим генератором тестов. Входные данные должны генерироваться с помощью генератора случайных чисел с учетом ограничений задачи. Также оставить возможность ввода входных данных вручную (с клавиатуры или из файла).

4.Протестировать и отладить программу.

Экспериментальная часть

5.Экспериментально определить предельные значения

объема входных данных Vmax, при которых все алгоритмы работают за приемлемое время (не более 2–3 минут на один тест).

140