игра брюс 2048
Главная / Программирование / Квантовые вычисления / Тест 15

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

Упражнение 1:
Номер 1
Какие утверждения справедливы:

Ответ:

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

 (2) Система криптографии с открытым ключом предполагает, что есть открытый ключ, доступный всем для шифрования сообщения, и есть секретный ключ, используемый для дешифрования, известный только получателю сообщения. 

 (3) Для интернет-торговли и других подобных ситуаций наиболее подходящей системой шифрования является криптографическая система с общим секретным ключом. 

 (4) Для интернет-торговли и других подобных ситуаций наиболее подходящей системой шифрования является криптографическая система с открытым ключом. 


Номер 2
Какие утверждения справедливы относительно криптографической системы RSA:

Ответ:

 (1) Это система с общим секретным ключом. 

 (2) Это система с открытым ключом. 

 (3) Открытый ключ в этой системе — простое число N большого размера — несколько десятков цифр. 

 (4) Открытый ключ в этой системе — пара чисел N и k, где N – произведение p * q двух больших простых чисел, а k – простое число в интервале: max(p, q) <k<M = (p - 1) (q – 1). 

 (5) Закрытый ключ в этой системе — пара чисел M и s, где s определяется из условия: ks = 1 mod M. 


Номер 3
Какие утверждения справедливы относительно криптографической системы RSA:

Ответ:

 (1) Исходное сообщение всегда можно представить бинарной строкой из 0 и 1. Эту строку можно нарезать на блоки длины n, подобранной так, чтобы каждый блок задавал число m, представляющее остаток по модулю N = pq, где p и q – большие простые числа. 

 (2) Число m можно зашифровать открытым ключом, используя соотношение: с = mk mod N. 

 (3) Число с можно расшифровать, получив m, используя закрытый ключ: m = ck mod M. 

 (4) Число с можно расшифровать, получив m, используя закрытый ключ: m = cs mod M. 

 (5) Если известны два большие числа N = pq и M = (p – 1) (q – 1), где p и q – большие простые числа, то определение p и q – вычислительно сложная задача. 

 (6) Если известны два большие числа N = pq и M = (p – 1) (q – 1), где p и q – большие простые числа, то определение p и q – вычислительно простая задача, сводящаяся к решению квадратного уравнения. 


Упражнение 2:
Номер 1
Пусть в криптографической системе RSAp = 3, q = 7, k = 11, s = 11. Зашифрованное сообщение c = 19. Определите исходное сообщение m:

Ответ:

 (1) 9. 

 (2) 10. 

 (3) 11. 


Номер 2
Пусть в криптографической системе RSAp = 3, q = 7, k = 11, s = 11. Зашифрованное сообщение c = 4. Определите исходное сообщение m:

Ответ:

 (1) 9. 

 (2) 10. 

 (3) 11. 


Номер 3
Пусть в криптографической системе RSAp = 3, q = 7, k = 11, s = 11. Зашифрованноесообщение c = 9. Определите исходное сообщение m:

Ответ:

 (1) 9. 

 (2) 10. 

 (3) 11. 

 (4) 18. 


Упражнение 3:
Номер 1
Пусть в криптографической системе RSAp = 3, q = 11, k = 13. Определите значение s – закрытого ключа:

Ответ:

 (1) 9. 

 (2) 13. 

 (3) 17. 

 (4) 18. 


Номер 2
Пусть в криптографической системе RSAp = 5, q = 11, k = 13. Определите значение s – закрытого ключа:

Ответ:

 (1) 9. 

 (2) 13. 

 (3) 17. 

 (4) 37. 


Номер 3
Пусть в криптографической системе RSAp = 7, q = 11, k = 17. Определите значение s – закрытого ключа:

Ответ:

 (1) 33. 

 (2) 43. 

 (3) 53. 

 (4) 35. 


Упражнение 4:
Номер 1
Какие утверждения справедливы относительно функции от двух аргументов f(x, y) = x * y, где x и y – целые из n битов в двоичной системе:

