L’informatica è una scienza e la programmazione è una delle sue applicazioni. Sembra una banalità ma voglio esordire così perché penso che questo concetto non sia molto chiaro al grande pubblico. Pensate a cosa accadrebbe se delle persone pretendessero di fare il medico o il chirurgo per hobby oppure di progettare grattacieli nel fine settimana. Non solo aumenterebbero drasticamente le morti per malattie e crolli per cedimenti strutturali ma avremmo anche il danno (ben peggiore) di trovare in libreria libri tipo Surgery for Dummies oppure di vedere fiorire decine di blog e forum in cui condividere le proprie esperienza con bisturi e cazzuola. Grazie a Dio questo non accade: la medicina e l’architettura (e la rispettiva l’ingegneria edile) sono infatti considerate scienze a tutti gli effetti ed evocano nella mente dei profani un certo timore reverenziale.
L’informatica invece è una scienza anomala. Tutti si sentono autorizzati a parlare al riguardo senza avere una minima idea di quello che l’informatica rappresenti. Ma non solo. Molte persone, per il solo fatto di avere un computer e di aver usato una volta regedit, pensano di avere tutte le basi necessarie per cominciare a praticare l’hobby della programmazione esattamente come se, tornando all’esempio medico di prima, avere un bisturi e un parente a portata di mano fosse condizione sufficiente per poter parlare di chirurgia.
In realtà di basi, molto spesso, non ne hanno alcuna e si forma nelle menti di molte persone l’idea che la programmazione sia una specie di rito sciamanico in cui la semplice combinazione di “parole magiche” permetta di far avverare i sogni più nascosti e peccaminosi. Allo scopo di apprendere questo rito di magia nera molti cominciano a studiare manuali su manuali come se per essere un bravo programmatore bastasse conoscere tutte le istruzioni di un dato linguaggio (sarebbe come a dire che per essere un bravo matematico basta conoscere somme, sottrazioni, prodotti e divisioni). Senza contare che spesso questi manuali, una volta letti, fanno pensare “e adesso che faccio?” con relativa presa di coscienza di non saper fare quasi nulla.
Ma perché tutta questa intraprendenza? Probabilmente perché la programmazione, fatta a livello dilettantesco, è effettivamente facile: creare piccoli script per automatizzare piccole operazioni o scrivere algoritmi che risolvano semplici problemi sono cose in cui la programmazione sciamanica svolge per bene il proprio lavoro. Il problema si manifesta nel momento in cui il novello programmatore decide di alzare il tiro e a creare il primo programma di utilità globale (o che lui ritiene tale). Infatti a questo punto, molto spesso, il malcapitato lancia il suo progetto su qualche forum in attesa di collaboratori (ovvero gente che programmi al posto suo) senza uno schema di progetto, senza un idea su come realizzarlo e finisce per occuparsi del sito o della grafica e dopo un paio di settimane del progetto rimane solo il nome.
Questo libro vuole colmare questa lacuna. Vuole addestrare la vostra mente ad un pensiero informatico in modo tale da avere almeno una piccola idea di cosa state facendo davanti alla finestra di un IDE di programmazione.
Per fare questo devo fare un avvertenza: la programmazione è al 90% matematica. Questo libro userà e tratterà di concetti matematici (in particolare logica, matematica discreta e teoria degli insiemi). Se non volete toccare la matematica siete liberi di farlo ma limitatevi alla programmazione sciamanica di cui trovate tanti trattati sul web: questo libro non fa per voi.
Mi capita spesso, infatti, che persone mi chiedano consigli su come imparare a programmare. Io, sempre, rispondo che per esercitarsi si può provare a risolvere alcuni problemi di natura matematica (trovare multipli, numeri primi e roba più complicata) e spesso ricevo la risposta “io non sono molto ferrato in matematica” o peggio ancora “ma questo a che mi serve? Io voglio solo fare un programma di video editing non-lineare multi-traccia”. Beh…se la pensate così scordatevi il mio aiuto.
A questo punto partiamo dal basso. Per capire come programmare bisogna innanzitutto capire come ragiona un pc. Per vostra fortuna un calcolatore è una macchina fondamentalmente “stupida”: l’unica cosa che sa fare è leggere e manipolare numeri. E nemmeno tutti, solamente i numeri naturali.
Il sistema scolastico italiano, unito alla sindrome del tifoso tipica della specie umana, forma però l’idea che i numeri naturali siano qualcosa di limitato e inutile. Perché questa idea? Forse perché i numeri naturali e l’aritmetica intera è praticamente roba che si fa solo alle elementari? Non ci è dato saperlo. Fatto sta che siamo abituati a considerare i numeri degli insiemi ℝ e ℤ solo un inutile limitazione.
Che i naturali abbiano delle limitazioni è ovvio: in ℕ infatti le uniche operazioni chiuse1sono la somma ed il prodotto mentre le loro inverse (sottrazione e divisione) finiscono spesso e volentieri fuori dall’insieme dei naturali. Inoltre, sappiamo dalla teoria che l’insieme dei naturali non è sufficente per indicizzare tutti i numeri reali (e quindi i reali sono più infiniti dei naturali).
Tuttavia questo insieme discriminato rimane ancora sufficentemente potente da poter essere usato per indicizzare univocamente tutto ciò che esiste nell’universo. Dal numero di telefono del vostro cellulare fino alla divina commedia o alla struttura atomica del sole: tutto può essere espresso tramite un unico e preciso numero naturale opportunamente codificato. Facciamo un piccolo esempio: consideriamo proprio la divina commedia e vediamo in che modo possiamo facilmente trovare un metodo per codificarla in un numero univoco. Limitandoci ad esempio alla prima frase
Nel mezzo del cammin di nostra vita
possiamo ricavare il seguente numero univoco:
|
| (1.1) |
e così via. In pratica elevo progressivamente tutti i numeri primi per la posizione che ha una certa lettera all’interno dell’alfabeto (e a 0 nel caso di uno spazio).
Ovviamente questo non è l’unico metodo possibile: provate ad esempio a scaricare tutta la divina commedia all’interno di un file di testo e a considerare questo file di testo nella sua forma binaria. Il numero binario in questione non è altro che un numero naturale univoco che individua la divina commedia all’interno dello spazio dei testi codificati.
Questo ragionamento non vale solo per i testi: anche una radiosveglia può essere scomposta in elementi riconducibili ad un unico mega-numero naturale (ad esempio le misure dei suoi lati e la struttura dei circuiti che la compongono).
Questo concetto di rappresentazione della realtà tramite un unico numero naturale è fondamentale nella programmazione e diventa sempre più importante man mano che ci avventuriamo in linguaggi più astratti.
Supponiamo infatti di voler scrivere un programma per giocare al classico Tris e di avere a disposizione solamente un linguaggio di bassissimo livello in grado di manipolare solo numeri nella memoria. Sorge spontaneo il problema di rappresentare la griglia di gioco tramite numeri. Si potrebbe ad esempio creare una lista di nove numeri (uno per casella) e assegnare, ad esempio, il valore 1 alla X, il valore 0 alla O e il valore 2 alle caselle vuote. In questo modo una lista del tipo 001012102, se ben interpretata, può rappresentare alla perfezione la nostra griglia e servire a memorizzare tutte le possibili partite che possiamo giocare nella nostra vita.
Questo problema, detto problema della riduzione, è probabilmente lo strumento principe nella testa di ogni informatico. Ma andiamo per gradi. A questo punto non ci interessa ancora imparare a rappresentare cose così complesse, ci basta sapere come rappresentare, ad esempio, numeri non-naturali tramite numeri naturali. Che è possibile lo sappiamo già, a meno che la vostra calcolatrice non esploda non appena fate 1 - 2.
Prima di avventurarci nella rappresentazione tramite naturali di insiemi numerici più complessi (e addirittura infinitamente più vasti) torniamo al nostro pc. Prima vi ho accennato che il pc è una macchina stupida. Beh, adesso voglio svelarvi un altro segreto: non è stupida, è completamente idiota. Questo perché non solo non riesce a memorizzare null’altro che numeri naturali, ma non riesce nemmeno a memorizzarli in un sistema numerico qualsiasi.
Prima di andare avanti voglio quindi che sia ben chiaro il concetto di sistema numerico: un sistema numerico non è altro che un sistema per rappresentare i numeri. Questo perché i numeri esistono a prescindere dal fatto che ci sia una scimmia bipede in grado di rappresentarli e soprattutto è indipendente dal mondo in cui si rappresentano. C’è quindi una differenza fondamentale fra il numerale, ovvero la serie di simboli che rappresentano un numero, e il numero in se. Ad esempio i numeriali VII e 7 rappresentano lo stesso numero anche se viene espresso in modo diverso, o meglio, in parole povere, Rambo III e Rambo 3 sono lo stesso film anche se vengono indicati con numerali diversi.
Solitamente l’uomo moderno utilizza il sistema numerico decimale. Il perché il numero magico sia proprio il dieci è probabilmente da a ttribuire al fatto che il dieci è proprio il numero delle nostre dita. Non a caso il più acerrimo nemico del 10 è il 12 che corrisponde al numero di falangi di una mano (pollice escluso). Ma tralasciando questo aspetto è chiaro che si può, in linea teorica, sostituire il dieci con qualsivoglia numero e utilizzare, quindi, qualsivoglia sistema numerico. Ad esempio un sistema numerico ternario è un sistema che utilizza solo 3 simboli (0,1 e 2) per rappresentare tutti i naturali. Ma come funziona il meccanismo? Semplice.
Consideriamo la nostra cara base10 (alla faccia della Dozenal Society of America) e consideriamo tutti i modi possibili per rappresentare un numero in questa base. Tali modi sono fondamentalmente due: associo un simbolo all’unità e a tutti i multipli della base oppure associo un simbolo a tutte le cifre comprese fra 0 e la base e do un valore alla posizione.
Il primo metodo è essenzialmente quello usato dai numeri romani: i romani infatti avevano simboli differenti per rappresentare 1,10,100,1000 (rispettivamente I,X,C e M) e formavano ogni numero ripetendo tali simboli tante volte quante erano contenute nel numero da rappresentare. Ad esempio il numero 1232 assumeva la forma MCCXXXII e il numero 44 era semplicemente XXXXIIII2.
Il secondo sistema è invece alla base di tutta la rappresentazione numerica di origine indiana ed è utilizzato tutt’ora in tutto l’occidente: è il sistema posizionale. Secondo questo metodo si danno dei valori base alle cifre inferiori alla base (0,1,2,3, ecc.) e tali cifre assumono un valore, oltre che in base al simbolo, anche in base alla posizione in cui esso viene collocato all’interno di un numerale. Nel sistema decimale, ad esempio, scrivere il numero 206 equivale a scrivere:
 | (1.2) |
