Доказательство принадлежности классу NP
Cрок выполнения : 1
Вид работы : Контрольная
Дисциплины:
Математические: Логика, теория Алгоритмов и Автоматов.
|
Добавлен 14.12.2014 15:49:37
Уникальность:
Доработка:
Подробно: 1.Доказать принадлежность классу NP предложенной задачи 2. Решить одну из двух проблем: а. доказать NP – полноту предложенной задачи б. построить приближенный алгоритм решения предложенной задачи и показать его точность. 1. ДИНАМИЧЕСКОЕ РАСПРЕДЕЛЕНИЕ ПАМЯТИ УСЛОВИЕ. Заданы множество элементов данных А, размер s(a) ϵ Z+ каждого элемента данных а ϵ А, время поступления r(a) ϵ Z0+ и время d(a) ϵ Z+ окончания работы с элементом данных a ϵ А, положительное целое число D – размер области памяти. ВОПРОС. Существует ли для множества элементов данных А допустимое распределение памяти? Иначе говоря, существует ли такая функция σ: A → {1, 2, ..., D}, что для каждого элемента a ϵ А интервал I(a)=[σ(a), σ(a) + s(a) – 1] содержится в [1, D], причем для любых а, а' ϵ A, если мно¬жество I(a) ∩ I(a') не пусто, то либо d(a) ≤ r(a'), либо d(a') ≤ r(a)? Подсказка. К этой задаче сводится 3-РАЗБИЕНИЕ.
Кратко: 1.Доказать принадлежность классу NP предложенной задачи 2. Решить одну из двух проблем: а. доказать NP – полноту предложенной задачи б. построить приближенный алгоритм решения предложенной задачи и показать его точность. 1. ДИНАМИЧЕСКОЕ РАСПРЕДЕЛЕНИЕ ПАМЯТИ УСЛОВИЕ. Заданы множество элементов дан