Técnicas de Programação

Prévia do material em texto

FORÇA BRUTA 
Definição: Uma solução direta para resolver um problema, geralmente baseada 
diretamente no enunciado do problema e nas definições dos conceitos 
envolvidos. 
 
 A força é do computador e não intelectual; 
 Enumeram-se todas as combinações possíveis e avaliam se satisfazem o 
problema; 
 Estratégia mais trivial para a solução de problemas; 
 Normalmente é muito fácil de aplicar; 
 Desempenho considerado muito ruim. 
Apesar de ser raramente uma fonte de algoritmos eficientes ou brilhantes, a 
técnica força bruta é uma importante estratégia de projeto de algoritmos. 
Utilizado principalmente em problemas de busca e ordenação ou quando um 
esforço maior para o desenvolvimento de um algoritmo mais eficiente não se 
justificar. 
 
Vantagens 
 Ampla aplicabilidade; 
 Simplicidade; 
 Algoritmos razoáveis para problemas importantes; 
 Algoritmos padrão para tarefas computacionais. 
 
Contras 
 Raramente fornece algoritmos eficientes; 
 Alguns algoritmos são muito vagarosos; 
 Não tão criativo quantas outras técnicas de desenvolvimento. 
 
Algumas aplicações 
 Ordenação (bubble sort); 
 Busca; 
 Criptografia (checar sistematicamente todas as possíveis chaves até a 
chave correta ser encontrada); 
 
 
 
 
 
 
 
 
 
 
 
DIVIDIR E CONQUISTAR 
 
Definição: O paradigma Divisão e Conquista consiste em dividir o problema a 
ser resolvido em partes menores, encontrar soluções para as partes, e então 
combinar as soluções obtidas em uma solução global. 
 
 Dividir: dividir a instância do problema original em duas ou mais 
instâncias menores, considerando-as como subproblemas. 
 Conquistar: resolver os subproblemas caso esses sejam suficientemente 
pequenos, caso contrário continuar a divisão. 
 Combinar: combinar as soluções encontradas em cada subproblema, 
compondo uma solução para o problema original. 
 
Esta técnica é bastante utilizada em desenvolvimento de algoritmos paralelos, 
onde os subproblemas são tipicamente independentes um dos outros, podendo 
assim serem resolvidos separadamente. 
 
Vantagens 
 Indicado para aplicações que tem restrição de tempo. 
 É de fácil implementação. 
 Simplifica problemas complexos. 
 
Desvantagens 
 Necessidade de memória auxiliar. 
 Repetição de Subproblemas. 
 Tamanho da pilha (número de chamadas recursivas e/ou armazenadas 
pode causar estouro de memória). 
 
Algumas aplicações 
 Multiplicação de inteiros longos. 
 Menor distância entre pontos. 
 Ordenação rápida (quicksort) e por intercalação (mergesort). 
 Pesquisa em árvore binária. 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
PROGRAMAÇÃO DINÂMICA 
 
Definição: A Programação Dinâmica pode ser caracterizada como um processo 
sequencial de tomada de decisões, onde uma decisão ótima global pode ser 
obtida através da otimização de subproblemas (ou ótimos locais) individuais. 
 
Na Programação Dinâmica resolvem-se os problemas de pequena dimensão e 
guardam-se as soluções em tabelas dinâmicas, a fim de evitar redundância de 
cálculo, ou seja, uma solução parcial obtida somente é calculada uma única vez. 
Este procedimento é importante porque, diferentemente da técnica de divisão e 
conquista, aqui cada subproblema é dependente de pelo menos um outro. A 
solução final é obtida combinando as soluções dos problemas menores. 
 
Vantagens 
 Pode ser utilizada num grande número de problemas de otimização 
discreta. 
 Não necessita de muita precisão numérica. 
 Útil para aplicar em problemas que exigem teste de todas as 
possibilidades. 
 
Desvantagens 
 Necessita de grande espaço de memória 
 A complexidade espacial pode ser exponencial 
 
Algumas aplicações 
 Multiplicação de várias matrizes 
 Projeto de sistemas confiáveis 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
ALGORITMOS GULOSOS 
 
Definição: De forma geral, os algoritmos gulosos escolhem a opção que parece 
ser a melhor no momento (escolha ótima), e esperam que desta forma consiga-se 
chegar a uma solução ótima global, mas nem sempre é possível chegar a uma 
solução ótima. 
 
Os algoritmos gulosos tomam decisões com base apenas na informação 
disponível, sem se preocupar com os efeitos futuros de tais decisões, isto é, eles 
nunca reconsideram as decisões tomadas, independentemente das consequências. 
Não há, portanto, necessidade de avaliar as alternativas nem de empregar 
procedimentos elaborados permitindo que decisões anteriores sejam desfeitas. 
 
Vantagens 
 Geralmente fácil de construir algoritmo 
 Baixa complexidade 
 Heurísticas (intuição) ajudam na otimalidade 
Desvantagens 
 Geralmente não obtém o ótimo 
 Garantir otimalidade é difícil 
 Podem gerar soluções muito ruins 
 
Algumas aplicações 
 Árvore geradora minima; 
 Caminho minimo; 
 Cobertura de conjuntos. 
 
 
 
 
 
 
 
 
 
 
BACKTRACKING 
Definição: é um tipo de algoritmo que representa um refinamento da busca por 
força bruta, em que múltiplas soluções podem ser eliminadas sem serem 
explicitamente examinadas. 
Vantagens 
 Forma bastante fácil de implementar um problema que de outra forma 
seria muito mais complexo de se resolver; 
 Linguagens de programação em logica oferecem suporte. 
Desvantagens 
 Programas de backtracking, a não ser que se programe 
restrições(constraints) executam sempre uma busca exaustiva e tenderão à 
explosão combinatória; 
 Programas de Backtracking são por natureza, Combinatórios; 
 Pode exigir muita memoria para problemas grandes. 
Algumas aplicações 
 Problemas de satisfação de restrições (palavras cruzadas); 
 Linguagens de programação em logica.