domenica 30 novembre 2014

Algoritmi golosi

Hieronymus Bosch, Sette peccati capitali, Gola
Nel sesto canto dell'Inferno, Dante incontra i golosi, flagellati da una piova etterna, maladetta, fredda e greve. 
La pioggia cade incessante, con intensità sempre uguale, mista a neve e grandine, e il fango che si forma al suolo è maleodorante.

Forse anche un ipotetico inferno degli informatici avrebbe un girone dei golosi: ma in questo caso a essere puniti non sarebbero gli ingordi di cibi e bevande, ma i progettisti di algoritmi che non si sono saputi trattenere dall'utilizzo di metodologie "golose", o "greedy".

Un algoritmo goloso è un metodo per risolvere un problema attraverso una serie di passi, ciascuno dei quali mira a espandere la soluzione parziale fino a quel momento costruita, con lo scopo di arrivare infine a una soluzione completa: a ogni passo, l'algoritmo goloso compie la propria scelta in modo "ingordo", perseguendo cioè il massimo guadagno possibile, senza ovviamente violare le regole del problema.

Vediamo un esempio. Supponiamo di avere una macchina distributrice di bevande in grado di dare il resto. Ogni volta che la macchinetta deve dare il resto, deve prendere decisioni inerenti a quali monete utilizzare per arrivare alla somma da restituire. L'obiettivo è quello di utilizzare ogni volta il numero più basso possibile di monete. Immaginiamo, per semplicità, che la macchina disponga sempre di quantità infinite di monete da 1 euro, 10 cent e 1 cent.
Un algoritmo goloso, in questo caso, potrebbe funzionare a ogni passo come segue:
1. calcola quanto manca al raggiungimento della somma da restituire;
2. seleziona, tra le monete con valore minore della somma che manca, quella con valore più alto;
3. emetti una moneta del tipo selezionato.
Se, per esempio, deve essere erogato un resto di 1,12 euro, la macchina sceglierà, al primo passo, di consegnare una moneta da 1 euro. Al secondo passo, dato che mancano 12 cent, la macchina selezionerà una moneta da 10 cent. Gli ultimi due passi comporteranno entrambi l'emissione di una moneta da 1 cent.
Tutto bene, direte voi. Anche noi, dovendo pagare 1,12 euro e disponendo di questi tagli, avremmo scelto questa combinazione. Sì, però abbiamo visto un caso fortunato, in cui l'algoritmo goloso perviene a una soluzione completa soddisfacente.
Cosa accadrebbe se invece di monete da 1 euro, 10 cent e 1 cent, la macchina disponesse di monete da 1 cent, 15 cent e 25 cent, e dovesse consegnare un resto di 30 cent? Per colpa del suo modo di pensare ingordo, sceglierebbe di erogare dapprima una moneta da 25 euro, e poi sarebbe costretta a snocciolare una dopo l'altra cinque monete da 1 cent. Si tratta della soluzione migliore? No, perché fa uso di ben sei monete, quando due monete da 15 cent avrebbero risolto il problema molto più brillantemente.
E non ditemi che le monete da 15 e da 25 cent non esistono: non è questo il punto.
Gli algoritmi golosi, in generale, non garantiscono il successo nel trovare la soluzione ottima di un problema. Anzi, possiamo dire che il  più delle volte falliscono miseramente.

Un altro esempio? Immaginate che quattro uomini, Aldo, Bernardo, Carlo e Damiano, equipaggiati con una torcia, debbano attraversare di notte un ponte pericolante. Non più di due persone alla volta possono passare sul ponte, e ogni uomo o coppia che si avventura deve avere con sè la torcia. La torcia, inoltre, deve essere portata avanti e indietro, e non può essere lanciata da un capo all'altro del ponte. Aldo impiega 1 minuto ad attraversare il ponte, Bernardo ci mette 2 minuti, Carlo 5 minuti, e Damiano 10 minuti. Una coppia impiegherà il tempo imposto dall'attraversatore più lento.
Qual è, per i quattro uomini, il modo più veloce di attraversare il ponte?

