Алгоритм Маркова - это
(*ответ*) языковый подход к понятию алгоритма, в основе которого лежит формализация процесса преобразования записей исходных данных в запись результатов
модель алгоритма, которая рассматривает алгоритм в виде набора инструкций для некоторой формальной вычислительной машины
модель алгоритма, которая рассматривает алгоритм в виде набора инструкций для персонального компьютера
математическая запись алгоритма
Большинство экспоненциальных алгоритмов - это алгоритмы
(*ответ*) полного перебора
подсчета числа вариантов
у которых сложность вычислений не зависит от длины входных данных
у которых сложность вычислений падает при увеличении длины входных данных
В каждую ячейку ленты машины Тьюринга может быть
(*ответ*) записан один символ внешнего алфавита
записан один символ внутреннего алфавита
записано не более двух символов внешнего алфавита
записано не более двух символов внутреннего алфавита
Внешний алфавит машины Тьюринга - это
(*ответ*) конечное множество символов, которыми кодируется входная информация
бесконечное множество символов, которыми кодируется входная информация
конечное множество символов, которыми характеризуются состояния машины
бесконечное множество символов, которыми характеризуются состояния машины
Внешняя память машины Тьюринга – это
(*ответ*) бесконечная в обе стороны лента
конечная в обе стороны лента
набор символов внешнего алфавита
набор символов внутреннего алфавита
Внутренний алфавит машины Тьюринга - это
(*ответ*) конечный набор символов, характеризующих состояния машины
бесконечный набор символов, характеризующих состояния машины
конечное множество символов, которыми кодируется входная информация
бесконечное множество символов, которыми кодируется входная информация
Всякая задача, разрешимая за полиномиальное время детерминированным алгоритмом,
(*ответ*) разрешима за полиномиальное время недетерминированным алгоритмом
разрешима за экспоненциальное время недетерминированным алгоритмом
не разрешима за полиномиальное время недетерминированным алгоритмом
разрешима за экспоненциальное время детерминированным алгоритмом
Две машины Тьюринга с одинаковой программой
(*ответ*) неразличимы
различимы
различаются по составу внешнего алфавита
различаются по составу внутреннего алфавита
Для любой машины Тьюринга в качестве размера задачи удобно выбрать
(*ответ*) длину входной цепочки
длину выходной цепочки
время работы машины Тьюринга
величину используемой памяти
Если все возможные варианты запуска экземпляров недетерминированного алгоритма Т не получили решения, значит
(*ответ*) решение задачи не существует
задача поставлена неверно
задача имеет много решений
задача имеет два решения
Если машина Тьюринга при входном слове А никогда не останавливается, то говорят что
(*ответ*) машина не применима к слову А
машина применима к слову А
программа машина составлена некорректно
слово А записано неверно
Если сравнивать полиномиальные и экспоненциальные алгоритмы, то полиномиальные алгоритмы
(*ответ*) считаются более предпочтительными по сравнению с экспоненциальными
считаются менее предпочтительными по сравнению с экспоненциальными
считаются равноценны экспоненциальным
не сравнимы с экспоненциальными, так как используются для разных задач
Задача называется трудно решаемой, если для ее решения
(*ответ*) не существует полиномиального алгоритма
не существует экспоненциального алгоритма
существует экспоненциальный алгоритм ее решения
существует полиномиальный алгоритм ее решения