Brevi note introduttive

Rappresentazione dei dati elementari.

Queste note descrivono i concetti elementari per la rappresentazione dei dati su di un calcolatore, al fine di illustrare come le sequenze di bit possano codificare numeri interi, caratteri, stringhe e numeri reali a precisione finita.
Bit:
Segnala la presenta (bit=1) o l'assenza (bit=0) di un segnale o di un evento con due possibilità equiprobabili (secondo la teoria dell'informazione di Shannon). Indicato anche come unità di misura minima dell'informazione (al pari di altre unità come metro e litro). Per esempio:
Interi:
Supponendo di avere k bit a disposizione, si possono rappresentare i numeri da 0 a 2k-1. Per esempio, con k=3 si ottengono:
N.
d2d1d0 = rappresentazione binaria
0
000
1
001
2
010
3
011
4
100
5
101
6
110
7
111
La regola per trasformare il binario in un numero è semplice ; basta moltiplicare ciascuno dei bit per potenze crescenti del 2, a partire dal bit più a destra (bit meno significativo):
numero = somma per i= 0, ..., k-1 di di*2i.
Continuando nell'esempio, prendiamo d2d1d0 = 011, ottenendo che 3 = 0*22 + 1*21 + 1*20 = 0 + 2 + 1. La regola inversa non viene data qui, rimandando il lettore al corso di architettura dei calcolatori. Per rappresentare gli interi negativi si usa il bit più a sinistra (bit più significativo). Rimandiamo anche tale discussione al corso di architettura.
Caratteri e stringhe:
Sono codificati come numeri su 8 bit (ASCII) oppure 16 bit (Unicode). La codifica rispetta l'ordine alfabetico, quindi la lettera 'A' viene codificata con un intero più piccolo della lettera 'Z'. Attenzione: la lettera '7' non è la stessa cosa del numero 7. Le stringhe sono sequenze di caratteri alfanumerici che vengono perciò rappresentati come sequenze di numeri.
Numeri reali:
Sono codificati con un numero limitato di bit (precisione finita di 32 o 64 bit nello standard IEEE754). Il primo bit è utilizzato per il segno; un certo numero dei bit successivi codifica l'esponente, mentre il resto dei bit serve per la mantissa. Per esempio, la codifica di -0.275 * 218 è ottenuta codificando il segno meno, l'esponente 18, e quindi la mantissa 0.275 (ciascuno con il numero assegnato di bit).

Modello di calcolo RAM

Queste note descrivono un modello astratto di calcolo con cui misurare la complessità degli algoritmi. Il modello RAM (Random Access Machine, cioè macchina ad accesso casuale o diretto) consiste in un processore di calcolo a cui viene associata una memoria di dimensione illimitata, in grado di contenere sia i dati che il programma da eseguire (detto anche modello di von Neumann, uno dei pionieri dell'informatica). Il processore dispone di una unità di elaborazione e di un numero sufficiente di registri, sia per tenere traccia dello stato di esecuzione del programma (per es., il registro per indicare la prossima istruzione) e sia per eseguire le istruzioni elementari (presenti nei moderni calcolatori): Le istruzioni di un linguaggio ad alto livello come C, Java e Pascal possono essere tradotte in una serie di tali operazioni elementari. Per esempio, il frammento di codice 
if (a <= b) {
    a = VECT[ b ];
} else {
    b = b+a;
}
...
può essere visto equivalentemente come la sequenza di operazioni elementari descritta sotto, assumendo che i registri R1 e R2 siano associati rispettivamente alle variabili a e b, e che la prima cella dell'array sia all'indirizzo VECT: 
1. Confronta R1 con R2.
2. Se R1 > R2 salta al passo 5.
3. Carica in R1 il contenuto della cella all'indirizzo VECT+R2.
4. Salta al passo 6.
5. Somma R1 e R2 ponendo il risultato in R2.
6. ...
Per una trattazione completa, si rimanda il lettore ai corsi di linguaggi formali e compilatori.

È possibile assegnare un costo uniforme alle operazioni elementari. In generale, ciascuna delle operazioni elementari richiede un tempo fisso e costante di esecuzione, assumendo che ogni registro e ogni cella di memoria non richieda un numero esagerato di bit (in altre parole, assumendo che tale numero cresca all'incirca con il logaritmo del numero totale di celle occupate).

Costo di alcuni costrutti in pseudocodice [CLR]

Viene dato uno schema conciso per inferire la complessità temporale di alcuni costrutti impiegati nel libro di testo [CLR]. Come ogni buona regola, vi sono le dovute eccezioni che saranno illustrate a lezione di volta in volta.

Roberto Grossi, Ottobre 2003.