Acessar o Zé Moleza
ou
O que você está pesquisando?
Classe de Problemas – Problema P versus NP
3079 visualizações
3598 palavras
Adicionar aos favoritos
Loading...- | |
Exemplo de classe NP de problemas
Os problemas de Coloração de Grafos, Bin Packing, Knapsack,
Caminhos e Ciclos de Hamilton, e Caixeiro Viajante são todos NP.
Exemplo:
"Knapsack": Dada uma mochila de capacidade C e n objetos de dimensões s1, . . . , sn e valores p1, . . . , pn,
Exemplo:
Caminhos e Circuitos de Hamilton: Num grafo G, um caminho de Hamilton é um caminho que passa por cada vértice exatamente uma vez. Um circuito de Hamilton é qualquer ciclo que seja um caminho de Hamilton.
Problema Dec: Decidir se G contém ou não um caminho de Hamilton (ou um circuito).
Classe de Problemas NP- Completos
São problemas que pertencem à classe NP e que têm a importante propriedade:
L’ £ P L, para todas as L’ Î NP
Tradução:
Se L Î NPC então todos os problemas pertencentes a NP podem ser reformulados (em tempo polinomial) para se tornarem no problema L.
Todos os problemas pertencentes a NP são redutíveis polinomialmente a problemas NPC. Todos os problemas NP podem ser resolvidos reduzindo-os a um problema NPC e depois resolvendo esse problema NPC.
Se um problema NPC possuir um algoritmo que descubra uma solução em tempo polinomial então TODOS os problemas…
Os problemas de Coloração de Grafos, Bin Packing, Knapsack,
Caminhos e Ciclos de Hamilton, e Caixeiro Viajante são todos NP.
Exemplo:
"Knapsack": Dada uma mochila de capacidade C e n objetos de dimensões s1, . . . , sn e valores p1, . . . , pn,
- Problema Opt: Determinar o valor máximo dos objetos que se consegue colocar na mochila (e a lista desses objetos).
- Problema Dec: Dado um inteiro k, existirá um conjunto de objetos que caiba na mochila e corresponda a um valor >= k?
Exemplo:
Caminhos e Circuitos de Hamilton: Num grafo G, um caminho de Hamilton é um caminho que passa por cada vértice exatamente uma vez. Um circuito de Hamilton é qualquer ciclo que seja um caminho de Hamilton.
Problema Dec: Decidir se G contém ou não um caminho de Hamilton (ou um circuito).
Classe de Problemas NP- Completos
São problemas que pertencem à classe NP e que têm a importante propriedade:
L’ £ P L, para todas as L’ Î NP
Tradução:
Se L Î NPC então todos os problemas pertencentes a NP podem ser reformulados (em tempo polinomial) para se tornarem no problema L.
Todos os problemas pertencentes a NP são redutíveis polinomialmente a problemas NPC. Todos os problemas NP podem ser resolvidos reduzindo-os a um problema NPC e depois resolvendo esse problema NPC.
Se um problema NPC possuir um algoritmo que descubra uma solução em tempo polinomial então TODOS os problemas…
É esse o conteúdo que você precisa?
Faça seu login e saiba como ver o trabalho completo
Institucional
Saiba como fazer
Trabalhos Acadêmicos
O Zé Moleza facilita sua vida acadêmica ajudando você em suas pesquisas, e a economizar o seu tempo e o seu dinheiro nos seus trabalhos de faculdade. São mais de 26144 pesquisa acadêmicas entre elas, monografia, temas de monografias, TCC, modelos de monografias, trabalhos de universidades, resenha, Paper, Ensaio, Bibliografia, Trabalhos Escolares.
Dicas de como fazer: Capa de Monografia, capa de TCC, Regras da ABNT, como fazer monografia, como fazer Projeto Final, como fazer seminário, como fazer capas, referências bibliográficas, modelo de monografia.
O Zé Moleza NÃO faz a venda de monografia e É TOTALMENTE CONTRA a compra de monografia pronta e trabalhos prontos. O Zé Moleza NÃO auxilia a quem compra monografia, NÃO apóia a quem quer comprar Trabalhos Prontos, e NÃO APROVA a quem quer comprar TCC prontos, dando dicas de formatação, regras da ABNT, dando sugestões de temas para monografia, resumo de livros, projeto de pesquisa, projeto de mestrado, projeto de pós-graduação, trabalhos acadêmicos, incentivando o usuário a desenvolver por conta própria sua monografia.
