Archivi annuali: 2010

Ricorsione

ricorsione, s.f.: vedi ricorsione

L’induzione, di cui ho parlato poco tempo fa, è una brutta bestia: non tanto per la complessità del concetto, quanto perché il modo con cui si impiega generalmente l’induzione è piuttosto astratto. Le dimostrazioni per induzione assomigliano spesso a un gioco di prestigio algebrico, con un po’ di operazioni formali. Insomma, qualcosa che funziona sì, ma non ci dà informazioni su cosa sta effettivamente dietro.
La cosa buffa è che però è relativamente semplice trovare spiegazioni sull’induzione, ma almeno per i matematici non ci sono così tante informazioni su un modo in un certo senso simile per risolvere i problemi matematici: la ricorsione. La mia sensazione è che la ricorsione era sempre stata usata dai matematici del passato, ma veniva considerata una tecnica di serie B e quindi snobbata nelle dimostrazioni “ufficiali”. Poi è arrivata l’informatica, dove la ricorsione è parecchio usata; di nuovo però i matematici pensano che una cosa usata dagli informatici non è poi così importante… Ma lasciamo perdere queste disquisizioni, e vediamo come funziona la ricorsione.
Tecnicamente la ricorsione consiste nel risolvere un problema P con dati in ingresso D riconducendosi alla risoluzione del problema P con dati in ingresso D’, dove i dati D’ sono “più semplici” dei dati D. La frasetta magica “ricondursi al caso precedente” ricorre spesso nelle barzellette create dai fisici per prendere in giro i matematici; ma in questo caso la cosa è piuttosto diversa, e molto più seria. Ecco l’esempio canonico di ricorsione, tanto per mettere le cose più in chiaro: il calcolo del fattoriale.
Come probabilmente ricordate, il fattoriale di un numero intero positivo n, indicato con n!, è il prodotto dei numeri da 1 a n. Per convenzione, 0! e 1! sono uguali a 1. Per calcolare n! si può appunto fare il prodotto dei numeri da 1 a n, ma si può anche operare in altro modo. Un informatico per esempio scriverebbe un programma la cui parte principale dice più o meno così: “Per calcolare la funzione “fattoriale di n“, chiamo la funzione “fattoriale di n-1″ e moltiplico il risultato per n.” Chi non è abituato a queste cose fa un balzo sulla sedia: “Ma come fa questo qua a scrivere una cosa del genere? Com’è possibile definire una funzione per mezzo di sé stessa? Non si sovrappongono i pezzi?” Per quanto riguarda la struttura informatica, vi posso assicurare che non ci sono problemi: quello che viene richiamato non è il programma inteso come archetipo ma una sua istanza, insomma un suo clone. Il punto chiave è che dobbiamo essere certi che il procedimento non si espenda all’infinito, oppure che a un certo punto si ritorni al punto di partenza ottenendo così un circolo vizioso. Ma per fortuna questo non è il caso: il numero di cui si deve calcolare il fattoriale continua a ridursi, e prima o poi diventerà 1 (beh, ammesso che l’input sia stato un numero intero positivo. Ma quello del validare i dati in ingresso è un altro tipo di problema: qui si fa matematica, non informatica). Ma noi sappiamo quanto vale il fattoriale di 1! (per la cronaca, quest’ultimo è un punto esclamativo, non il simbolo di fattoriale), cioè 1. In definitiva, basta aggiungere il caso particolare; “Per calcolare la funzione “fattoriale di n“, verifico se n=1; in caso affermativo il risultato è 1, altrimenti, ecc. ecc.”.
Notata la differenza con l’induzione? Lì partivamo da 1 e salivamo fino all’infinito, grazie al quinto postulato di Peano; qui partiamo da un numero qualunque e scendiamo fino a 1. C’è però un altro punto che in genere viene trascurato. L’induzione parte da una formula chiusa, una cioè dove basta infilare il numero e si ottiene il risultato; con la ricorsione non c’è nulla del genere, e anzi trovare una formula chiusa a partire da quella ricorsiva non è sempre così semplice. Tanto per fare un esempio pratico, prendiamo i numeri di Fibonacci. Come ricordate, la loro definizione è ricorsiva: F1 = F2 = 1, e Fn+1 = Fn + Fn-1. È anche possibile avere una formula esplicita per l’n-simo numero di Fibonacci:
[1/sqrt(5) * ((phi_1)^n - (phi_2)^n)]
dove φ1 è (1+√5)/2 e φ2 è (1-√5)/2. Semplice, no? Vero che ce l’avevate sulla punta della lingua? D’accordo, questo è forse un caso limite: ma in genere ci vuole comunque una certa arte per trovare la formula chiusa corrispondente a una formula ricorsiva.
Nonostante tutto, però, la ricorsione almeno a mio parere è un modo più naturale per trovare la soluzione di tutta una classe di problemi, e quindi dovrebbe essere sempre pronta nella borsa degli attrezzi di un matematico.

