Крючкова Е.Н. Основы математической логики и теории алгоритмов

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

совпадающие симптомы, поэтому задан набор C подмножеств множества A, пред-

ставляющий двоичные тесты. Имеется некоторое натуральное число m, ограничива-

ющее число тестов, которые должен пройти один больной.

Вопрос: существует ли такое множество тестов C

⊆ C, |C

| ≤ m, что для любой

пары (a

, a

) возможных диагнозов из A имеется некоторый тест, различающий a

, т.е. такой тест c ∈ C, для которого |{a

, a

} ∩ c| = 1.

Задача 3. Доминирующее множество. Задан граф G = (V, E) и положительное

целое число K ≤ |V |.

Вопрос: существует ли в графе G доминирующее множество вершин V

, состоящее

не более, чем из K элементов, такое, что |V

| ≤ K и для всех вершин u ∈ V \ V

существует в G дуга (u, v) ∈ E, связывающая вершину u с какой–либо вершиной v

из множества V

Задача 4. Изоморфизм подграфу. Заданы два графа G

= (V

, E

) и G

= (V

, E

Вопрос: содержит ли граф G

подграф, изоморфный графу G

? Иначе говоря,

существуют ли подмножества V и E, V ⊆ V

, E ⊆ E

, такие, что |V | = |V

|, |E| = |E

и такая взаимно–однозначная функция f : V → V

, что ребро (u, v) ∈ E тогда и

только тогда, когда (f(u), f(v)) ∈ E

Задача 5. Изоморфный остов. Задан граф G = (V, E) и дерево T = (V

, E

Вопрос: верно ли что граф G содержит остовное дерево, изоморфное T ?

Задача 6. Коммивояжер. Задано множество C = {c

, c

, ..., c

} городов. Между

каждой парой городов задано расстояние d (c

, c

), являющееся натуральным числом.

Задано также положительное целое число K.

Вопрос: Существует ли маршрут длины не более K, проходящий через все города

из C? Иными словами, существует ли такая перестановка городов ⟨c

n(1)

, c

n(2)

, ..., c

n(m)

⟩,

что

m−1

∑

i=1

d(c

n(i)

, c

n(i+1)

) + d(c

n(m)

, c

n(1)

) ≤ K.

Задача 7. Сельский почтальон. Задан граф G = (V, E), длина l(e) каждого ребра

e ∈ E и положительное целое число K.

Вопрос: Существует ли в G цикл, сумма длин ребер которого не меньше K?

Задача 8. Упаковка множеств. Задан набор C конечных множеств и положи-

тельное целое число K ≤ |C|.

Вопрос: Верно ли, что множество C содержит по крайней мере K непересекаю-

щихся подмножеств?

Замечание: задача остается NP –полной даже при |c

| ≤ 3 для всех c

∈ C. С

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

| ≤ 2 для всех c

∈ C.

Задача 9. Расщепление множества. Задан набор C конечных подмножеств мно-

жества S.

Вопрос: Существует ли такое разбиение множества S на два подмножества S

, что ни одно подмножество из C не содержится целиком ни в S

, ни в S

Замечание: задача остается NP –полной даже при |c

| ≤ 3 для всех c

∈ C. Задача

решается за полиномиальное время, когда |c

| ≤ 2 для всех c

∈ C (такая задача

называется раскрашиваемость графа в два цвета ).

Задача 10. Упаковка в контейнеры. Задано конечное множество

U = {u

, u

, ..., u

}

121

предметов, для каждого из которых задано натуральное число s(u

) — линейный

размер предмета u

. Даны также положительное целое число B — вместимость кон-

тейнера и число K — количество контейнеров.

Вопрос: Существует ли такое разбиение множества U на K непересекающихся

подмножеств U

, U

,...,U

, что сумма размеров предметов из каждого подмножества

не превосходит B?

Задача 11. Квадратичные сравнения. Заданы положительные целые числа a, b

и c.

Вопрос: Существует ли положительное целое число x < c, такое, что x

= a(mod b)?

Замечание: задача остается NP–полной, даже если в условии даны разложение

числв b на простые множители и решение данного сравнения по всем простым моду-

лям, входящим в разложение числа b.

Задача 12. Составление кроссворда. Заданы конечное множество слов W и мат-

рица A из нулей и единиц размером n × n.

Вопрос: Можно ли составить кроссворд из слов множества W , чтобы слова впи-

сывались в клетки матрицы A, соответствующие нулям в ней?

Задача 13. Отсутствие тавтологии. Задано булевское выражение E на мно-

жестве переменных U = {u

, u

, ..., u

}. В выражении используются логические опе-

рации ∧ (и), ∨ (или), ¬ ( не), → (следует).

Вопрос: Верно ли, что E не тавтология, т.е. существует ли такой набор значений

переменных u

, u

, ..., u

, что E принимает значение "ложь"?

Задача 14. Программы с рекурсивными функциями. Задано конечное множе-

ство идентификаторов функций языка Си. Для каждой функции приводится тело

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

Вопрос: Верно ли, что некоторая функция из множества функций A рекурсивна

и вызывает не менее k других функций?

Задача 15. Составление учебного расписания. Заданы конечное множество H

рабочих часов, множество C преподавателей, множество D учебных дисциплин. Для

каждого преподавателя c

∈ C дано подмножество A(c

) ⊆ H, называемое допусти-

мыми часами для преподавателя c

. Для каждой дисциплины d

∈ D дано подмноже-

ство A(d

) ⊆ H, называемое допустимыми часами для дисциплины d

. Для каждой

пары (c

, d

) ⊆ C × D задано число r(c

, d

), называемое требуемой нагрузкой.

Вопрос: Существует ли учебное расписание, обслуживающее все дисциплины?

Другими словами, существует ли функция

f : C × D × H → {0, 1},

где f (c

, d

, h

) = 1 означает, что преподаватель c

занимается дисциплиной d

момент времени h

Задача 16. Динамическое распределение памяти. Задано конечное множество

A = {a

, a

, ..., a

} элементов динамических данных языка Си. Известен требуемый

размер памяти в байтах s(a

), который необходимо выделить для каждого элемента

∈ A. Для каждого данного a

∈ A известно время n(a

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

выделение памяти для этого данного, и время f (a

) окончания работы с ним. Кро-

ме того, известно положительное целое число M — максимальный размер в байтах

области памяти, в которой размещаются все данные.

Вопрос: Существует ли для множества данных A допустимое распределение па-

мяти? Иначе говоря, существует ли такая функция

g : A → {1, 2, 3, ..., M},

122

что для каждого элемента a

∈ A выделен непрерывный участок памяти

[g(a

), g(a

) + s(a

) − 1] ,

целиком содержащийся в допустимой области [1, M], причем в одно и то же время

разные данные не могут занимать пересекающиеся участки памяти.

Задача 17. Дерево с заданными вершинами. Дан граф G = (V, E), подмножество

вершин V

⊆ V и целое число K ≤ |V

| − 1.

Вопрос: существует ли поддерево в G, содержащее все вершины из V

и имеющее

не более K ребер?

Задача 18. Квадратные диофантовы уравнения. В заключение рассмотрим за-

дачу, иллюстрирующую процесс получения различного спектра задач — от класса P

до неразрешимых.

Задача "квадратные диофантовы уравнения"состоит в следующем. Пусть заданы

положительные целые числа a, b, c.

Вопрос: существуют ли положительные целые числа x и y, такие , что ax

+by = c?

Эта задача является NP –полной. Задача решения диофантова уравнения ax

= c

разрешима в целых числа за полиномиальное время для произвольных k. Общая

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

целыми коэффициентами " неразрешима.

5.6 Методы решения NP-полных задач

В соответствии с представлением алгоритма решения NP –полных задач с помо-

щью алгоритма угадывания и алгоритма проверки программы, реализующие NP–

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

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

варианты решений на глубину 1 и оставшуюся задачу меньшего размера.

Рассмотрим в качестве примера решение следующей задачи. Пусть имеется про-

извольное клеточное поле и плитки размером 1×2. Необходимо покрыть данное поле

такими плитками. Очевидно, что произвольное клеточное поле можно представить

матрицей, в которой клетки заданного поля имеют следующие значения:

а) 0 — свободны,

б) число n > 0 — клетка занята плиткой с номером n,

в) число -1 — не принадлежащие полю клетки.

