Главная Промышленная автоматика.

УПРАЖНЕНИЯ

10.1. Выпишите все правильные последовательности шагов НМТ, изображенной на рис. 10.1, для входа 10101. Допускает ли эта НМТ указанный вход?

10.2. Неформально опишите НМТ или недетерминированную программу на Упрощенном Алголе, допускающую

(а) множество таких цепочек 10«10». . .10*, что ir=i, для некоторых l<r<s<,

(б) множество таких цепочек хсу, что х и у принадлежат {а, Ь}* и X - подцепочка в у,

(в) множество цепочек, как в (б), но х - подпоследовательность в у.

10.3. Опишите РАМ-программу, моделирующую недетерминированную РАМ-программу.

10.4. Пусть М обозначает (тХп)-матрицу из нулей и единиц. Напишите программу на Упрощенном Алголе, которая находила бы такую наименьшую (sXn)-подматрицу S матрицы М, что если ми, /1=1, то S[k, j]=\ для некоторого l<fe<s. Какова временная сложность вашей программы?

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

(а) n (в) 2»,

(б) п-п+1, (г) п1.

10.6. Покажите, что если одноленточная НМТ с емкостной сложностью S («), имеющая s состояний и t ленточных символов, допускает слово длины п, то она допускает его не более чем за sS («)/*"> шагов.

*10.7. Покажите, как вычислить на РАМ значение булевой формулы за время 0(п).

10.8. Покажите, что язык, состоящий из булевых функций, не являющихся тавтологиями NP-полон.

10.9. Покажите, что задача об изоморфизме подграфу ("Изоморфен ли данный неориентированный граф G некоторому подграфу данного неориентированного графа G?") NP-полна. Указание: Воспользуйтесь NP-полнотой задачи о клике или о гамильтоновом цикле.

10.10. Покажите, что задача о ранце ("Существует ли для данной последовательности целых чисел S=ti, ia,. . ., in и целого

1) Тавтологией называется булева формула, принимающая значение 1 на всех наборах значений ее переменных.



числа подпоследовательность в S, сумма членов которой равна к}") NP-полна. Указание: Используйте задачу о точном покрытии.

*10Л1. Покажите, что задача о разбиении (задача о ранце из упр. 10.10 с 20=2*) NP-полна.

10Л2. Покажите, что задача о коммивояжере ("По данному графу G с целочисленными весами ребер найти цикл, который включает каждый узел и сумма весов ребер которого не превосходит к") NP-полна.

**10ЛЗ. Покажите, что NP-полна задача распознавания следующего свойства: регулярное выражение без * (т. е. такое, в котором употребляются только операции + и •) не представляет всех цепочек некоторой фиксированной длины. Указание: Трансформируйте в эту задачу о регулярных выражениях задачу КНФ-выполнимости.

**10Л4. Покажите, что NP-полна задача распознавания следующего свойства: регулярное выражение над алфавитом {0} не представляет О*.

**10Л5. Пусть G=(V, Е) - неориентированный граф и Wj, Ua - два различных узла. Разрезом для Vi и Wa называется такое подмножество SE, что любой путь между Vi и Wa содержит элемент из S. Покажите, что NP-полна задача распознавания того, есть ли в графе такой разрез размера к для Vi и Wa, что обе части графа содержат равные количества узлов.

**10Л6. Одномерная задача об упаковке состоит в следующем. Пусть С=(У, Е) - неориентированный граф и к - положительное целое число. Существует ли такая нумерация Vi, Wa,- • , узлов из V, что

2 \i-i\<k?

Покажите, что эта задача NP-полна.

**10Л7. Докажите, что задача о раскраске остается NP-полной, даже если ограничить к числом 3, а наибольшую степень каждой вершины - числом 4.

**10Л8. Выполните упр. 10.17 для планарных графов. Указание: Покажите, что планарный граф на рис. 10.14 можно раскрасить в три цвета только тогда, когда Vi и w[ раскрашены одинаково, а также Wa и Wa раскрашены одинаково. Скомбинируйте этот результат с вашим ответом на упр. 10.17.

*10Л9. Докажите NP-полноту задачи о клике, непосредственно представляя вычисления НМТ вместо того, чтобы трансформировать ее из 3-КНФ-выполнимости.




Рис. 10.14. Планарный граф.

*10.20. Рассмотрим ориентированный граф с двумя выделенными узлами S н t. Припишем каждому ребру целочисленную "пропускную способность". Можно построить максимальный поток из s в /, многократно находя путь из s в t и увеличивая поток вдоль него до максимума, разрешаемого пропускными способностями его ребер. Покажите, что задача нахождения наименьшего множества путей, на которых следует увеличивать поток, NP-полна. Указание: Рассмотрите граф типа изображенного на рис. 10.15 и свяжите эту задачу с задачей о ранце.

**10.21. Задача о расписании работ с равными временами выполнения состоит в следующем. Даны множество работ S-(Ji,. . ., J„), лимит времени t, число процессоров р и частичный порядок < на S. Существует ли расписание работ из S, требующее не более / единиц времени, т. е. такое отображение / из S в {1, 2,. . ., /}, что в каждое целое число отображается не более р работ, и если J<.J, то f{J)<-f{J) Покажите, что эта задача NP-полна.

10.22. Покажите, что каждая из задач, перечисленных в теореме 10.2, принадлежит классу ЛЗ-ТШЕ.

10.23. Пусть pi{x) и paix) - полиномы. Покажите, что некоторый полином для каждого х принимает значение, большее pi (ра (х)).

10.24. Выпишите выражение fjyftt, введенное в доказательстве теоремы 10.3, для 8{qu, Ху)={{дз, Х, L), (q„ Х, R)}.

**10.25. Постройте алгоритм полиномиальной сложности для проверки 2-выполнимости.





0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 [145] 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174

0.0019