Ultimo aggiornamento: 2010-04-01 11:43

Sono cose.

No, non è un pesce d’Aprile. Martedì scorso, dopo soli 53 giorni, è tornata a funzionare la macchinetta del caffè in ufficio. Adesso non ho più scuse per non essere sveglio.

Ultimo aggiornamento: 2010-04-01 11:41

Nicola Arigliano

Chi ha la mia età associa inevitabilmente al nome di Nicola Arigliano la frase “Gruppo vacanze Piemonte, si parte!”, dai Caroselli del digestivo Antonetto. Pe chi è più giovane il suo nome non dice assolutamente nulla, anche se negli anni ’90 era tornato ad apparire anche in televisione.
Ma Nicola Arigliano, morto stanotte, era molto di più: non solo un crooner ma anche un jazzista, con uno stile di antan che era assolutamente piacevole all’ascolto. Eppure è sempre la tv, anzi la pubblicità, quella per cui vieni ricordato…

Ultimo aggiornamento: 2010-03-31 11:40

Quanto è difficile processare dati online

Ricordate il treno che abbiamo preso domenica con ritardo maggiore di un’ora? Con le nuove norme (“ah, signora mia, è l’Europa che ci ha costretto a seguirle!”) In teoria avremmo diritto a un rimborso di ben il 25% del prezzo del biglietto. Addirittura (e qui in effetti c’è un obbligo europeo, mi sa) non come bonus ma come rimborso sulla carta di credito. In pratica?
La mia richiesta online ha dato questa risposta: «Il viaggio da lei effettuato non ha diritto ad un indennizzo. Di seguito il dettaglio: Evento non elaborato»
In effetti, leggendo attentamente qui, è chiarissimo che «Trascorsi 20 giorni dalla data del tuo viaggio (successivo al 13 dicembre 2009) puoi interrogare direttamente i sistemi informativi Trenitalia per verificare l’ammissibilità o meno del diritto all’indennità (biglietterie, agenzie di viaggio, self-service, internet, Call Center) e poi chiedere presso le biglietterie di stazione o l’ agenzia di viaggio presso cui hai acquistato il biglietto:» [ecc.ecc.: il grassetto è mio]
Capisco ventiquattr’ore di attesa, ma VENTI GIORNI? Con dati che si suppone siano già disponibili online, visto che il ritardo me lo sono visto man mano con il telefonino? Faccio il dietrologo: secondo me è un gomblotto perché la gente così si dimentica di fare la richiesta.

Ultimo aggiornamento: 2010-03-31 07:00

Contro il doppio lavoro