Сначала все свободные клетки заняты нулями, а все клетки, не подлежащие за-

полнению, числом -1. Приведем пример подлежащего заполнению поля:

0 0 -1 -1 -1

-1 0 -1 -1 -1

-1 0 0 0 0

-1 -1 0 0 0

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

номера положенных туда плиток. Поскольку на каждом шаге придется рассматри-

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

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

и столбец, как показано на рисунке:

123

1 1 -1 -1 -1 -1

-1 2 -1 -1 -1 -1

-1 2 3 4 4 -1

-1 -1 3 5 5 -1

-1 -1 -1 -1 -1 -1

Тогда для размещения очередной плитки необходимо сначала найти первую сво-

бодную клетку. Попытка положить плитку вправо является успешной, если, во–

первых, справа есть пустая клетка, а, во–вторых, если дальнейшее решение на следу-

ющих уровнях рекурсии позволит выполнить покрытие. Попытка положить плитку

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

выполняется аналогично. Задача решена успешно, если все попытки на всех уровнях

рекурсии оказались успешными. Если полный перебор укладки плиток не привел к

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

указанные действия.

// укладка плиток 1*2 на заданное поле

#include <stdio.h>

#include <STDLIB.H>

#define MAXK 20

int Q[MAXK+1][MAXK+1]; // клеточное поле

