np-complexo

7876 palavras 32 páginas
Projeto e
Análise de Algoritmos
Problemas N P-Completo e
Algoritmos Aproximados
Antonio Alfredo Ferreira Loureiro loureiro@dcc.ufmg.br http://www.dcc.ufmg.br/~loureiro

UFMG/ICEx/DCC

PAA

·

Problemas NP-Completo e Algoritmos Aproximados

1

Introdução
• Problemas intratáveis ou difíceis são comuns na natureza e nas áreas do conhecimento. • Problemas “fáceis”: resolvidos por algoritmos polinomiais.
• Problemas “difíceis”: no momento, conhecemos apenas algoritmos exponenciais para resolvê-los.
• A complexidade de tempo da maioria dos problemas é polinomial ou exponencial.

UFMG/ICEx/DCC

PAA

·

Problemas NP-Completo e Algoritmos Aproximados

2

Introdução
• Polinomial: função de complexidade é O(p(n)), onde p(n) é um polinômio. – Por exemplo, pesquisa binária (O(log n)), pesquisa seqüencial (O(n)), ordenação por inserção (O(n2)), e multiplicação de matrizes (O(n3)).
• Exponencial: função de complexidade é O(cn), c > 1.
– Por exemplo, problema do caixeiro viajante (PCV) (O(n!)).
– Mesmo problemas de tamanho pequeno a moderado não podem ser resolvidos por algoritmos não-polinomiais.

UFMG/ICEx/DCC

PAA

·

Problemas NP-Completo e Algoritmos Aproximados

3

Problemas N P-Completo
• A teoria de complexidade a ser apresentada não mostra como obter algoritmos polinomiais para problemas que demandam algoritmos exponenciais, nem afirma que não existem.
• É possível mostrar que os problemas para os quais não há algoritmo polinomial conhecido são computacionalmente relacionados.
• Formam a classe conhecida como N P.
• Propriedade: um problema da classe N P poderá ser resolvido em tempo polinomial se e somente se todos os outros problemas em N P também puderem.
• Este fato é um indício forte de que dificilmente alguém será capaz de encontrar um algoritmo eficiente para um problema da classe N P.

UFMG/ICEx/DCC

PAA

·

Problemas NP-Completo e Algoritmos Aproximados

4

Classe N P: Problemas “Sim/Não”

Relacionados

  • Sopas, Caldos e Molhos
    5147 palavras | 21 páginas
  • sistemas lineares
    4191 palavras | 17 páginas
  • Edipo lacan
    942 palavras | 4 páginas
  • Tese
    36813 palavras | 148 páginas
  • Trabalho complexidade computacional
    875 palavras | 4 páginas
  • Normas
    1159 palavras | 5 páginas
  • Pontes de macarrão
    3393 palavras | 14 páginas
  • A metáfora paterna - psicanálise
    1501 palavras | 7 páginas
  • Atividades formativas 1
    1098 palavras | 5 páginas
  • NPS - e-book tracksale
    3260 palavras | 14 páginas