Divisão e conquista: diferenças entre revisões
Conteúdo apagado Conteúdo adicionado
m colocar data, Replaced: {{wikificar}} → {{Wikificação|data=Fevereiro de 2008}} utilizando AWB |
wikificado e expandido |
||
Linha 1:
'''Divisão e Conquista''' (do [[inglês]] Divide and Conquer) em [[computação]] é uma [[Técnicas de Projeto de Algoritmos|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 [[recursão|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:
# '''Divisão''': o problema maior é dividido em problemas menores e os problemas menores obtidos são novamente divididos sucessivamente de maneira recursiva.
# '''Conquista''': o resultado do problema é calculado quando o problema é pequeno o suficiente.
# '''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 [[processador|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 [[LIFO|pilha]] de chamadas.
=={{Ver também}}==
* [[Indução matemática]]
* [[Torre de Hanoi]]
* [[Merge sort]]
* [[Quicksort]]
| |||