Questo significa che i coefficenti moltiplicativi sono sottointesi e impliciti nella posizione della cifra all’interno del numero. Il numero 10 implicito nella numerazione prende il nome di base ed equivale al numero di simboli utilizzati nel sistema numerico. Analogamente, al posto di 10, possiamo considerare una base qualsiasi (2, 3, 50, 9000) e dotarci del numero adatto di simboli per creare la nostra personale base numerica.
Tornando al caso precedente possiamo facilmente convertire un numerale in base 3 in un numerale in base 10 semplicemente conoscendo le regole del sistema posizionale. Ad esempio il numero in base tre 2101 equivale al numero in base dieci:
 | (1.3) |
Semplice. A questo punto torniamo al pc. Come ben sapete l’unico sistema di riferimento intellegibile da un pc è il sistema binario ovvero in base 2. Il binario non è il più semplice sistema numerico possibile (il più semplice possibile sarebbe un semi-inutile sistema unario) ma sicuramente è quello che più gli si avvicina. Nei sistemi informatici viene scelto il sistema binario per tre semplici motivi:
Senza addentrarci troppo nei particolari aggiungiamo inoltre che il sistema binario ha anche il vantaggio che la sua applicazione al sistema posizionale è più immediata: poiché i coefficenti dei vari 2n sono o 0 o 1 risulta evidente che il sistema posizionale si riduce a sommare le potenze di due nelle posizioni in cui compare un 1. Facciamo un esempio spicciolo: nel numero 1010 compare un 1 nella posizione 3 e nella 1 e quindi il corrispondente decimale sarà semplicemente
 | (1.4) |
