Какое из следующих утверждений истинно?
Свойство детерминированности алгоритма означает, что
А) Алгоритм всегда останавливается после фиксированного числа шагов
В) Алгоритм всегда останавливается, решая задачу на некоторых данных, но число выполненных шагов зависит от конкретных исходных данных
(*ответ*) А – нет, В – нет
A – да, B – да
A – нет, B – да
A – да, B - нет
Какое из следующих утверждений истинно?
А) Алгоритм нахождения корней квадратного уравнения является дискретным и детерминированным
В) Алгоритм нахождения корней квадратного уравнения является конечным и массовым
(*ответ*) А – да, В – да
A – нет, B – да
A – да, B – нет
A – нет, B - нет
Какое из следующих утверждений истинно?
А) Любая NP может быть сведена к NP-полной задаче
В) Любая NP может быть сведена к P-задаче
(*ответ*) A – да, B - нет
A – да, B – да
A – нет, B – нет
A – нет, B - да
Какое из следующих утверждений истинно?
А) Понятие частично-рекурсивной функции - строгое математическое понятие
В) Понятие частично-рекурсивной функции – логическое понятие
(*ответ*) А – да, В – нет
A – да, B – да
A – нет, B – нет
A – нет, B - да
Какое из следующих утверждений истинно?
А) Тезис Черча - это не теорема, а утверждение, которое связывает понятие алгоритма и строгое математическое понятие частично-рекурсивной функции
В) Тезис Черча нельзя доказать
(*ответ*) А – да, В – да
A – да, B – нет
A – нет, B – да
A – нет, B - нет
Какое из следующих утверждений истинно?
А) Функция называется примитивно - рекурсивной, если она может быть получена из простейших функций обнуления и следования
В) Функция называется примитивно - рекурсивной, если она может быть получена из простейших функций обнуления и проектирования
(*ответ*) А – нет, В – нет
A – нет, B – да
A – да, B – да
A – да, B - нет
Какое из следующих утверждений истинно?
А) Хотя класс частично-рекурсивных функций содержит только функции, определенные на множестве натуральных чисел, это не снижает общности представления об алгоритме.
В) Хотя класс частично-рекурсивных функций содержит только функции, определенные на множестве действительных чисел, это не снижает общности представления об алгоритме.
(*ответ*) А – да, В – нет
A – нет, B – да
A – да, B – да
A – нет, B - нет
Какое из следующих утверждений истинно?
А) Для любой машины Тьюринга можно построить эквивалентную машину, работающую на левой полуленте
В) Для любой машины Тьюринга можно построить эквивалентную машину, работающую на ленте ограниченного размера
(*ответ*) А – да, В – нет
A – да, B – да
A – нет, B – да
A – нет, B - нет
Какое из следующих утверждений истинно?
А) Множество квадратов натуральных чисел рекурсивно перечислимо, так как оно задано уравнением
В) Множество квадратов натуральных чисел перечислимо, так как оно задано уравнением
(*ответ*) А – да, В – да
A – да, B – нет
A – нет, B – нет
A – нет, B - да