Articoli

AMBITO: Matematica

Il progetto nasce ufficialmente all'inizio di agosto 2012 come una sorta di banco prova per algoritmi.

La libreria di algoritmi utilizzata è la OLib Library ed è open e disponibile a tutti su code.google.com.

 

Al momento il progetto lavora sulla congettura di Goldbach e sulla ricerca dei numeri fatidici.

 

AMBITO: Matematica

SAT@home è un progetto di ricerca che utilizza computer connessi a Internet per risolvere problemi difficili e praticamente importanti (problemi di inversione di funzioni discrete, ottimizzazione discreta, bioinformatica, ecc.) Che possono essere efficacemente ridotti al problema di soddisfacibilità booleana. Al momento stiamo risolvendo il problema della ricerca di coppie ortogonali di quadrati latini diagonali di ordine 9 e 10. Nel prossimo futuro speriamo di trovare la tripla di quadrati latini mutuamente ortogonali di ordine 10 o di dimostrare l'assenza di tali triple. Il progetto è stato implementato usando la libreria DC-API.
 Ci sono molti problemi praticamente importanti per i quali non è stata dimostrata l'esistenza di algoritmi (polinomiali) efficaci della loro risoluzione.  Molti di questi problemi sono NP-hard. Significa che sotto alcune supposizioni ragionevoli (anche se non provate), questi problemi non possono essere risolti in tempo polinomiale. Tuttavia, molti dei loro casi speciali si presentano in applicazioni pratiche: vari problemi di ottimizzazione discreti (ad esempio, pianificazione della produzione) e problemi di verifica dei dispositivi discreti (derivanti, ad esempio, dalla progettazione di circuiti e dalla verifica della correttezza del programma). Pertanto è molto importante avere metodi per la loro risoluzione che non hanno complessità polinomiale, ma che sono efficaci nella pratica: tali metodi possono far fronte ai numerosi casi speciali di problemi NP-hard di dimensioni enormi. Uno dei metodi più semplici nella sua base, e quindi il più efficiente in termini di implementazioni software, è l'approccio SAT. Questo approccio è basato sulla riducibilità del problema originale ad un Boolean satisfiability problem (SAT). I problemi SAT ammettono una forma molto naturale di parallelismo, consentendo l'uso del calcolo distribuito (incluso il calcolo volontario) per risolverli. In realtà la riduzione al SAT può essere effettuata in modo efficace (in effetti, deriva dal famoso teorema di Cook-Levin).

Pertanto, il progetto è finalizzato alla risoluzione di vari problemi combinatori difficili (dalle aree di crittografia, ottimizzazione discreta, bioinformatica) che possono essere efficacemente ridotti a SAT.

 

Terza partecipazione del team BOINC.Italy un po' sottotono rispetto alle precedenti: pur incrementando la potenza di calcolo del 21% rispetto al 2010, il team non riesce ad entrare nei primi 10 attestandosi all'undicesimo posto, ultimo del club dei 10 milioni di punti WCG (che come è noto sono 7 volte superiori ai crediti BOINC). Gli utenti del team partecipanti sono stati 243.

Questo challenge è una gara tra team ma è disponibile anche una classifica interna: Daniele si migliora (nell'edizione 2010 classificato 5° con un nick diverso) e stravince frantumando il precedente record di crediti per il challenge. Anche Gionata.Ercolani si migliora e conquista la 2a posizione mentre Bax chiude 3°, unico a podio per 3 edizioni consecutive. Molte novità anche nel resto della top ten, comunque tutti partecipanti che l'anno precedente ne erano rimasti fuori.

AMBITO: Matematica

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.