Ответ:

 (1) Функцию нельзя представить как функцию с одним аргументом над бинарными строками Bm→ Bk

 (2) Функцию можно представить как функцию с одним аргументом над бинарными строками Bn→ Bn

 (3) Функциюможно представить как функцию с одним аргументом над бинарными строками B2n→ Bn+1, рассматривая результат как целое число из n+1 бита. 

 (4) Для квантового компьютера функцию следует представить обратимой функцией B3n+1→ B3n+1, где первые 2n битов – это входные данные, а последние n+1 биты – результат умножения. 


Номер 2
Какие утверждения справедливы относительно функции от двух аргументов f(x, y) = x + y, где x и y – целые из n битов в двоичной системе:

Ответ:

 (1) Функцию можно представить как функцию с одним аргументом над бинарными строками B2n→ Bn+1, рассматривая результат как целое число из n+1 бита. 

 (2) Для квантового компьютера функцию следует представить обратимой функцией B3n+1→ B3n+1, где первые 2n битов – это входные данные, а последние n+1 биты – результат сложения. 

 (3) Функцию нельзя представить как функцию с одним аргументом над бинарными строками Bm→ Bk

 (4) Функцию можно представить как функцию с одним аргументом над бинарными строками Bn→ Bn


Номер 3
Укажите корректные высказывания:

Ответ:

 (1) Не всякий классический алгоритм реализуем на квантовом компьютере. 

 (2) Любой алгоритм можно представить как функцию Bn→Bk, где вход и выход — это бинарные строки размера n и k. 

 (3) Функция Bn→Bk не обратима и потому не может быть реализована квантовым алгоритмом. 

 (4) Функция Bn→Bk всегда может быть преобразована в обратимую функцию Bn+k→Bn+k


Упражнение 5:
Номер 1
Какие утверждения справедливы относительно функции от двух аргументов f(x, y) = x + y, где x и y – целые из n битов в двоичной системе:

Ответ:

 (1) Функцию нельзя представить как функцию с одним аргументом над бинарными строками Bm→Bk

 (2) Функцию можно представить как функцию с одним аргументом над бинарными строками Bn→Bn

 (3) Функцию можно представить как функцию с одним аргументом над бинарными строками B2n→Bn, рассматривая результат как целое число из n битов. 

 (4) Для квантового компьютера функцию следует представить обратимой функцией B3n→B3n,где первые 2n битов – это входные данные, а последние n битов – результат сложения. 


Номер 2
Пусть на классическом компьютере реализована функция f :Bn→Bk : y = f(x) .Какие утверждения справедливы в отношении реализации этой функции на квантовом компьютере:

Ответ:

 (1) На квантовом компьютере можно реализовать аналогичную функцию ˜f: Bn→Bk : y = ˜f(x). 

 (2) На квантовом компьютере можно реализовать преобразованную функцию ˜f: Bn+k→Bn+k : ˜f(x, y) = (x, y ^ f(x)), где операция ^ означает побитовое сложение по модулю 2. 

 (3) Функция ˜f необратима. 

 (4) Функция ˜f обратима и обратной к ней является сама функция ˜f. 


Номер 3
Пусть на классическом компьютере реализована функция f от двух аргументов: B2n→ Bk :z = f(x, y). Какие утверждения справедливы в отношении реализации этой функции на квантовом компьютере:

Ответ:

 (1) На квантовом компьютере можно реализовать аналогичную функцию ˜f: B2n → Bk : z = ˜f(x, y). 

 (2) На квантовом компьютере можно реализовать преобразованную функцию ˜f: B2n+k→B2n+k : ˜f(x, y, z) = (x, y, z ^ f(x, y)), где операция ^ означает побитовое сложение по модулю 2. 

 (3) Функция ˜f необратима. 

 (4) Функция ˜f обратима и обратной к ней является сама функция ˜f. 


Упражнение 6:
Номер 1
Пусть Tf – трансформация, реализующая функцию ˜f:  Bn+k→Bn+k :
˜f(x, y) = (x, y ^ f(x)), где операция ^ означает побитовое сложение по модулю 2. Какие утверждения справедливы для этой трансформации:

