Для задания машины Тьюринга необходимо задать один входной алфавит:
(*ответ*) нет
да
Заключительное состояние машины Тьюринга - состояние, в котором происходит остановка машины:
(*ответ*) да
нет
Класс примитивно-рекурсивных функций строго содержится в классе частично-рекурсивных:
(*ответ*) да
нет
Команда машины Тьюринга указывает только направление движения управляющей головки:
(*ответ*) нет
да
Любой алгоритм может быть всегда сведен к численному алгоритму:
(*ответ*) да
нет
Машина Тьюринга - чисто техническое понятие:
(*ответ*) нет
да
Область применимости алгоритма А - совокупность тех объектов, к которым он применим:
(*ответ*) да
нет
При построении примитивно-рекурсивных функций используется только один оператор рекурсии:
(*ответ*) нет
да
Программа машины Тьюринга - конечное непустое множество попарно согласованных команд:
(*ответ*) да
нет
Программы работы машины Тьюринга можно задать в виде таблицы:
(*ответ*) да
нет
Условия любой задачи могут быть однозначно заданы с помощью ее Геделевского номера:
(*ответ*) да
нет
Частично рекурсивная функция может быть получена из исходных с помощью применения конечного числа раз подстановок, примитивных рекурсий и мю-оператора:
(*ответ*) да
нет
NP-полные задачи - класс задач, лежащих в классе P задач:
(*ответ*) нет
да
NP-полные задачи входят в класс NP задач:
(*ответ*) да
нет
Алгоритмическая сложность - зависимость времени исполнения алгоритма от длины входных данных:
(*ответ*) да
нет
Алгоритмы класса O(N) эквивалентны использованию одномерных циклов:
(*ответ*) да
нет
Алгоритмы сложности O(N) в общем случае сложнее, чем алгоритмы сложности O(N log(N)):
(*ответ*) нет
да
Детерминированная машина Тьюринга - машина, использующая фиксированный набор входных данных:
(*ответ*) нет
да
Детерминированность означает, что при выполнении каждого очередного шага, мы точно знаем, какой шаг мы сделаем следующим:
(*ответ*) да
нет
Для алгоритмов класса O(N) каждый входной элемент обрабатывается С*N раз, где С - некоторая постоянная:
(*ответ*) да
нет
Для алгоритмов класса сложности О(1) количество шагов алгоритма линейно зависит от количества входных данных:
(*ответ*) нет
да
Для одной и той же проблемы могут существовать алгоритмы, различные по сложности:
(*ответ*) да
нет