Semplice ed essenziale. Per lo stesso motivo un numero decimale viene convertito in binario semplicemente individuando quali potenze di due lo compongono. Anche qui chiariamo con un esempio: il numero decimale 24 è composto da:
 | (1.5) |
e corrisponde, quindi, al numero binario 11000.
Esisto però altri due sistemi numerici spesso usati in informatica: l’ottale e l’esadecimale i quali sono rispettivamente in base otto e in base sedici. Il motivo di queste scelte è l’immediata conversione da binario a ottale o da binario a esadecimale. Consideriamo infatti il numero binario 101110. Se vogliamo convertirlo in ottale ci basta scomporlo in gruppi di tre cifre e convertire singolarmente questi gruppi: 101 diventa 5 e 110 diventa 6 e quindi abbiamo come risultato che il numero 101110 corrisponde all’ottale 56. Analogamente, per convertire lo stesso numero in esadecimale usiamo gruppi da 4 cifre (aggiungendo 0 laddove non ci siano cifre sufficienti): 0010 diventa 2 e 1110 diventa 14 (che corrisponde alla cifra esadecimale E) e quindi abbiamo come risultato il numerale 2EIl sistema esadecimale rappresenta le cifre corrispondenti a 10, 11, 12, 13, 14 e 15 rispettivamente con A, B, C, D, E e F. . Ovviamente per tutti questi casi è valido anche il passaggio inverso.
Da questo possiamo ricavare una tabella che indica i modi migliori per passare attraverso i vari sistemi numerici.
| Da | A | Metodo | |
| Base10 | Base2 | Trovare le potenze di due che compongono il numero. |
|
| Base10 | Base8 | Convertire prima in Base2 e poi convertire in Base8 con il metodo dei gruppi. |
|
| Base10 | Base16 | Convertire prima in Base2 e poi convertire in Base8 con il metodo dei gruppi. |
|
| Base2 | Base10 | Sommare le potenze di due nella posizione in cui compare un uno. |
|
| Base8 | Base10 | Metodo Posizionale (o conversione in Base2) |
|
| Base16 | Base10 | Metodo Posizionale (o conversione in Base2) |
Ovviamente il metodo ancora migliore esiste: usare la calcolatrice. Tuttavia spesso ci serve una conversione al volo e famigliarizzare con certe tecniche è fondamentale. Non approfondirò più ulteriolmente questo aspetto perché ha un utilità limitata, l’importante è che vi sia chiaro il sistema binario in quanto i calcolatori, per il momento, utilizzano solo questo sistema.
L’insieme ℤ rappresenta l’insieme dei numeri relativi, meglio conosciuti come numeri interi, ed è composto dall’unione dei naturali3(0,1,2...) con i numeri negativi. (−1,−2,−3...). Questo insieme ha quindi il pregio di ammettere come operazioni chiuse non solo somma e prodotto ma anche la sottrazione. A questo punto torniamo alla domanda da cui eravamo partiti: come rappresentiamo un numero relativo utilizzando solo numeri naturali? Questo a prima vista sembra un assurdo: se i numeri relativi sono composti da tutti i naturali più un infinità di altri numeri come diavolo è possibile rappresentarli tutti usando solo i naturali? La questione è interessante, ma per ora ci basta sapere che nonostante ciò l’insieme dei numeri naturali contiene lo stesso numero di elementi dell’insieme dei relativi. Possiamo creare infatti una funzione, una regoletta, che ci permette di associare a tutti i numeri relativi un numero intero:
 | (1.6) |
