La matematica e l'informatica

Spesso l'informatica viene descritta come una disciplina derivata dalla matematica. Ciò è sicuramente vero nel caso della parte più teorica dell'informatica, mentre un corso di informatica della scuola secondaria di primo o secondo grado non richiede particolari conoscenze matematiche se non quelle che ogni alunno dovrebbe già avere al suo livello.

Questa lezione tratterà in modo semplice ed adatto alla scuola secondaria concetti matematici alla base dell'informatica quali:

• La Macchina di Turing
• Il sistema binario
• I bit, i byte e le operazioni matematiche con essi
• Matematiche finite, virgola fissa e mobile

L'obiettivo di questa lezione è di fornire una base teorica semplice spendibile, eventualmente, in un futuro universitario e utile per comprendere le basi del computer e le differenze tra la matematica classica e quella adoperata dai computer.

Macchina di Turing

La Macchina di Turing rappresenta un modello teorico, dunque non esistente nella realtà, di una macchina che si muove su un nastro infinito e in base a ciò che legge su di esso fa delle azioni, che si limitano allo spostarsi sul nastro e allo scrivere su un nuovo simbolo.

Funzionamento

La Macchina di Turing funziona a stati, definiti da chi la programma: a seconda di quale stato la macchina si trova potrà compiere delle azioni definite dal programmatore.

Capacità della Macchina di Turing

Nonostante sia un modello molto semplice la Macchina di Turing è in grado di risolvere qualsiasi problema risolvibile da un computer.

Attenzione: non tutti i problemi sono risolvibili da un computer. Ad esempio è impossibile sapere se un algoritmo, ossia una serie ordinata di passi (ad esempio un programma) termina o no con un dato input.

Se tuttavia un problema può essere risolto da un computer può essere risolto da una Macchina di Turing e viceversa: Si parla dunque di Turing equivalenza per parlare di quei computer o software in grado di comportarsi come macchine di Turing.

Un esempio di software involontariamente Turing equivalente è il celebre gioco Campo Minato: Alcuni matematici hanno dimostrato che se opportunamente utilizzato può essere usato come una Macchina di Turing.

Approfondimento: Gli automi a stati finiti (superiori)

Più correttamente ogni macchina di Turing è un automa a stati finiti.

Un automa a stati finiti è un sistema, reale o teorizzato, che si basa sull'avere degli stati, definiti e in numero finito, nei quali l'automa si può trovare.

Un esempio è un tornello che si attiva a gettone, come accade in alcune linee metropolitane: Il tornello può essere aperto o chiuso, il suo stato iniziale sarà chiuso, all'inserimento del gettone diverrà aperto e quando passa l'utente torna chiuso.

Definizione (superiori)

Ogni Macchina di Turing è definita da una tabella di stati possibili e da una lista di istruzioni fatte da quintuple, ossia cinque istruzioni costituite da:

Stato attuale, simbolo sul nastro -> nuovo stato, nuovo simbolo sul nastro: spostamento sul nastro

Ad esempio:

A, 0 -> B, 1, R

Ogni volta che la macchina incontrerà nello stato A uno zero passerà allo stato B, cambierà lo 0 con 1 e andrà a destra.

Sistema binario

La stragrande maggioranza dei computer, oggi praticamente tutti, funzionano grazie all'elettricità. Il sistema più semplice per misurare un qualcosa in elettronica è dire se c'è o non c'è, ossia un sistema con due possibili cifre, per convenzione 0 e 1.

Esattamente come l'uomo, che ha dieci dita, ha scelto un sistema con dieci cifre, da 0 a 9, l'informatica ha scelto un sistema binario, con solo 0 e 1 come cifre.

Bit, byte e operazioni con essi

L'unità base di memoria informatica è il bit, che rappresenta una singola cifra binaria, ossia o 0 o 1. Otto bit costituiscono un byte, capace di rappresentare qualunque numero tra 0 e 255.

Le operazioni semplici tra numeri binari si basano sulle medesime regole di quelle con i numeri decimali. Vediamo alcuni esempi:

Addizione

L'addizione si effettua semplicemente facendo la somma bit a bit e considerando eventuali riporti. Ad esempio:

0010 0011 +
0010 1001 =
___________
0100 1100

Il problema della sottrazione

In linea di massima la sottrazione binaria segue le stesse regole di quella decimale, tuttavia realizzare un sistema elettronico capace di fare la sottrazione richiede molte risorse. Per questo in informatica è molto più diffuso il sistema del complemento a due.

Un'operazione del tipo: $5-3$

Può essere resa anche come: $5+(-3)$

Dal punto di vista decimale poco cambia e l'operazione da fare resta sempre la medesima, mentre in binario permette di fare ogni sottrazione come un'addizione.

Per fare un paragone è come se mettere il segno - a un numero permettesse di lavorarci sopra con l'addizione ottenendo però il numero sottratto.

Pratica del complemento a due (superiori)

