WWW.MASH.DOBROTA.BIZ
БЕСПЛАТНАЯ  ИНТЕРНЕТ  БИБЛИОТЕКА - онлайн публикации
 

«1. Доказать NP-полноту задачи САМЫЙ ДЛИННЫЙ ПУТЬ: ДАННЫЕ: граф G = (V, E) и положительное целое число K |V |. ВОПРОС: имеется ли в G простой путь (т.е. путь, не проходящий дважды через одну ...»

Задачи к зачету/экзамену по курсу

“Сложность вычислений”

1. Доказать NP-полноту задачи САМЫЙ ДЛИННЫЙ ПУТЬ:

ДАННЫЕ: граф G = (V, E) и положительное целое число K |V | .

ВОПРОС: имеется ли в G простой путь (т.е. путь, не проходящий

дважды через одну вершину), состоящий из не менее чем K ребер?

2. Доказать NP-полноту задачи МИНИМАЛЬНЫЙ ЭКВИВАЛЕНТНЫЙ

ОРИЕНТИРОВАННЫЙ ГРАФ:

ДАННЫЕ: ориентированный граф G = (V, E) и положительное целое число K |E| .

ВОПРОС: существует ли ориентированный граф G = (V, E ) такой, что E E, |E | K и для каждой пары вершин u, v V в G имеется ориентированный путь из u в v тогда и только тогда, когда в G имеется ориентированный путь из u в v?

3. Доказать NP-полноту задачи ОСТОВНОЕ ДЕРЕВО ОГРАНИЧЕННОЙ СТЕПЕНИ:

ДАННЫЕ: граф G = (V, E) и положительное целое число K |V |1 .

ВОПРОС: имеется ли в G остовное дерево, в котором все вершины имеют степень не более K?

4. Доказать NP-полноту задачи РАЗБИЕНИЕ НА ГАМИЛЬТОНОВЫ

ЦИКЛЫ:

ДАННЫЕ: граф G = (V, E) и положительное целое число K |V | .

ВОПРОС: можно ли множество V разбить на k K непересекающихся подмножеств V1, V2,..., Vk так, чтобы для всех i (1 i k) каждый подграф, порожденный подмножеством Vi, содержал гамильтонов цикл?

5. Доказать NP-полноту ЗАДАЧИ КОММИВОЯЖЕРА С ОГРАНИЧЕННЫМИ РАССТОЯНИЯМИ:

ДАННЫЕ: множество C из m городов, расстояние d(ci, cj ) Z+ между каждой парой различных городов ci, cj C и положительное целое число B .



ВОПРОС: существует ли маршрут, проходящий через все города и не содержащий ребер длины, большей B? Иначе говоря, существует ли такая перестановка городов c(1), c(2),..., c(m), что d(c(i), c(i+1) ) B при 1 i m и d(c(m), c(1) ) B?

6. Доказать NP-полноту задачи УПАКОВКА МНОЖЕСТВ:

ДАННЫЕ: семейство C конечных множеств и положительное целое число K |C| .

ВОПРОС: верно ли, что ли в C имеется K непересекающихся множеств?

7. Доказать NP-полноту задачи МИНИМАЛЬНОЕ ПОКРЫТИЕ:

ДАННЫЕ: семейство C подмножеств конечного множества S и положительное целое число K .

ВОПРОС: содержит ли C покрытие множества S размера не более K, т.е. такое подсемейство C C, что |C | K и c = S?

cC

8. Доказать NP-полноту задачи МНОЖЕСТВО ПРЕДСТАВИТЕЛЕЙ:

ДАННЫЕ: семейство C подмножеств конечного множества S и положительное целое число K .

ВОПРОС: содержит ли S множество представителей для C мощности, не превосходящей K, т.е. такое подмножество S S, что |S | K и S содержит по крайней мере один элемент из каждого множества семейства C?

9. Доказать NP-полноту задачи ИЗОМОРФИЗМ ПОДГРАФУ:

ДАННЫЕ: графы G = (V1, E1 ) и H = (V2, E2 ) .

ВОПРОС: содержит ли граф G подграф, изоморфный H?

10. Доказать NP-полноту задачи НАИБОЛЬШИЙ ОБЩИЙ ПОДГРАФ:

ДАННЫЕ: графы G1 = (V1, E1 ), G2 = (V2, E2 ), и

–  –  –

12. Доказать NP-полноту задачи РЮКЗАК:

ДАННЫЕ: конечное множество A, размер s(a) Z+ и стоимость v(a) Z+ для каждого a A и положительные целые числа B и K .

ВОПРОС: существует ли подмножество A A такое, что

–  –  –

16. Доказать NP-полноту задачи МНОЖЕСТВО ВЕРШИН, РАЗРЕЗАЮЩИХ КОНТУРЫ:

ДАННЫЕ: ориентированный граф G = (V, E) и положительное целое число K |V | .



ВОПРОС: существует ли такое подмножество V V, что |V | K и любой ориентированный цикл в G проходит по крайней мере через одну вершину из V ?

Указание: свести к данной задаче задачу ВЕРШИННОЕ ПОКРЫТИЕ .

17. Доказать NP-полноту задачи ДОМИНИРУЮЩЕЕ МНОЖЕСТВО:

ДАННЫЕ: граф G = (V, E) и целое число K |V | .

ВОПРОС: cуществует ли такое подмножество V V, что |V | K и каждая вершина v V \V соединена ребром по крайней мере с одной вершиной из V ?

Указание: свести к данной задаче задачу ВЕРШИННОЕ ПОКРЫТИЕ .

18. Доказать NP-полноту задачи ТОЧНОЕ ПОКРЫТИЕ ТРЕХЭЛЕМЕНТНЫМИ МНОЖЕСТВАМИ:

ДАННЫЕ: множество X из 3q элементов и семейство C трехэлементных подмножеств множества X .

ВОПРОС: cуществует ли подсемейство C C такое, что каждый элемент из X принадлежит в точности одному подмножеству из C ?

Указание: свести к данной задаче задачу 3-СОЧЕТАНИЕ .

19. Доказать NP-полноту задачи ДЕРЕВО ШТЕЙНЕРА:

ДАННЫЕ: граф G = (V, E), подмножество R V и положительное целое число K |V | 1 .

ВОПРОС: существует ли поддерево в G, содержащее все вершины из R и имеющее не более K ребер?

Указание: свести к данной задаче задачу ТОЧНОЕ ПОКРЫТИЕ

ТРЕХЭЛЕМЕНТНЫМИ МНОЖЕСТВАМИ .

20. Доказать NP-полноту задачи ТОЧНОЕ ПОКРЫТИЕ ЧЕТЫРЕХЭЛЕМЕНТНЫМИ МНОЖЕСТВАМИ:

ДАННЫЕ: множество X из 4q элементов и семейство C четырехэлементных подмножеств множества X .

ВОПРОС: cуществует ли подсемейство C C такое, что каждый элемент из X принадлежит в точности одному подмножеству из C ?

Указание: свести к данной задаче задачу ТОЧНОЕ ПОКРЫТИЕ

ТРЕХЭЛЕМЕНТНЫМИ МНОЖЕСТВАМИ .

21. Доказать NP-полноту задачи УПОРЯДОЧЕНИЕ ВНУТРИ ИНТЕРВАЛОВ:

ДАННЫЕ: конечное множество T заданий, длительность (t) Z+, время готовности r(t) Z+ и директивный срок d(t) Z+ для каждого задания t T .

ВОПРОС: существует ли допустимое расписание для T, т.е. такое отображение : T Z+, что (t) + (t) d(t), (t) r(t) и при t = t либо (t) + (t) (t ), либо (t ) + (t ) (t)?

Указание: свести к данной задаче задачу РАЗБИЕНИЕ .

22. Доказать, что задача КЛИКА и ее переборный вариант (в данном графе требуется найти клику с наибольшим числом вершин) сводятся друг к другу по Тьюрингу .

23. Доказать, что задача ВЕРШИННОЕ ПОКРЫТИЕ и ее переборный вариант (в данном графе требуется найти вершинное покрытие с наименьшим числом вершин) сводятся друг к другу по Тьюрингу .

24. Доказать, что задача НЕЗАВИСИМОЕ МНОЖЕСТВО и ее переборный вариант (в данном графе требуется найти независимое множество с наибольшим числом вершин) сводятся друг к другу по Тьюрингу .

25. Доказать, что задача ГАМИЛЬТОНОВ ЦИКЛ и ее переборный вариант (в данном графе требуется найти гамильтонов цикл, если он существует) сводятся друг к другу по Тьюрингу .

26. Доказать, что задача ВЫПОЛНИМОСТЬ и ее переборный вариант (по данной системе клозов требуется найти набор значений истинности переменных, делающий все клозы истинными, если он существует) сводятся друг к другу по Тьюрингу .





27. Доказать, что задача 3-СОЧЕТАНИЕ и ее переборный вариант (по данному системе троек требуется найти подсистему, являющуюся трехмерным сочетанием, если оно существует) сводятся друг к другу по Тьюрингу .

28. Доказать, что задача РАЗБИЕНИЕ и ее переборный вариант (по данному множеству взвешенных элементов требуется найти его разбиение на два подмножества одинакового суммарного веса, если оно существует) сводятся друг к другу по Тьюрингу .

29. В оптимизационном варианте задачи РЮКЗАК даны конечное множество A, размер s(a) Z+ и стоимость v(a) Z+ для каждого a A и положительное целое число B. Требуется найти подмножество A A такое, что aA s(a) B, а величина aA v(a) принимает наибольшее возможное значение. Доказать, что если P = NP, то не существует приближенного полиномиального алгоритма A такого, что при некоторой константе C неравенство |OP T (x) A (x)| C верно для любого экземпляра x задачи РЮКЗАК .

30. В задаче МАКСИМАЛЬНАЯ 3-ВЫПОЛНИМОСТЬ дан набор клозов, каждый из которых включает ровно три литерала, и требуется найти набор значений истинности переменных, выполняющий наибольшее возможное число клозов. Указать приближенный полиномиальный алгоритм A такой, что для любого экземпляра x задачи МАКСИМАЛЬНАЯ 3-ВЫПОЛНИМОСТЬ выполняется неравенство A (x) 8 OP T (x) .






Похожие работы:

«За Рулем: Тесты зимних шипованных шин размера 205/55R16 (2012) Эксперты журнала "За Рулем" провели испытания 12 моделей зимних шипованных шин (шины Goodyear были протестированы вне зачета) в размере 205/55R16. Текст: Сергей Мишин.Список протестированных шин: Bridgestone Ice Cruiser 7000 Continental ContiIceContact Cordiant...»

«СВОЙСТВА ЧИСЕЛ. ДЕЛИМОСТЬ 1. Если в произведении двух чисел первый множитель увеличить на 1, а второй уменьшить на 1, то произведение увеличится на 2011. Как изменится произведение исходных чисел, если, наоборот, первый множитель уменьшить на 1, а второй увеличить на 1? Ответ. Уменьшится на 2013. Решение. Пусть изначально...»

«LOGGER ver.4.1. – ИНСТРУКЦИЯ ДЛЯ ПОЛЬЗОВАТЕЛЯ mgr in. Anna Jerzykowska z mgr in. Krzysztof Blasiok z Катовице, март 2006/ревизия май 2010 Оглавление 1 Вступление 6 2 Требования программы 7 3 Обслуживание программы 8...»

«Слово Протоиерея Александра Шаргунова в 3-ю неделю по Пасхе Об Иосифе Аримафейском и Никодиме Христос воскресе! Второе воскресенье после Светлой Седмицы — память святых жен-мироносиц и святых праведных Иосифа Аримафейского и Никодима. Тех, которые более вс...»

«Section VI. Physics of Nuclear Reactors, Problems of Atomic Energy and Reactors of the Future нейтронного поля в местах расположения ОС в реакторе ВВЭР-1000 могут быть определены только с помощью специальной расчетной методики...»

«Ад HORTUS DAEMONUM • Истоки доктрины;"шеол" и "геенна" • ТЕОЛОГИЯ АДА • Вечность ада • "Отсрочка ада"• Строение и величина ада; лимбы и чистилище • Виды наказаний • Состояние грешников в аду • Ад как зрелище для праведников • Демоны в аду • ОБРАЗНОСТЬ АДА • Местонахождение ада...»

«Информация "Об исполнении областного бюджета за 2017 год" Областной бюджет по доходам в течении года был уточнен 4 раза в сторону увеличения на сумму 330,0 млн. тенге без учета республиканских трансфертов и составил 172 млрд. 710,9...»

«АКАДЕМИЯ НАУК СС С Р ОРДЕНА ТРУДОВОГО КРАСНОГО ЗНАМЕНИ ИНСТИТУТ ВОСТОКОВЕДЕНИЯ ТЮРКОЛОГИЧЕСКИЙ СБОРНИК ИЗДАТЕЛЬСТВО "НАУКА" ГЛАВНАЯ РЕДАКЦИЯ ВОСТОЧНОЙ ЛИТЕРАТУРЫ МОСКВА 1984 Ц. А. Абуладзе, М. X. Сванидзе РЕЕСТРЫ ТРАПЕЗУНДСКОГО, ЧИЛДЫРСК...»




 
2019 www.mash.dobrota.biz - «Бесплатная электронная библиотека - онлайн публикации»

Материалы этого сайта размещены для ознакомления, все права принадлежат их авторам.
Если Вы не согласны с тем, что Ваш материал размещён на этом сайте, пожалуйста, напишите нам, мы в течении 1-2 рабочих дней удалим его.