Come si può vedere facilmente tale funzione trasforma ogni numero relativo in un numero univoco naturale: -4 viente trasformato in 8, 3 diventa 5, -1 diventa 2 e così via.
Sappiamo quindi che è possibile fare ciò che ci siamo prefissi, non ci resta che vedere il modo in cui farlo. Non possiamo certo utilizzare la funzione precedente in quanto necessitiamo di un metodo veloce e semplice (senza moduli e divisioni) che ci permetta di rappresentare un numero negativo. A questo proposito notiamo che i numeri negativi non sono altro che numeri naturali a cui è stato accostato il simbolo meno (-). La prima cosa che ci viene in mente è quindi di sacrificare una cifra per rappresentare il segno meno. Considerando quindi l’insieme dei numeri binari di 4 cifre, definiamo la prima cifra come segno e le restanti cifre come numero. Scegliendo lo 0 come + e la cirfra 1 come “-” otteniamo che il numero 0010 continua a rappresentare, come suo solito, il numero 2 mentre il numero 1010, che avrebbe indicato il numero 10, rappresenta ora il numero -2.
Ogni cosa ha però il suo prezzo: il costo di rappresentare il segno di fatto dimezza il massimo numero rappresentabile con 4 cifre. Con 4 cifre, senza segno, possiamo rappresentare correttamente i numeri da 0 a 15, utilizzando il segno, invece, rappresentiamo i numeri da -7 a +7. Un altra cosa da notare è che secondo questa rappresentazione utilizziamo due numerali per indicare lo zero: il numero 0000 è infatti lo stesso numero rappresentato da 1000 in quanto +0 e -0 sono lo stesso numero.
Per evitare questa confusione (e per ottenere vantaggi che vedremo poi nelle operazione aritmetiche) il sistema attualmente utilizzato per rappresentare numeri relativi è quello del complemento a due. Secondo questo sistema la cifra più significativa rimane sempre ad indicare il segno ma con la differenza che, se questa cifra è 1, tutte le cifre che seguono sono invertite (uno 0 diventa 1 e un 1 diventa 0) e alla fine viene sommato 1.
Facciamo qualche esempio: +3 rimane sempre 0011, per convertire -5, invece, troviamo prima il valore di +5, ovvero 0101, poi invertiamo tutte le cifre, ricavando 1010 e infine sommiamo 1 per ottenere il risultato definitivo 1011. Esiste anche un metodo più semplice che consiste nello scorrere il numero da destra a sinistra ed invertire tutto quello dopo il primo 1 che incontriamo: ad esempio per -3 si deve invertire 0011 nel modo precedentemente indicato ottenendo 1101 che è proprio il complemento a due di -3.
Per convertire invece un numero espresso in complemento a due nel corrispettivo numero relativo ci basta convertire semplicemente il numero (segno escluso) e poi sottrarre il segno (ovvero, nel caso di 4 cifre, il numero 1000 = 8). Infatti, considerando -3 otteniamo che 101 = 5 e quindi 5 − 8 = −3.
L’intervallo dei numeri rappresentabili con questo sistema varia da -8 a +7 (guadagnamo quindi un numero negativo in più rubandolo alla doppia rappresentazione dello zero).
Ma tutta questa complicazione a che serve? A semplificare notevolmente le operazione di somma e sottrazione con numeri binari: queste infatti possono essere trattate esattamente come se fossero somme e sottrazioni di numeri naturali dimenticandosi (o quasi) del segno. Supponiamo infatti di voler eseguire la somma di 5 e -3: 5 è rappresentato da 0101 mentre -3 è 1101. Ora ci basta sommare i numeri come se fossero due interi ed ottenere il numero 0010 (non consideriamo le cifre che vanno oltre la quarta). Quel numero è proprio 2, il risultato che ci aspettavamo.
Non andrò oltre per il momento e per maggiori informazioni vi rimando a testi di calcolatori.
Per evitare discriminazioni fastidiose è venuto il momento di inglobare nella nostra rappresentazione anche i numeri razionali e i numeri reali. I primi sono composti da tutti i numeri rappresentati come frazione di due interi. L’insieme dei razionali è grande tanto quanto i naturali (e quindi tanto quanto i numeri interi) ed è semplicemente dimostrabilie disponendo una tabella in cui ci sia una riga e una colonna per ogni numero naturale: partendo dal punto (1,1) si può creare una linea che tocca tutte le coppie di numeri che compongono la tabella.
Non solo. Molte coppie toccate rappresentano lo stesso numero (come ad esempio 1/2 e 2/4 oppure tutti gli altri numeri colorati in rosso) e quindi siamo stati fin troppo precisi e puntigliosi nel nostro ragionamento. Questo risultato implica che, disponendo di numeri con cifre infinite, possiamo tranquillamente rappresentare ogni numero razionale con un singolo numero intero.
L’insieme dei reali invece è più infinito de naturali. Questo significa che, anche utilizzando un numero di cifre binarie infinito, non potremo mai rappresentare tutti i numeri reali. Oh oh. E allora? Dobbiamo rinunciare al nostro sogno? Niente affatto, a patto di accontentarsi di una certa approssimazione.
I calcolatori elettronici rappresentano reali e razionali in virgola mobile (floating point) e in particolare secondo lo standard IEEE 754 che consiste nei seguenti elementi:
Il numero è quindi calcolato secondo la formula
 | (1.7) |
Dove la mantissa è solitamente normalizzata, ovvero va intesa come preceduta da “1,” (uno virgola) e rappresenta quindi la parte decimale del numero 1,xxxxxxx…
La precisione di questa rappresentazione dipende quasi esclusivamente dalla dimensione in bit della mantissa. Nonostante ciò tale rappresentazione è bucata, esistono cioè infiniti numeri non rappresentabili che dividono due numeri rappresentati. Per renderci conto della dimensione di questi “buchi” facciamo qualche esempio numerico prendendo come esempio una rappresentazione dotata di una mantissa a 7 bit.
In un numero float con una mantissa di 7 bit il massimo numero N rappresentabile è dato da:
 | (1.8) |
Mentre il numero subito precedente M è:
 | (1.9) |
A questo punto per avere un idea del vuoto che incorre fra i due numeri basta calcolare la differenza N − M:
 | (1.10) |
Ovvero una voragine dell’ordine di 2120 (svariati miliardi se espressi in modo convenzionale). La nostra rappresentazione quindi, più che a una strada provinciale con qualche buca, sembra proprio una dissestata strada di montagna. Tuttavia tale voragine equivale ad un errore relativo dello 0.4% per numeri vicini al limite superiore. E questo per una mini-mantissa di 7bit. Con una mantissa di 23 bit l’errore crolla ad un misero 0.001% (e nel caso sia ancora troppo potete utilizzare la precisione doppia, double, per ottenere mantisse di 52bit oppure la precisione quadrupla per sfoderare una mantissa da 112 bit). E’ possibile inoltre dimostrare che l’errore relativo rimane pressocché costante anche spingendoci verso i più piccoli numeri positivi (dell’ordine di ).
Anche questa volta non approfondirò nel dettaglio tale rappresentazione e vi rimando quindi a testi specialistici.
Come ogni buon libro che cerca di insegnare qualcosa non potevo non lasciare la possibilità, a chi volesse, di impiantarsi per bene le nozioni precedentemente acquisite tramite una manciata di esercizi. Buon divertimento.
Definizione 1 (Algebra di Boole). Un algebra
booleana (o reticolo booleano) è una struttura algebrica 
= {I,⋅,+,NOT} in
cui I è un insieme di due elementi 0,1, ⋅ e + sono due operatori binari e NOT
è un operatore unario. L’algebra booleana gode delle seguenti proprietà:
 | (2.1) (2.2) (2.3) |
Inoltre vengono definiti due elementi speciali indicati con 0 e 1 tali che:
 | (2.4) (2.5) (2.6) (2.7) (2.8) |
