Análise e complexidade de algoritmos

ANHANGUERA EDUCACIONAL S.A.

Faculdade Anhanguera de Taubaté – Unidade II

Curso de Ciência da Computação

Análise e Complexidade de Algoritmos

Professor : Fernando Salles Claro

Taubaté
2012

Sumário

1. Tentativa e Erro 3 2. Divisão e Conquista 5 3. Recursividade 6 4. Referências Bibliográficas 8

1. Tentativa e Erro

Algoritmos de tentativa e erro (Backtracking) consistem em decompor o processo em um numero finito de sub-tarefas parciais que devem ser exploradas exaustivamente.
Eles não seguem uma regra fixa de computação, cada passo em direção a solução final, são registrados a cada tentativa, casos esses passos tomados não levem a solução final, podem ser retirados e apagados do registro.
O processo de tentativa gradualmente constrói e percorre uma arvore de sub-tarefas. Quando a pesquisa na árvore de soluções cresce rapidamente é necessário usar algoritmos aproximados ou heurísticos que não garantem a solução ótima, mas são rápidos.

Algoritmos aproximados: – Algoritmos usados normalmente para resolver problemas para os quais não se conhece uma solução polinomial. – Devem executar em tempo polinomial dentro de limites “prováveis” de qualidade absoluta ou assintótica.

Heurística: – Algoritmo que tem como objetivo fornecer soluções sem um limite formal de qualidade, em geral avaliado empiricamente em termos de complexidade (média) e qualidade das soluções. – É projetada para obter ganho computacional ou simplicidade conceitual, possivelmente ao custo de precisão.

Está técnica é usada quando não se sabe exatamente que caminho seguir para encontrar uma solução, ela não garante uma solução ótima e pode ser vista como uma variante da recursividade.

Ao se fazer a análise de um algoritmo que usa esse tipo de algoritmo , deve-se também