comp-aulas-2019-07

Prévia do material em texto

Projeto de Algoritmos usando Induc¸a˜o
Paradigmas de Projeto
I Paradigma Incremental:
usando induc¸a˜o fraca
I Paradigma Divisa˜o e Conquista:
usando induc¸a˜o forte
Hip. de Induc¸a˜o
{
Fraca : Paradigma Incremental
Forte : Paradigma Divisa˜o e Conquista
Caracterizando um problema
I Problema
I entrada de tamanho n
I X = {x1, x2, . . . , xn}
I Complexidade
I dado em func¸a˜o de n
I T (n)
Paradigma Incremental
Hip. de Induc¸a˜o Fraca: Incremental
I Base:
se n = n0 conhec¸o soluc¸a˜o para o problema
I H. I. Fraca:
I para X ′ = {x ′1, x ′2, . . . , x ′n−1}
I assume-se que sabemos resolver o problema para X ′
I Passo de Induc¸a˜o:
conhecendo a soluc¸a˜o para X ′, S(X ′), obtemos S(X )
Algoritmo Incremental
I Pseudo co´digo para o Paradigma INCremental
INC(X,n)
Se n <= n0, resolver usando caso base
Sena˜o
TE (n) – Escolher xi ∈ X tal que X ′ ← X − {xi}
INC(X’,n-1)
TC (n) – Obter S(X ) a partir de S(X
′) e xi
fim-se
Custo do Paradigma Incremental
Complexidade: T (n) = T (n − 1) + TE (n) + TC (n)
I T (n): custo total
I T (n − 1): custo da hipo´tese (HI fraca)
I TE (n): custo da escolha (xi ∈ X )
I TC (n): custo de obter S(X ), ou seja, da combinac¸a˜o de S(X ′) e xi
Paradigma de Divisa˜o e Conquista
Hip. de Induc¸a˜o Forte: (D & C)
I Base:
sabemos resolver para n = n0
I H. I. Forte:
I com X ′ = {x ′1, x ′2, . . . , x ′k},
I assume-se que sabemos resolver o problema para k < n
I Passo de Induc¸a˜o:
conhecendo a soluc¸a˜o para X ′, S(X ′), obtemos S(X )
Algoritmo de D&C
I Pseudo co´digo para o Paradigma D&C
D&C (X , 1, n)
Se n <= n0, resolve-se pelo caso base
Sena˜o
TD(n) – Particionar X em 2 subconjuntos, X1 e X2,
onde |X1| = |X2| = n2
D&C (X1, 1,
n
2 )
D&C (X2, 1,
n
2 )
TC (n) – Combinar X1 e X2
fim-se
Custo do Paradigma D&C
Complexidade: T (n) = 2T ( n2 ) + TD(n) + TC (n)
I T (n): custo total
I 2T ( n2 ): custo da hipo´tese (HI forte – 2 chamadas)
I TD(n): custo da divisa˜o (achar X1 e X2)
I TC (n): custo de obter S(X ), ou seja, de combinar S(X1) e S(X2)
Ideia geral
I Resolver um problema X de tamanho n
I Projetar um algoritmo para resolver X
I Dividir o problema X em problemas menores
I Incremental, X ′, ou com D&C, X1 e X2
	Projeto de Algoritmos