Nonostante i tecnicismi, necessari per essere il più rigoroso possibile su una materia tanto importante come l’algebra booleana, la definizione appena fornita è indubbiamente banale. L’operatore “⋅” prende il nome di prodotto logico o congiunzione logica ed è spesso chiamato anche con il termine inglese AND. L’operatore “+”, invece, è chiamato somma logica o disgiunzione logica ed è spesso indicato anche con il termine inlese OR. L’insieme I, che nel nostro caso abbiamo considerato per comodità come l’insieme formato dai due elementi 1 e 0, è in generale un qualunque insieme di due elementi. Potete scegliere, se volete, anche l’insieme I = falso,vero oppure I = rosso,verde, la sostanza non cambia: l’importante è che associate ad un elemento di I il valore di 1 e al restante il valore di 0.
Le proprietà sopra elencate sono più che sufficienti per derivare tutta la logica booleana come è intuitivamente conosciuta. Inoltre possiamo derivare un altra proprietà che ci tornerà molto utile.
Corollario 1. L’operatore prodotto logico (⋅) gode della proprietà distributiva rispetto all’operatore di somma logica (+). Ovvero che, dati a,b,c ∈ I,
 | (2.9) |
Dimostrazione. La dimostrazione è molto semplice. Basta infatti considerare i due soli casi possibili per a. Se a = 1 allora per la (2.6) il primo membro vale b + c esattamente come il secondo (basta infatti applicare sempre la (2.6) sui due addendi del secondo membro). Se invece a = 0 i due membri si riducono ad un banale 0 = 0. __
Se pensavate che stessi parlando dei dieci comandamenti redatti da Dio in persona grazie alla segreteria di Mosè probabilmente avete saltato qualche pagina. In realtà in questa sezione parleremo di un metodo molto semplice per valutare e ricordare le funzioni booleane. Questo metodo è talmente terra-terra che solitamente, per spiegare la logica booleana, si parte direttamente dalle tavole di verità e si derivano le proprietà algebriche a partire dalle stesse. Forse è proprio questo aspetto metafisico che unisce le tavole di Mosè con quelle di Boole. Nonostante ciò è importante ricordare che le tavole restano una derivazione delle proprietà dell’algebra e non viceversa. Prima di parlare delle tavole è meglio definire meglio cosa si intende per funzione booleana.
Definizione 2. Si definisce funzione booleana a n variabili la funzione f : In → I dove I è l’insieme di definizione booleano I = {0,1}. La funzione è rappresentata come
 | (2.10) |
