Análise e complexidade de algoritmos

Páginas: 5 (1009 palavras) Publicado: 30 de setembro de 2012
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 64. 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, casosesses 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 usadosnormalmente 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 dassoluçõ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émanalisar o crescimento do espaço de soluções.























































2. Divisão e Conquista


A estratégia de divisão e conquista opera decompondo um problema em subproblemas independentes, resolvendo-os e combinando as soluções obtidas em uma solução para o problema original. Esse processo recursivo dedecomposições e recombinações funciona da seguinte maneira. Dada uma entrada, se ela é suficientemente simples, obtemos diretamente uma saída correspondente. Caso o contrário, ela é decomposta em entradas mais simples, para quais aplicamos o mesmo processo, obtendo saídas correspondentes, que são então combinadas em uma saída para a entrada original.
Algoritmos de tentativa e erro nãoseguem uma regra fixa de computação:
– Passos em direção à solução final são tentados e registrados.
– Caso esses passos tomados não levem à solução final, eles podem ser retirados e apagados do registro.
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ápidas.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 avaliadoempiricamente 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.
3. Recursividade


A recursividade é um mecanismo útil e poderoso que permite a uma função chamar a si mesma direta ou indiretamente, ou seja, uma função é dita recursiva se ela contém pelo menos...
Ler documento completo

Por favor, assinar para o acesso.

Estes textos também podem ser interessantes

  • Analise e complexidade de algoritmos
  • analise e complexidade de algoritmos
  • Analise e complexidade de algoritmos
  • Analise e complexidade de algoritmos
  • ANALISE E COMPLEXIDADE DE ALGORITMOS
  • Análise de Complexidade de Algoritmos
  • ATPS Analise e Complexidade de Algoritmos
  • Atps análise e complexidade de algoritmos

Seja um membro do Trabalhos Feitos

CADASTRE-SE AGORA!