AAI Analise resumos

Resumo de Analise de Algoritmo

Força Bruta: esta técnica é, em geral, a primeira a ser tentada. Esses algoritmos são óbvios, fáceis de implementar, e fornecem soluções ótimas. Como desvantagem, eles são normalmente lentos, e algumas vezes tão lentos que inviabilizam sua utilização. Se você só precisa de calcular a solução uma única vez e o tempo de execução é razoável, força bruta pode ser uma abordagem válida.

Algoritmo Guloso: É aquele em que fazemos a melhor escolha em cada estágio do algoritmo, dada á
Informação imediatamente disponível. Essas escolhas não levam em conta todos os dados disponíveis em todos os estágios. Algumas vezes a informação imediata é suficiente e uma solução ótima é encontrada; algumas vezes isso não é suficiente, e chegamos a soluções não ótimas.
Algoritmos gulosos algumas vezes permitem reduzir o trabalho necessário para um algoritmo de força bruta.
A dificuldade com algoritmos gulosos é garantir que uma solução ótima será encontrada, enquanto que com a estratégia de força bruta isso sempre acontecerá.

Heurística: Uma heurística é um método prático e informal, como uma regra ou princípio geral, para ajudar a resolver um problema. Da mesma forma que com algoritmos gulosos, usamos heurísticas para reduzir o trabalho, em comparação com os algoritmos de força bruta.
Também da mesma forma, não há nenhuma garantia de que uma solução ótima será encontrada mas, muito provavelmente, chegaremos a uma solução útil.

Divisão e Conquista: Esta técnica trabalha quebrando recursivamente um problema em dois ou mais subproblemas de mesmo tipo (ou de tipo relacionado). Esta “divisão” continua até que os subproblemas se tornem simples o bastante para serem resolvidos diretamente. Então nós “conquistamos”, ou seja, as soluções dos subproblemas são combinadas para obter uma solução para o problema original.
Algoritmos de divisão e conquista tendem a ser inerentemente simples e eficientes, se os subproblemas forem corretamente divididos e combinados.