dove i vari xi prendono il nome di letterali.
Per esempio sono funzioni booleane le funzioni a(b + c) oppure a + b + b, rispettivamente a tre e due variabili. Di seguito presentiamo alcune funzioni notevoli con cui avremo a che fare nei prossimi paragrafi.
A questo punto possiamo definire una tavola di verità.
Definizione 3. Una tavola di verità per una funzione f è una tabella che ha per colonne tutte le variabili della funzione f più una colonna addizionale per f stessa. In ogni riga appare una delle possibili combinazioni di valori per le variabili di f ed il risultato dell’applicazioni di tale combinazione ad f.
Possiamo scrivere quindi le tavole di verità corrispondenti alle funzioni “base” dell’algebra booleana. Tali tavole sono mostrate nelle tabelle 2.1, 2.2 e 2.3.
Ovviamente è però possibile scrivere tavole di verità per ogni funzione booleana esistente o anche solo lontanamente immaginabile. Le tavole di verità sono molto utili anche per effettuare piccole dimostrazioni. Vale infatti il seguente teorema.
Teorema 1. Due funzioni booleane f(x1,...,xn) e g(x1,...,xn) sono logicamente equivalenti se e solo se le loro rispettive tavole di verità sono uguali (salvo riordino delle righe).
Non darò la definizione formale di questo teorema ma è abbastanza chiaro che se le due funzioni reagiscono allo stesso modo per uguali valori di variabili allora le due funzioni sono intercambiabili. Posso, cioè, utilizzare l’una o l’altra indifferentemente perché tanto entrambe restituiscono gli stessi valori.
Tramite questo teorema potete provare a dimostrare il Corollario 1 presentato all’inizio del capitolo. Costruite le tavole di verità per ogni membro dell’equazione e verificate che siano uguali.
Il limite maggiore di questa tecnica è la grandezza delle tavole. Per funzioni con 3-4 variabili le tavole sono uno strumento facile ed immediato ma per funzioni con decine di variabili la costruzione di una tavola diventa un opera biblica. Per una funzione a n variabili, infatti, la tabella conterrà esattamente 2n righe. Troppe.
Per ovviare al problema vedremo nelle prossime sezioni altri metodi di deduzione. Ma prima dobbiamo passare per il regno del “banale”.
Se non è zuppa è pan bagnato. No. Non sono uscito di senno. Semplicemente pensavo che questo fosse il modo più smart per presentare un argomento che in logica ricopre un ruolo importantissimo anche se, nella vita di tutti i giorni, è sinonimo di banalità (o al peggio idiozia). Sto parlando di tautologie e contraddizioni.
Un tatutologia, nel linguaggio comune, rappresenta una figura retorica che consiste nell’aggiunta di contenuto ridondante e dal significato ripetitivo all’interno di un dato discorso al fine di porre maggiore enfasi. Ad esempio frasi tipo “i clienti sono usciti fuori” o “entra dentro” sono celeberrimi casi di tautologia. In logica il concetto non è molto diverso: una tautologia è infatti un predicato logico che è sempre vero per ogni valutazione ovvero che, presa una qualsiasi combinazione di valori per le variabili, la funzione restituisce sempre il valore 1.
Ad esempio possiamo provare che la funzione a + è una tautologia. Ci basta verificare che se a = 0 allora abbiamo che 1 + 0 = 1 mentre se a = 0 abbiamo ancora che 0 + 1 = 1.
Non penso necessiti di dimostrazione il seguente teorema:
Teorema 2. Una funzione f è una tautologia se e solo se l’ultima colonna della tavola di verità associata contiene solamente 1.
La motivazione è ovvia: dato che la tavola di verità ci dice tutti i possibili esiti di una funzione è banale constatare che se tali esiti sono solamente composti da valori 1 è rispettata la definizione di tautologia.
Si contrappone alla tautologia la contraddizione la quale è definita semplicemente come una funzione booleana che assume sempre il valore 0 per ogni sua valutazione. In pratica è come una tautologia, solo che, invece di essere sempre vera, è sempre falsa. Infatti è valida la seguente osservazione:
Ma a cosa servono contraddizioni e tautologie? Quale vantaggio può darci una funzione che non fa altro che darci sempre o solo verità o solo falsità? La prima grande applicazione la si ritrova nel teorema di sostituzione.
Teorema 4 (di sostituzione). Data una funzione f(x1,...,xn) e assumiamo che sia possibile ricavare da f una sotto-funzione g tale che f = h(x1,...,xn,g(x1,...,xn)). allora vale che:
Il teorema, qui esposto in modo volutamente complesso e rigoroso, nasconde un principio molto semplice che chiariremo subito con un esempio. Consideriamo infatti la semplice funzione f = a + ab. Una volta messo in comune il letterale a si riduce a f = a( + b). Ora poiché noi sappiamo che + b è una tautologia possiamo semplicemente rimuovere l’intero pezzo e lasciare al suo posto 1 ottenendo che f = a. In pratica il teorema ci dice che ogni volta che in una funzione booleana individuiamo dei pezzi che sono riconducibili a tautologie e/o contraddizioni possiamo rispettivamente sostituirli con 1 o 0.
Contraddizioni e tautologie sono anche, e soprattutto, utili come strumento deduttivo. Il concetto di tautologia e di contraddizione svolgono un ruolo centrale per quel che riguarda l’equivalenza e l’implicazione logica. Abbiamo già visto il concetto di equivalenza nel teorema 1. In quel caso avevamo sfruttato le tavole di verità per valutare l’equivalenza di due o più funzioni. Adesso vediamo come possiamo sfruttare la tautologia per verificare tale equivalenza.
Definizione 4. Due funzioni booleane f e g sono logicamente equivalenti se e solo se la formula f ↔ g è una tautologia.
Tale equivalenza si indica con f ⇔ g.
L’equivalenza logica, per farla breve, ci dice che le due formule assumono sempre gli stessi volori a parità di variabili. Se per esempio la formula f(a,b) vale 1 solo se a = 0 e b = 1 e sappiamo che è equivalente a g(a,b) allora sappiamo già che g varrà 1 solo con a = 0 e b = 1. Questo ci permette di formulare una versione potenziata del teorema di sostituzione.
Teorema 5 (di sostituzione). Data una funzione f(x1,...,xn) e assumiamo che sia possibile ricavare da f una sotto-funzione g tale che f = h(x1,...,xn,g(x1,...,xn)). allora vale che:
Se g ⇔ p allora f = h(x1,...,xn,p(x1,...,xn))
È facile notare come questo teorema si riconduce alla prima versione che abbiamo dato. Dire che g è una tautologia e che g è logicamente equivalente ad una tautologia è praticamente la stessa cosa. Questo ragionamento giustifica inoltre alcune sostituzioni note come ad esempio le Leggi di De Morgan:
Potete dimostrare, per esercizio, che le formule sopra citate sono logicamente equivalenti.
Definizione 5. Date due funzioni booleane f e g si dice che f implica logicamente g se e solo se la formula f → g è una tautologia.
Tale equivalenza si indica con f ⇒ g.
L’implicazione logica è invece un argomento più delicato. Mentre le equivalenze logiche non fanno altro che generare nuovi modi di dire la stessa cosa, le implicazioni logiche ci dicono qualcosa in più. Ci dice infatti che se f è vera allora sarà vera anche g ma non ci dice nulla su cosa accade quando f è falsa. f e g non sono quindi due oggetti identici ma ci dice una regola che mette in correlazione f con g.
Non approfondirò oltre questo aspetto perché rischierei di essere troppo dispersivo e ci sposteremo in campi troppo lontani dal nostro obiettivo. Siamo partiti per imparare a programmare ed ora siamo pronti per fare il primo grande passo.
Prima di concludere il capitolo voglio mostrarvi il motivo fondamentale per cui vi ho tediato con la logica booleana, ovvero come è possibile utilizzare le operazioni e i teoremi dell’algebra di Boole per eseguire una somma fra due numeri. L’aspetto fondamentale da cui partiamo è che sommiamo solo numeri espressi in base due. Il motivo di questa scelta è ovvio: l’algebra di boole sa manipolare soltanto due elementi, il vero e il falso, lo 0 el’1. La scelta del sistema binario è quindi ovvia.
Per prima cosa, per semplicità, consideriamo di voler sommare solamente numeri a una cifra: in questo caso avremo i seguenti casi.
Notiamo subito che il risultato r equivale proprio alla funzione binaria XOR vista in precedenza mentre il resto c equivale alla funzione binaria AND.
Consideriamo ora la somma di numeri a n cifre e per questo scopo li consideriamo nella forma A = a0a1...an e B = b0b1...bn dove i vari ai e bi sono le singole cifre binarie che compongono i due numeri. In questo caso dobbiamo agire come ci hanno insegnato alle elementari nel fare le tradizionali somme in colonna: sommiamo cifra a cifra e se la somma supera la base aggiungiamo un riporto di 1 nel passo successivo. Ed è proprio il riporto a complicare la situazione in quanto aggiunge una variabile nel calcolo del risultato. Il risultato i-esimo questa volta è una funzione ternaria che dipende dalla cifra ai, bi e dal valore del riporto ci. Il valore del riporto che ci porteremo alla prossima cifra è anch’esso una funzione ternaria. Abbiamo quindi i casi elencati nella seguente tabella:
| ai | bi | ci | ri | ci+1 |
| 0 | 0 | 0 | 0 | 0 |
| 0 | 0 | 1 | 1 | 0 |
| 0 | 1 | 0 | 1 | 0 |
| 0 | 1 | 1 | 0 | 1 |
| 1 | 0 | 0 | 1 | 0 |
| 1 | 0 | 1 | 0 | 1 |
| 1 | 1 | 0 | 0 | 1 |
| 1 | 1 | 1 | 1 | 1 |
I dati della tabella sono facilmente verificabili. A partire da questa tabella possiamo ricavare la funzione ri e la funzione per ricavare il riporto ci+1. La funzione r assume il valore 1 solamente quando c’è un numero dispari di 1. Usiamo quindi la seguente funzione:
 | (2.11) |
