Computação Quântica/Capítulo 3/Exercícios: mudanças entre as edições
imported>Alexandre146 |
imported>Reubot |
||
(19 revisões intermediárias por 10 usuários não estão sendo mostradas) | |||
Linha 1: | Linha 1: | ||
== Exercícios Cap.3 - Introdução à Ciência da Computação == | == 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. | |||
[[Image:Nand-gate-en.svg|100px]] <math>A=B \,\!</math> | |||
* A porta AND pode ser simulada através dos circuitos apresentados na figura abaixo, onde também podemos ver a tabela verdade destes. | |||
[[Image:AND from NAND.svg|120px]] | |||
* A porta XOR pode ser simulada através do circuito apresentado na figura abaixo, onde também podemos ver a tabela verdade deste. | * A porta XOR pode ser simulada através do circuito apresentado na figura abaixo, onde também podemos ver a tabela verdade deste. | ||
[[ | {| | ||
|[[Image:XOR using NAND.svg]] | |||
| | |||
{|{{prettytable}} | |||
!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)) <math>\to</math> g(n) é Ω(f(n)).''' | |||
::f(n) é O(g(n)) | |||
::f(n) <= c.g(n), para algum n >= n<sub>0</sub> e c. | |||
::f(n) / c <= g(n) | |||
::c'.f(n) <= g(n), chamando <math>c' = \frac{1}{c}</math> | |||
::g(n) é Ω(f(n)), pela definição de Omega de uma função (com c = c' e n<sub>0</sub>' = n<sub>0</sub>) | |||
:'''g(n) é Ω(f(n)) <math>\to</math> f(n) <math>\gets</math> é O(g(n)).''' | |||
::g(n) é Ω(f(n)) | |||
:: <math>\ c.f(n) \leq \ g(n)</math>, para algum n <math>\geq</math> n<sub>0</sub> e c qq. | |||
::<math>f(n) \leq \frac{g(n)}{c}</math> | |||
::<math>f(n) \leq c.g(n)</math>, chamando <math>c' = \frac{1}{c}</math> | |||
::<math>\ f(n)</math> é <math>\ O(g(n))</math>, pela definição de Omega de uma função. | |||
=== Exercicío 3.11: Mostre que log n é O(n<sup>k</sup>) para todo k > 0. === | |||
:'''Indução, Caso base:''' | |||
::p/ k = 1: | |||
::log n <= c<sub>1</sub>.n<sub>1</sub> | |||
::c<sub>1</sub> >= log n / n | |||
::para n grande: lim (<math>n \to \infty</math>) ( log n / n ) = 0 | |||
::Logo, c<sub>1</sub> >= 0 | |||
:'''Hipótese da indução:''' log n <= c<sub>1</sub>.n<sup>k</sup> ( log n é O(n<sup>k</sup>)) | |||
::'''A provar, para k + 1:''' log n <= c<sub>2</sub>.n<sup>k+1</sup> ( log n é O(n<sup>k+1</sup>)) | |||
:::'''Da hipótese:''' 1 <= c<sub>1</sub>.n<sup>k</sup> / log n | |||
:::'''P/ k + 1:''' | |||
::::log n <= c<sub>2</sub>.n<sup>k+1</sup> | |||
::::log n <= c<sub>2</sub>.n<sup>k</sup>n .(c<sub>1</sub>.n<sup>k</sup> / log n) | |||
::::log n <= (c2c1n2kn) / log n | |||
::::fazendo c<sub>3</sub> = c<sub>2</sub>.c<sub>1</sub> | |||
::::c<sub>3</sub> >= log2n / n2kn | |||
::::para n grande, lim (<math>n \to \infty</math>) ( log<sup>2</sup>n / n<sup>2k</sup>n ) = 0 | |||
::::Assim, c<sub>3</sub> >= 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<sub>1</sub>.f(n) | |||
:De II, temos: g(n) <math> \leq </math> c<sub>2</sub>.g(n) | |||
Assim: | |||
:e(n)g(n) c<sub>1</sub>.c<sub>2</sub>.f(n).h(n) | |||
:e(n)g(n) <= c<sub>3</sub>.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, | |||
-> <math>x \in L3</math> se somente se <math>R2(x) \in L2</math> | |||
-> <math>x \in L2</math> se somente se <math>R1(x) \in L1</math> | |||
* 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 <math>x \in L3</math> então <math>y1 \in L2</math> e consequentemente <math>y \in L1</math>, por outro lado se <math>x \notin L3</math> então <math>y \notin L2</math> e consequentemente <math>y \notin L1</math>. | |||
Portanto, pelo algoritmo acima vale a propriedade <math>x \in L3</math> se e somente se <math>R(x) \in L1</math>. 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]] | |||
{{AutoCat}} |
Edição atual tal como às 10h29min de 14 de junho de 2011
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 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.
|
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)) 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.
- 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)).
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.
- 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