Divisão e Conquista

Prévia do material em texto

Análise de Algoritmos
DIVISÃO E CONQUISTADIVISÃO E CONQUISTA
Bacharelado em Ciência da Computação
Flávia Coelho
flaviacoelho@ufersa.edu.br
Atualizado em Setembro de 2016
 
Motivação
● Considerar um problema de entrada grande
● Quebrar a entrada em pedaços menores → 
DIVISÃO
● Resolver cada pedaço separadamente → 
CONQUISTA
● Combinar os resultados em uma solução 
global
Obtem soluções eficientes para resolver
problemas nos quais os subproblemas
são versões menores do problema 
original
 
Exemplo
Merge Sort
 
Passos Fundamentais
DIVIDIR O PROBLEMA ORIGINAL
EM SUBPROBLEMAS MENORES
RESOLVER CADA SUBPROBLEMA
COMBINAR AS SOLUÇÕES ENCONTRADAS,
COMPONDO UMA SOLUÇÃO PARA O 
PROBLEMA ORIGINAL
 
Algoritmo DeC Genérico
divisãoeConquista(x){
  se x é pequeno ou simples faça
    retorne resolver(x)
  casocontrário{
    decompor x em conjuntos menores x0, x1, …, xn
    para i   0 a n ← faça
      yi   divisãoeConquista(x← i)
    combinar yi’s
    retorna y
  }
}
 
Exemplo
Encontrar o maior elemento do array A[1..n]
maximo (A[1..n]){
max   A[1]←
  for i   2 ← to n do
if(A[i] > max) then max   A[i]←
     return max
}
 
Exemplo
Encontrar o maior elemento do array A[1..n]
maximoDeC(A[x..y]){
if (x – y) <= 1 then 
return max (A[x], A[y])
else{
          m   (x + y)/2←
          v1   maximo(A[x..m])←
          v2   maximo(A[m+1..y]) ←
} 
return max (v1, v2)
}
 
Exemplo
Potência - Computar an, onde n  N 
pow(a, n){
p   a←
  for i   2 ← to n do
p   p * a←
return p
}
 
Exemplo
Potência - Computar an, onde n  N 
powDeC(a, n){
if n = 0 then 
return 1
if n é par then
y = powDeC(a,n/2)
return y * y
else 
y = powDeC(a,(n­1)/2)
return a*y*y
}
 
Técnica Genérica de Análise da 
Complexidade Computacional
● Algoritmos baseados em divisão-e-
conquista são recursivos
● A maioria dos algoritmos divide o 
problema em a subproblemas da 
mesma natureza, de tamanho n/b
● T(n) = aT(n/b) + f(n) 
● Vantagens
● São altamente paralelizáveis
 
Exemplo
Análise da Complexidade Computacional
maximoDeC(A[x..y]){
if (x – y) <= 1 then 
return max (A[x], A[y])
else{
          m   (x + y)/2←
          v1   maximo(A[x..m])←
          v2   maximo(A[m+1..y]) ←
} 
return max (v1, v2)
}
 
Exemplo
Análise da Complexidade Computacional
powDeC(a, n){
if n = 0 then 
return 1
if n é par then
y = powDeC(a,n/2)
return y * y
else 
y = powDeC(a,(n­1)/2)
return a*y*y
}
 
Quando Utilizar Divisão e 
Conquista?
● Três condições devem ser satisfeitas
● Deve ser possível decompor uma 
instância em sub-instâncias
● A combinação dos resultados deve ser 
eficiente
● As sub-instâncias devem ser mais ou 
menos do mesmo tamanho
 
Leitura Recomendada
N. Ziviani. Projeto de Algoritmos com 
Implementações em Java e C++. 
Thompson Learning, 2007
 
Referências
Material didático elaborado por Jorge Cesar 
Abrantes de Figueiredo, UFCG 
(Universidade Federal de Campina 
Grande)
	Slide 1
	Slide 2
	Slide 3
	Slide 4
	Slide 5
	Slide 6
	Slide 7
	Slide 8
	Slide 9
	Slide 10
	Slide 11
	Slide 12
	Slide 13
	Slide 14
	Slide 15