Алгоритмы и модели вычислений - тест 5

Задача распознавания свойств характеризуется

Вопрос в задаче распознавания свойств ставится в виде

К словам алфавита в задаче распознавания свойств следует от нести

Значения всех параметров в задаче распознавания свойств формируют

Каким образом обозначается длина слова x в задаче распознавания свойств?

К составляющим частям машины Тьюринга следует отнести

Из приведенных ниже записей выделите составляющие части машины Тьюринга:

Какие из приведенных ниже элементов являются составляющими частями машины Тьюринга?

Имитация других исполнителей машиной Тьюринга осуществляется с помощью заданий

Правила перехода формируются с помощью

Если каждой комбинации состояния и ленточного символа в таблице соответствует не более одного правила, машина Тьюринга называется

Если существует пара (ленточный символ - состояние), для которой существует две и более команд, такая машина Тьюринга называется

Для какого состояния машины Тьюринга не формируются правила

При любом входе машина Тьюринга должна

Тип формального языка, называемый разрешимым по Тьюрингу, носит название

Класс всех рекурсивных языков обозначается

Рекурсивное подмножество множества всех возможных слов в алфавите формального языка носит название

Формальный язык, для которого существует машина Тьюринга, которая останавливается на любой входной цепочке и допускает ее тогда и только тогда, когда она принадлежит языку, является

К рекурсивным языкам следует отнести

По каким из приведенных ниже операций замкнуты рекурсивные языки?

Из приведенных ниже операций выделите те, по которым рекурсивные языки замкнуты:

Класс всех рекурсивно распознаваемых языков называется

Рекурсивно перечислимое подмножество множества всевозможных слов над алфавитом языка представляет собой

Если язык распознаваем некоторой полиномиальной машиной Тьюринга, то он называется

К примерам алгоритмов класса P следует отнести

Сложность функции в классе P, вычисляемой некоторой машиной Тьюринга, зависит

Языки, для которых существуют распознающие их предикаты класса P, следует отнести

Множество алгоритмов, время работы которых существенно зависит от размера входных данных, и которое уменьшается при предоставлении алгоритму некоторых дополнительных сведений, носит название

Всякую задачу, принадлежащую NP, можно решить

Если классы P и NP равны, то любую задачу из класса NP можно будет решить

Задача из класса NP, к которой можно свести любую другую задачу из класса NP, называется

Определение факта, принадлежит ли данное слово языку, носит название

К NP-полным задачам следует отнести

Класс всех NP-полных языков обозначается

Из приведенных ниже областей выберите те, в которых реализованы NP-полные задачи:

Какое количество литералов применяется в задаче 3-выполнимости?