Logo Passei Direto
Buscar

Concursos

Outros

Qual e a complexidade do algoritmo de Shor em relacao ao numero de bits n do numero a ser fatorado? a) O(n^2) b) O(n^3) c) O((logn)^3) d) O(n^3 logn)

User badge image
Desenvolvendo com Questões

há 2 meses

User badge image
Desenvolvendo com Questões

há 2 meses

Algoritmo de Shor
7 pág.

Algoritmo de Shor

Respostas

User badge image

Ed Verified user icon

há 2 meses

O algoritmo de Shor é um algoritmo quântico que fatoriza números inteiros em tempo polinomial. A complexidade do algoritmo de Shor em relação ao número de bits \( n \) do número a ser fatorado é \( O(n^2) \). Analisando as alternativas: a) O(n^2) - Esta é a complexidade correta do algoritmo de Shor. b) O(n^3) - Não é a complexidade correta. c) O((logn)^3) - Não se aplica ao algoritmo de Shor. d) O(n^3 logn) - Também não é a complexidade correta. Portanto, a alternativa correta é: a) O(n^2).

Essa resposta te ajudou?

0
Dislike0

Ainda com dúvidas?

Envie uma pergunta e tenha sua dúvida de estudo respondida!

Essa pergunta também está no material:

Algoritmo de Shor
7 pág.

Algoritmo de Shor

Mais perguntas desse material

O que e o algoritmo de Shor?
a) Um algoritmo classico para ordenacao de numeros inteiros.
b) Um algoritmo quantico para fatoracao de numeros inteiros grandes.
c) Um protocolo de criptografia simetrica.
d) Um algoritmo para simulacao de sistemas fisicos classicos.

Qual e a importancia do algoritmo de Shor na criptografia moderna?
a) Ele melhora a eficiencia de algoritmos simetricos.
b) Ele permite quebrar sistemas de criptografia baseados em fatoracao, como RSA.
c) Ele cria chaves de criptografia mais longas.
d) Ele protege contra ataques de forca bruta em sistemas classicos.

Qual e o papel da Transformada de Fourier Quantica (QFT) no algoritmo de Shor?
a) Ordenar os fatores de forma crescente.
b) Encontrar periodos de funcoes modulares de forma eficiente.
c) Medir diretamente os fatores primos.
d) Simular o comportamento de sistemas classicos.

Por que a fatoracao de numeros inteiros grandes e considerada dificil para computadores classicos?
a) Porque exige memoria ilimitada.
b) Porque a melhor tecnica conhecida tem tempo de execucao subexponencial, que cresce muito rapidamente com o tamanho do numero.
c) Porque nao existem algoritmos conhecidos para fatoracao.
d) Porque a computacao classica nao consegue lidar com numeros primos.

Qual e a principal limitacao pratica do algoritmo de Shor atualmente?
a) Falta de algoritmos classicos alternativos.
b) A necessidade de computadores quanticos com muitos qubits confiaveis.
c) Ele nao consegue fatorar numeros primos.
d) Ele e mais lento que metodos classicos para numeros pequenos.

Qual das etapas abaixo nao faz parte do algoritmo de Shor?
a) Escolha aleatoria de um numero coprimo ao numero a ser fatorado.
b) Aplicacao da Transformada de Fourier Quantica para determinar o periodo.
c) Medicao direta dos fatores primos.
d) Uso de aritmetica modular para encontrar multiplos do periodo.

O algoritmo de Shor funciona apenas para numeros pares?
a) Sim, numeros impares nao podem ser fatorados.
b) Nao, ele pode fatorar numeros impares e pares.
c) Apenas numeros primos.
d) Apenas multiplos de 3.

Qual conceito da computacao quantica e explorado pelo algoritmo de Shor para superar algoritmos classicos?
a) Superposicao e interferencia quantica.
b) Memoria RAM ilimitada.
c) Processamento paralelo classico.
d) Compressao de dados.

Se o numero a ser fatorado for N=15, qual e um possivel resultado do algoritmo de Shor?
a) 2 e 8
b) 3 e 5
c) 1 e 15
d) 5 e 10

Mais conteúdos dessa disciplina