NP-полная задача - такая задача из класса P, к которой можно свести любую другую задачу из класса P:
(*ответ*) нет
да
Алгоритмическая сложность - зависимость времени исполнения алгоритма от длины (объема) входных данных:
(*ответ*) да
нет
В рамках теории сложности любые алгоритмы, работающие с полиномиальной скоростью, считаются быстрыми:
(*ответ*) да
нет
Временем работы алгоритма Tm(x) при фиксированном входном слове x называется длина ленты, которую использует машина Тьюринга (М) при реализации алгоритма:
(*ответ*) нет
да
Время при оценке сложности алгоритма измеряется объемом входной информации:
(*ответ*) нет
да
Действие управляющего устройства машины Тьюринга зависит только от содержимого прочитанной ячейки:
(*ответ*) нет
да
Для алгоритма класса O(N) (N - объем входных данных) для каждого данного выполняется только одно действие:
(*ответ*) да
нет
Для алгоритмов сложности О(1) количество шагов алгоритма зависит от количества входных данных:
(*ответ*) нет
да
Доказано, что классы алгоритмов P и NP совпадают:
(*ответ*) нет
да
Задача выполнимости Булевых формул относится к классу NP:
(*ответ*) да
нет
Задача нахождения нуля функции методом деления отрезка пополам относится к задачам логарифмической сложности:
(*ответ*) да
нет
Задача поиска нужного слова в словаре и задача чистки ковра заданной площади - задачи одного класса сложности:
(*ответ*) нет
да
Класс сложности NP - класс сложности алгоритмов, выполняемых детерминированной машиной Тьюринга за полиномиальное время:
(*ответ*) нет
да
Регистрация заявок в мастерской бытового обслуживания - пример алгоритма линейного класса сложности:
(*ответ*) да
нет
Тест простоты - тест на проверку того, является ли заданное число простым или нет:
(*ответ*) да
нет
Управляющее устройство машины Тьюринга может и считывать, и записывать информацию в ячейки ленты:
(*ответ*) да
нет
Алгебра логики - область традиционной логики, а не математики:
(*ответ*) нет
да
Алгебра логики может быть применена в любой области человеческой деятельности:
(*ответ*) нет
да
Булевы переменные могут принимать только два значения:
(*ответ*) да
нет
В булевой алгебре закон гласит, что если два раза подряд применить операцию отрицания, то получится ноль:
(*ответ*) нет
да
Другое название операции дизъюнкции - логическое умножение:
(*ответ*) нет
да
Другое название операции конъюкции - логическое сложение:
(*ответ*) нет
да