Классические и квантовые вычисления

Упражнение 1:

Номер 1

Машина Тьюринга, переходящая в состояние, определяемое результатом некоторого случайного процесса, называется:

Ответ:

(1) вероятностной

(2) детерминированной

(3) недетерминированной

(4) переходной

Номер 2

Состояние перехода вероятностной машины Тьюринга определяется:

Ответ:

(1) результатом некоторого случайного процесса

(2) заранее определенным состоянием

(3) предыдущим состоянием

Номер 3

Для вероятностной машины Тьюринга можно определить:

Ответ:

(1) вероятность того или иного ответа

(2) выдаваемый ответ

(3) нет верного ответа

Упражнение 2:

Номер 1

Условие существования вероятностной машины Тьюринга  и полинома , причем машина  заведомо остановится за время, не превосходящее , определяет, что:

Ответ:

(1) предикат math

принадлежит классу BPP

(2) предикат math

принадлежит классу PSPACE

(3) предикат math

принадлежит классу NP

Номер 2

Если  предикат  принадлежит классу BPP, то  выражение  означает, что:

Ответ:

(1) вероятностная машина Тьюринга с вероятностью большей math

дает ответ "нет"

(2) вероятностная машина Тьюринга с вероятностью большей math

дает ответ "да"

(3) вероятностная машина Тьюринга с вероятностью меньшей math

дает ответ "да"

Номер 3

Если вероятность правильного ответа для каждого экземпляра из  запущенных машин Тьюринга равна , то вероятность правильного ответа после голосования  машин:

Ответ:

(1) не меньше math

, где

(2) не меньше math

, где

(3) не больше math

, где

Упражнение 3:

Номер 1

Если установлена принадлежность предиката  к классу BPP, существуют полином  и предикат , то выражение  означает, что:

Ответ:

(1) доля слов math

длины

, для которых выполнено math

, больше

(2) доля слов math

длины

, для которых выполнено math

, меньше

(3) доля слов math

длины

, для которых выполнено math

, больше

Номер 2

Проверка простоты числа является классическим примером задачи класса:

Ответ:

(1) P

(2) NP

(3) BPP

Номер 3

Выберите верное утверждение:

Ответ:

(1) в вероятностных машинах Тьюринга имеются состояния, из которых возможен переход в несколько состояний

(2) предикаты из класса BPP можно считать реально вычислимыми

(3) для определения простоты числа существует вероятностный алгоритм, работающий за полиномиальное время

Упражнение 4:

Номер 1

Утверждение "если - простое и , то " является:

Ответ:

(1) малой теоремой Ферма

(2) китайской теоремой об остатках

(3) теоремой Кука, Левина

Номер 2

"Если  - разложение числа на взаимно простые множители, то существует взаимно однозначное соответствие между остатками от деления на  и парами остатков от деления на  и на  " - утверждает:

Ответ:

(1) китайская теорема об остатках

(2) малая теорема Ферма

(3) теорема Черча

Номер 3

Формулировкой китайской теоремы об остатках является:

Ответ:

(1) "если math

- разложение числа на взаимно простые множители. Тогда math

"

(2) "если math

- простое и math

, то

"

(3) нет верного ответа

Упражнение 5:

Номер 1

Алгоритм Евклида основан на рекурсивном использовании равенства:

Ответ:

(1)

(2)

(3)

Номер 2

В соответствии с алгоритмом Евклида, если делить большее число на меньшее, то длина записи меньшего числа уменьшается на константу:

Ответ:

(1) на каждом шаге

(2) остается неизменной

(3) за каждый два шага

Номер 3

Размер схемы умножения чисел ,  столбиком определяется, как:

Ответ:

(1)

(2)

(3)

Упражнение 6:

Номер 1

Условие  алгоритма проверки простоты числа, где  - случайное среди чисел от 1 до :

Ответ:

(1) определяет, что math

- cоставное

(2) определяет, что math

- простое

(3) не является определяющим

Номер 2

Условием выхода из алгоритма проверки простоты числа является:

Ответ:

(1) если math

- нечетное и больше 2

(2) если из math

извлекается нацело корень math

- й степени при math

(3) если math

- четное и больше 2

Номер 3

Условием алгоритма проверки простоты числа , определяющим что  - составное, где  - случайное среди чисел от 1 до ,  - нечетное, является:

Ответ:

(1) нахождение math

, для которого math

а

(2) нахождение math

, для которого math

а

(3) нахождение math

, для которого math

а

Упражнение 7:

Номер 1

Вероятность получения ответа " - составное" для алгоритма проверки простоты составного числа n равна:

Ответ:

(1)

(2)

(3)

Номер 2

Алгоритм проверки простоты числа с вероятностью  выдает ответ:

Ответ:

(1) "

- составное", если math

- простое

(2) "

- простое", если math

- простое

(3) "

- составное", если math

- составное

Номер 3

При двойном проведении алгоритма проверки простоты числа вероятность ошибки оказывается:

Ответ:

(1) меньше math

(2) меньше math

(3) меньше math

Упражнение 8:

Номер 1

Усиление оценки вероятностей с  до  является основанием доказательства:

Ответ:

(1) китайской теоремы об остатках

(2) малой теоремы Ферма

(3) теоремы math

Номер 2

Выберите верное утверждение:

Ответ:

(1) повторение опытов за полиномиальное время экспоненциально уменьшает оценку вероятности ошибки

(2) повторение опытов за полиномиальное время не меняет размер входа math

(3) повторение опытов за полиномиальное время экспоненциально увеличивает оценку вероятности ошибки

Номер 3

Из утверждения "вероятность того, что объекта с нужными свойствами не существует, меньше 1" следует, что:

Ответ:

(1) хотя бы один такой объект существует

(2) не существует ни одного подобного объекта

(3) нет верного ответа

Классические и квантовые вычисления - тест 3