Embed Size (px)
Citation preview
Projeto e Análise de Algoritmos
Cristiano Damiani Vasconcellos
Agradeço ao Prof. Diego Buchinger por ajudar a aprimorar esse material.
Bibliografia
Algoritmos. Thomas H. Cormen, Charles E. Leiserson, Ronald L.
Rivest, Cliford Stein. Campus.
Algorithms. Sanjoy Dasgupta, Christos Papadimitriou, Umesh
Vazirani. McGraw Hill.
Análise de Algoritmos
Analisar um algoritmo significa prever os recursos que
algoritmo necessita. Por exemplo, memória, largura de
banda e mais frequentemente o tempo de computação.
Para analisar um algoritmo é necessário definir um
modelo de computação. O modelo de computação do
computador tradicional é o RAM (Random Access
Machine). Onde as instruções são executadas em
sequência, sem concorrência, e os dados são
armazenados em células de memória com acesso
aleatório.
Análise de Algoritmos
Contar o número de instruções que são executadas pelo
algoritmo. Por exemplo: load, store, add, sub, div, mul,
call, ret, cmp, jump, etc.
Qual o tempo de execução?
int pesquisa(Estrutura *v, int n, int chave)
{
int i;
for (i = 0; i < n; i++)
if (v[i].chave == chave)
return i;
return -1;
}
O número de instruções e o tempo de execução dependedo processador, compilador, etc.
Programa
• Notação Assintótica.
• Complexidade de tempo e espaço.
• Relações de Recorrência.
• Somatórios.
• Divisão e Conquista.
• Algoritmos Gulosos.
• Programação Dinâmica.
• Tratabilidade (classes P, NP e NP-Completo).
Crescimento de Funções
Para simplificar o processo usamos uma abstração que
ignora o custo de cada instrução, que é constante.
Concentrando a análise no crescimento do tempo de
execução (ou de outro recurso) em relação ao
crescimento da entrada.
Notação Assintótica
(Notação O grande – Limite Superior)
Uma função f(n) domina assintoticamente outra função
g(n) se existem duas constantes positivas c e n0 tais que,
para n > n0, temos |g(n)| c.|f(n)|. g(n) = O(f(n))
n2 + 4n - 4 = O(n2)
0
100
200
300
400
500
600
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
2n2
n2 + 4n - 4
Algumas Operações com
Notação O
c.O(f(n)) = O(f(n)), onde c é uma constante.
O(f(n)) + O(g(n)) = O(MAX(f(n), g(n))
n.O(f(n)) = O(n.f(n))
O(f(n)).O(g(n)) = O(f(n).g(n))
Complexidade de Tempo
int pesquisa(Estrutura *v, int n, int chave)
{
int i; // O(1)
for (i = 0; i < n; i++) // O(n)
if (v[i].chave == chave) // O(1)
return i; // O(1)
return -1; // O(1)
}
Em que situações ocorrem o melhor caso, pior caso e o caso médio?
Complexidade de Tempo
Caso médio: Caso o i-ésimo registro seja o registro
procurado são necessárias i comparações. Sendo pi a
probabilidade de procurarmos o i-ésimo registro temos:
f(n) = 1.p1 + 2.p2 + ... + n.pn.
Considerando que a probabilidade de procurar qualquer
registro é a mesma probabilidade, temos
pi = 1/n, para todo i.
2
)1(
2
)1(1)...21(
1)(
nnn
nn
nnf
Crescimento de Funções
log(n)
n
n.log(n)
n22nn!
Crescimento de Funções
0
1000000
2000000
3000000
4000000
5000000
6000000
7000000
8000000
9000000
10000000
11000000
12000000
13000000
14000000
15000000
16000000
17000000
18000000
19000000
20000000
1 4 7 10 13 16 19 22 25 28 31 34 37 40 43 46 49 52 55 58 61 64
0
1000000
2000000
3000000
4000000
5000000
6000000
7000000
8000000
9000000
10000000
11000000
12000000
13000000
14000000
15000000
16000000
17000000
18000000
19000000
20000000
1 4 7 10 13 16 19 22 25 28 31 34 37 40 43 46 49 52 55 58 61 64
2n
n4
n3
Hierarquia de funções
Hierarquia de funções do ponto de vista assintótico:
ncnnnc cncnnnnn loglogloglog1
onde e c são constantes arbitrárias tais que 0 < < 1 < c.
Exemplo
(Ordenação por Inserção)
void insercao(int *v, int n)
{
int i, j, x;
for (i = 1; i < n; i++)
{
x = v[i];
j = i - 1;
while (j >= 0 && v[j] > x)
{
v[j+1] = v[j];
j--;
}
v[j+1] = x;
}
}
Exemplo
(Bubble Sort)
void bubble(int *v, int n)
{
int i, j, aux;
for (i = n - 1; i > 0; i--)
{
for (j = 0; j < i; j++)
{
if (v[j] > v[j+1])
{
aux = v[j];
v[j] = v[j+1];
v[j+1] = aux;
}
}
}
}
Exemplo
(Pesquisa Binária)
int pesqbin(int *v, int p, int r, int e)
{
int q;
if (r<p)
return -1;
q = (p + r)/2;
if (e == v[q])
return q;
if (e < v[q])
return pesqbin(v, p, q-1, e);
return pesqbin(v, q+1, r, e);
}
Exemplo
(Pesquisa Binária)
int pesqbin(int *v, int p, int r, int e)
{
int q;
if (r<p)
return -1;
q = (p + r)/2;
if (e == v[q])
return q;
if (e < v[q])
return pesqbin(v, p, q-1, e);
return pesqbin(v, q+1, r, e);
}
Relação de Recorrência:
T(n) = T(n/2) + O(1)
T(1) = O(1)
A relação abaixo descreve de forma
mais precisa a execução, mas a
simplificação acima não altera a
complexidade:
T(n) = T(n/2 - 1) + O(1)
T(1) = O(1)
Relação de Recorrência
T(n) = T(n/2) + 1
T(n/2) = T(n/22) + 1
T(n/22) = T(n/23) + 1
...
T(n/l-1) = T(n/2l) + 1
12
l
n
n = 2l
l = log2 n
T(n) = 1 + 1 + ... + 1 + T(1)
log2 n vezes
O(log n)
Mudança de base:
b
nn
a
ab
log
loglog
Exemplo
(Pesquisa Binária)int pesqbin2 (int *v, int n, int e)
{
int p, q, r;
p = 0; r = n-1;
do
{
q = (p + r) / 2;
if (e == v[q])
return q;
if (e < v[q])
r = q -1;
else
p = q + 1;
} while (p<= r);
return -1;
}
Recursividade de cauda
Uma função apresenta recursividade de cauda se nenhuma
operação é executada após o retorno da chamada recursiva,
exceto retornar seu valor.
Em geral, compiladores, que executam otimizações de código,
substituem as funções que apresentam recursividade de cauda por
uma versão não recursiva dessa função.
Exemplo
(Merge Sort)
int mergeSort(int *v, int p, int r)
{
int q;
if (p<r)
{
q = (p+r)/2;
mergeSort(v, p, q);
mergeSort(v, q+1, r);
merge(v, p, q, r);
}
}
void mSort(int *v, int n)
{
mergeSort(v, 0, n-1);
}
Exemplo
(Merge Sort)
int mergeSort(int *v, int p, int r)
{
int q;
if (p<r)
{
q = (p+r)/2;
mergeSort(v, p, q);
mergeSort(v, q+1, r);
merge(v, p, q, r);
}
}
void mSort(int *v, int n)
{
mergeSort(v, 0, n-1);
}
Relação de Recorrência:
T(n) = 2T(n/2) + O(n)
T(1) = O(1)
Dividir e Conquistar
Desmembrar o problema original em vários subproblemas
semelhantes, resolver os subproblemas (executando o mesmo
processo recursivamente) e combinar as soluções.
Quick Sort
void quickSort(int *a, int p, int r)
{
int q;
if (p < r)
{
q = particao(a, p, r);
quickSort(a, p, q);
quickSort(a, q + 1, r);
}
}
Quick Sort
int particao(int *v, int e, int d)
{
int pivo, j, aux;
pivo = e; // Geralmente essa não é a melhor escolha para o pivô.
for (j = e + 1; j <= d; ++j)
{
if (v[j] < v[e])
{
++pivo;
swap(&v[pivo], &v[j]);
}
}
swap(&v[e], &v[pivo]);
return pivo;
}
Propriedades dos Somatórios
n
i
i
ni
i
n
i
n
i
i
n
i
iii
n
i
i
n
i
i
aa
baba
acca
0
0
0 00
00
)(
(Distributiva)
(Associativa)
(Comutativa)
Propriedades das Potências
nmnm
n
nn
nnn
nm
n
m
nmnm
aa
bb
a
b
a
baab
aaa
a
aaa
)(
0,
)(
0,
Propriedades dos Logaritmos
ac
c
cb
b
c
b
ccc
ccc
b
a
b
bb
a
ca
b
aa
aca
baba
baab
ba
bcca
loglog
log
log
loglog
loglog
loglog)/(log
loglog)(log
log
Notação Assintótica
Limite Inferior (Notação )
Uma função f(n) é o limite inferior de outra função g(n) se
existem duas constantes positivas c e n0 tais que, para n > n0,
temos |g(n)| c.|f(n)|, g(n) = (f(n)).
0
50
100
150
200
250
300
350
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
n2
n2 + 4n - 4
n2 + 4n - 4 = (n2)
Notação Assintótica
Limite Firme (Notação )
Uma função f(n) é o limite restrito de outra função g(n) se existem
três constantes positivas c1, c2, e n0 tais que, para n > n0, temos
c1.|f(n)| |g(n)| c2.|f(n)|, g(n) = (f(n))
0
100
200
300
400
500
600
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
n2 + 4n - 4
n2
2n2
n2 + 4n - 4 = (n2)
Ordenação por Inserção
0
5
10
15
20
25
30
35
40
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
Pior caso Caso médio
Melhor caso
Pior Caso: (n2-n)/2
O(n2), (n2), (n2).
Caso Médio: n2/4
O(n2), (n2), (n2).
Melhor Caso: n-1
O(n), (n), (n).
Heap Binário
É um arranjo, onde os dados estão organizados de forma que podem ser
acessados como se estivessem armazenados em uma árvore binária. No
caso de um heap máximo, os elementos armazenado em uma subárvore
serão sempre menores que o elemento armazenado na raiz. Essa árvore
é completa todos seus níveis, com a possível exceção do nível mais
baixo.
0 1 2 3 4 5 6 7 8 9
12 10 11 8 9 1 4 5 7 2 12
1110
8
75
49
2
1
int esquerda (int i)
{return (2 * i + 1);}
int direita(int i)
{return (2 * i + 2);}
Heap Binário
void heapify (int *a, int n, int i)
{
int e, d, maior;
e = esquerda(i);
d = direita(i);
if (e < n && a[e] > a[i])
maior = e;
else
maior = i;
if (d < n && a[d] > a[maior])
maior = d;
if (maior != i)
{
swap (&a[i], &a[maior]);
heapify(a, n, maior);
}
}
3
n
3
n
3
n
)1()1(
)1()32()(
OT
OnTnT
Heap Binário
int heapExtract(int *a, int n)
{
int maior;
maior = a[0];
a[0] = a[n - 1];
heapify(a, n - 1, 0);
return maior;
}
void buildHeap(int *a, int n)
{
int i;
for (i = (n-1)/2; i >= 0; i--)
heapify(a, n, i);
}
Heap Binário
void buildHeap(int *a, int n)
{
int i;
for (i = (n-1)/2; i >= 0; i--)
heapify(a, n, i);
}
)(
2)()(2log
0
nO
ihnTn
i
i
h
Heap Sort
void heapSort(int *a, int n)
{
int i;
buildHeap(a, n);
for (i = n - 1; i > 0; i--)
{
swap(&a[0], &a[i]);
heapify(a, i, 0);
}
}
Algoritmos com Inteiros
Até esse momento temos considerado constante a complexidade
de operações como: adição, subtração, multiplicação, divisão,
módulo e comparação.
Mas quando essas operações envolvem números cujo o tamanho,
em número de bits, é muito maior que a palavra do processador
(atualmente 32 ou 64 bits)?
Algoritmos com Inteiros
A adição e multiplicação de grandes números em computadores é
bastante similar a operações com bits.
Carry:11 1
1111010 (122)
1100011 (99)
11011101 (221)
Podemos considerar que a adição de grandes números tem
complexidade O(n), onde n é o número de bits.
+
bnbn-1 ... b2b1b2nb2n-1 ... bn+2bn+1
Adição de 2n bits, onde n é o tamanho da
palavra do processador:
Carry
Algoritmos com Inteiros
(Multiplicação)
bigInt mul (bigInt x, bigInt y)
{
bigInt r = 0;
while (y > 0) // Comparação entre inteiros grandes
{
r = r + x; // Adição entre inteiros grandes O(n).
y--;
}
return r;
}
O(n) + O(n) + ... + O(n)
y vezes
Sendo n o número de bits, qual o valor de y no pior caso?
Algoritmos com Inteiros
(Multiplicação)
12
215
60 (multiplica por 5, desloca 0)
12 (multiplica por 1, desloca 1)
24 (multiplica por 2, desloca 2)
2580
1010 (10)
1101 (13)
1010 (multiplica por 1, desloca 0)
0000 (multiplica por 0, desloca 1)
1010 (multiplica por 1, desloca 2)
1010 (multiplica por 1, desloca 3)
10000010 (130)
XX
Algoritmos com Inteiros
(Multiplicação)
bigInt mul(bigInt x, bigInt y)
{
bigInt r;
if (y == 0) return 0;
r = mul(x, y >> 1) // r = x * (y/2)
if (par(y))
return r << 1; // return 2*r
else
return x + r << 1; // return x+2*r
}
Algoritmos com Inteiros
(Multiplicação)
)()(22
)2)(2(
2
2
2/
2/2/
2/
2/
RRLRRL
n
LL
n
RL
n
RL
n
RL
n
RL
RL
n
RL
yxyxyxyxxy
yyxxxy
yyyyy
xxxxx
Algoritmos com Inteiros
(Multiplicação)
bigInt mul(bigInt x, bigInt y) // onde n é o número de bits dos inteiros x e y.
{
bigInt xl, xr, yl, yr, p1, p2, p3, p4;
if (n == 1) return xy; // se numéro de bits for 1 (retorna 1 se x = 1 ou y =1).
xl = leftMost(x, n/2); xr= rightMost(x, n/2); // bits mais à esquerda e mais à direita.
yl = leftMost(y, n/2); yr= rightMost(y, n/2);
p1 = mul (xl, yl);
p2 = mul (xl, yr);
p3 = mul (xr, yl);
p4 = mul (xr, yr);
return p1 << n + (p2 + p3) << (n/2) + p4;
}
)()(22 2/
RRLRRL
n
LL
n yxyxyxyxxy
Números Primos
Uma número natural é primo se possui exatamente dois
divisores: o número 1 e ele mesmo. Todo número
composto pode representado pela multiplicação de seus
fatores primos.
Primos relativos:
Dois inteiros são chamados de primos relativos se o
único inteiro positivo que divide os dois é 1. Por
exemplo, 49 e 15 são primos relativos.
Números Primos
Teste de primalidade: Dado um número n, determinar
se n é primo (fácil).
Fatoração de inteiros: Dado um número n, representar
n através de seus fatores primos (difícil).
Aritmética Modular
É um sistema para manipular faixas restritas de números inteiros.
Relação de congruência:
a b (mod m) m divide (a – b).
a b (mod m) se e somente se a mod m = b mod m.
Exemplos:
38 14 (mod 12), 38 mod 12 = 14 mod 12
-10 38 (mod 12), -10 mod 12 = 38 mod 12
Aritmética Modular
O inverso multiplicativo modular de um inteiro a no módulo m é
um inteiro x tal que: ax 1 (mod m).
O inverso multiplicativo de a no módulo m existe se e somente
se a e m são primos relativos.
O inverso multiplicativo de a no módulo m é um inteiro x que
satisfaz a equação: ax = 1 + my.
Exemplo: Qualquer número congruente à 5 (no módulo 12) é o
inverso multiplicativo de 5 no módulo 12: {…, -7, 5, 17, 29, …}.
Criptográfia RSA
Transforma um inteiro M (que representa um bloco dedados da mensagem) em um inteiro C (que representaum bloco da mensagem criptografada), usando aseguinte função:
Sendo n = pq, onde p e q são números primos, e e umprimo relativo de (p - 1)(q - 1):
mdc (e, (p - 1)(q - 1)) = 1
Chave pública = (e, n).
nMC e mod
Criptográfia RSA
A transformação da mensagem criptografada C na
mensagem original é executada através da formula:
Onde d é o inverso modular de e:
Chave privada = (d, n).
nCM d mod
))1)(1mod((1 qped
Criptográfia RSA
(Exemplo)
Para M = 92, p = 11 e q = 13 o valor de n = 143.
Escolher arbitráriamente um valor para e = 17, note que:
mdc (17, 120) = 1. Chave pública = (17, 143).
Como 17d ≡ 1 (mod 120), podemos dizer que 17d = 1 + 120a,
uma possível solução é a = -1 e d = -7 (ver algoritmo de Euclides Estendido), outras soluções são a = 16 e d = 113, a = 33 e d = 233, …
Se -7 é o inverso modular de 17 mod 120 então todo inteiro congruente a -7 mod 120 é também o inverso modular de 17 mod 120: (…, -7, 113, 233, 353, …). Chave privada = (113, 143).
C = 9217 mod 143, C = 27.
M = 27113 mod 143, M = 92.
Algoritmos Gulosos(Greedy Algorithms)
Uma técnica para resolver problemas de otimização, um
algoritmo guloso sempre faz a escolha que parece ser a
melhor em um determinado momento, esperando que
essa melhor escolha local leve ao melhor resultado do
problema como um todo.
Uma técnica simples, mas que na maioria das vezes não
leva ao resultado ótimo.
Codificação de Huffman
É um método de compressão de dados. Esse método usa a
frequência com que cada símbolo ocorre, em uma coleção de
dados, para determinar um código de tamanho variável para o
símbolo.
Caractere Frequência Código
(fixo)
Código
(variável)
a 45 000 0
b 13 001 101
c 12 010 100
d 16 011 111
e 9 100 1101
f 5 101 1100
Exemplo:
... faca ...
... 101000010000 ...
... 110001000 ...
Codificação de Huffman
(Exemplo)
a:45
100
55
25 30
c:12 b:13 14 d:16
f:5 e:9
0
0
0
0
0
1
1
1
1
1
Exemplo:
... faca ...
... 101000010000 ...
... 110001000 ...
Codificação de Huffman
Huffman(C)
n |C|
Q C
para i 1 até n - 1
z AlocaNo()
x z.esq Extrair-Minimo(Q)
y z.dir Extrair-Minimo(Q)
z.valor = x.valor + y.valor
Inserir(Q, z)
retorne Q
Árvore Geradora Mínima(Minimum Spanning Tree)
Uma árvore geradora para um grafo conexo é uma
árvore que conecta todos os vértices do grafo e que o
conjunto de arestas é um subconjunto das arestas
desse grafo. A árvore geradora é mínima se o
somatório dos custos associados cada arestas for o
menor possível.
a
cb d
ei
g fh
9
14
10
4
4 2
21
68
117
8 7
Árvore Geradora Mínima(Minimum Spanning Tree)
MST-PRIM(G,w, r) // G – grafo, w – custos, r – vértice inicial
para cada u G.V
u.key = ∞
u.π = null
r.key = 0
Q = G.V
Enquanto Q ≠ Ø // Executa |V| vezes
u = Extrai-Minimo(Q) // O(log |V|) heap binário
para cada v G.Adj[u] // Executa |A| vezes
se v Q e w(u, v) < v.key
v. π = u
v.key = w(u, v) // propriedade de heap O(log |V|)
Árvore geradora mínima = {(v, v.π) | v V - {r}}
a
cb d
ei
g fh
9
14
10
4
4 2
21
68
117
8 7
Problemas tratáveis e intratáveis
Problemas tratáveis: resolvidos por algoritmos que
executam em tempo polinomial.
Problemas intratáveis: não se conhece algoritmos que
os resolvam em tempo polinomial.
Problemas de Decisão.
Problemas de Otimização: Cada solução possível tem
um valor associado e desejamos encontrar a solução
com melhor valor.
Problemas de Decisão: Problemas que tem resposta
sim ou não.
Problema do Caixeiro Viajante
Um vendedor deseja visitar n cidades e retornar a cidade
de origem. Dado um grafo não orientado completo com
n vértices, onde existe um custo c(i, j) (associado a cada
aresta) para viajar da cidade i a cidade j. Qual o trajeto
com custo mínimo?
A
B
E
C
D
10
2
4
11 5
3
9
7
46
Problema do Caixeiro Viajante
Existe um caminho com custo menor que k?
Algoritmos Não Deterministas
Capaz de escolher uma entre várias alternativas possíveis
a cada passo. A alternativa escolhida será sempre a
alternativa que leva a conclusão esperada, caso essa
alternativa exista.
int pesquisa(Estrutura *v, int n, int chave){
int i;
for (i = 0; i < n; i++)if (v[i].chave == chave)
return i;return -1;
}
int pesquisa(Estrutura *v, int n, int chave){
int i;
i = escolheND(0, n - 1);if (v[i].chave == chave)
return i;return -1;
}
Classes de Problemas P e NP
Classe de Problemas P: Problemas que podem ser
resolvido (por algoritmos deterministas) em tempo
polinomial.
Classe de Problemas NP: Problemas que podem ser
resolvidos por algoritmos não deterministas em tempo
polinomial. Ou problemas que a solução pode ser
verificada em tempo polinomial.
NP
PPossível relação entre
as classes:
Redução de Problemas
Problema
A
Algoritmo de
Redução
Problema
B
Algoritmo que
Resolve B
Sim
Não
Solução para o Problema A
Ciclo Hamiltoniano
Um Ciclo Hamiltoniano em um grafo não orientado é
um caminho que passa por cada vértice do grafo
exatamente uma vez.
Problema do Ciclo Hamiltoniano: Um grafo G possui
um ciclo Hamiltoniano?
A B
D
C
E
Redução do Problema do Ciclo Hamiltoniano
ao Problema do Caixeiro Viajante
para cada vértice i
para cada vértice j
se (i, j) H então c(i, j) 0
senão c(i, j) 1
A B
D
C
E
A B
D
C
E
0
01
0
0
0
0
1
1
1
pRedução em
tempo
polinomial
G (G´, 0)
(SAT) Satisfazibilidade
de Fórmulas Booleanas
O problema da Satisfazibilidade de fórmulas booleanas
consiste em determinar se existe uma atribuição de
valores booleanos, para as varáveis que ocorrem na
fórmula, de tal forma que o resultado seja verdadeiro.
Exemplo:
)()()( 32132121 xxxxxxxx
NP-Completo
Teorema de Cook: SAT está em P se e somente se P = NP.
Um problema X é NP-Completo se:
1. X NP
2. X´ p X para todo X´ NP.
NP
PNP-Completo
Possível relação entre
as classes:
Forma Normal Conjuntiva
Um literal é uma variável proposicional ou sua negação.
Uma formula booleana está na Forma Normal Conjuntiva
(CNF) se é expressa por um grupo cláusulas AND, cada
uma das quais formada por OR entre literais.
Uma fórmula booleana esta na k-CNF se cada cláusula
possui exatamente k literais:
)()()( 321321321 xxxxxxxxx
3-CNF-SAT
Verificar se uma fórmula booleana na 3-CNF é
satisfazível.
3-CNF-SAT é NP-Completo:
– 3-CNF-SAT NP.
– SAT p 3-CNF-SAT.
SAT p 3-CNF-SAT
Dada uma fórmula booleana: )( 211 xxx
1x
1x2x
1y
2y
3y
1. Construir uma árvore que
represente à fórmula.
2. Introduzir uma variável yi
para a raiz e a saída de cada
no interno.
SAT p 3-CNF-SAT
))(()())(( 213322111 xxyyyyxyy
1x
1x2x
1y
2y
3y
3. Reescrevemos a fórmula
original como conjunções
entre a variável raiz
cláusulas que descrevem as
operações de cada nó.
Introduz 1 variável e 1 cláusula
para cada operador.
SAT p 3-CNF-SAT
Para cada construir uma tabela tabela verdade, usando
as entradas que tornam verdade, construir uma
forma normal disjuntiva para cada .
))(()())(( 213322111 xxyyyyxyy
i
i
i
SAT p 3-CNF-SAT
))(()())(( 213322111 xxyyyyxyy
y1 x1 y2
V V V V
V V F F
V F V F
V F F F
F V V F
F V F V
F F V V
F F F V
)( 2112 yxy
)(
)(
)(
)(
211
211
211
2112
yxy
yxy
yxy
yxy
Cada cláusula de ´ introduz no
máximo 8 cláusulas em ´´, pois cada
cláusula de ´ possui no máximo 3
variáveis.
SAT p 3-CNF-SAT
)()(
)()(
211211
2112112
yxyyxy
yxyyxy
)()(
)()(
211211
2112112
yxyyxy
yxyyxy
Converter a fórmula para a CNF usando as leis de De Morgan:
SAT p 3-CNF-SAT
O último passo faz com que cada cláusula tenha
exatamente 3 literais, para isso usamos duas novas
variáveis p e q. Para cada cláusula Ci em :
1. Se Ci tem 3 literais, simplesmente inclua Ci.
2. Se Ci tem 2 literais, , inclua:
3. Se Ci tem 1 literal, l1, inclua:
Introduz no máximo 4 cláusulas por cláusula em .
)( 21 llCi
)()( 2121 pllpll
)()()()( 1111 qplqplqplqpl
SAT p 3-CNF-SAT
))(()())(( 213322111 xxyyyyxyy
)()()()( 11111 qpyqpyqpyqpy
))(()())(( 213322111 xxyyyyxyy
)()()()(
)()()()(
211211211211
1111
yxyyxyyxyyxy
qpyqpyqpyqpy
CLIQUE
Um Clique em um grafo não direcionado G = (V, A) é um
subconjunto de vértices V’ V, onde cada vértice está conectado
por uma aresta. Ou seja um subgrafo completo.
Versão de otimização: Encontrar o maior Clique possível.
Versão de decisão: Existe um Clique de tamanho ≥ k?
a
b c
d e
f
CLIQUE
Clique NP
a
b c
d e
f
Dado um grafo G = (V, A) , a solução (certificado) V’ e k
Verificar de |V| ≥ k
Para cada u V’
Para cada v V’
Se u ≠ v então verificar se (u, v) A
3-CNF-SAT p CLIQUE
ϕ = (x1 ˅ ~x2 ˅ ~x3) ˄ (~x1 ˅ x2 ˅ x3) ˄ (x1 ˅ x2 ˅ x3)
x1
~x2
~x3
~x1 x2 x3
x1
x2
x3
Existe um clique de tamanho k? Sendo k o número de cláusulas.
3-CNF-SAT p CLIQUE
Dada uma instancia ϕ do problema 3-CNF-SAT, cada cláusula de
ϕ gera 3 vértices, sendo que cada vértice corresponde a um literal
da cláusula.
É adicionada uma aresta para cada par de vértices u e v se as
duas condições a seguir forem satisfeitas:
• Se u e v não foram gerados a partir da mesma cláusula;
• Se u e v não foram gerados a partir de um literal que
corresponde a uma variável e sua negação. Por exemplo, um
vértice correspondente a variável x1 não pode ser conectado a
um vértice correspondente a negação de x1.
Cobertura de Vértices(VERTEX-COVER)
Uma Cobertura de Vértices de um grafo não orientado
G = (V, A) é um subconjunto V’ V tal que se (u, v) A,
então u V’ ou v V’.
a
b c
d e
f
Cobertura de Vértices(VERTEX-COVER)
Versão de otimização: Encontrar menor Cobertura de
Vértices.
Versão de decisão: Existe uma cobertura de tamanho k?
a
b c
d e
f
Cobertura de Vértices(VERTEX-COVER)
Cobertura de Vértices NP.
Dado um grafo G =(V, A) e a solução (certificado) V´
Verificar de |V| ≥ k
Para cada (u, v) A
Verificar se u V´ ou v V´
a
b c
d e
f
CLIQUE pVERTEX-COVER
a
b c
d e
fa
b c
d e
f
CLIQUE
Entrada (G, k), onde G = (V, A)
VERTEX-COVER
Entrada ( , |V| - k)G
SUBSET-SUM
Dado um conjunto finito de de inteiros positivos S e um
inteiro t > 0, determinar se existe um subconjunto S’ S
onde o somatório dos elementos de S’ é igual a t.
n
i
i ts1
3-CNF-SAT p SUBSET-SUM
)()( 321321 xxxxxx x1 x2 x3 C1 C2
v1 1 0 0 0 1
v'1 1 0 0 1 0
v2 0 1 0 1 1
v'2 0 1 0 0 0
v3 0 0 1 0 0
v'3 0 0 1 1 1
s1 0 0 0 1 0
s'1 0 0 0 2 0
s2 0 0 0 0 1
s'2 0 0 0 0 2
t 1 1 1 4 4
Programação Dinâmica
Método de solução de problemas baseado no uso de
tabelas.
Resolve problemas combinando as soluções de
subproblemas. As soluções para cada um dos
subproblemas são armezadas em uma tabela, dessa
forma uma solução não necessita ser recalculada quando
um subproblema ocorre repetidas vezes.
Programação Dinâmica
É indicada quando um subproblema ocorre
repetidamente e sua solução pode ser reaproveitada.
Exemplo:
1 se )2()1(
10 se )(
nnfibnfib
nnnnfib
Programação Dinâmica
Abordagem top-down (Memoization)
Pode ser vista como o uso de recursão com apoio de
tabelas:
• Como ocorre em algoritmos recursivos (divisão e
conquista), um problema é resolvido dividindo-o em
subproblemas menores, resolvendo esses
subproblemas recursivamente e combinando suas
soluções.
• A solução de cada subproblema é armazenada em uma
tabela, dessa forma não é recalculada caso o
subproblema ocorra repetidamente.
Programação Dinâmica
Abordagem top-down (Memoization)
Fib(n)
se n ≤ 1 então
retorne n
senão
se F[n] está indefinido
F[n] ← Fib(n – 1) + Fib(n – 2)
retorne F[n]
Programação DinâmicaAbordagem bottom-up
Fib(n)
F[0] = 0
F[1] = 1
para i ← 2 até n
F[i] = F[i – 2] + F[i – 1]
retorne F[n]
Programação DinâmicaChange-Making Problem
Dado um conjunto de n moedas, cada uma com um
valor xi, e um valor t, achar o conjunto {f1, f2, …, fn},
onde fi representa a quantidade de moedas de valor xi,
que minimiza:
tal que:
n
i
if1
n
i
ii tfx1
Programação DinâmicaChange-Making Problem
Imprimir-Troco (s, x, t)
Enquanto t > 0
Imprimir (x[s[t]])
t ← t – x[s[t]]
Onde c[t] é o número mínimo de moedas para totalizar
o valor t e s[t] é o índice da última moeda que ocorre
nessa solução.
t c s
0 0 -
1 1 1
2 1 2
3 2 2
4 2 2
5 1 3
6 2 3
7 2 3
8 3 3
9 3 3
Exemplo: x = {1, 2, 5} e t = 9
Programação DinâmicaChange-Making Problem
Troco(x[1..n], t)
c[0] ← 0
para p ← 1 até t
min ← ∞
para i ← 1 até n
se (x[i] p) e (c[p – x[i]] + 1 min) então
min ← c[p – x[i]] + 1
moeda ← i
c[p] ← min
s[p] ← moeda
retorne (c, s)
Programação Dinâmica
(Subset-Sum)
Dado um conjunto de inteiros positivos, representados
como um arranjo S[1..n], e um inteiro t, existe algum
subconjunto de S tal que a soma de seus elementos seja t.
])[,1(),1(
0 se
0 se
),(
ixtiSubsetStiSubsetS
nitFalsidade
tVerdade
tiSubsetS
Programação Dinâmica
(Subset-Sum)
Exemplo: x = {2, 3, 5} e t = 8.
])[,1(),1(
0 se
0 se
),(
ixtiSubsetStiSubsetS
nitFalsidade
tVerdade
tiSubsetS
Programação Dinâmica
(Subset-Sum)
SubsetSum(x[1..n], t)
S[n + 1, 0] ← Verdade
para j ← 1 até t
S[n + 1, j] ← Falsidade
para i ← n até 1
S[i, 0] ← Verdade
para j ← 1 até x[i] – 1
S[i, j] ← S[i + 1, j]
para j ← x[i] até t
S[i, j] ← S[i + 1, j] v S[i + 1, j – x[i]]
retorne S[1,t]
Programação Dinâmica
(Subset-Sum)
0 1 2 3 4 5 6 7 8 9 10
1 V V F V V V V V V V V
2 V F F V F V F V V F V
3 V F F F F V F V F F F
4 V F F F F F F V F F F
5 V F F F F F F F F F F
Exemplo: x = {1, 3, 5, 7} e t = 10.
Algoritmos que Executam
em Tempo Pseudo-Polinomial
SUBSET-SUM
Usando programação dinâmica podemos implementar
um algoritmo pseudo-polinomial com complexidade
O(nt), onde n é o numero de elemetos no conjunto e t o
valor do somatório que se deseja alcançar.
Se restringirmos nossa atenção a instâncias do problema
onde o valor de t é limitado por um polinómio existe
uma solução eficiente.
Algoritmos que Executam
em Tempo Pseudo-Polinomial
Essa restrição pode ser bastante razoável na prática:
• Problemas onde é impossível a ocorrência de números
muito grandes (e.g. problemas de escalonamento).
• Problemas onde o tamanho do número possa ser restrito ao
tamanho da palavra do processador.
Note que esse não é o caso da redução do 3-CNF-SAT ao
SUBSET-SUM, onde o valor de t cresce exponenciamente
ao número de variáveis e cláusulas presentes na fórmula
booleana.
Heurísticas e
Algoritmos de Aproximação
Procedimentos heurísticos são métodos que buscam
soluções próximas a solução ótima de um problema.
Utilizam alguma informação (ou intuição) sobre a
instância do problema para resolvê-lo de forma
eficiente.
Um algoritmo de aproximação, além de uma solução
eficiente, garante a qualidade da solução. É necessário
provar a garantia de proximidade da solução ótima.
Algoritmos de Aproximação
Caixeiro Viajante
Dado o grafo G = (V, A) e o custo c:
1. Selecione um vértice r V para ser
o vértice raiz.
2. Obtenha a ávore geradora mínima a
partir de r.
3. Faça P ser a lista de vertices
ordenados de acordo com a primeira
visita, considerando um percurso em
pré-ordem.
Se a função custo satisfaz a desigualdade
de triângulos: c(u, w) ≤ c(u, v) + c(v, w)
c(T ) < c(ótimo)
c(T concatenado com [r]) ≤ 2c(ótimo)
A
B
E
C
D
10
2
4
11 5
3
9
7
46
A
B
E
C
D
10
2
4
11 5
3
9
7
46
Referências
Algoritmos. Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest,
Cliford Stein. Campus.
Algorithms. Sanjoy Dasgupta, Christos Papadimitriou, Umesh Vazirani.
McGraw Hill.
Concrete Mathematics: A Foundation for Computer Science (2nd Edition).
Ronald L. Graham, Donald E. Knuth, Oren Patashnik. Addison Wesley.
M. R. Garey and D. S. Johnson. 1978. “Strong” NP-Completeness Results:
Motivation, Examples, and Implications. J. ACM 25, 3 (July 1978)