Se gli uomini decidono di risolvere il problema adottando un approccio greedy, saranno inviate al di là del ponte le due persone più veloci, cioè Aldo e Bernardo, che impiegheranno 2 minuti. Il più veloce dei due, cioè Aldo, tornerà con la torcia in un minuto. Di nuovo partiranno i due uomini più veloci disponibili, cioè Aldo e Carlo, che arriveranno al di là del ponte in 5 minuti. Tornerà di nuovo Aldo con la torcia, impiegando 1 minuto. Infine sarà la volta di Aldo e Damiano, che giungeranno a destinazione in 10 minuti. Il tempo complessivo sarà quindi di 19 minuti.
Secondo voi è il modo più veloce di attraversare il ponte, cioè è la soluzione ottimale del problema? Provate a investigare: scoprirete che non lo è: esiste una soluzione migliore, e quindi la "golosità algoritmica" ha messo a grave rischio i quattro uomini (ricordate che il ponte era pericolante, e ogni minuto risparmiato era prezioso).

Non si devono confondere gli algoritmi greedy con gli algoritmi di discesa: è vero che anche in questo secondo caso si tratta di procedure che, a ogni passo, scelgono la via che appare più conveniente, senza guardare alla globalità del problema, ma i due scenari sono molto diversi.
Il "passo" di un algoritmo greedy serve a espandere la soluzione fino a quel momento costruita: aggiunge, per così dire, un mattone al muro in costruzione, ma il muro completo, che può essere definito una soluzione, sarà pronto soltanto alla fine dell'algoritmo.
Nel problema del resto, ogni passo corrisponde a una delle monete erogate. Nel problema del ponte, ogni passo è un attraversamento.
Gli algoritmi di discesa, invece, costruiscono a ogni passo una soluzione completa, e cercano di migliorarla costruendone un'altra che differisce dalla precedente per qualche particolare. In questa transizione effettuano una scelta che, in un certo senso, è miope, cioè cerca di massimizzare un qualche "profitto". Anche in questo tipo di metodologia la scarsa lungimiranza può portare su strade poco promettenti, è vero: ma in generale si tratta di un approccio molto importante nella risoluzione dei problemi di ottimizzazione, che con alcune correzioni e accorgimenti particolari può condurre a risultati interessanti. Nel vecchio post Mosse tabu avevo accennato a una di queste importanti correzioni.

domenica 16 novembre 2014

Carnevale della Matematica #79 sul Coniglio Mannaro

Annuncio in ritardo il Carnevale della Matematica n. 79, ospitato dal sontuoso e sempre stimolante blog Il Coniglio Mannaro di Spartaco Mencaroni: sono già passati due giorni, è vero, ma sono fiducioso che il Coniglio mi perdonerà.
Dopo sei mesi torna alla ribalta un numero primo, il 79 appunto, e per l'occasione il Sommo Popinga ha indicato un nuovo verso della sua Poesia Gaussiana: senza posa.
Il tema scelto da Spartaco per l'occasione era di quelli davvero affascinanti: matematica e libertà.
Come afferma lo stesso Mencaroni, il verso gaussiano ben si adatta all'argomento carnevalizio:

Una scelta di termini decisamente appropriata, se pensiamo agli sforzi che l'uomo ha fatto, e che continua a compiere, per la ricerca o la riconquista della propria libertà.

Quanto all'ancora più suggestivo legame tra libertà e matematica, bè, qui Spartaco si produce in un excursus storico molto interessante, del quale riporto solo l'inizio:

La storia parte da lontano ed ha molto a che fare con il rapporto fra umanesimo e scienza. In genere si tende a far coincidere l'avvio di questo dialogo con il Rinascimento, considerato un'epoca in cui il risveglio e il fermento della società occidentale costituiscono il periodo prodromico della nascita del pensiero moderno. L'uomo medioevale si desta da una sorta di (presunto) sonno della ragione, popolato di pensiero magico, credenze superstiziose, bestiari e orripilari; riscopre la cultura tardo antica, liberandola dalle pastoie delle interpretazioni dottrinali scolastiche ed iniziando così la sua marcia trionfale verso il pensiero laico e razionale.

