Divisão e conquista – Wikipédia a enciclopédia livre

Prévia do material em texto

Divisão e conquista
Origem: Wikipédia, a enciclopédia livre.
Divisão e Conquista (do inglês Divide and Conquer) em computação é uma técnica de projeto de algoritmos
utilizada pela primeira vez por Anatolii Karatsuba em 1960 no algoritmo de Karatsuba.
Técnica
Esta técnica consiste em dividir um problema maior recursivamente em problemas menores até que o problema
possa ser resolvido diretamente. Então a solução do problema inicial é dada através da combinação dos
resultados de todos os problemas menores computados. Vários problemas podem ser solucionados através
desta técnica, como o da ordenação de números através do algoritmo merge sort e da transformação discreta
de Fourier através da transformada rápida de Fourier. Outro problema clássico que pode ser resolvido através
desta técnica é a Torre de Hanoi.
A técnica soluciona o problema através de três fases:
1. Divisão: o problema maior é dividido em problemas menores e os problemas menores obtidos são
novamente divididos sucessivamente de maneira recursiva.
2. Conquista: o resultado do problema é calculado quando o problema é pequeno o suficiente.
3. Combinação: o resultado dos problemas menores são combinados até que seja obtida a solução do
problema maior.
Eficiência
Problemas que utilizam esta técnica podem tirar proveito de máquinas com múltiplos processadores pois a fase
de divisão em problemas menores proporciona uma divisão natural do trabalho. Cada um dos problemas
menores obtidos pode ser calculado separadamente em um processador sem depender dos demais.
A solução por esta técnica também é eficiente no uso da memória cache pois ao final da fase de divisão grande
parte dos dados necessários para a fase de combinação já estão disponíveis na cache proporcionando um
acesso mais veloz aos dados. Porém o caráter recursivo das soluções acaba gerando um trabalho de
processamento maior devido ao uso de chamadas recursivas e o uso da pilha de chamadas.
Ver também
Indução matemática
Torre de Hanoi
Merge sort
Quicksort
Obtida de "http://pt.wikipedia.org/w/index.php?title=Divisão_e_conquista&oldid=32018252"
Categoria: Algoritmos de otimização
Esta página foi modificada pela última vez à(s) 13h29min de 29 de agosto de 2012.
Este texto é disponibilizado nos termos da licença Atribuição-Partilha nos Mesmos Termos 3.0 não
Adaptada (CC BY-SA 3.0); pode estar sujeito a condições adicionais. Consulte as condições de uso
para mais detalhes.