Post

Visualizzazione dei post da Novembre, 2014

Algoritmi golosi

Immagine
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. Supp…

Carnevale della Matematica #79 sul Coniglio Mannaro

Immagine
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 …

Il weekend di Altramatematica

Immagine
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, pre…

I premi Turing: Charles Bachman

Immagine
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.  Un…

Come costruire un libro infinito (terza parte)

Immagine
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 t…