int M, N; //число строк и столбцов

FILE *in = fopen("plitka.in","r");

FILE *out= fopen("plitka.out","w");

int Set(int n)

// уложить одну очередную плитку

{

int i,j,in,jn,flag=0;

for (i=0; (i<M) && (flag==0); i++)

for(j=0; (j<N) && (flag==0); j++)

if (Q[i][j]==0){flag=1; in=i; jn=j;}

if (flag==0) return 1; // все замостили - задача решена

if ( (Q[in][jn+1]!=0) && (Q[in+1][jn]!=0) ) return 0;

//нет решения, т.к. изолированная плитка

if (Q[in][jn+1]==0) // можно положить горизонтально

{

Q[in][jn]=n+1; Q[in][jn+1]=n+1;

if (Set(n+1)) return 1; // успешное решение

Q[in][jn]=0; Q[in][jn+1]=0; // возврат при неудаче

}

if (Q[in+1][jn]==0) // можно положить вертикально

{

Q[in][jn]=n+1; Q[in+1][jn]=n+1;

if (Set(n+1)) return 1; // успешное решение

Q[in][jn]=0; Q[in+1][jn]=0; // возврат при неудаче

}

return 0; // нет решения

124

}

int main(void)

{

int i,j;

char a[MAXK+1] ; // для ввода строки занятости поля

fscanf(in,"%d %d\n",&M,&N);

for (i=0; i<M; i++)

{

fscanf(in,"%s\n",&a);

for(j=0; j<N; j++)

if (a[j]==’.’)Q[i][j]=0; else Q[i][j]=-1;

}

for (i=0; i<M; i++) Q[i][N]=-1;

for (j=0; j<N; j++) Q[M][j]=-1; //выполнили обрамление

if (Set(0)==0) fprintf(out,"Нет решения\n");

else {

for (i=0; i<M; i++)

{

for(j=0; j<N; j++) fprintf(out,"%3d",Q[i][j]);

fprintf(out,"\n");

}

fclose(in); fclose(out);

return 0;

}

Исходные данные представлены следующим образом. Первую строку исходного

файла plitka.in занимают два числа M и N — число строк и столбцов матрицы

(M, N ≤ 20). Далее файл содержит M текстовых строк. Каждый символ строки

представляет собой знак ". если поле свободно, и знак "*" при занятом поле.

Результат работы программы записывается в файл plitka.out и представляет со-

бой содержимое сформированной матрицы Q.

5.7 Контрольные вопросы к разделу

1. Чем класс P отличается от класса NP ?

2. Что представляет собой множество NP \ P ?

3. Чем различаются задачи класса P и NP –полные задачи?

4. Приведите пример NP –полной задачи.

5. Приведите пример задачи класса P .

6. Какие способы доказательства NP –полноты Вы знаете?

7. Сформулируйте задачу о дизъюнкциях.

8. Приведите пример доказательства NP –полноты методом сводимости.

9. Как построить алгоритм решения задачи класса NP –полных задач?

10. Что называется размером задачи?

11. Как определяется временная сложность NP–полных задач?

12. Как вычислить временную сложность для заданной программы на языке Си?

125

13. Чему равна временная сложность задачи о рюкзаке?

14. Как вычислить рост размера решаемых задач при замене существующего ком-

пьютера на новый, скорость которого в 100 раз выше скорости старого компьютера?

15. Что означает запись формулы временной сложности: T(n) = O(2

16. Для решения некоторой задачи имеется две программы. Первая из них имеет

временную сложность T

(n) = 250n

, вторая — сложность T

(n) = 3

. Какая про-

грамма лучше? Всегда ли является предпочтительной только одна из них?

17. Как вычисляется временная сложность фрагмента программы, содержащего

цикл?

18. Как вычисляется временная сложность фрагмента программы, содержащего

оператор условия?

19. Приведите пример фрагмента программы, имеющего временную сложность

полинома второй степени.

20. Приведите пример функции временной сложности, для которой увеличение

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

дачи, решаемой за некоторое фиксированное время.

5.8 Упражнения к разделу

Задание. Доказать NP–полноту поставленной задачи. Написать программу ре-

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

5.8.1 Задача 3 – выполнимость

Дан набор C = {c

, c

, ..., c

} дизъюнкций на некотором конечном множестве

логических переменных U = {u

, u

, ..., u

}, причем каждая дизъюнкция построена

точно из трех переменных. Вопрос: существует ли на U такой набор значений истин-

ности, при котором выполняются все дизъюнкции из C?

Решение. Очевидно, что задача "3 – выполнимость" есть просто ограничен-

ный вариант задачи "выполнимость в которой каждая индивидуальная задача име-

ет ровно три переменных в каждой дизъюнкции. Чтобы показать, что задача "3–

выполнимость" является NP –полной, достаточно задачу "выполнимость" полиноми-

ально свести к задаче "3 – выполнимость". Для этого нужно каждую произвольную

дизъюнкцию свести к набору трехэлементных дизъюнкций.

Пусть имеется задача "выполнимость". Это значит, что имеется набор дизъ-

юнкций D = {d

, d

, ..., d

} на некотором множестве логических переменных W =

, w

, ..., w

}. Новый набор дизъюнкций будет строиться путем замены каждой

отдельной дизъюнкции w

∈ W эквивалентным набором дизъюнкций из трех пере-

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

переменных Z.

Исходное множество D может содержать следующие дизъюнкции:

а) короткие дизъюнкции, содержание одну или две переменных;

