SubsetSum@home

AMBITO: Matematica

STATO: ATTIVO

ATTACH: http://volunteer.cs.und.edu/subset_sum/

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.

Pagina in allestimento.

Testo a cominciare dalla riga precedente (no formattazione grandezza testo) e foto (larghezza max 625) o altro (filmati, tabelle, link).

Stato del progetto: progetto attivo

Iscrizione libera.

Requisiti minimi: nessuno hardware

Gli sviluppatori non segnalano requisiti minimi da rispettare.

Screensaver: disponibile non disponibile

Note o immagine

Assegnazione crediti: fissati per singola WU/ variabili in base al tempo di elaborazione

Quorum = 2 (se è >1 le WU dovranno essere convalidate confrontando i risultati con quelli di altri utenti).

Applicazioni e WU disponibili: vedi scheda "Link"

Cliccare sulle icone relative alle "Applicazioni"

e allo "Stato del server"

Sistemi operativi supportati: vedi scheda "Info tecniche"

Dati specifici sull'elaborazione: vedi scheda "Info tecniche"

Per ottenere dati sulla durata media dell'elaborazione, la RAM necessaria e la dead line, consultare la scheda "Info tecniche" qui a destra. Per informazioni particolareggiate (specifiche per applicazione e sistema operativo, intervallo di backup e crediti assegnati) rifarsi alla pagina dei risultati del progetto WUprop@home.

Problemi comuni: nessuno vedi elenco

Non si riscontrano problemi significativi.

Supporto al progetto: supportato

Per unirsi al team BOINC.Italy consultare la scheda "Link" qui a destra cliccando sull'icona relativa al "JOIN"