Técnicas de Projetos de algoritmos

Olá, nesse post irei falar um pouco sobre técnicas de projetos de algoritmos.

O que são Técnicas de Projetos de Algoritmos ?

São técnicas que compreendem os métodos de codificação de algoritmos de forma a acentuar sua complexidade, levando em conta a forma que determinado algoritmo chega a solução desejada.

Técnicas comuns são: 'Força Bruta' e a 'Divisão e conquista'.

Força Bruta:
A força bruta (ou busca exaustiva) é um algoritmo de uso geral que consiste em enumerar todos os possíveis candidatos de uma solução e verificar se cada um satisfaz o problema.
Ex.: Um algoritmo para encontrar os divisores de um número natural n é enumerar todos os números naturais de 1 a n e verificar para cada um se ele dividido por n resulta em resto 0;
Esse algoritmo possui uma implementação muito simples, e sempre encontrará uma solução se ela existir. Entretanto, seu custo computacional é proporcional ao número de candidatos a solução, que, em problemas reais, tende a crescer exponencialmente. Portanto, a força bruta é tipicamente usada em problemas cujo tamanho é limitado, ou quando há uma heurística usada para reduzir o conjunto de candidatos para uma espaço aceitável. Também pode ser usado quando a simplicidade da implementação é mais importante que a velocidade de execução, como nos casos de aplicações críticas em que os erros de algoritmo possuem em sérias consequências.

Divisão e conquista:
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.
A técnica soluciona o problema em 3 técnicas: Divisão, conquista e combinação.
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.


Bom, espero que tenha entendido, em breve postarei mais sobre o assunto. Qualquer dúvida deixe nos comentário que procurarei responder em breve.

Fonte:Técnicas de Projetos de Algoritmos