Алгоритм выполняется детерминированно, если представляющая алгоритм последовательность действий
(*ответ*) на одних и тех же данных всегда выполняется одинаково
на различных данных всегда выполняется одинаково
конечна
бесконечна
В качестве начальной информации на ленту машины Тьюринга можно подать
(*ответ*) любую конечную систему знаков внешнего алфавита, расставленную произвольным образом по ячейкам
любую конечную систему знаков внутреннего алфавита, расставленную произвольным образом по ячейкам
любую бесконечную систему знаков внешнего алфавита, расставленную произвольным образом по ячейкам
любую конечную систему знаков внешнего алфавита, расположенную в начале ленты
В качестве простейших функций в формализации понятия алгоритма на основе частично рекурсивных функций используются
(*ответ*) три функции
две функции
четыре функции
пять функций
В одном такте работы машины Тьюторинга управляющая головка может сдвигаться
(*ответ*) только на одну клетку вправо или влево или оставаться на месте
только на одну клетку вправо или влево на месте
только на одну клетку вправо или оставаться на месте
только на одну клетку влево или оставаться на месте
Если при входном на ленте А после конечного числа тактов машина Тьюринга останавливается, то говорят что
(*ответ*) машина применима к слову А
машина не применима к слову А
программа машины не корректна
входное слово ошибочно
Задача называется полной для данного класса, если
(*ответ*) любая задача из класса сводится к такой задаче, и притом сама задача лежит в классе
любая задача из класса сводится к такой задаче, и притом сама задача не лежит в классе
ни одна задача из класса сводится к такой задаче, и притом сама задача лежит в классе
есть задачи из класса, которые сводятся к такой задаче, и притом сама задача лежит в классе
Класс DTIME(f(n)) определяется как класс языков,
(*ответ*) принимаемых детерминированными машинами Тьюринга, заканчивающими свою работу за время, не превосходящее f(n)
принимаемых не детерминированными машинами Тьюринга, заканчивающими свою работу за время, не превосходящее f(n)
принимаемых детерминированными машинами Тьюринга, заканчивающими свою работу за время, превосходящее f(n)
не принимаемых детерминированными машинами Тьюринга, заканчивающими свою работу за время, не превосходящее f(n)
Классами сложности называются множества вычислительных задач, одинаковых
(*ответ*) по сложности вычисления
по объему входной информации
по объему выходной информации
по размеру используемой памяти
Множество М разрешимо тогда и только тогда, когда
(*ответ*) оно само и его дополнение эффективно перечислимы
оно эффективно перечислимо
его дополнение эффективно перечислимо
оно само эффективно перечислимо, а его дополнение нет
Управляющая головка машины Тьюринга может
(*ответ*) передвигаться вдоль ленты и может останавливаться напротив какой-либо клетки и воспринимать символ
передвигаться вдоль ленты и не может останавливаться напротив какой-либо клетки и воспринимать символ
не может передвигаться вдоль ленты и не может останавливаться напротив какой-либо клетки и воспринимать символ
передвигаться вдоль ленты и может останавливаться напротив какой-либо клетки, но не может воспринимать символ
Одна из формулировок тезиса Черча звучит так
(*ответ*) всякий алгоритм может быть реализован частично-рекурсивной функцией
всякий алгоритм может быть реализован
не всякий алгоритм может быть реализован частично-рекурсивной функцией
всякий алгоритм является частично-рекурсивным
NP-полные задачи – это
(*ответ*) NР-задачи, для решения которых не существует детерминированного алгоритма, работающего за полиномиальное время
Р-задачи, для решения которых не существует детерминированного алгоритма, работающего за полиномиальное время
NР-задачи, для решения которых не существует детерминированного алгоритма, работающего за экспоненциальное время
Р-задачи, для решения которых не существует детерминированного алгоритма, работающего за экспоненциальное время
NP-полная задача -
(*ответ*) задача из класса NP, к которой можно свести любую другую задачу из класса NP за полиномиальное время
задача из класса NP, к которой можно свести любую другую задачу из класса NP за экспоненциальное время
задача из класса P, к которой можно свести любую задачу из класса NP за полиномиальное время
задача из класса NP, к которой можно свести любую задачу из класса P за полиномиальное время