Teoria_algoritmov.tst

Теория алгоритмовdNP задачиВыберите полиномиальные задачиЗадача о гамильтоновом циклеЗадача коммивояжераЗадача распознавания булевской логикиЗадача 3-выполнимости-dCNP задачиВыберите все NP-полные задачи из ниже перечисленныхРеберное покрытиеВершинное покрытие3-выполнимость12sОбратная задача к NPЧто знаем об задаче обратной к полиномиальной?Она полиномиальнаОна не полиномиальнаНеопределённо0sОбратная задача к CNPЧто знаем о задаче обратной к задаче из класса CNP?Она из класса CNPона не пренадлежит классу CNPОна из класса NPничего точно не знаем1aОпределения_1Напишите термин определение которого написано ниже.
Некоторый общий вопрос, на который следует дать ответ. Обычно содержит ряд параметров(свободных переменных), значения которых заранее не определеныМассовая задачамассовая задачаaОпределения_2Напишите термин определение которого написано ниже.
Точное конечное предписание, задающее детерминированный вычислительный процесс, начинающийся с произвольного, но выбранного из фиксированной для данного алгоритма совокупности,
исходного данного и направленный на получение полностью определенного этим данным результатаАлгоритмалгоритмdОпределения_3Какую задачу называют труднорешаемой?задачу, решение которой трудно запрограммироватьзадачу, для решения которой не существует полиномиального алгоритмазадачу, для решения которой не существует экспоненциального алгоритмазадачу, для решения которой требуется более 2^16 тактов процессора1