# Computação Quântica/Capítulo 3/Exercícios
## Exercícios Cap.3 - Introdução à Ciência da Computação

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.

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.

* A porta NOT pode ser simulada através dos circuitos apresentados na figura abaixo, onde também podemos ver a tabela verdade destes.
$A=B\,\!$
* 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)).

Provar que f(n) é O(g(n)) se e somente se g(n) é Θ(f(n)).
    f(n) é O(g(n)) $\to$ g(n) é Ω(f(n)).
       f(n) é O(g(n))
       f(n) <= c.g(n), para algum n >= n$_0$ e c.
       f(n) / c <= g(n)
       c'.f(n) <= g(n), chamando $c'={\frac {1}{c}}$
       g(n) é Ω(f(n)), pela definição de Omega de uma função (com c = c' e n$_0$' = n$_0$)
    g(n) é Ω(f(n)) $\to$ f(n) $\gets$ é O(g(n)).
       g(n) é Ω(f(n))
       $\ c.f(n)\leq \ g(n)$, para algum n $\geq$ n$_0$ e c qq.
       $f(n)\leq {\frac {g(n)}{c}}$
       $f(n)\leq c.g(n)$, chamando $c'={\frac {1}{c}}$
       $\ f(n)$ é $\ O(g(n))$, pela definição de Omega de uma função.

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

    Indução, Caso base:
       p/ k = 1:
       log n <= c$_1$.n$_1$
       c$_1$ >= log n / n
       para n grande: lim ($n\to \infty$) ( log n / n ) = 0
       Logo, c$_1$ >= 0
    Hipótese da indução: log n <= c$_1$.n$^k$ ( log n é O(n$^k$))
       A provar, para k + 1: log n <= c$_2$.n$^{k+1}$ ( log n é O(n$^{k+1}$))
          Da hipótese: 1 <= c$_1$.n$^k$ / log n
          P/ k + 1:
             log n <= c$_2$.n$^{k+1}$
             log n <= c$_2$.n$^k$n .(c$_1$.n$^k$ / log n)
             log n <= (c2c1n2kn) / log n
             fazendo c$_3$ = c$_2$.c$_1$
             c$_3$ >= log2n / n2kn
             para n grande, lim ($n\to \infty$) ( log$^2$n / n$^{2k}$n ) = 0
             Assim, c$_3$ >= 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)).

Temos que:
    e(n) é O(f(n)) ( I )
    g(n) é O(h(n)) ( II )
    De I, temos: e(n) c$_1$.f(n)
    De II, temos: g(n) $\leq$ c$_2$.g(n)
Assim:
    e(n)g(n) c$_1$.c$_2$.f(n).h(n)
    e(n)g(n) <= c$_3$.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.

* Por hipótese existem reduções polinomiais R1 e R2 tal que,
-> $x\in L3$ se somente se $R2(x)\in L2$
-> $x\in L2$ se somente se $R1(x)\in L1$
* 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 $x\in L3$ então $y1\in L2$ e consequentemente $y\in L1$, por outro lado se $x\notin L3$ então $y\notin L2$ e consequentemente $y\notin L1$.
Portanto, pelo algoritmo acima vale a propriedade $x\in L3$ se e somente se $R(x)\in L1$. 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