Indice articoli

Valutazione attuale: 5 / 5

Stella attivaStella attivaStella attivaStella attivaStella attiva
 
SubsetSum

 

AMBITO: Matematica
STATO:  ATTIVO 
VOTO: ( N.P. )

 

Il problema della somma di sottoinsiemi è descritto come segue: dato un insieme di numeri interi positivi S e la somma obbiettivo T, esiste un sottoinsieme di S la cui somma è T? Si tratta di uno dei più conosciuti e complicati problemi in campo informatico. In realtà è un problema molto semplice, e il codice per risolverlo non è molto complicato. La complicazione sta nel tempo di esecuzione; tutti gli algoritmi esatti noti hanno tempo di esecuzione che è proporzionale ad una funzione esponenziale del numero di elementi nella serie (nel caso peggiore del problema).
 
Nel corso degli anni, numerosi problemi combinatori hanno dimostrato di essere nella stessa classe della somma di sottoinsiemi (chiamati problemi NP-completi). Ma, a seconda di come si misura la dimensione del problema, ci sono prove che la somma di sottoinsiemi sia in realtà un problema più facile della maggior parte degli altri della sua categoria. L'obiettivo di questo progetto è quello di rafforzare l'evidenza che la somma di sottoinsiemi sia il problema più semplice di quelli difficili.
 
Si suppone di avere un insieme di n numeri interi positivi, chiamato S, il cui valore singolo massimo è m. Si definirà il rapporto n/m come densità dell'insieme S e la somma di tutti gli elementi dell'insieme come ∑S. Se si guarda la lista delle somme prodotte da sottoinsiemi di S, si nota che molti risultati sono vicini al valore generale sum(S) se S è abbastanza denso. In realtà, sembra che vi sia una soglia di densità oltre la quale non ci sono somme al di fuori dell'intervallo tra m e la metà di S. Gli esperimenti preliminari del team di questo progetto hanno portato alla seguente ipotesi: un insieme di numeri interi positivi con massimo m e dimensione n > floor(m/2)+1 ha un sottoinsieme la cui somma è T per ogni T nell'intervallo m < T < ∑S − m.
 
Ecco, quindi, dove il volontario può intervenire: finora non si è stati in grado di dimostrare l'ipotesi di cui sopra. Se si vuole essere veramente utili è sufficiente inviare al team una prova (o mostrare dove trovarne una nella letteratura scientifica) che dimostri l'ipotesi e il progetto sarà terminato; altrimenti se volete divertirvi di più si può volontariamente donare la propria potenza elaborativa per estendere l'evidenza empirica dell'ipotesi. Questo aiuterà anche a capire meglio il modo di applicare il calcolo distribuito per problemi combinatori.

 

Per ulteriori informazioni visitate il thread ufficiale presente nel nostro forum.


Accedi per commentare