Класс DSPACE(f(n)) обозначает класс языков,
(*ответ*) принимаемых детерминированными машинами Тьюринга, использующих не более f(n) ячеек памяти на рабочей ленте
не принимаемых детерминированными машинами Тьюринга, использующих не более f(n) ячеек памяти на рабочей ленте
принимаемых детерминированными машинами Тьюринга, использующих более f(n) ячеек памяти на рабочей ленте
принимаемых недетерминированными машинами Тьюринга, использующих не более f(n) ячеек памяти на рабочей ленте
Класс NSPACE(f(n)) определяют как класс языков,
(*ответ*) принимаемых недетерминированными машинами Тьюринга, использующих не более f(n) ячеек памяти на рабочей ленте
не принимаемых недетерминированными машинами Тьюринга, использующих не более f(n) ячеек памяти на рабочей ленте
принимаемых детерминированными машинами Тьюринга, использующих не более f(n) ячеек памяти на рабочей ленте
не принимаемых детерминированными машинами Тьюринга, использующих не более f(n) ячеек памяти на рабочей ленте
Класс NTIME(f(n)) определяют как класс языков,
(*ответ*) принимаемых недетерминированной машиной Тьюринга, заканчивающими свою работу за время, не превосходящее f(n)
не принимаемых недетерминированной машиной Тьюринга, заканчивающими свою работу за время, не превосходящее f(n)
принимаемых детерминированной машиной Тьюринга, заканчивающими свою работу за время, не превосходящее f(n)
принимаемых недетерминированной машиной Тьюринга, заканчивающими свою работу за время, превосходящее f(n)
Класс задач, для решения которых существует недетерминированный алгоритм, решающий эту задачу за полиномиальное время, называется классом
(*ответ*) NP-задач
полиномиальных задач
Р-задач
экспоненциальных задач
Любой алгоритм обрабатывает исходные данные
(*ответ*) конечной длины, причем эти данные представлены в конечном алфавите
бесконечной длины, причем эти данные представлены в конечном алфавите
конечной длины, причем эти данные представлены в бесконечном алфавите
конечной длины, причем эти данные представлены в двоичном алфавите
Машина Тьюринга - это автомат, который
(*ответ*) имеет потенциально бесконечную в обе стороны ленту, считывающую головку и управляющее устройство
имеет конечную ленту, считывающую головку и управляющее устройство
имеет потенциально бесконечную в обе стороны ленту, считывающую головку
имеет считывающую головку и управляющее устройство
Машина Тьюринга – это
(*ответ*) модель алгоритма, которая рассматривает алгоритм в виде набора инструкций для некоторой формальной вычислительной машины
модель персонального компьютера
набор инструкций по решению задачи для реализации на ЭВМ
модель алгоритма, которая рассматривает алгоритм в виде набора инструкций для персонального компьютера
Множество М называется разрешимым, если для него существует алгоритм, решающий проблему
(*ответ*) вхождения слова х в М
правильности слова х
конечности множества М
счетности множества М
Множество М называется эффективно перечислимым, если для него существует алгоритм, позволяющий
(*ответ*) перечислить все элементы множества
решить проблему вхождения слова х в М
решить проблему конечности множества М
решить проблему счетности множества М
Недетерминированность алгоритма Т означает, что при запуске многих экземпляров этого алгоритма
(*ответ*) какой-то из них возможно получит решение задачи
все они получат решение задачи
ни один из них не получит решение задачи
какой-то из них наверняка получит решение задачи
Недетерминированный алгоритм всегда должен выдавать на выходе одно из двух сообщений:
(*ответ*) "получено решение" или "решение не получено"
"задача решаема" или "задача не решаема"
"задача сформулирована корректно" или " задача сформулирована не корректно "
"входных данных достаточно" или " входных данных не достаточно "
Необходимость формального определения алгоритма определяется тем, что необходимо иметь математически точный инструмент
(*ответ*) для сравнения различных алгоритмов решения одних и тех же задач
для сравнения различных алгоритмов решения разных задач
для написания программы для компьютера
для выбора языка программирования
Необходимость формального определения алгоритма определяется тем, что только при наличии формального определения алгоритма можно
(*ответ*) ставить задачу о разрешимости или неразрешимости каких-либо проблем
написать программу для компьютера
словесно сформулировать задачу
выбрать язык программирования для решения задачи