б) дизъюнкции, содержащие ровно три переменных; эти дизъюнкции оставим без

изменения;

в) длинные дизъюнкции, содержащие более трех переменных.

Рассмотрим сначала короткие дизъюнкции. Введем в множество дополнительных

переменных две переменные a

и a

. Вместо короткой исходной дизъюнкции d

из

126

одной переменной w

( d

= w

) в новое множество дизъюнкций включим четыре

дизъюнкции:

∨ a

Очевидно, что исходная дизъюнкция d

= w

будет истинна тогда и только тогда, ко-

гда истинны все перечисленные выше дизъюнкции. Аналогично для короткой дизъ-

юнкции d

, состоящей из двух переменных, в новое множество дизъюнкци включим

две дизъюнкции:

∨ a

которые истинны тогда и только тогда, когда истинна d

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

ных. Наша задача — разбить их на более короткие дизъюнкции с использованием

дополнительных переменных. Это также легко сделать, если каждой дизъюнкции

∨ w

... ∨ w

k−2

∨ w

k−1

∨ w

поставим в соответствие множество дизъюнкций

∨ w

∨ y

∨ w

∨ y

∨ w

∨ y

. . .

k−3

∨ w

k−2

∨ y

k−2

∨ w

k−1

∨ w

Переменные y

