O Problema da Soma dos Subconjuntos

1058 palavras 5 páginas
TECNICAS DE PESQUISA E ORDENAÇAO I

COLATINA
2013

1. O Problema da Soma de Subconjuntos

O problema da soma de subconjuntos é um importante problema da teoria da complexidade computacional e criptografia. O problema é este: dado um conjunto de inteiros, existe um subconjunto não-vazio cuja soma é 0? Por exemplo, dado o conjunto { −7, −3, −2, 5, 8}, a resposta é sim porque o subconjunto { -3, -2, 5} resulta numa soma que dá zero. O problema é NP-completo.
Um problema equivalente é este: dado um conjunto de inteiros e um inteiro s, existe algum subconjunto que some s? Um caso interessante de soma subconjunto é o problema de partição, em que s é a metade da soma de todos os elementos do conjunto.

2. Complexidade

A complexidade da soma de subconjuntos poderá ser vista de dois parâmetros, N, o número de variáveis de decisão, e P, a precisão do problema.
A complexidade do melhor algoritmo conhecido é exponencial no menor dos dois parâmetros N e P. Assim, o problema é mais difícil se N e P são da mesma ordem.
O que acontece é que o problema se torna aparentemente não-exponencial quando se é prático para considerar o espaço da solução. Existem duas maneiras de medir o espaço de solução do Problema da soma dos subconjuntos. Uma delas é contar o número de maneira que as variáveis podem ser combinadas. Existem 2N possíveis maneiras de combinar as variáveis. Contudo, com N = 10, existem somente 1024 possíveis

Relacionados

  • O problema dos filósofos famintos
    375 palavras | 2 páginas
  • Problema da mochila em java
    4821 palavras | 20 páginas
  • O Problema dos 36 oficiais
    1000 palavras | 5 páginas
  • O problema da incredulidade no século xvi: a religião de rabelais
    2119 palavras | 9 páginas
  • QUAL O PROBLEMA PRINCIPAL DO CASO
    395 palavras | 2 páginas
  • Resumo do Livro Problemas da Estética de Luigi Pareyson
    1541 palavras | 7 páginas
  • Resumo do texto "O Problema da Escala", de Iná Elias de Castro
    941 palavras | 4 páginas
  • Problema da mochila
    2073 palavras | 9 páginas
  • Mulan: Problemas do Género e da Identidade do Sujeito
    2478 palavras | 10 páginas