Ответ:

 (1) Трансформация Tf обратима. 

 (2) Трансформация Tf каждый базисный вектор преобразует в базисный вектор. 

 (3) Трансформация Tf каждый базисный вектор преобразует в суперпозицию базисных векторов. 

 (4) Если на входе трансформации — запутанное состояние, представляющее суперпозицию всех возможных входов, то на выходе состояние представляет суперпозицию результатов всех входов. Измерение выходного состояния позволит выяснить значение только одного результата. 


Номер 2
Какие утверждения справедливы относительно реализации классических вычислений на квантовом компьютере:

Ответ:

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

 (2) Для реализации классических вычислений требуется использовать весь набор трансформаций, доступных для квантового компьютера.  


Номер 3
Какие утверждения справедливы относительно реализации классических вычислений на квантовом компьютере:

Ответ:

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

 (2) Входные данные не меняются в ходе вычислений 

 (3) Выходные данные инициализируются нулевыми значениями. 

 (4) Обратимая функция имеет вид: f^(x, y) = (x, y ^ f(x)), где ^ - операция побитового сложения по модулю 2. 


Упражнение 7:
Номер 1
Набор из трех логических функций — отрицание, конъюнкция, дизъюнкция - является базисом. Это означает, что для любой логической функции существует эквивалентная формула, содержащая только функции базиса. Укажите корректные формулы, содержащие только функции из этого базиса для функции: (x = y) | (z → x) & (z → y). (Здесь = это операция эквивалентность, →  - импликация, которая ложна только в случае, когда посылка истинна, а заключение ложно, ˜ - отрицание, | - дизъюнкция, & - конъюнкция):

Ответ:

 (1) (x & y) | (˜x & ˜y) | (˜z | x) & (˜z | y). 

 (2) (x & y) | (˜x & ˜y) | ˜z. 

 (3) (x & y & z) | (˜x & ˜y & ˜z). 


Номер 2
Набор из трех логических функций — отрицание, конъюнкция, дизъюнкция - является базисом. Это означает, что для любой логической функции существует эквивалентная формула, содержащая только функции базиса. Базис можно сократить до двух функций из этого набора. Какие утверждения справедливы:

Ответ:

 (1) Операцию дизъюнкции можно записать формулой, содержащей операции отрицания и конъюнкции. 

 (2) Операцию конъюнкции можно записать формулой, содержащей операции отрицания и дизъюнкции. 

 (3) Операцию отрицания можно записать формулой, содержащей операции дизъюнкции и конъюнкции. 


Номер 3
Какие утверждения справедливы относительно реализации классических вычислений на квантовом компьютере:

Ответ:

 (1) Любой алгоритм, реализуемый на классическом компьютере, может быть реализован на квантовом компьютере. 

 (2) Существуют алгоритмы, реализуемые на классическом компьютере, но которые нельзя реализовать на квантовом компьютере. 


Упражнение 8:
Номер 1
Логические функции эквивалентны, если совпадают их таблицы истинности. Постройте таблицу истинности для логической операции импликация (логическое следование) a → b, которая ложна только в случае, когда посылка a истинна, а заключение b ложно. Какие формулы эквивалентны импликации (Здесь → операция импликации, ˜ - отрицание, | - дизъюнкция, & - конъюнкция):

Ответ:

 (1) ˜a | b. 

 (2) ˜b | a. 

 (3) ˜b & a. 

 (4) ˜(a & ˜b). 


Номер 2
Постройте ДНФ функции (x = y) | (z → x) & (z → y). (Здесь = это операция эквивалентность, → - импликация, которая ложна только в случае, когда посылка истинна, а заключение ложно). Укажите, сколько конъюнктов включает ДНФ:

Ответ:

 (1) 5. 

 (2) 6. 

 (3) 7. 

 (4) 8. 


Номер 3
Постройте ДНФ функции (x ^ y) | (z → x) & (z → y). (Здесь ^ это операция исключающее или, → - импликация, которая ложна только в случае, когда посылка истинна, а заключение ложно). Укажите, сколько конъюнктов включает ДНФ:

Ответ:

 (1) 5. 

 (2) 6. 

 (3) 7. 

 (4) 8. 