, y

, ..., y

k−2

являются уникальными для каждой исходной дизъюнк-

ции.

Для того, чтобы убедиться, что эта сводимость полиномиальная, достаточно заме-

тить, что число новых трехэлементных дизъюнкций ограничено полиномом степени

l m , l = |D|, m = |W |. Таким образом, любую задачу "выполнимость" мы полино-

миально свели к задаче "3–выполнимость". Из NP –полноты задачи "выполнимость"

следует NP –полнота задачи "3-выполнимость". Таким образом, доказательство NP –

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

ритма решения этой задачи.

NP –полнота задачи означает необходимость реализации полного перебора значе-

ний переменных. Значением каждой переменной является 0 или 1. Для организации

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

разрядов, сколько имеется двоичных переменных. Начиная со значения 0 этого длин-

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

значения соответствующих логических переменных. Увеличение на 1 следует пре-

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

произойдет, когда появится единица переноса в следующий ("лишний") разряд.

Каждую трехэлементную дизъюнкцию будем представять номерами трех пере-

менных, составляющих эту дизъюнкцию. Если переменная входит в дизъюнкцию

с отрицанием, номер переменной будет иметь знак минус. Исходную информацию

127

прочитаем из файла. Исходная информация - это число переменных, число дизъ-

юнкций и сами дизъюнкций. Результат работы тоже запишем в файл. Результатом

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

сутствии решения. Таким образом, поставленную задачу можно решить с помощью

следующей программы.

//задача 3-выполнимость

#include <stdio.h>

#include <STDLIB.H>

#define MAXP 1000 //максимальное число переменных

#define MAXD 10000 // максимальное число дизъюнкций

FILE * in=fopen("input.txt","r"); // файл с исходными данными

FILE * out=fopen("output.txt","w"); // файл результатов

int nd, np; // исходные данные: число дизъюнкций и переменных

unsigned char p[(MAXP+7)/8]; // значение переменных

int d[MAXD][3]; // дизъюнкции

int GetP(int ip)

// получить значение переменной с номером ip

{

int k,j,i=1; // i - маска выделения переменной из байта

j=ip/8; k=ip%8; // j - номер байта

i=i<<k;

if (p[j] & i) return 1;

return 0;

}

int Next(void)

// получить следующий набор значений переменных

// возвращает 1, если следующий набор существует (не нулевой)

{

int a, j=0; // номер очередного байта

int i=1; // единица переполнения

do {

a=p[j]+i;

if(a&0xff00){ p[j]=0; i=1; }

else { p[j]=a; i=0; }

j++;

}while(i);

if (GetP(np)) return 0; // все варианты перебрали

return 1;

}

int Diz(void)

// вычислить значения всех дизъюнкций