Per avere il complemento a due di un numero in binario lo si deve negare bit a bit (ogni zero diventa uno e ogni uno diventa zero) per poi sommarvici uno.

Ad esempio se 4 è 0100 -4 si otterrà con:

0100 (4)
1011+
0001=
______
1100 (-4)

Matematiche finite, virgola fissa e mobile

Il computer: una macchina limitata?

Tendiamo a pensare al computer come ad una macchina con una memoria enorme, ed è vero: tuttavia non è infinita. Proprio per questa ragione la matematica di un computer è una matematica finita.

Quanti numeri ci sono

Ovviamente, nella matematica classica, infiniti. Infatti dato un qualsiasi numero $n$ basta fare $n+1$ per ottenere un numero più elevato. Ma dato che un computer ha memoria limitata a un certo punto i suoi numeri devono fermarsi.

Essendo i computer macchine binarie questo limite è espresso tipicamente in potenze di due: Nei primi computer erano anche numeri bassi, di quattro o otto cifre binarie, mentre i primi computer domestici offrivano 16 bit, per un numero massimo di 65536. Oggi è possibile rappresentare numeri, con particolari tecniche, fino a $1.2\cdot 10^{4932}$.

N = N+1 termina? (superiori)

Parlavamo, nella sezione dedicata alla Macchina di Turing, di problemi che non terminano mai: un esempio è il sovracitato $n=n+1$: in un ipotetico computer con memoria infinita il computer continuerebbe a stampare numeri in eterno, mentre nei computer al raggiungimento di un limite predeterminato possono accadere varie cose, la più nota è l'overflow.

Se ad esempio ho un byte (8 bit) $1111\ 1111$ e provo a sommare $1$ otterrò $1\ 0000\ 0000$, che tuttavia non si può rappresentare in otto bit e quindi verrà reso come $0000\ 0000$, ossia zero.

Ogni software comunque tratta un eventuale superamento alla sua maniera: ad esempio il ben noto videogioco Minecraft permette un'altezza massima di viaggio (non di costruzione!) di $2^{1024}$, un numero di 308 cifre. Quando questo numero viene superato il gioco crasha, perché considera l'altezza infinita.

Quanti numeri ci sono tra ogni numero?

Tra $1$ e $2$ quanti numeri ci sono? Probabilmente un bambino delle elementari, che conosce solo l'insieme $\mathbb {N}$, direbbe nessuno, mentre chi conosce i numeri razionali ($\mathbb {Q}$) o reali ($\mathbb {R}$) risponderà infiniti.

In un computer dipende dalla definizione della virgola, che descriveremo dopo. In una matematica finita dev'essere il progettista a definire la sua definizione. Ad esempio in matematica tra $1,2$ e $1,3$ ci sono infiniti numeri, se parliamo di Euro, invece, ce ne sono solo 10.

Sta dunque al programmatore decidere come impiegare i numeri per decidere quanti numeri ci sono tra due dati numeri.

La virgola

In linea di massima un computer non è in grado di mettere il punto in un insieme binario, un po' come se $500.13$ e $50013$ fossero visti come la stessa cosa. Il programmatore, poi, sa com'è formato il numero e con esso lavora.

In questo caso si parla di virgola fissa, ma c'è un piccolo problema: la virgola fissa è a definizione fissa. Ciò va bene se, come si esponeva prima, si parla di soldi, ma ci sono ambiti dove ciò funziona poco.

Pensiamo di avere un numero in metri definito fino ai centimetri. Se misuriamo una formica probabilmente il nostro numero sarà $0.01$, se misuriamo un umano sarà $1.75$. Fin qui tutto ok, no?

Misuriamo la distanza tra Terra e Sole, la cosiddetta unità astronomica. Ebbene, sono $149597828677.28$ metri. Se dunque sviluppassimo un programma (potrebbe, ad esempio, essere una libreria di conversione che lavora sia con numeri enormi sia con numeri piccolissimi) che deve trattare entrambi ci servirebbero di default 13 cifre, anche se poi rappresentiamo la lunghezza della formica, ossia $00000000000.01$.

Ovviamente si tratta di uno spreco non da poco, che ogni programmatore vorrebbe evitare. Come?

Virgola mobile (superiori)

Grazie alla virgola mobile. In effetti, quel $149597828677.28$ si può rappresentare in notazione scientifica come $1.49\cdot 10^{11}$, mentre la lunghezza della formica è $1\cdot 10^{-}2$ e l'altezza umana $1.75\cdot 10^{1}$.

Per quanto questi siano numeri enormemente diversi la rappresentazione è abbastanza standardizzata: poche cifre di base, poche cifre di esponente.

Se questo meccanismo viene tradotto in binario e adattato ai computer diviene la virgola mobile, che permette, a seconda della rappresentazione, di rappresentare numeri enormi con scalabilità differente. Diventa dunque possibile rappresentare con lo stesso spazio in memoria e senza sprechi la grandezza che separa due atomi e quella che separa due galassie.