Valutazione attuale: 0 / 5

Stella inattivaStella inattivaStella inattivaStella inattivaStella inattiva
 
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.


SubsetSum




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

 


SubsetSum




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" ico32_applicazioni e allo "Stato del server" ico32_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.

 


SubsetSum




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

 

Referente/i: posizione vacante
Se sei interessato al progetto e vuoi dare una mano diventando referente, contatta i moderatori in privato o attraverso le pagine del forum.

 

Posizione del team nelle classifiche modiali:



Andamento dei crediti giornalieri:



Andamento del RAC:



Statistiche interne: vedi scheda "Link"
Cliccare sulle icone relative alle "Statistiche progetto" ico32_stats o alla "Classifica utenti" ico32_classutenti (solo per iscritti al team).

 

Statistiche BOINC.Stats: vedi scheda "Link"
Cliccare sulle icone relative alle "Statistiche del team sul progetto" ico32_boincstats o alla "Classifica dei team italiani" ico32_statita.


Per commentare questo post nel forum devi effettuare il login

Articoli

Written on 11/02/2019, 11:13 by boboviz
boinc-workshop-2019Anche quest'anno si terrà il Boinc Workshop, dal 9 al 12 Luglio a Chicago. La partecipazione è libera e gratuita.

Ultime dal Blog

Written on 19/06/2017, 14:38 by boboviz
addio-lugano-bellaCari sodali scaccolatori,come alcuni di voi sanno, il sottoscritto, oltre ad essere appassionato di Boinc, è anche "appassionato" di HPC e, visto che il...