domenica 28 febbraio 2010

Il dugongo

(Tutto il movimento di ricordi che segue nasce da una parola letta qui)

Ero un bimbetto di circa dieci anni e, durante le estati, mentre i miei lavoravano, stavo quasi sempre con la nonna, la mamma di mia mamma. Ogni tanto, però, andavo dagli altri nonni, i genitori del babbo, che abitavano vicino al centro città. Il nonno, che ora non c'è più, andava quasi quotidianamente a chiacchierare con il suo consuocero, proprietario di una libreria (che esiste ancora, e porta ancora il cognome del consuocero, anche se ora non è più il proprietario). Io andavo con lui.

Voglio dire: io passavo le mattine all'interno di una libreria, toccavo i libri, li guardavo, li prendevo, li leggevo. Li annusavo.

Sì, oggi si può entrare in una grande libreria, toccare quello che si vuole, leggere magari a scrocco, ma non è la stessa cosa. Quella là era una libreria vera, con un'anima. E un libraio che conosceva ogni volume che aveva in vendita, che salutava i clienti che entravano, scambiava quattro chiacchiere, consigliava.

Vabbè, lo so che adesso, con la diffusione degli ebook reader, quelli che parlano del profumo dei libri sono guardati con sufficienza (non che prima fossero considerati delle persone del tutto normali, eh), ma portate pazienza. Per me quello era un posto speciale.

Mi ci sono letto le origini di Diabolik, per dire.

