Computação Quântica/Capítulo 3/Exercícios: mudanças entre as edições
imported>Karinina |
imported>NiginiOliveira Sem resumo de edição |
||
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]] | |||
=== 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. === | === 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. === | ||
Linha 36: | Linha 38: | ||
* Pela propriedade do algoritomo 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>. | * Pela propriedade do algoritomo 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. | 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]] |
Edição das 13h58min de 18 de julho de 2005
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
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.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 algoritomo 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