Главная Проекты Учеба Фото Авторы Гостевая книга Послать письмо автору

 

Контрольная работа по теории сложности

Вариант 1

1. Верно ли, что класс языков Р замкнут относительно операции объединения?

Является ли NP-полной задача «Целочисленное линейное программирование»? (Заданы матрица А с элементами а_ij   (i=1,..., т; j=l,...,n), векторы    c=(c₁,...,c_n),    b=(b₁,...,b_m)    и число Т. Существует ли целочисленный неотрицательный вектор х=(х₁,...,х_n),  такой, что   (с,х) >= Т,    Ах <= b ?). Является ли эта задача co-NP-полной? При доказательстве NP-полноты можно пользоваться NP-полнотой только семи основных NP-полных задач.
Является ли NP-полной в сильном смысле задача «Расписание для многопроцессорной системы»? (Заданы множество работ N={I,...,n}, число идентичных процессоров m, длительности t_i,   выполнения работ и общий директивный интервал [0, Т] для всех работ. Существует ли допустимое m-процессорное расписание выполнения работ из N без прерываний и переключений, такое, что t_i + t_i <Т при всех iI принадлежит N. где t_i - момент начала выполнения работы i ?).
Доказать, что оптимизационная задача «Упаковка в контейнеры» (Заданы множество предметов N={I,...,n}, их объемы v_i и объем V контейнеров. Требуется упаковать все предметы из  N в минимальное число контейнеров) является NP-трудной и NP-легкой.
Существует ли приближенный полиномиальный алгоритм  А  решения задачи 4 с оценкой   r_A²<=K,где К - константа?