PAACap4TeoriadaComplexidade 20150525172641

Projeto e Análise de Algoritmos

Teoria da Complexidade

Disciplina: Projeto e Análise de Algoritmos
Curso: Ciência da Computação
Professor: Tiago Rodrigues

Projeto e Análise de Algoritmos Conteúdo






Problemas Polinomiais, Não Polinomiais
Classe P
Classe NP
Classe NP-Completa
Satisfabilidade e Teorema de Cook

Projeto e Análise de Algoritmos – Problemas
Polinomiais, Não Polinomiais


Problemas Polinomias:
 São problemas resolvidos por algoritmos de tempo polinomial.
▪ O(p(n)) onde p(n) é um polinômio.



Algoritmos de tempo polinomial:
▪ Dada uma entrada N, seu tempo de execução no pior caso é O(n k) onde k é uma constante.

Tais problemas são chamados de problemas “tratáveis” ou “fáceis”
 Muitos dos problemas existentes na computação são tratáveis


▪ Ex: pesquisa binária O(log n), pesquisa sequencial O(n), soma de matrizes
O(n2) e multiplicação de matrizes O(n3).


Problemas Não Polinomiais:
 São problemas resolvidos por algoritmos de tempo não polinomial.
▪ Ex: Algoritmos com tempo exponencial.



Algoritmos de tempo exponencial:
▪ Dada uma entrada N, seu tempo de execução no pior caso é O(c n), onde c é uma constante maior que 1.



Tais problemas são chamados de problemas “intratáveis“ou
“difíceis”

Projeto e Análise de Algoritmos – Problemas
Polinomiais, Não Polinomiais


Problemas Não Polinomiais:
 Tais problemas são chamados de problemas “intratáveis“ou
“difíceis”
 Ex:
▪ Problema do Caixeiro Viajante -> O(n!), mas pode ser reduzido para um problema de ordem O(n22n)



Em resumindo
 Problema tratável ou fácil: existe um algoritmo decidível que resolve o problema em um tempo polinomial.
 Problemas intratável ou difícil: existe um algoritmo decidível que resolve o problema em um tempo não polinomial.

PERGUNTAS