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

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

Вариант 2.

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

Является ли NP-полной задача «Трехпроцессорное расписание»? (Заданы множество работ N={1,...,п}, три идентичных процессора, длительности t_i выполнения работ и общий для всех работ директивный интервал [0, Т]. Существует ли допустимое трехпроцессорное расписание выполнения работ из N без прерываний и переключений, такое, что t_i + t_i <=Т при всех iI принадлежащих N, где t_i - момент начала выполнения работы i?). Является ли эта задача co-NP-полной? При доказательстве NP-полноты можно пользоваться NP-полнотой только семи основных NP-полных задач.
3. Является ли NP-полной в сильном смысле задача «Упаковка в контейнеры»? (Заданы множество предметов N={1,...,n}, их объемы v_i, объем V контейнеров и число К. Можно ли упаковать все предметы из N в К контейнеров?).
4. Доказать, что оптимизационная задача «Многопроцессорное расписание» (Заданы множество работ N={1,...,n}, число идентичных процессоров m и длительности t_i, выполнения работ. Найти оптимальное по быстродействию расписание выполнения работ N без прерываний и переключений) является NP-трудной и NP-легкой.
5.  Существует ли приближенный полиномиальный алгоритм  А  решения задачи 4 с оценкой   r_A²<=К, где К - константа?