Le sconfitte alle comunali del mininistro Brunetta a Venezia e del sottosegretario ingegner Castelli a Lecco mi paiono un’ottima cosa.
Nel caso ve lo chiedeste, la mia gioia non è per la vittoria del centrosinistra, ma per una questione molto più generale. I rappresentanti del Popolo della Libertà e della Lega erano infatti stati pronti a render noto che in caso di vittoria loro non si sarebbero affatto dimessi dal governo, perché tanto sarebbero stati in grado di svolgere al meglio i due lavori. Ecco: io sono contento perché cotale protervia è stata punita. Già ho dei dubbi sul doppio lavoro di parlamentare e membro del governo, ma almeno sono compiti complementari; voler dirigere contemporaneamente una città e lo stato è però uno schiaffo a chi magari il lavoro lo cerca e non lo trova. Lasciatemi sperare che molti elettori di centrodestra l’abbiano capito – per quelli di centrosinistra credo il problema non si porrà per molto, molto tempo.

Ultimo aggiornamento: 2010-03-30 16:13

Aiuto! Firefox e charset

A quanto pare, questo problema ce l’hanno in tanti e nessuno riesce a risolverlo, o perlomeno io non sono riuscito a trovare una risposta. Però magari qualcuno dei miei lettori sa che cosa fare.
Ogni tanto mi capita un messaggio illeggibile su GMail, visto da Firefox (3.6, su macchine XP). Ad esempio, la newsletter di Meridiano Zero mi arriva con dei rettangolini che corrispondono agli apostrofi; Chrome in compenso visualizza il tutto bene. Ho provato a toccare View → Character Encoding, mettendo di tutto (Universal/Off, ISO-8859-1/UTF-8), ma niente da fare. Guardando i sorgenti della newsletter, vedo che è un MIME multipart: la parte testuale ha come header
  Content-transfer-encoding: quoted-printable
e quella HTML
  Content-type: text/html; charset=iso-8859-1
  Content-transfer-encoding: quoted-printable
mentre però la pagina inizia con
  <!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN"
"http://www.w3.org/TR/html4/loose.dtd">

  <html>
  <head>
  <meta http-equiv="Content-Type" content="text/html; charset=UTF-8">
il che mi può far immaginare che ci sia un problema di contrasto tra i due content type.
Ma ci sono cose peggiori: provate a guardare questi due messaggi che sono arrivati sul blog: good e bad. Io non riesco a vedere alcuna differenza, però il bad mostra le lettere accentate come se fossero scritte in ISO-8859-2, insomma con le lettere degli alfabeti slavi, mentre il good è perfetto.
Qualche idea, qualcuno?

Ultimo aggiornamento: 2010-03-30 13:22

epperò!

Non mi sarei aspettato la vittoria di Cota in Piemonte, ma sono contento per i miei corregionali che finalmente avranno quello che bramavano da un pezzo. (Ah, non è colpa di beppegrillo™ se la Bresso ha perso. Se uno ha votato il movimento a 5 stelle, non era certo uno che si sarebbe mosso per votare la Mercedes).
Non mi sarei aspettato una vittoria così ampia di Vendola in Puglia. E la divisione del centro-destra conta poco, perché molti ex AN non avrebbero comunque votato la traditrice Poli Bortone. Ma mi sa che sia vero che ormai la politica è protagonismo dei leader, da Silvio a Di Pietro financo a Casini – che però è rimasto fregato con la sua politica dei due forni – e l’unico vero leader che ha il PD è D’Alema, il che fa capire come la sigla sta per Party Doomed.
Sul risultato del Lazio resto agnostico, nel senso che non avevo grosse previsioni.
Sul risultato di Penati in compenso non avevo dubbi. Vedere come, pure in mezzo alla disfatta del centrosinistra (la sinistra non è pervenuta, ma tanto quelli sono troppo fuori dal mondo), sia riuscito a prendere otto punti percentuali in meno di quanto fece Sarfatti cinque anni fa dovrebbe voler dire qualcosa. Ma non lo dirà.
Ad ogni modo queste elezioni hanno dimostrato che la televisione non conta poi molto. Confrontate il risultato della Lega con lo spazio lasciato al Fedele Alleaten da RaiSet.

Ultimo aggiornamento: 2010-03-30 10:29