{

int i,res,a,b,c,pa,pb,pc;

for (i=0; i<nd; i++)

{

128

a=d[i][0]; pa=GetP(abs(a)-1); if (a<0) pa=!pa;

b=d[i][1]; pb=GetP(abs(b)-1); if (b<0) pb=!pb;

c=d[i][2]; pc=GetP(abs(c)-1); if (c<0) pc=!pc;

res = pa || pb || pc;

if (res==0) return 0;

}

return 1;

}

int main(void)

{

int i,j,k,a,b,c,res;

fscanf(in,"%d %d",&np, &nd);

for (i=0; i<nd; i++)

{

fscanf(in,"%d %d %d",&a,&b,&c); // ввели одну дизъюнкцию

d[i][0]=a;d[i][1]=b;d[i][2]=c;

}

for (i=0; i<(np+7)/8; i++) p[i]=0; // обнулили все переменные

while (!(res=Diz()) && Next());

if (res) for (i=0; i<np; i++) fprintf(out,"%d ",GetP(i));

else fprintf(out,"Нет решения\n");

fclose(in);

fclose(out);

return 0;

}

Перейдем теперь к оценке временной сложности. Введем сначала размер зада-

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

задачи — число переменных и число дизъюнкций. Из этих двух переменных число

дизъюнкций является вторичным по отношению к числу переменных, т.к. именно

от их количества зависит и число дизъюнкций, и время решения задачи. Поэтому в

качестве размера выберем число переменных.

Обозначим n — количество переменных, m — количество дизъюнкций. Тогда вре-

мя работы программы равно

T (n) = a + bm + dn + c · f(n),

где a — фиксированное время, затраченное на ввод двух переменных; bm + dn —

суммарное время ввода m дизъюнкций и вывода n значений переменных; f(n) – ко-

личество различных вариантов значений набора логических переменных; c —- фик-

сированное время проверки значения одной трехэлементной дизъюнкции. Число ва-

риантов f (n) = 2

, тогда

T (n) = a + bm + dn + c · f(n) = a + bm + dn + c2

= O(2

В программе значение n ограничено числом разрядов двоичного целого числа:

#define MAXP 1000

unsigned char p[(MAXP+7)/8]; .

129

Однако, порядок временной сложности показывает, что при больших размерах n

задача не будет решена за разумное время. Поэтому предложенная выше реализация

преследует лишь иллюстративные цели, демонстрируя программистский прием пе-

речисления всевозможных значений переменных. Для практических целей решение

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

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

приемлемое время. Поэтому вместо массива p[(MAXP + 7)/8] достаточно использо-

вать переменную типа int.

unsigned int p; // глобальная переменная

...

// по всем 16 - ти разрядам:

for (p=0; (p<=65535) && (!res)) res=Diz(); // вызов в main()

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

границы изменения переменной p = 2

−1, а не оставлять ее в виде константы 65535,

как это сделано в приведеннойм фрагменте. Приведем текст итоговой программы.

//задача 3-выполнимость

#include <stdio.h>

#include <STDLIB.H>

#define MAXP 1000 //максимальное число переменных

#define MAXD 10000 // максимальное число дизъюнкций

FILE * in=fopen("input.txt","r"); // файл с исходными данными

FILE * out=fopen("output.txt","w"); // файл результатов

int nd, np; // исходные данные: число дизъюнкций и переменных

unsigned int p; // значение переменных

int d[MAXD][3]; // дизъюнкции

int GetP(int ip)

// получить значение переменной с номером ip

{

if (p & (1<<ip) ) return 1;

return 0;

}

int Diz(void)

// вычислить значения всех дизъюнкций

{

int i,res,a,b,c,pa,pb,pc;

for (i=0; i<nd; i++)

{

a=d[i][0]; pa=GetP(abs(a)-1); if (a<0) pa=!pa;

b=d[i][1]; pb=GetP(abs(b)-1); if (b<0) pb=!pb;

c=d[i][2]; pc=GetP(abs(c)-1); if (c<0) pc=!pc;

res = pa || pb || pc;

if (res==0) return 0;

}

return 1;

130