La funzione XOR è infatti anche chiamata funzione di disparità in quanto da come risultato 1 solo se c’è un numero dispari di 1. Per il riporto, invece, possiamo generare questa funzione:
 | (2.12) |
Notate che nella formula è incluso anche il caso in cui tutte e tre le variabili hanno valore 1. A questo punto è ovvio che per sommare un numero binario non ci basta che affiancare n sommatori di questo tipo. Questo è esattamente il meccanismo che utilizza il vostro pc per sommare due numeri. Le funzioni r e c sono direttamente costruite tramite circuiti elettronici nella zona della CPU che si occupa dei calcoli matematici.
TODO
La gran parte dell’informatica si riduce alla progettazione e analisi di algoritmi. È quindi ovvio che in questo testo gran parte dei miei sforzi si concentrino nel piantarvi in testa più nozioni possibili riguardo gli algoritmi.
Innanzitutto definire un algoritmo è un compito piuttosto banale: un algoritmo non è altro che una sequenza finita e ordinata di istruzioni che servono a raggiungere un dato obbiettivo. Questa definizione si allarga quindi a molte cose, anche a situazioni e azioni che compiamo quotidianamente nella vita di tutti i giorni. Fare la spesa, svegliarsi, lavarsi i denti, sono tutte cose che eseguiamo seguendo alla lettera un dato “algoritmo naturale”, ognuno a proprio modo e seguendo le proprie istruzioni, ma sicuramente seguendo dei “‘comandi” ben precisi e in sequenza. Sfido infatti chiunque ad eseguire una sola delle azioni sopraelencate eseguendo a caso ogni tipo di movimento possibile. Tale sequenza di azioni è sempre ordinata e finita. Senza queste due condizioni non avremmo infatti nessuna garanzia di raggiungere l’obbiettivo prefisso ne di raggiungere mai qualcosa. Ad esempio, nel caso di lavarsi i denti, non è conveniente spazzolarsi i denti e mettere il dentifricio poi, come non è intelligente ripetere infinite volte il gesto di prendere lo spazzolino.
Tutte le applicazioni esistenti utilizzano algoritmi dalle complessità più disparate, basti pensare che tutto quello che un pc è in grado di fare, da internet ai videogame, è eseguito utilizzando una ventina di azioni diverse. Un niente se paragonate alle cose che un pc riesce a fare. Se volete, infatti, potete vedere un algoritmo come un mezzo per eseguire azioni complesse unendo in una data sequenza due o più azioni atomiche o di base allo stesso modo di come solo 4 nucleotidi del DNA danno vita alla sterminata varietà delle specie viventi.
Il vero problema dell’algoritmica è però la sua modellizzazione e rappresentazione astratta. Essendo oggetti di natura così varia, che spazia dai comportamenti umani fino ai programmi per pc, è difficile formulare teoremi e regole che abbiano valenza generale e, soprattutto, dimostrare la validità di tali congetture. Come posso infatti stabilire una proprietà che valga per ogni possibile algoritmo? E non solo algoritmi che facciano qualunque cosa ma anche scritti in qualunque modo, ovvero utilizzando un qualunque insieme di comandi base.
A questo scopo presenterò molto brevemente due dei metodi di rappresentazione astratta più importanti. Una trattazione formale e precisa di queste rappresentazioni occuperebbe infatti un intero libro e necessiterebbe di un bagaglio matematico troppo vasto. Mi limiterò quindi a trattare solo i principi di funzionamento e alcune conseguenze teoriche interessanti. Solo in seguito passeremo a vedere quale rappresentazione di algoritmo si avvicina di più a quella di un vero PC.
Prima di fare questo è però importante evidenziare quali parti imprescindibili devono avere queste rappresentazioni astratte o macchine virtuali per poter rappresentare un algoritmo. La prima cosa è appunto il set di azioni base. Tale insieme continene sempre un numero limitato di azioni. Una macchina è tanto più astratta quanto più si poggia su un insieme piccolo di azioni base.
Altrettanto importante è una memoria. Ovvero un qualcosa sulla quale questa macchina virtuale può leggere e scrivere informazioni. In realtà possiamo anche pensare a macchine sprovviste di questa capacità ma queste riuscirebbero a rappresentare solo una classe molto semplice di algoritmi e, quindi, per semplicità consideremo la memoria come parte fondamentale di una macchina astratta.
La macchina di Turing (o MdT) è forse l’esempio più importante e trattato di macchina virtuale. Tale macchina fu teorizzata nel 1936 da Alan Turing come risposta al problema di decisione di Hilbert1ma nemmeno lo stesso Turing aveva pienamente compreso la portata della sua formulazione. Essa è infatti il primo esempio di “computer” sebbene in forma prettamente teorica.
Il meccanismo su cui si basa una macchina di Turing è piuttosto semplice anche se, in principio, neccessita di un piccolo sforzo di immagginazione. Immaginate infatti una macchina in grado i leggere e scrivere su un nastro infinito che potete immaginare come una lunga lista di caselle vuote. Le uniche operazioni che questa macchina è in grado di fare sono:
La macchina non può fare nient’altro. Essa è inoltre una macchina a stati. Senza entrare nel dettaglio delle macchine a stati vi basti sapere che potete considerare una macchina a stati come una macchina che è in grado di ricordare un numero (lo stato in cui si trova) e, a seconda del numero che la macchina ha in memoriaa essa risponderà in modo diverso agli input (ad esempio eseguendo un azione e/o cambiando stato). Per farci un idea concreta potizziamo una semplice macchina a stati in grado di riconoscere se le vengono date in ingresso tre 1 di seguito. Essa sarà semplicemente una macchina con quattro stati:
Ogni numero in ingresso non farà altro che far cambiare stato alla macchina oppure lasciarlo inalterato (è molto istruttivo provare a pensare come cambiano gli stati a seconda dell’ingresso).
Torniamo però alla nostra macchina di Turing. Supponiamo di voler rappresentare con questa macchina un algoritmo che inserisca due b dopo ogni c di una qualunque parola. Consideriamo come ingresso o dati di un algoritmo tutto ciò che è presente sul nastro prima che l’algoritmo cominci. Ipotizziamo di avere come dati la parola aceto (useremo il carattere _ per indicare una cella vuota), lo stato iniziale sul nastro sarà il seguente:
 | (3.1) |
