Задача о коммивояжере относится к классу P задач:
(*ответ*) нет
да
Из классов P, NP и NP-полных задач самыми легкими являются NP-полные задачи:
(*ответ*) нет
да
Недетерминированная машина Тьюринга выбирает, куда ей двинуться на каждой развилке случайным образом:
(*ответ*) да
нет
Проблема Кука формулируется следующим образом: может ли проверка правильности решения задачи быть более длительной, чем само получение решения, независимо от алгоритма проверки:
(*ответ*) да
нет
Сложность алгоритма определяется объемом входных данных задачи:
(*ответ*) нет
да
Аксиомой называется
(*ответ*) исходное положение научной теории, принимаемое без доказательства
положение научной теории, получаемое в результате доказательства
положение научной теории, которое в рамках данной теории может быть опровергнуто
утверждение, о котором можно сказать, что оно либо истинно, либо ложно
Активной зоной при работе машины Тьюринга называется
(*ответ*) множество непустых ячеек ленты, которые просматривались при работе машины Тьюринга
множество пустых ячеек ленты, которые просматривались при работе машины Тьюринга
количество ячеек ленты, которые были изменены при работе машины Тьюринга
количество ячеек ленты, которые не были изменены при работе машины Тьюринга
Алгебра высказываний – это
(*ответ*) система теоретико-множественных операций над высказываниями
система логического вывода на множестве высказываний
система арифметических операций, примененных к высказываниям
определенным образом заданные функции над высказываниями, принимающие значения 0 и 1
Алгоритм называется экспоненциально ограниченным, если его сложность
(*ответ*) возрастает экспоненциально с ростом длины обрабатываемой последовательности
возрастает полиномиально с ростом длины обрабатываемой последовательности
возрастает линейно с ростом длины обрабатываемой последовательности
не зависит от длины обрабатываемой последовательности
Алгоритмом называется
(*ответ*) точно определенный способ решения задачи
метод доказательства теоремы в рамках формальной теории
численный метод нахождения корней полинома
численный метод дифференцирования многочлена
Внешний алфавит машины Тьюринга – это
(*ответ*) символы, подающиеся на вход машины Тьюринга и выдающиеся на ее выходе
символы, характеризующие состояние машины Тьюринга
набор команд машины Тьюринга
символы, из которых строятся команды машины Тьюринга
Внутренний алфавит машины Тьюринга – это
(*ответ*) символы, характеризующие состояние машины Тьюринга
символы, подающиеся на вход машины Тьюринга и выдающиеся на ее выходе
набор команд машины Тьюринга
символы, из которых строятся команды машины Тьюринга
Временной сложностью вычисления функции f(x) называется
(*ответ*) число шагов машины Тьюринга, вычисляющей эту функцию
длина активной зоны машины Тьюринга, вычисляющей эту функцию
время, требуемое для вычисления функции с помощью электронно-вычислительной машины
объем памяти, требуемой для вычисления функции с помощью электронно-вычислительной машины
Высказывание – это
(*ответ*) повествовательное предложение, о котором можно сказать, что оно либо истинно, либо ложно
повествовательное предложение, о котором можно сказать, что оно истинно
повествовательное предложение, о котором можно сказать, что оно ложно
повествовательное предложение, о котором нельзя сказать, что оно истинно или ложно