Come sempre, il post carnevalesco mette in evidenza numerosissimi contributi, provenienti da diversi colleghi blogger.
Basterebbero loro, oltre alla bravura di Spartaco nel presentarli, a rendere il Carnevale meritevole di essere letto. Ma un evento speciale, avvenuto da pochi giorni, rende ancora più singolare il Carnevale novembrino: lo stesso Mencaroni, annuncia l'uscita del nuovo librino di Altramatematica, scritto da lui medesimo assieme a Roberto Zanasi.
Il titolo del libro è Matematica e gioco d'azzardo, che dice già molto sull'argomento (attualissimo) che viene trattato: prima o poi su questo blog uscirà una recensione dell'e-book.

Ringrazio Spartaco per avere segnalato le tre parti (1, 2, 3) del mio multi-post sui libri infiniti, oltre all'articolo su Charles Bachman.
Congratulazioni a lui e a tutti gli autori dei post segnalati!
Il prossimo Carnevale, quello che fa da preludio alle feste natalizie, sarà organizzato dal blog Pitagora e dintorni dell'amico Flavio Ubaldini.
Buona lettura a tutti!

martedì 11 novembre 2014

Il weekend di Altramatematica

Si annuncia un lungo e straordinario fine settimana per la collana Altramatematica di 40K.
Giovedì, infatti, parte Bookcity Milano, iniziativa che comprende moltissimi eventi di interesse librario, tra i quali segnalo la presentazione dell'ottimo Matematica in pausa caffè di Maurizio Codogno.
Cosa c'entra Altramatematica? Bè, in occasione dell'iniziativa milanese, la casa editrice 40K ha deciso di vendere tutti gli e-book della collana a soli 99 centesimi! La promozione durerà da domani mercoledì 12 fino a domenica 16 compresa.
Si tratta di un'occasione davvero da non perdere. Tenete presente che tutti i titoli della collana saranno scontati, anche il teatrale Partition, che solitamente è venduto a 2,99 euro.
Come ha suggerito l'amico Flavio Ubaldini, acquistando tutti i librini risparmierete ben 12 euro. Mica male, no?
Ma il weekend di Altramatematica non si ferma alla promozione (che pure non è poco). Come già annunciato, venerdì 14 novembre, alle ore 21, presso l'Auditorium di Villa Olivi a Breda di Piave, presenterò il mio e-book La matematica dei Pink Floyd, in una serata (a ingresso libero) che offrirà molte sorprese.

E non è finita qui: domani uscirà un nuovo librino della collana: il dodicesimo, e l'unico che resterà a prezzo pieno. Di che cosa si tratta? Solo poche ore di pazienza, lo saprete domani!
Catapultatevi sugli store online, allora: l'occasione è ghiotta!

domenica 9 novembre 2014

I premi Turing: Charles Bachman


