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

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

Номер 1

Обозначение класса дополнений классу языков  имеет вид:

Ответ:

(1)

(2)

(3)

Номер 2

Какая запись является верной:

Ответ:

(1)

(2)

(3)

Номер 3

Какое обозначает запись  по отношению к классу А:

Ответ:

(1) класс дополнений

(2) эрмитово сопряженный оператор

(3) множество конечных слов в алфавите math

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

Номер 1

Автором теоремы ""  является:

Ответ:

(1) Лаутеман

(2) Кук, Левин

(3) Черч

Номер 2

При доказательстве утверждения "" используется:

Ответ:

(1) тождественность класса BPP относительно дополнений

(2) замкнутость класса BPP относительно дополнений

(3) открытость класса BPP относительно дополнений

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

Номер 3

Что из ниже перечисленного верно отражает свойство "множество содержит много элементов":

Ответ:

(1)

(2)

(3)

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

Номер 1

Утверждение о том, что для случайных независимых  вероятность события  больше 0, содержится в записи :

Ответ:

(1)

(2)

(3)

Номер 2

Чему равна вероятность того, что случайный сдвиг  не покрывает (не содержит) некоторый фиксированный элемент, где  - некоторая группа, а  - подмножество :

Ответ:

(1)

(2)

(3)

Номер 3

Чему равна вероятность того, что что  случайных сдвигов не покрывают фиксированный элемент, где  - некоторая группа, а  - подмножество :

Ответ:

(1)

(2)

(3)

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

Номер 1

Чем объясняется то, что вероятность события  не больше , где  - некоторая группа, а  - подмножество :

Ответ:

(1) вероятность объединения событий не меньше суммы вероятностей этих событий

(2) вероятность объединения событий не больше суммы вероятностей этих событий

(3) вероятность объединения событий не больше разности вероятностей этих событий

Номер 2

Использование генераторов псевдослучайных чисел является основой идеи:

Ответ:

(1) сокращения времени вычисления функций из класса BPP менее math

(2) удержании времени вычисления функций из класса BPP на math

(3) сокращения времени вычисления функций из класса NP менее math

Номер 3

В каком случае заведомо не существует псевдослучайных генераторов:

Ответ:

(1)

(2)

(3)

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

Номер 1

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

Ответ:

(1)

(2)

(3)

Номер 2

Какому классу принадлежит , если существует такая игра с полиномиальным от длины входного слова числом ходов и полиномиально вычислимым результатом, что  Б имеет выигрышную стратегию (Б - игрок, имеющих имя "белые"):

Ответ:

(1)

(2)

(3)

Номер 3

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

Ответ:

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

(2) вычисление на памяти math

бессмысленно проводить дольше, чем время math

(3) псевдослучайные генераторы отсутствуют при math

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

Номер 1

Количество состояний системы, где  - память,  - соответственно множество состояний управляющего устройства и алфавит рассматриваемой машины Тьюринга, определяется по формуле:

Ответ:

(1)

(2)

(3)

Номер 2

В формуле  для нахождения количества состояний системы,  - это:

Ответ:

(1) используемая системой память

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

(3) множество состояний управляющего устройства

Номер 3

Если число ходов ограничено , а , то время работы машины Тьюринга ограничено:

Ответ:

(1)

(2)

(3)

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

Номер 1

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

Ответ:

(1) за один такт

(2) за два такта

(3) за три такта

Номер 2

Верным является тождество:

Ответ:

(1)

(2)

(3)

Номер 3

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

Ответ:

(1) по двум сложностным классам math

и

можно определить класс math

таких языков, которые распознаются машинами из класса math

с оракулами из math

(2) класс языков, распознаваемых недетерминированными машинами, работающими на памяти math

, содержится в классе языков, распознаваемых детерминированными машинами, работающими на памяти math

(3)

- класс языков, вычислимых за экспоненциальное время math

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

Номер 1

Задача  является полной задачей класса:

Ответ:

(1)

(2)

(3)

Номер 2

В качестве  в булевой формуле  задаваемой задачей , где , - некоторая логическая формула, выступает:

Ответ:

(1)

(2)

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

Номер 3

Выберите верные тождества, где  - язык, :

Ответ:

(1)

(2)

(3)

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