BCC-244
Modelos de Computação
1
Computação
CPU
memória
2
memória temporária
memória entrada
CPU
memoria saida
memória de programa
3
Exemplo:
f ( x)  x
3
memória temporária
memória entrada
CPU
memória de programa
compute
xx
compute
x x
memória saida
2
4
f ( x)  x
memória temporária
3
memória entrada
x2
CPU
memória de programa
compute
xx
compute
x x
memória saída
2
5
memória temporária
z  2*2  4
f ( x)  z * 2  8
f ( x)  x
3
memória entrada
x2
CPU
memória de programa
compute
xx
compute
x x
memória saída
2
6
memória temporária
z  2*2  4
f ( x)  z * 2  8
f ( x)  x
3
memória entrada
x2
CPU
memória de programa
compute
xx
compute
x x
f ( x)  8
memória saída
2
7
Autômato
memária temporária
Autômato
memória entrada
CPU
memória saída
memória de programa
8
Diferentes Tipos de Autômatos
Autômatos se distinguem pela memória temporaria
•Autômato Finito:
sem memória temporária
•Autômato de Pilha :
pilha
•Máquina de Turing:
memória RAM
9
Autômato Finito
memória temporária
Autômato
Finito
memória entrada
memória saída
Máquinas de Venda (pequeno poder de computação)
10
Autômato de Pilha
Pilha
Autômato
de Pilha
Push, Pop
memória entrada
memória saida
Parser de Linguagens de Programação
(médio poder de computação)
11
Máquina de Turing
Memória Acesso
Aleatório
Máquina
de Turing
Algoritmos
memória entrada
memória saída
(mais alto poder de computação)
12
Poder de Autômatos
Autômato
Finito
Autômato
Máquina
de Pilha
de Turing
13
Vamos mostrar no curso
• Como construir compiladores para LPs
• Alguns problemas não têm solução computacional
• Alguns problemas são difíceis de resolver
14
Preliminares Matemáticos
15
Preliminares Matemáticos
• Conjuntos
• Funções
• Relações
• Grafos
• Técnicas de Prova
16
CONJUNTOS
Um conjunto é uma coleção de elementos
A  {1, 2, 3}
B = {train, bus, bicycle, airplane}
Escrevemos
1 A
ship  B
17
Representação de Conjuntos
C = { a, b, c, d, e, f, g, h, i, j, k }
C = { a, b, …, k }
conjunto finito
S = { 2, 4, 6, … }
conjunto infinito
S = { j : j > 0, e j = 2k para algum k>0 }
S = { j : j is não negativo e par }
18
A = { 1, 2, 3, 4, 5 }
U
A
6
1
7
10
Conjunto Universal:
2
4
8
3
5
9
Todos os elementos possíveis
U = { 1 , … , 10 }
19
Operações sobre conjuntos
A = { 1, 2, 3 }
B = { 2, 3, 4, 5}
A
• União
B
A U B = { 1, 2, 3, 4, 5 }
• Interseção
U
A
B = { 2, 3 }
• Diferença
A-B={1}
B - A = { 4, 5 }
A-B
20
• Complemento
Conjunto Universal = {1, …, 7}
A = { 1, 2, 3 }
4
A = { 4, 5, 6, 7}
A
1
5
A
2
6
3
7
A=A
21
{ inteiros pares } = { inteiros ímpares }
Inteiros
1 impares
2
3
pares
0
4
5
6
7
22
Leis de DeMorgan’s
U
A
U
AUB=A
B
B=AUB
23
Conjunto Vazio, Nulo:
={}
SU
=S
S
=
U
S-
= Conjunto Universal
=S
-S=
24
Subconjunto
A = { 1, 2, 3}
B = { 1, 2, 3, 4, 5 }
U
A
A
U
Subconjunto próprio
B
B
B
A
25
Subconjuntos Disjuntos
A = { 1, 2, 3 }
A
U
A
B = { 5, 6}
B=
B
26
Cardinalidade de Conjuntos
• Para conjuntos finitos
A = { 2, 5, 7 }
|A| = 3
27
Conjunto Potência
Um Conjunto Poetência é um conjunto de conjuntos
S = { a, b, c }
Conjunto Potência de S = conjunto de todos
os subconjuntos de S
2S = {
, {a}, {b}, {c}, {a, b}, {a, c}, {b, c}, {a, b, c} }
Observação: | 2S | = 2|S|
( 8 = 23 )
28
Produto Cartesiano
A = { 2, 4 }
B = { 2, 3, 5 }
A X B = { (2, 2), (2, 3), (2, 5), ( 4, 2), (4, 3), (4, 4) }
|A X B| = |A| |B|
Generaliza para mais de dois conjuntos
AXBX…XZ
29
FUNÇÕES
contra-domínio
domínio
A
1
2
f(1) = a
a
b
3
Se A = domínio
B
c
f : A -> B
então f é uma função total
caso contrário f é uma função parcial
30
RELAÇÕES
R = {(x1, y1), (x2, y2), (x3, y3), …}
xi R yi
e. x. se R = ‘>’: 2 > 1, 3 > 2, 3 > 1
Em relações xi pode ser repetido
31
Relações de Equivalência
• Reflexiva:
xRx
• Symétrica:
xRy
• Transitiva:
xRY e
yRx
yRz
xRz
Exemplo: R = ‘=‘
•x=x
•x=y
•x=y e y=z
y=x
x=z
32
Classes de Equivalência
Para uma relação de equivalência R
classe de equivalência de x = {y : x R y}
Exemplo:
R = { (1, 1), (2, 2), (1, 2), (2, 1),
(3, 3), (4, 4), (3, 4), (4, 3) }
Classe de equivalência de 1 = {1, 2}
Classe de equivalência de 3 = {3, 4}
33
GRAFOS
Um grafo direcionado
e
nodo
b
d
a
c
• Nodos (Vértices)
V = { a, b, c, d, e }
• Arcos
E = { (a, b), (b, c), (c, a), (b, d), (d, c), (e, d) }34
Grafo Rotulado
6
a
b
1
5
3
e
6
2
d
c
35
Percurso
e
b
d
a
c
Percurso é uma sequência de arcos adjacentes
(e, d), (d, c), (c, a)
36
Caminho
e
b
d
a
c
Caminho é um percurso sem nenhum arco repetido
Caminho simples: nenhum nodo é repeatido
37
Ciclo
a
3
e
base
b
2
1
d
c
Ciclo: caminho de um nodo (base) até ele próprio
Ciclo simples: somento o node base é repetido
38
Ciclo de Euler
8
b
4
a
7
3
6
5
base
e
1
2
d
c
Ciclo que contém cada arco exatamente uma vez.
39
Ciclo Hamiltoniano
5
b
4
a
3
base
e
1
2
d
c
Ciclo simples que contém todos os nodos
40
Encontrando todos os caminhos simples
e
f
b
d
a
c
41
Passo 1
e
b
f
d
a
c
(c, a)
(c, e)
42
Passo 2
e
b
d
a
(c, a)
f
c
(c, a), (a, b)
(c, e)
(c, e), (e, b)
(c, e), (e, d)
43
Passo 3
e
b
d
a
(c, a)
f
c
(c, a), (a, b)
(c, e)
Repete o mesmo
(c, e), (e, b)
para cada nodo inicial
(c, e), (e, d)
(c, e), (e, d), (d, f)
44
raiz
Árvores
pai
folha
filho
Árvores não têm ciclos
45
raiz
Nível 0
Nível 1
Altura 3
folha
Nível 2
Nível 3
46
Árvores Binárias
47
TECNICAS DE PROVA
• Prova por indução
• Prova por contradição
48
Indução
Temos asserções P1, P2, P3, …
Se sabemos
• para algum k P1, P2, …, Pk são verdadeiros
• para todo n >= k
P1, P2, …, Pn implica Pn+1
Então
Todo Pi é verdadeiro
49
Prova por Indução
• Base da Indução
Encontre P1, P2, …, Pk que sejam verdadeiros
• Hipótese de Indução
Suponha que P1, P2, …, Pn sejam verdadeiros,
para todo n >= k
• Passo Indutivo
Mostre que Pn+1 é verdadeiro
50
Exemplo
Teorema: Uma árvore binária de altura n
tem no máximo 2n folhas.
Prova:
seja l(i) o número de folhas no nível i
l(0) = 1
l(3) = 8
51
Queremos mostrar: l(i) <= 2i
• Base da Indução
l(0) = 1
(o nodo raiz)
• Hipótese de Indução
Suponha l(i) <= 2i for all i = 0, 1, …, n
• Passo Indutivo
queremos mostrar que l(n + 1) <= 2n+1
52
Passo Indutivo
Nível
n
hipótese: l(n) <= 2n
n+1
53
Induction Step
Nível
n
hipótese: l(n) <= 2n
n+1
l(n+1) <= 2 * l(n) <= 2 * 2n <= 2n+1
54
Lembrete
Recursão é semelhante
Exemplo de função recursiva:
f(n) = f(n-1) + f(n-2)
f(0) = 1, f(1) = 1
55
Prova por Contradição
Queremos provar que uma asserção P é verdadeira
• supomos que P seja falsa
• então obtemos uma conclusão absurda
• portanto, a asserção P deve ser verdadeira
56
Exemplo
Teorema:
2
não é racional
Prova:
Suponha, por contradição, que seja racional
2
= n/m
n e m não possuem fatore comuns
Cvamos mostrar que isso é impossível
57
2
= n/m
Portanto,
2 m2 = 4k2
n2
2 m 2 = n2
n é par
é par
n=2k
m2 = 2k2
m é par
m=2p
Então, m e n têm em comum o fator 2
Contradição!
58