Charles Bachman (da http://amturing.acm.org)
Che cos'è l'informatica?  Cercate il termine su un qualsiasi dizionario: con ogni probabilità, troverete definizioni del tipo "La scienza che si occupa dell’ordinamento, del trattamento e della trasmissione delle informazioni per mezzo dell’elaborazione elettronica" (questa è tratta dal Le Monnier).
In ogni caso, è pressoché certo che all'interno della definizione troviate la parola  "informazione" (lo stesso vocabolo "informatica" è la contrazione di "informazione automatica"). Se gli informatici hanno soprattutto a che fare con informazioni, è evidente che uno delle loro necessità principali sia quella di immagazzinare queste informazioni da qualche parte.

I database (o le “basi di dati”, se preferite la dizione italiana, ormai un po’ desueta), sono una delle più importanti risposte escogitate per soddisfare questo bisogno. Esistono molti tipi di database, ma la categoria di gran lunga più utilizzata è quella dei database relazionali. 
Uno dei primi ricercatori a occuparsi dell’argomento fu l’americano Charles Bachman, classe 1924, premio Turing 1973. 
Il padre di Charles era un allenatore di squadre universitarie di football, e negli anni dell’infanzia di Charles si spostò molto tra gli atenei americani, portando con sé la famiglia. Nel 1944 Charles si arruolò nell’esercito e combatté fino alla fine della guerra nel teatro del Pacifico. Nel 1950 si laureò in ingegneria meccanica presso l’Università della Pennsylvania. Negli anni successivi fu ingaggiato da una compagnia chimica per lavorare su alcuni problemi di ricerca operativa, e fu in questa occasione che ebbe le sue prime esperienze con i computer. 
Da allora in poi, il suo percorso di ricerca e sviluppo si svolse interamente presso aziende piuttosto che in ambito accademico. Nel 1960, presso la General Electric, cominciò la sua lunga e onorata carriera di ricercatore nell’ambito dei database progettando IDS ("Integrated Data Store"), uno dei primi e più famosi sistemi di gestione di dati della storia.
IDS implementava una serie di tecnologie innovative che rappresentarono per molti anni il punto di riferimento nell'ambito dei database. Ci volle molto tempo prima di vedere emergere altri sistemi che potessero competere con quello progettato da Bachman.

Charles Bachman
Il contributo più noto di Bachman riguarda però i diagrammi che portano il suo nome: schemi utilizzati per descrivere la struttura di un database relazionale come una rete che collega tra di loro diverse “relazioni”. Una relazione è un insieme di “tuple” (d1, d2, ..., dn), ciascuna delle quali è una sequenza di m attributi (dove m è un numero naturale). I valori ammessi per gli attributi di una tupla possono appartenere a insiemi diversi, ma la sequenza di domini ammessi è la stessa per tutte le tuple di una stessa relazione.
Il modo più intuitivo per raffigurarci mentalmente una relazione è vederla come una tabella: le sue tuple sono le righe, mentre gli attributi (ciascuno con il suo dominio) che compongono le tuple corrispondono alle colonne. Una relazione serve astrattamente per rappresentare un’entità, e più concretamente per contenere dei dati. Per esempio, una relazione “Impiegati” potrebbe servire per descrivere gli impiegati di un’azienda, ciascuno corrispondente a una tupla, e ciascuna tupla potrebbe essere formata da una sequenza di attributi (nome, cognome, numero di matricola, mansione, stipendio, e così via). 

In un database, e qui tocchiamo il punto critico, vi sono sempre dei legami tra una relazione e l’altra. Supponiamo che oltre alla relazione “Impiegati” il database contenga una relazione “Dipartimenti”: è naturale pensare che tra le due relazioni sussista un legame, allo scopo di stabilire a quale dipartimento appartiene ciascun impiegato, cioè a quale tupla della relazione “Dipartimenti” sia associata ogni tupla della relazione “Impiegati”.


Le figure qui a fianco sono tratte da uno degli articoli fondamentali di Bachman, intitolato Data structure diagrams, e pubblicato nel 1969.
Le due relazioni (o entità) “Dipartimenti” e “Impiegati” sono mostrate come rettangoli che vengono poi collegati tra di loro. La freccia serve a indicare graficamente tale collegamento, e rappresenta l'idea che ogni impiegato è assegnato a uno dei dipartimenti.
In generale, i collegamenti tra entità possono essere caratterizzati da diversi tipi di cardinalità: il tipo più comune è quello 1 a n (un dipartimento contiene n impiegati), ma esistono anche collegamenti 1 a 1, e n a n.

Charles Bachman fu così, verso la fine degli anni Sessanta, uno dei pionieri dei diagrammi che descrivono la struttura di un database relazionale. 
A partire dal 1976, soprattutto in seguito ai lavori dell'informatico Peter Chen, i modelli di questo tipo vengono chiamati “diagrammi entità-relazioni”, o diagrammi E-R. Ma attenzione: qui la parola “relazione” indica i legami tra le relazioni (come quello tra impiegati e dipartimenti), e non le relazioni stesse, che invece sono denominate “entità”. Questa confusione terminologica è stata fonte di mille fraintendimenti. Si noti però che in inglese i termini sono ben distinti: “relation” è l’insieme di tuple che corrisponde a un entità e viene implementato da una tabella, e “relationship” è l’associazione che lega due relazioni, o due entità o tabelle.

Il premio Turing fu assegnato a Charles Bachman nel 1973 per i suoi “eccezionali contributi alla tecnologia dei database”. Le sue ricerche pionieristiche riguardanti la modellizzazione dei database sono state, in effetti, di enorme importanza per lo sviluppo dei potentissimi sistemi oggi disponibili.
Nella storia del prestigioso riconoscimento, Bachman fu il primo vincitore privo di un dottorato, il primo ingegnere (e non matematico), e il primo ricercatore industriale non accademico.
Pare che dopo essere stato insignito, Bachman si interessò molto alla vita di Alan Turing, e fece persino la conoscenza di Sara Turing, l'anziana madre del grande matematico.

lunedì 3 novembre 2014

Come costruire un libro infinito (terza parte)

Jean Paul Delahaye
Per chi si fosse perso le prime due puntate di questo blog multiplo sui libri infiniti, ecco la prima e la seconda. Nella seconda parte accennavo alle caratteristiche paradossali di alcuni dei libri descritti da Jean Paul Delahaye.

Per esempio, aprendo a caso il libro Q, legato all'insieme dei numeri razionali compresi tra 0 e 1, troviamo con certezza due pagine nere a sinistra e a destra: questo volume sembra possedere più pagine nere-abisso del libro R, associato all'insieme dei numeri reali inclusi nello stesso intervallo.

Possiamo costruire un altro libro alquanto bizzarro togliendo al libro Q la prima e l'ultima pagina: il libro Q' che otteniamo sembra non contenere alcuna pagina stampata, quando invece ne contiene infinite.
D'altro canto, un libro infinito non può essere privo di pagine leggibili: anzi, per definizione, ne deve contenere in quantità infinita. Le pagine stampate del libro Q', infatti, ci sono, e sono appunto infinite, ma non è possibile trovarle aprendo il libro: sono, paradossalmente, pagine segrete, del tutto impenetrabili ai nostri occhi.

Anche il libro R è, a modo suo, paradossale. Aprendolo a caso, come abbiamo già visto, troviamo una pagina nero-abisso e una pagina leggibile. Ogni pagina stampata, in effetti, è sempre preceduta e seguita da pagine nere: i testi del libro sono tutti isolati e sconnessi gli uni dagli altri.

Una versione tridimensionale dell'insieme di Cantor
Un altro libro infinito paradossale riflette la struttura del frattale noto come "insieme di Cantor". Partendo dall'intervallo [0, 1], lo si divide in tre parti uguali e si scarta quella centrale. Quindi, per ciascuno degli intervalli rimasti, si ripete il procedimento, e così via ad infinitum.
Questo processo di eliminazione continua produce, al limite, un insieme che si dimostra essere di misura nulla e tuttavia formato da un'infinità di numeri. Non solo: si tratta di un'infinità non numerabile.
Detto diversamente: le pagine del libro di Cantor, che chiamiamo C, sono infinite  quanto i numeri reali, e non soltanto come i numeri interi. Aprendo il libro a caso, si trovano sempre due pagine stampate, ma subito prima e subito dopo vi sono pagine nere. Il libro è molto strano: sembra essere composto da coppie di pagine leggibili, isolate e circondate da pagine nere-abisso. Come il libro R, con la differenza che ogni pagina isolata è stata, per così dire, sdoppiata. Ma anche questo è paradossale, perché in realtà C ha meno pagine di R.

Questa ubriacatura di libri paradossali fa venire alla mente il paradosso del bibliotecario. In una grande biblioteca venivano prodotti molti cataloghi del posseduto: uno elencava i libri in italiano, un altro quelli in inglese, un altro ancora i volumi di matematica, e così via. I cataloghi venivano classificati dal bibliotecario come libri ordinari, e come tali erano disposti sui normali scaffali della biblioteca e catalogati al pari degli altri volumi.
Un giorno il bibliotecario si accorse che alcuni dei cataloghi erano elencati in se stessi (per esempio l'elenco dei volumi in italiano e quello dei volumi stampati nell'anno in corso), e altri (per esempio quello dei libri in inglese e quello dei libri di matematica) non lo erano. Per approfondire la curiosa questione, il bibliotecario decise allora di stilare due ulteriori cataloghi: quello dei cataloghi  elencati in se stessi e quello dei cataloghi non elencati in se stessi. I problemi del bibliotecario iniziarono non appena si domandò se quest'ultimo volume dovesse o no includere se stesso.
Infatti, supponiamo che il catalogo dei cataloghi non elencati in se stessi contenga anche se stesso: ma allora il catalogo stesso è elencato in se stesso, e come tale non dovrebbe comparire nella sua stessa lista. Viceversa, supponiamo che questo elenco non contenga se stesso: se ciò accade, si tratta di un catalogo che dovrebbe comparire nella lista dei cataloghi non elencati in se stessi, quindi l'elenco dovrebbe autoincludersi.
Non c'è via d'uscita: siamo di fronte a un paradosso, un po' come quello del famoso barbiere di Russell o quello del mentitore cretese.

A parte il carattere paradossale, cosa c'entra la storiella del bibliotecario con i libri infiniti? Nella versione classica, che è quella che ho raccontato, nulla. Ma esiste una versione alternativa della storia ambientata in una biblioteca che comprende tutti i libri possibili: anche quelli mai esistiti, impossibili, impensabili. In una simile vertiginosa e infinita biblioteca, anche il fatidico catalogo dei cataloghi non elencati in se stessi, per quanto contraddittorio, deve essere presente.

Da http://www.vallesabbianews.it
Qui a essere infinito non è il singolo libro, ma la biblioteca, e parlando di biblioteche infinite non può non tornare in mente La biblioteca di Babele. Non a caso, in questo racconto Borges allude un paio di volte al paradosso del bibliotecario:

Come tutti gli uomini della Biblioteca, in gioventù io ho viaggiato; ho peregrinato in cerca di un libro, forse del catalogo dei cataloghi; ora che i miei occhi quasi non possono decifrare ciò che scrivo, mi preparo a morire a poche leghe dall'esagono in cui nacqui.

Non vi sono, nella vasta Biblioteca, due soli libri identici. (…) i suoi scaffali registrano tutte le possibili combinazioni dei venticinque simboli ortografici (numero, anche se vastissimo, non infinito), cioè tutto ciò che è dato di esprimere in tutte le lingue. Tutto: la storia minuziosa dell’avvenire, le autobiografie degli arcangeli, il catalogo fedele della Biblioteca, migliaia e migliaia di cataloghi falsi, la dimostrazione della falsità di questi cataloghi, la dimostrazione della falsità del catalogo autentico, (…)

D'accordo, nella Biblioteca di Babele si parla di una biblioteca infinita, ma, come già ricordato nella prima parte di questo post, è Borges stesso a osservare come una biblioteca infinita sia perfettamente equivalente a un unico libro infinito, formato da un numero infinito di fogli infinitamente sottili.
Anche un libro infinito, come quelli descritti da Delahaye, potrebbe ospitare in sè tutti i libri della Biblioteca di Babele, i suoi cataloghi, i cataloghi dei cataloghi, e così via.
La questione interessante, sostiene il matematico francese, consiste casomai nell'analizzare i diversi modi in cui un libro infinito può contenere informazione. Da questo punto di vista, Delahaye individua quattro diverse tipologie di libro infinito:
1. libri infiniti in cui ogni pagina contiene un numero fisso di caratteri (o pixel di immagini);
2. libri infiniti in cui ogni pagina contiene un numero finito ma variabile di caratteri (o pixel di immagini);
3. libri infiniti in cui ogni pagina contiene una infinità numerabile di caratteri (o pixel di immagini);
4. libri infiniti in cui ogni pagina è assimilabile a una porzione del piano cartesiano, sulla quale si possono disegnare testi e immagini in modo infinitamente fine.
Ciascuna di queste famiglie di libro infinito è caratterizzata da situazioni e conseguenze diverse, che Delahaye sviscera in dettaglio.
E qui mi fermo, stavolta definitivamente. Il lettore troverà senz'altro ulteriori spunti di approfondimento sul citato libro di Delahay, e ovviamente anche sui testi letterari da me citati in questi tre post.
Ve lo posso assicurare: sono tutti libri finiti, quindi li potete leggere dall'inizio alla fine tranquillamente, senza pericolo di perdervi nei vertiginosi meandri dell'infinito.