Lista de Exercicios - Analise e Complexidade de Algoritmos

Centro Universitario Anhanguera de Campo Grande – Unidade I

Professor: Antonio Felício Netto

LISTA DE EXERCÍCIOS N2

 

1. Como se caracteriza os algoritmos de Algoritmos Gulosos?

A principal característica são algoritmos que buscam uma solução para o problema independentemente da quantidade de recurso necessário para a solução. São algoritmos que buscam uma solução rápida.

1. Qual a diferença entre algoritmos NP e NP-Difícil?

AS classes de algoritmos NP são os algoritmos que não consegue criar uma classificação polinomial.

E os algoritmos NP-Difícil são os algoritmos NP que contem a classificação resolvida através da saída que resolva o problema.

1. Qual o vínculo entre os algoritmos NP-Difícil e teoria de Grafos?

Um algoritmo que usa a técnica de grafos é classificado como NP-Difícil. Pois a contagem de pontos se dá através de aproximação.

1. Como funciona a análise de Recorrência na análise de algoritmos recursivos?

A recorrência verifica a avaliação do algoritmo recursivo em 3 partes

• Identifica a condição de parada da recursividade dentro do algoritmo.
• A avaliação da maneira que é realizada a separação do problema com o método da recursividade.
• Multiplicação das linhas que chama a recursividade.

1. Qual a classificação de um algoritmo de tentativa e erro (backing track), explique o motivo.

 Os algoritmos de tentativa e erros são conhecidos como algoritmos de força bruta. Onde visa combinar os valores até se identificar a solução do problema. Um exemplo são os algoritmos de quebrar senha.

1. Um algoritmo com classificação assintótica polinomial pode ser um algoritmo NP-Difícil? Por que?

Todos os algoritmos que tem a classificação assintótica através de polinômios, a classe p cotem o conjunto dos algoritmos NP.

As classes NP-Completo tem os problemas intratáveis cujo o limite interior conhecido como polinomial.

[pic 1]

...