Если задача Z Î NP, то существует такой полином р(n), что задача
Z может быть решена детерминированным алгоритмом с временной сложностью
Какое из следующих утверждений истинно?
Свойство детерминированности алгоритма означает, что
А) Алгоритм всегда останавливается после фиксированного числа шагов
В) Алгоритм всегда останавливается, решая задачу на некоторых данных, но число выполненных шагов зависит от конкретных исходных данных
Какое из следующих утверждений истинно?
А) Алгоритм нахождения корней квадратного уравнения является дискретным и детерминированным
В) Алгоритм нахождения корней квадратного уравнения является конечным и массовым
Какое из следующих утверждений истинно?
А) Любая NP может быть сведена к NP-полной задаче
В) Любая NP может быть сведена к P-задаче
Какое из следующих утверждений истинно?
А) Понятие частично-рекурсивной функции - строгое математическое понятие
В) Понятие частично-рекурсивной функции – логическое понятие
Какое из следующих утверждений истинно?
А) Тезис Черча - это не теорема, а утверждение, которое связывает понятие алгоритма и строгое математическое понятие частично-рекурсивной функции
В) Тезис Черча нельзя доказать
Какое из следующих утверждений истинно?
А) Функция называется примитивно - рекурсивной, если она может быть получена из простейших функций обнуления и следования
В) Функция называется примитивно - рекурсивной, если она может быть получена из простейших функций обнуления и проектирования
Какое из следующих утверждений истинно?
А) Хотя класс частично-рекурсивных функций содержит только функции, определенные на множестве натуральных чисел, это не снижает общности представления об алгоритме.
В) Хотя класс частично-рекурсивных функций содержит только функции, определенные на множестве действительных чисел, это не снижает общности представления об алгоритме.
Какое из следующих утверждений истинно?
А) Для любой машины Тьюринга можно построить эквивалентную машину, работающую на левой полуленте
В) Для любой машины Тьюринга можно построить эквивалентную машину, работающую на ленте ограниченного размера
Какое из следующих утверждений истинно?
Функцию (2n+1)! необходимо представить рекурсивно. Схема примитивной рекурсии для этой функции имеет вид
А)
В)
Какое из следующих утверждений истинно?
А) Множество квадратов натуральных чисел рекурсивно перечислимо, так как оно задано уравнением
В) Множество квадратов натуральных чисел перечислимо, так как оно задано уравнением
Алгоритм выполняется детерминированно, если представляющая алгоритм последовательность действий
В качестве начальной информации на ленту машины Тьюринга можно подать
В качестве простейших функций в формализации понятия алгоритма на основе частично рекурсивных функций используются
В одном такте работы машины Тьюторинга управляющая головка может сдвигаться
Если при входном на ленте А после конечного числа тактов машина Тьюринга останавли­вается, то говорят что
Задача называется полной для данного класса, если
Класс DTIME(f(n)) определяется как класс языков,
Классами сложности называются множества вычислительных задач, одинаковых
Множество М разрешимо тогда и только тогда, когда
Нуль- функция в формализации понятия алгоритма на основе частично рекурсивных функций имеет вид
Управляющая головка машины Тьюринга может
Функции g и h в рекуррентных соотношениях для функции , если рекурсия проводится по х равны
Функция выбора в формализации понятия алгоритма на основе частично рекурсивных функций имеет вид
Функция следования в формализации понятия алгоритма на основе частично рекурсивных функций имеет вид
Одна из формулировок тезиса Черча звучит так
NP-полные задачи – это
NP-полная задача -
Алгоритм быстрой сортировки, в среднем требует только около _______ операций для того, чтобы отсортировать N элементов
Алгоритм Маркова - это
Большинство экспоненциальных алгоритмов - это алгоритмы
В каждую ячейку ленты машины Тьюринга может быть
Внешний алфавит машины Тьюринга - это
Внешняя память машины Тьюринга – это
Внутренний алфавит машины Тьюринга - это
Всякая задача, разрешимая за полиномиальное время детерминированным алгоритмом,
Две машины Тьюринга с одинаковой программой
Для класса Р и NP-задач справедливо соотношение
Для любой машины Тьюринга в качестве размера задачи удобно выбрать
Если все возможные варианты запуска экземпляров недетерминированного алгоритма Т не получили решения, значит
Если машина Тьюринга при входном слове А никогда не останавливается, то говорят что
Если сравнивать полиномиальные и экспоненциальные алгоритмы, то полиномиальные алгоритмы
Задача называется трудно решаемой, если для ее решения
Класс DSPACE(f(n)) обозначает класс языков,
Класс NSPACE(f(n)) определяют как класс языков,
Класс NTIME(f(n)) определяют как класс языков,
Класс задач, для решения которых существует недетерминированный алгоритм, решающий эту задачу за полиномиальное время, называется классом
Любой алгоритм обрабатывает исходные данные
Машина Тьюринга - это автомат, который
Машина Тьюринга – это
Множество М называется разрешимым, если для него существует алгоритм, решающий проблему
Множество М называется эффективно перечислимым, если для него существует алгоритм, позволяющий
Можно выделить следующие основные типы универсальных алгоритмических моделей
Недетерминированность алгоритма Т означает, что при запуске многих экземпляров этого алгоритма
Недетерминированный алгоритм всегда должен выдавать на выходе одно из двух сообщений:
Необходимость формального определения алгоритма определяется тем, что необходимо иметь математически точный инструмент
Необходимость формального определения алгоритма определяется тем, что только при наличии формального определения алгоритма можно
Одним из главных результатов теории алгоритмов является доказательство существования
Оператор суперпозиции из функций и имеет вид
Основным свойством конструктивного подхода к понятию алгоритма является то, что все множество функций строится
Полиномиальная сложность алгоритма – это сложность алгоритма, у которого зависимость временной и емкостной сложности от размера задачи, имеет вид
Полиномиальные алгоритмы обычно можно построить лишь тогда, когда
Полиномиальным алгоритмом называется алгоритм, у которого временная сложность T(n), где n – размер задачи, есть
Применение оператора суперпозиции к функциям и дает следующие функции
Проблема P = NP состоит в следующем:
Проблема равенства классов P и NP можно сформулировать как: является ли
Проблема распознавания самоприменимости машины Тьюринга
Проблема самоприменимости машины Тьюринга формулируется так:
Размером задачи является характеристика, которая определяет
Свойство вычислимости алгоритма означает, что
Свойство дискретности алгоритма означает, что
Свойство конечности алгоритма означает, что
Свойство результативности алгоритма означает, что
Трудно решаемыми являются задачи класса
Функция f(n) ecть О(g(n)), если
Частично-рекурсивной называется функция, построенная из простейших с помощью
Частично-рекурсивные фунции – это модель алгоритма, которая
Число 2, выраженное с помощью оператора суперпозиции через нуль-функцию и функцию следования имеет вид
Экспоненциальная сложность алгоритма – это сложность алгоритма, у которого зависимость временной и емкостной сложности от размера задачи, имеет вид