Computação Quântica/Capítulo 3/Exercícios

Exercícios Cap.3 - Introdução à Ciência da Computação

editar

Volte para a página principal do livro clicando aqui: Computação_Quântica

Exercício 3.3 (Máquina de Turing para inverter um string de bits) Descreva uma máquina de turing que, dado um número binário X como entrada, sua saída seja os bits do número X em ordem inversa.

editar

Considere os seguintes caracteres especiais do alfabeto da máquina: % (inicio da fita), B (espaço em branco), i (caracter invertido), * (indica fim da entrada).

A estratégia é marcar o fim da entrada com um caracter especial e fazer o cabeçote da máquina buscar um a um, em ordem invertida, os símbolos da entrada e escrevê-los após a marcação. Por fim, a marcação de fim de entrada é substituída por ínicio da fita.

  • Acha o fim do número X e marca com caracter especial *
    • < Q1 , % , Q1 , % , +1 >
    • < Q1 , 1 , Q1 , 1 , +1 >
    • < Q1 , 0 , Q1 , 0 , +1 >
    • < Q1 , B , Q2 , * , -1 >
  • Caminha para a esquerda encontrando os valores para inversão
    • < Q2 , 0 , Q3 , i , +1 >
    • < Q2 , 1 , Q4 , i , +1 >
    • < Q2 , i , Q2 , i , -1 >
    • < Q2 , % , Q6 , B , +1 >
  • Inverte o símbolo 0
    • < Q3 , i , Q3 , i , +1 >
    • < Q3 , * , Q3 , * , +1 >
    • < Q3 , 0 , Q3 , 0 , +1 >
    • < Q3 , 1 , Q3 , 1 , +1 >
    • < Q3 , B , Q5 , 0 , -1 >
  • Inverte o símbolo 1
    • < Q4 , i , Q4 , i , +1 >
    • < Q4 , * , Q4 , * , +1 >
    • < Q4 , 0 , Q4 , 0 , +1 >
    • < Q4 , 1 , Q4 , 1 , +1 >
    • < Q4 , B , Q5 , 1 , -1 >
  • Anda para a esquerda até encontrar o marcador de fim de entrada *
    • < Q5 , 0 , Q5 , 0 , -1 >
    • < Q5 , 1 , Q5 , 1 , -1 >
    • < Q5 , * , Q2 , * , -1 >
  • Remarca o começo da fita, sinalizando que o algoritmo terminou
    • < Q6 , i , Q6 , B , +1 >
    • < Q6 , * , Q6 , % , 0 >

Exercicío 3.8 (Universalidade de NAND) Mostre que a porta NAND pode ser usada para simular as portas AND, XOR e NOT, utilizando também fios, bits de trabalho (ancilla) e FANOUT.

editar
  • A porta NOT pode ser simulada através dos circuitos apresentados na figura abaixo, onde também podemos ver a tabela verdade destes.

   

  • A porta AND pode ser simulada através dos circuitos apresentados na figura abaixo, onde também podemos ver a tabela verdade destes.

 

  • A porta XOR pode ser simulada através do circuito apresentado na figura abaixo, onde também podemos ver a tabela verdade deste.
 
A B S
0 0 0
0 1 1
1 0 1
1 1 0

Exercicío 3.9: Prove que f(n) é O(g(n)) se e somente se g(n) é Ω(f(n)). Deduza que f(n) é Θ(g(n)) se e somente se g(n) é Θ(f(n)).

editar

Provar que f(n) é O(g(n)) se e somente se g(n) é Θ(f(n)).

f(n) é O(g(n))   g(n) é Ω(f(n)).
f(n) é O(g(n))
f(n) <= c.g(n), para algum n >= n0 e c.
f(n) / c <= g(n)
c'.f(n) <= g(n), chamando  
g(n) é Ω(f(n)), pela definição de Omega de uma função (com c = c' e n0' = n0)
g(n) é Ω(f(n))   f(n)   é O(g(n)).
g(n) é Ω(f(n))
 , para algum n   n0 e c qq.
 
 , chamando  


  é  , pela definição de Omega de uma função.

Exercicío 3.11: Mostre que log n é O(nk) para todo k > 0.

editar
Indução, Caso base:
p/ k = 1:
log n <= c1.n1
c1 >= log n / n
para n grande: lim ( ) ( log n / n ) = 0
Logo, c1 >= 0
Hipótese da indução: log n <= c1.nk ( log n é O(nk))
A provar, para k + 1: log n <= c2.nk+1 ( log n é O(nk+1))
Da hipótese: 1 <= c1.nk / log n
P/ k + 1:
log n <= c2.nk+1
log n <= c2.nkn .(c1.nk / log n)
log n <= (c2c1n2kn) / log n
fazendo c3 = c2.c1
c3 >= log2n / n2kn
para n grande, lim ( ) ( log2n / n2kn ) = 0
Assim, c3 >= 0.

Exercicío 3.14: Suponha que e(n) é O(f(n)) e g(n) é O(h(n)). Mostre que e(n)g(n) é O(f(n)h(n)).

editar

Temos que:

e(n) é O(f(n)) ( I )
g(n) é O(h(n)) ( II )
De I, temos: e(n) c1.f(n)
De II, temos: g(n)   c2.g(n)

Assim:

e(n)g(n) c1.c2.f(n).h(n)
e(n)g(n) <= c3.f(n).h(n)
e(n)g(n) é O(f(n)h(n)), pela definição de Big O.

Exercicío 3.21 Mostre que se uma linguagem L1 é redutível para a linguagem L2 e a linguagem L2 é redutível para a linguagem L3, então L1 é redutível para a linguagem L3.

editar
  • Por hipótese existem reduções polinomiais R1 e R2 tal que,

->   se somente se  

->   se somente se  

  • Considerando o seguinte algoritmo:

R(x)

y1 <- R2(x)

y <- R1(y1)

return y

  • Pela propriedade do algoritmo que usa R1 e R2 sabemos que se   então   e consequentemente  , por outro lado se   então   e consequentemente  .

Portanto, pelo algoritmo acima vale a propriedade   se e somente se  . Logo o algoritmo é polinomial e consequentemente L1 é redutível para L3.

Volte para a página principal do livro clicando aqui: Computação Quântica