Упражнение 9:
Номер 1
Операции отношения можно выразить логическими операциями. Какие логические формулы позволяют выразить отношение a ≥  b для пары битов (Здесь → операция импликации, ˜ - отрицание, | - дизъюнкция, & - конъюнкция):

Ответ:

 (1) a & b. 

 (2) a | b. 

 (3) b →a. 

 (4) ˜b | a. 


Номер 2
Операции отношения можно выразить логическими операциями. Какая логическая формула позволяет выразить отношение a>b для пары битов (Здесь → операция импликации, ˜ - отрицание, | - дизъюнкция, & - конъюнкция):

Ответ:

 (1) a & b. 

 (2) a | b. 

 (3) a & ˜b. 

 (4) a | ˜b. 


Номер 3
Постройте ДНФ функции (x → y) | (z → x) & (z → y). (Здесь → это импликация, которая ложна только в случае, когда посылка истинна, а заключение ложно). Укажите, сколько конъюнктов включает ДНФ:

Ответ:

 (1) 5. 

 (2) 6. 

 (3) 7. 

 (4) 8. 


Упражнение 10:
Номер 1
Какие утверждения справедливы:

Ответ:

 (1) Арифметические операции можно выразить логическими операциями. 

 (2) Операцию сложения двух двоичных чисел длины n можно задать набором логических операций, в который входит операция сложения трех битов, реализованная логической операцией «исключающее или» (сложение по модулю 2). 

 (3) Арифметические операции нельзя выразить логическими операциями. 


Номер 2
Какие соотношения справедливы и представляют законы логики (Здесь:  ! – операция отрицания, & - конъюнкция, | - дизъюнкция, = - эквивалентность, → - импликация, ^ - исключающее или) :

Ответ:

 (1) !(x & y) = !x | !y. 

 (2) !(x | y) = !x& !y. 

 (3) !(x = y) = x ^ y. 

 (4) !(x & y) = !x & !y. 


Номер 3
Какие соотношения справедливы и представляют законы логики (Здесь:  ! – операция отрицания, & - конъюнкция, | - дизъюнкция, = - эквивалентность, → - импликация, ^ - исключающее или) :

Ответ:

 (1) x→ y = !x | y. 

 (2) x& ( y | z) = (x & y) | (x & z). 

 (3) x& (y | z) = (x | y) & (x | z). 

 (4) x | (y & z) = (x | y) & (x | z). 


Упражнение 11:
Номер 1
Какие стандартные элементы схем классического компьютера требуют преобразования при переходе к стандартным элементам квантового компьютера:

Ответ:

 (1) NOT. 

 (2) AND. 

 (3) OR. 


Номер 2
Какие утверждения справедливы для квантового стандартного элемента схемы CNOT:

Ответ:

 (1) Может использоваться для копирования данных. 

 (2) Используется как управляемое отрицание.  

 (3) Выполняет сборку мусора. 


Номер 3
Какой из стандартных квантовых элементов позволяет копировать данные:

Ответ:

 (1) NOT. 

 (2) CNOT. 

 (3) AND. 

 (4) OR. 


Упражнение 12:
Номер 1
Укажите корректные утверждения:

Ответ:

 (1) Для любого классического вычисления существует квантовая схема, реализующая это вычисление и включающая квантовую сборку мусора. 

 (2) Сборка мусора на квантовом компьютере может выполняться независимо от выполнения алгоритма, решающего задачу.  

 (3) Дополнительные переменные после выполнения их задачи следует очистить (выполнить сборку мусора), иначе, находясь в запутанном состоянии они могут исказить значения выходных переменных.  


Номер 2
Реализация сборки мусора квантового компьютера требует:

Ответ:

 (1) Введения дополнительной памяти для выходных переменных. 

 (2) Выполнения обратной трансформации на заключительномэтапе. 

 (3) Введения дополнительной памяти для входных переменных. 


Номер 3
Какие утверждения справедливы для сборки мусора квантового компьютера:

Ответ:

 (1) Сборка мусора не требуется. 

 (2) Сборку мусора реализовать невозможно. 

 (3) Сборка мусора необходима и реализуема.  




Главная / Программирование / Квантовые вычисления / Тест 15