Спасибо!
Информация о работе
Подробнее о работе
Индивидуальное домашнее задание по математической логике NP класс задач
- 5 страниц
- 2014 год
- 317 просмотров
- 0 покупок
Гарантия сервиса Автор24
Уникальность не ниже 50%
Фрагменты работ
-
-
Липецкий государственный технический университет
Кафедра автоматизированных систем управления
Индивидуальное домашнее задание
по математической логике
NP класс задач
Студент _____________________ _____________________
подпись, дата фамилия, инициалы
Группа _____________________
Руководитель
___________________________ _______________________ ___________________
Ученая степень, ученое звание подпись, дата фамилия, инициалы
Липецк 2014 г.
Задание кафедры
1.Доказать принадлежность классу NP предложенной задачи
2. Решить одну из двух проблем:
а. доказать NP – полноту предложенной задачи
б. построить приближенный алгоритм решения предложенной задачи и показать его точность.
Задача(1 вариант):
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'), либо f(a') ≤ r(a)?
1. An Annotated List of Selected NP-complete Problems [Электронный ресурс]. – Режим доступа: http://cgi.csc.liv.ac.uk/~ped/teachadmin/COMP202/annotated_np.html. Время обращения: 7:00 24.12.2014.
2. Proving NP-Completeness Results [Электронный ресурс]. – Режим доступа: http://www.di.unipi.it/~luccio/GJ Cap 3.PDF. Время обращения: 7:00 24.12.2014.
3. Гэри М., Джонсон Д. Вычислительные машины и труднорешаемые задачи – М., "Мир", 1982, 419 с.
4. Статья «NP-полная задача» в свободной онлайн-энциклопедии Википедия [Электронный ресурс]. – Режим доступа: https://ru.wikipedia.org/wiki/NP-полная_задача. Время обращения: 7:00 24.12.2014.
5. Статья «P (complexity)» в свободной онлайн-энциклопедии Википедия [Электронный ресурс]. – Режим доступа: https://en.wikipedia.org/wiki/P_(complexity). Время обращения: 7:00 24.12.2014.
6. Статья «Класс NP» в свободной онлайн-энциклопедии Википедия [Электронный ресурс]. – Режим доступа: https://ru.wikipedia.org/wiki/Класс_NP. Время обращения: 7:00 24.12.2014.
Форма заказа новой работы
Не подошла эта работа?
Закажи новую работу, сделанную по твоим требованиям
