1
  • Qual a diferença entre as técnicas de design de algoritmo Divide and Conquer e Decrease and Conquer?
  • A divide é recursiva e a decrease não?
  • Algum exemplo para a decrease?
  • E dynamic programming?

1 Resposta 1

0

Olá! Primeiro é importante observar que todas essas técnicas são baseadas em indução.

Divide and conquer é uma técnica de projeto de algoritmos que consiste em dividir o problema em subproblemas menores. Esses algoritmos são divididos em duas fases: divisão e conquista. Na divisão, dividimos o problema ao meio (ou em alguma fração) e resolvemos cada subproblema. Na fase de conquista, combinamos as soluções dos subproblemas para obter a solução para o problema total. Exemplos de algoritmos que usam essa técnica são o MergeSort e o QuickSort.

Decrease and conquer é semelhante à divide and conquer, com a diferença de que nessa técnica a fase de decrease apenas diminui o problema, gerando um subproblema menor (ao invés de dividir em vários subproblemas). Após resolver o subproblema menor, a fase de conquista é executada para utilizar a solução do subproblema para obter a solução do problema total. Exemplos de algoritmos de decrease and conquer são Busca Binária (dividimos o vetor no meio e executamos a busca apenas em um dos lados) e DFS. Algoritmos de decrease and conquer também podem ser recursivos, a exemplo da busca binária.

Já a programação dinâmica é uma técnica que utiliza memorização para resolver subproblemas. Essa técnica faz sentido quando subproblemas se repetem. Um exemplo de problema que pode ser resolvido com programação dinâmica é o fibonacci, pois, fibonacci(N) = fibonacci(N-1) + fibonacci(N-2), fibonacci(N-1) = fibonacci(N-2) + fibonacci(N-3), e assim por diante... Note que o subproblema fibonacci(N-2) se repete. A programação dinâmica consiste em memorizar as solução dos subproblemas para que não sejam recalculados.
Outra coisa importante é que a programação dinâmica só pode ser aplicada a problemas com subestrutura ótima. Dizer que um problema tem subestrutura ótima significa que uma solução ótima para o problema maior contém as soluções ótimas para os subproblemas.

Estou deixando algumas referências com explicações mais detalhadas.

https://www.geeksforgeeks.org/decrease-and-conquer/
https://stackoverflow.com/questions/13538459/difference-between-divide-and-conquer-algo-and-dynamic-programming
https://pt.wikipedia.org/wiki/Programa%C3%A7%C3%A3o_din%C3%A2mica

Espero ter ajudado.

1
  • aqui tem uma resposta minha mostrando cálculo de números de fibonacci com memorização
    – zentrunix
    Commented 1/05/2019 às 22:04

Você deve fazer log-in para responder a esta pergunta.

Esta não é a resposta que você está procurando? Pesquise outras perguntas com a tag .