Il nonno aveva, a casa sua, una edizione della Divina Commedia della casa editrice Nerbini, Firenze. Io la guardavo in continuazione (anche un po' di nascosto: c'erano delle figure un po' scollacciate che non sapevo bene se potevo guardare oppure no); in libreria avevo riconosciuto la stessa casa editrice (la stessa carta, lo stesso profumo) in un paio di libri dalla copertina blu: Iliade ed Eneide. Il nonno me li regalò quando ero alle medie.

Ma tutto ciò non ha nulla a che fare con il dugongo.

Intanto: sapete cos'è un dugongo? Se no, andate pure avanti a leggere. Se sì, fermatevi un attimo a pensare: quando avete imparato il significato della parola? Ve lo ricordate? Io sì, come se fosse ieri. Ero là in quella libreria, e stavo leggendo un libro. Uno di quelli a cui tengo di più.

Pausa.

Ho conosciuto l'arte di Franco Caprioli in quella libreria, leggendo una riduzione a fumetti del romanzo L'isola misteriosa, di Verne. Non conoscevo né il disegnatore, né il romanzo: quando trovai il volume in libreria, non lo mollai più. È un'avventura meravigliosa, con i misteri, le esplorazioni, la natura selvaggia. Con l'ingegnere che sa risolvere ogni tipo di problema (sì, certo, è un'opera di fantasia), sa calcolare l'altezza di un monte utilizzando le proporzioni, sa fabbricare i mattoni, sa estrarre il ferro, sa creare la nitroglicerina, sa trovare longitudine e latitudine. E te lo spiega, anche. E tu, leggendo, impari come si fa.

E i disegni. I disegni di questo artista che disegna con una pazienza infinita. Non usa retini: disegna i puntini a mano. Ne pubblico qualcuno qua sotto: non ho chiesto nessun permesso e, se qualcuno protesterà, li cancellerò. Non ci guadagno nulla.

Il marinaio Pencroff

Una delle invenzioni dell'ingegnere

La lezione sulla similitudine

Il mare è spettacolare

Ed ecco il dugongo

venerdì 19 febbraio 2010

Il teorema dello pseudo Scoto

Già chiamarsi Duns Scoto è strano, ma se poi tutti ti chiamano Doctor Subtilis la faccenda diventa impegnativa.

Della vita di John Duns Scotus (questo è il suo nome non italianizzato) si sa poco: nasce intorno al 1265, probabilmente nella cittadina scozzese di Duns. È un filosofo, un teologo, un sacerdote e un beato della chiesa cattolica.

La tradizione lo vede autore di un teorema denominato Ex falso quodlibet, utilizzato da xkcd nella sua striscia di oggi:

Principle of Explosion

Il teorema afferma che partendo da una contraddizione si può dimostrare qualunque affermazione. Ecco come si fa.

Prendiamo una affermazione qualsiasi; che so, l'ipotesi di Riemann: supponiamo che sia vera e falsa. Ora vogliamo dimostrare che la seguente uguaglianza è vera: “1+1=3”.

Bene, dato che l'ipotesi di Riemann è vera, allora è vera anche l'affermazione che dice “l'ipotesi di Riemann è vera oppure 1+1=3”. Infatti una generica proposizione “p oppure q” è vera quando almeno una delle due proposizioni che la compongono (cioè p oppure q) è vera.

Perfetto. Dato che la proposizione composta “l'ipotesi di Riemann è vera oppure 1+1=3” è vera, e dato che l'ipotesi di Riemann è falsa, allora occorre che sia vero che “1+1=3”. Quindi 1+1 è uguale a 3.

Gli inglesi chiamo questo teorema Principio di esplosione, perché a partire da una semplice contraddizione esso permette di dimostrare tutto. Noi lo chiamiamo invece Teorema dello pseudo Scoto, perché in realtà pare che esso sia stato enunciato da un autore sconosciuto.

Giovanni Duns Scoto, comunque, avrebbe detto che poco importa chi lo ha enunciato: ciò che conta è che il teorema esista. Ed esso esisteva anche prima che lo pseudo Scoto lo portasse alla luce.

sabato 6 febbraio 2010

Eh eh


(via Aleio)

Per iniziare bene la giornata



(via Mariano Tomatis)

L'algoritmo di Warnsdorff

Il giochino di cui ho parlato qualche giorno fa può essere risolto con un programma per computer. Tecnicamente si tratta di una ricerca di un cammino hamiltoniano su un grafo, che sarebbe poi un percorso che tocca tutti i vertici di un grafo una volta sola.

La scacchiera 10×10 deve essere infatti vista come un grafo: ogni casella è collegata a tutte quelle che sono raggiungibili, a partire da essa, con una sola mossa.

Per esempio, se noi partiamo dalla casella nell'angolo in alto a sinistra, osserviamo che essa è collegata soltanto a tre altre caselle, come nella seguente figura.


A sua volta, ognuna delle tre caselle raggiungibili con la prima mossa è collegata ad altre caselle, e così via. Dunque, per completare il giochino il nostro programma dovrebbe esplorare l'albero delle mosse allo scopo di trovare un percorso che tocchi tutte le caselle una volta sola.

Come si fa? Bè, in generale il problema della ricerca di un cammino hamiltoniano è NP-completo. In linguaggio non da informatico significa che è un problema difficile. Volendo essere più precisi, si può dire che se si riesce a trovare una soluzione al problema, allora è facile verificare che essa sia giusta; ma il problema è trovarla. Infatti la caratteristica principale dei problemi NP-completi è che non si conosce nessun tipo di algoritmo veloce per poterli risolvere. Ciò significa che il tempo impiegato dal computer per risolvere il problema diventa rapidamente dell'ordine degli anni (o delle migliaia di anni, milioni di anni, miliardi di anni, esagerate pure) appena si tenta di aumentare un po' la dimensione del problema stesso.

Volendo essere ancora più precisi: se si riesce a trovare una soluzione veloce a uno dei tanti problemi NP-completi, allora è stato dimostrato che si può trovare una soluzione altrettanto veloce per tutti i problemi della categoria NP-completi. In pratica, sono tutti equivalenti. Per dare un'idea dell'importanza di tutto ciò, sappiate che se riuscite a trovare l'algoritmo veloce avete diritto a un premio di un milione di dollari. Anzi, forse avete diritto al premio anche se dimostrate soltanto l'esistenza di un algoritmo veloce, senza trovarlo (per capire bene se le cose stanno così bisognerebbe leggersi tutto il bando ufficiale del premio).

Bene, torniamo al nostro programma. La scacchiera 10×10 è ancora abbastanza piccola, per cui l'albero delle possibili mosse può ancora essere esplorato andando per tentativi: si prova a sistemare il primo numero, poi si prova col secondo, e così via. Se si arriva all'ultimo, siamo fortunati e il giochino è risolto, altrimenti si torna indietro, si cambia una scelta fatta, e si percorre una nuova strada. Prima o poi si trova la soluzione (o si percorrono tutte le strade e si può affermare con certezza che la soluzione non esiste). Questa tecnica è detta backtracking, ovvero prova e riprova.

Questo particolare tipo di problema di ricerca di cammino hamiltoniano, però, può anche essere risolto senza fare uso della forza bruta, ma utilizzando un algoritmo veloce, detto algoritmo di Warnsdorff (che è poi quello che ho usato io quando ho risolto a mano il gioco).

Funziona in questo modo: supponiamo di avere riempito una certa casella; dobbiamo decidere quale sarà la successiva da riempire. Per ognuna delle caselle candidate, andiamo a vedere a quante altre caselle esse sono collegate. Per esempio, se cominciamo con la prima casella in alto a sinistra, abbiamo tre possibilità. Osserviamo che da due caselle possiamo proseguire in 4 modi diversi, e dalla terza casella possiamo proseguire in 5 modi.

Bene, per andare avanti dobbiamo sempre scegliere la casella con il minor numero di connessioni, cioè quella più difficile da raggiungere (se ci sono più caselle con lo stesso minimo numero di connessioni, scegliamone una a caso). Se seguiamo questo accorgimento, siamo sicuri di arrivare in fondo. Ecco, per esempio, una soluzione generata al computer.

+---+---+---+---+---+---+---+---+---+---+
|  1| 62| 40| 16| 61| 39| 75| 49| 38| 74|
+---+---+---+---+---+---+---+---+---+---+
| 54| 18|  3| 53| 58|  4| 52| 72|  5| 51|
+---+---+---+---+---+---+---+---+---+---+
| 41| 15| 60| 67| 94| 79| 66| 95| 78| 48|
+---+---+---+---+---+---+---+---+---+---+
|  2| 63| 57| 17| 64| 69| 76| 50| 37| 73|
+---+---+---+---+---+---+---+---+---+---+
| 55| 19| 99| 82| 59| 98| 91| 71|  6| 90|
+---+---+---+---+---+---+---+---+---+---+
| 42| 14| 29| 68| 93| 80| 65| 96| 77| 47|
+---+---+---+---+---+---+---+---+---+---+
| 23| 83| 56| 24| 86| 70| 25| 87| 36| 10|
+---+---+---+---+---+---+---+---+---+---+
| 30| 20|100| 81| 32| 97| 92| 33|  7| 89|
+---+---+---+---+---+---+---+---+---+---+
| 43| 13| 28| 44| 12| 27| 45| 11| 26| 46|
+---+---+---+---+---+---+---+---+---+---+
| 22| 84| 31| 21| 85| 34|  8| 88| 35|  9|
+---+---+---+---+---+---+---+---+---+---+

Un gioco simile a questo è il giro del cavallo: si tratta di toccare tutte le caselle di una scacchiera utilizzando le mosse del cavallo degli scacchi. In questo caso l'algoritmo di Warnsdorff non sempre assicura il successo; se volete divertirvi, in questa pagina c'è una applet java che vi permette di provare.