Consideriamo come stato iniziale della macchina la sua posizione sulla prima lettera. A questo punto possiamo elaborare il seguente algoritmo:
A questo punto starete già inorridendo. A prima vista sembra che io abbia violato la regola fondamentale che mi ero prefisso: si possono utilizzare solo le istruzioni del set di azioni atomiche. Le azioni 3,4 e 5 non appartengono a tale insieme. È facile però notare come queste azioni “composte” possano essere riscritte utilizzando il set base: la (5) diventa facilmente la ripetizione di “muoversi a destra” per due volte oppure la (4) possa essere composta da:
Questa volta interamente composta da istruzioni atomiche2.
La macchina di Turing sembra un’astrazione terribilmente limitata. Non riusciamo facilmente a pensare a programmi ed algoritmi che vadano oltre la semplice manipolazione di stringhe. E per un certo verso è giusto che sia così: scrivere formalmente una macchina di turing che esegua algoritmi complessi, come ad esempio approssimazioni di integrali di funzioni, richiederebbe un numero di stati talmente alto che sfuggirebbero anche al più intelligente degli esseri umani.
Tuttavia il fatto che una cosa sia di difficile realizzazione non significa che non sia possibile. Anni di studio hanno infatti dimostrato come tutte le cose che sono effettivamente calcolabili sono rappresentabili da una macchina di Turing. Anzi, le cose sono così strettamente collegate che si dice che una cosa è calcolabile se e solo se esiste una macchina di Turing in grado di calcolarla. Addirittura è possibilr creare una meta-macchina in grado di eseguire altre macchine, ovvero, la possibilità di creare una macchina M che, presa in ingresso la codifica di una macchina N, esegua il compito (algoritmo) di N come se fosse N in modo del tutto indipendente.
Questa cosa non deve sconvolgere perché una tale macchina ce l’abbiamo davanti gli occhi tutti i giorni: il PC. Se ci pensate bene essa non è altro che una macchina che prende degli algoritmi codificati in binario e li esegue. E’ appunto una meta-macchina.
Questo ha spinto alla formulazione della congettura di Church-Turing la quale afferma che non esiste una macchina più potente di una macchina di Turing. Notate che la parola potenza, in questo caso, indica la quantità di compiti eseguibili e non la velocità con cui questi compiti vengono svolti. Tale congettura è ovviamente indimostrabile: per dimostrarla bisognerebbe infatti trovare tutti i problemi irrisolvibili da una macchina di Turing e dimostrare che è impossibile risolverli utilizzando una qualunque altra macchina astratta. Un compito evidentemente improbabile.
Un’altra conseguenza di questa idea riguarda proprio noi. Se la congettura di Church-Turing è vera (come sembra) significa che anche il nostro cervello è potente tanto quanto una macchina di Turing perché altrimenti noi riusciremmo a risolvere problemi che una tale macchina non potrebbe risolvere. Ma in questo caso allora nulla vieta ad una macchina di Turing di “emulare” un cervello umano.
Lasciamoci però queste considerazioni affascinanti alle spalle e torniamo nel nostro mondo astratto. A noi basta sapere che tutto ciò che può essere fatto può essere fatto con una macchina di Turing. A questo punto però sorge spontaneo chiedersi come mai il nostro pc non è dotato di un nastro infinito…
Il modello che presentiamo in questa sezione è radicalmente differente da una macchina di Turing. Tuttavia tale modello è turing-completo, vale a dire che è equipotente ad una MdT: se una cosa può essere calcolata con una macchina a registri allora può sicuramente essere sicuramente calcolata da una MdT e viceversa.
La particolrità che però desta tanto interesse nelle macchine a registri consiste nel fatto che esse sono il modello di calcolo che più si avvicina ai moderni PC. Nelle macchine a registri il nastro è sostituito da una serie di registri. Tali registri sono infiniti, possono contenere solo numeri interi e sono indicati con un numero come R1 per il primo registro, R2 per il secondo e, in generale, Ri per l’i-esimo registro. Inoltre consideriamo due registri speciali: il registro TEMP in cui viene momentaneamente memorizzato il valore letto e/o elaborato, e il registo COUNT che tiene conto della prossima istruzione da eseguire. Il set di istruzioni atomiche consiste in:
La codifica di un programma secondo questo modello è molto vicina alla scrittura di codice assembly e, quindi, è del tutto simile a quello che viene intimamente fatto nei PC moderni. Tuttavia è possibile dimostrare che esiste un modello a registri ancora più semplice: la macchina a registri elementare.
Questa macchina ha solo tre istruzioni e nessun registro TEMP:
Credete che sia troppo poco? Allora potete provare a cercare sul web il linguaggio Brainfuck il quale non è altro che un linguaggio che contiene solamente le istruzzioni di una macchina a registri elementare. Potete trovare facilemente molti incomprensibili esempi.
Come vedremo in seguito, però, i moderni processori (che, ricordiamolo, sono macchine a registri) implementano un set di istruzioni relativamente alto per facilizzare e ottimizzare la scrittura del codice (scritto quasi esclusivamente dai compilatori). Possono infatti implementare l’istruzione per moltiplicare e dividere ma anche per eseguire logaritmi. Oppure avere istruzioni di salto più o meno complesse.