Fondamenti di informatica

Prima parte teoria informatica - tipi di variabili e costanti

Tipi

Il linguaggio C rappresenta i dati attraverso i tipi.

Tipi elementari del C:

• Int: numeri interi con segno.
• Unsigned int: numeri interi senza segno.
• Float: numeri razionali in virgola mobile.
• Double: numeri razionali in virgola mobile con precisione doppia rispetto al float.
• Char: caratteri.
• Void: tipo nullo, usato quando la sintassi del linguaggio richiede di specificare un tipo di dato ma la semantica non lo prevede.

In C non esistono valori booleani, questi sono sostituiti da numeri interi con la seguente convenzione:

• 0 codifica il valore booleano FALSE.
• Qualsiasi altro intero con valore diverso da zero, tipicamente 1, codifica il valore booleano TRUE.

Variabili

Variabile = locazione di memoria che contiene un valore di un tipo.

• Il valore può variare, il TIPO è invariante.
• Si può associare un nome, formato da una sequenza di caratteri alfanumerici, ad una variabile.
• Il primo carattere non può essere numerico, ma solo alfabetico.

Il nome viene associato alla variabile tramite una DICHIARAZIONE, es. float media;.

Per associare un valore ad una variabile si ricorre ad un’ASSEGNAZIONE, es. media = 25.5;.

Variabile array = insieme di variabili dello stesso tipo che possono essere referenziate tramite un nome collettivo e un indice che le identifica.

Esempio: dichiara una variabile di nome V costituita da 10 variabili int.

int V[10];

Le singole locazioni sono referenziate attraverso un indice entro parentesi quadre:

V[0] è il riferimento alla PRIMA variabile dell’array.

V[9] è il riferimento dell’ULTIMA variabile dell’array.

Costanti

Costante = valore di un certo tipo che non cambia durante la computazione.

• Le costanti non possono essere modificate all’interno del programma.
• Le costanti sono rappresentate in maniera diversa a seconda del tipo.

Es: int = 10, float = 43.25.

const definisce una variabile di sola lettura che non può essere modificata all’interno del programma.

#define è una direttiva a livello di pre-processore: prima di eseguire la compilazione, il compilatore sostituisce tutte le istanze delle costanti con il loro valore. Viene così definito un identificatore tramite cui in modo che la costante sia utilizzabile da tutto il codice del programma, con #define non deve essere seguita dal “;”.

Operatori ed espressioni

Espressione = combinazione di variabili e costanti attraverso operatori.

Operatori: si possono distinguere in:

• Aritmetici: somma (+), sottrazione (-), prodotto (*), modulo (%). Il modulo restituisce il resto della divisione intera.
• Relazionali: minore (<), minore o uguale (<=), uguale (==), diverso (!=).
• Logici: congiunzione and (&&), disgiunzione or (||), negazione (!).
• Incremento e decremento: ++, --.
• Assegnamento: =.

Istruzioni

Istruzione = determina la sequenza delle espressioni da eseguire e quindi il flusso di lavoro del programma.

L’ESECUZIONE di un’istruzione consiste nel calcolare l’espressione, producendone i side-effects, e poi procedere all’istruzione successiva.

Sequenza di istruzioni:

int a,b;

b=5;

a=b+10

Istruzione Compound: consiste nell’esecuzione dell’istruzione che sta dentro le parentesi graffe, permette di raccogliere le istruzioni in blocchi in modo che siano trattati in maniera unitaria.

{int a, b;

b=5;

a=b+10;}

Istruzioni Condizionali: permettono di decidere direzioni diverse nel flusso di esecuzione, in base al valore restituito da un’espressione di controllo, guardia.

• IF: si può avere con o senza compound.
• IF ELSE: ha due corpi di istruzione alternativi, eseguiti a seconda del valore restituito dall’espressione di guardia, true o false.

Istruzioni di iterazione: permettono di rieseguire in maniera ripetitiva un corpo di istruzioni fino al verificarsi di una certa condizione sulle variabili del programma. Le istruzioni sono 3: FOR, WHILE, DO-WHILE.

• FOR: un corpo di istruzioni è eseguito ripetitivamente sotto il controllo di una guardia costituita da tre espressioni, inizializzazione (1), guardia (2) e incremento (3). NON ha l’istruzione COMPOUND. Il corpo del ciclo for per costruzione potrebbe non essere eseguito se già alla prima verifica della guardia risulta FALSE.
• WHILE: un corpo di istruzioni è eseguito ripetitivamente fino a che un’espressione di guardia restituisce un valore vero. Ha l’istruzione COMPOUND, anche in questo caso notiamo che il corpo del ciclo potrebbe non essere mai eseguito se già alla 1° verifica della guardia risulta FALSE.
• DO WHILE: esecuzione simile al ciclo while, ma con la condizione di guardia è posta in coda al corpo delle istruzioni. Anche questo ciclo ha l’istruzione COMPOUND, quindi differisce dal ciclo While solo per la posizione della guardia.

Rappresentazione dei dati

Numero = concetto caratterizzato da un suo significato intrinseco, che può essere descritto tramite rappresentazioni differenti, che dipendono dalla combinazione di più convenzioni:

• Posizionalità della codifica: un numero rappresentato con una codifica posizionale è un numero nel quale il peso di ciascuna cifra dipende dalla posizione che quella cifra occupa nella rappresentazione del numero.
• Base di rappresentazione.
• Numero di cifre che si hanno a disposizione per la rappresentazione.
• Codifica del segno.
• Rappresentazione di parti frazionarie e valori razionali.

Codifica posizionale: la codifica di un insieme di numeri, ad es. i numeri naturali, avviene attraverso una base finita di N cifre, nella codifica decimale le cifre da 0 a 9, che serve a rappresentare anche tutti gli altri numeri, combinando più cifre sulla base di una notazione posizionale, il peso delle cifre dipende dalla loro posizione.

[ … ] ∷= ∑ 1 0 =0 = MSD, most significant digit = LSD, least significant digit. 0 = base.

Rappresentazione binaria: il calcolatore utilizza la codifica in base 2, la quale è la minima base che include due cifre diverse, 0 e 1, e che quindi può rappresentare i numeri in maniera posizionale, semplificando inoltre l’implementazione di algoritmi da parte dell’unità aritmetico logica del processore.

Algoritmo di conversione della base di rappresentazione di un numero:

1. Ottenere la rappresentazione polinomiale del numero della base di partenza.
2. Effettuare la conversione di coefficienti e potenze nella base di arrivo.
3. Eseguire somme e prodotti nella base di arrivo.

6 3 1 0

Conversione da base 2 a base 10: [1001011] = [1·2⁶ + 1·2³ + 1·2¹ + 1·2⁰] = [75].

2 2 10

Conversione da base 10 a base 2:

Algoritmo dei resti successivi. Il procedimento termina quando il quoziente della divisione è 0.

6 5 4 3 2 0

Esempio: [125] = [1111101] per verificare → = [2⁶ + 2⁵ + 2⁴ + 2³ + 2² + 2⁰] = [64+32+16+8+4+1] = [125].

10 2 10 10 10

L’algoritmo termina quando il quoziente della divisione intera è = 0.

Base esadecimale

16 cifre: 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, A, B, C, D, E, F.

→ Per convertire da base 2 a base 16, si formano i gruppi di 4 bit del numero in base 2, dopodiché si convertono i numeri rappresentati da ognuno dei gruppi.

[125] = [1111101] = [0111 1101] = [7 D].

10 2 2 16

→ Per convertire da base 16 a base 2, si converte ogni cifra in base esadecimale nella rappresentazione a 4 bit in base 2.

[F F A 3] = [1111 1111 1010 0011].

16 2

Parte frazionaria

Parte frazionaria = numero razionale minore dell’unità.

Anche per convertire la parte frazionaria si possono eseguire i 2 diversi approcci, utilizzando cioè la base di partenza o di arrivo.

1) Base di ARRIVO, da base 10 a base 2.

Se si ha una rappresentazione finita in base 10 non è detto che convertendola in base 2 venga nuovamente una rappresentazione finita.

[0.7] = [7/10] = [0111/1010] = [0.10110].

10 10 2 2

2) Base di PARTENZA.

Algoritmo:

• Moltiplicare per 2 la parte frazionaria.
• Sottrarre dal risultato ottenuto la sua parte intera.
• La sequenza delle parti intere sottratte fornisce la rappresentazione voluta.

[0.7] = [0.10110].

10 2

Interi senza segno

Unsigned int a; −1 { } viene rappresentato su N bit di memoria che codificano il valore in forma posizionale in base 2.

=0−1 = ∑ · 2 =0 N

Rappresentazione di tutti e soli i numeri naturali tra [0, … 2^N -1] compresi.

N varia a seconda dell’architettura del processore, tipicamente 32 o 64 bit.

Per N = 32 bit si possono rappresentare gli interi compresi tra 0 e 2³² -1.

Caratteri

Char c;

Codifica posizionale in base 2 su 8 bit, con i quali è possibile rappresentare i numeri interi senza segno da 0 a 255.

La corrispondenza tra i caratteri e i numeri naturali compresi tra 0 e 255 è definita dalla Tabella dei Caratteri ASCII.

Numeri interi con segno

Int a;

Vengono rappresentati su N bit tramite la rappresentazione “Complemento a 2”, simile allo sviluppo polinomiale, in cui però il Most Significant Bit ha peso negativo.

N-1 N-1

Codifica di tutti e soli i numeri interi con segno compresi nell’intervallo [-2, … 2 -1 …],

N-1 N-1

in cui -2, minimo numero rappresentabile, e 2 -1, maggior numero rappresentabile, sono rappresentati → N-1 come:

-2 [100..00] 2C. È negativo, quindi il suo bit più significativo è = 1 e gli altri sono = 0.

→ N-1. 2 -1 [011..11] 2C. È positivo, quindi il suo bit più significativo è = 0 e gli altri sono = 1.

Un numero è negativo se e solo se a = 1, cioè se il bit più significativo è = 1.

N-1

Il suo OPPOSTO si determina determinando il suo complemento a 2, ovvero complementando i bit uno ad uno e sommando 1 al risultato.

Inoltre aggiungendo un 1 al MASSIMO numero rappresentabile si ottiene il MINIMO numero rappresentabile.

Overflow

Overflow: l’operazione di somma può dare origine a una condizione OVERFLOW, che si verifica quando il risultato dell’operazione eccede la dinamica dei valori rappresentabili.

• Interi senza segno: si verifica overflow se e solo se è presente un bit di riporto nella somma dei MSB.
• Interi con segno: si verifica overflow se e solo se i due addendi sono concordi ma il segno del risultato è opposto a quello dei due addendi.

ESEMPIO di overflow con somma di interi senza segno rappresentati su 6 bit:

Con 6 bit si possono rappresentare gli interi senza segno nell’intervallo [0, 2⁶-1] = [0,63].

1 1 1 1 1 1 + [63] + [1] = [111111] + [000001] Є [0,31]

10 10 2 10

. 0 0 0 0 0 1 = Riporto 1 0 0 0 0 0 0 nel MSB.

6-1 6-1

Con 6 bit si possono rappresentare gli interi con segno compresi tra [-2, 2 -1] = [-32,31].

0 1 1 1 1 1 + [31] + [1] = [011111] + [000001] Є [-32,31]

10 10 2C 2C

. 0 0 0 0 0 1 = Il risultato della somma 1 0 0 0 0 0 0 ha segno opposto ai due operatori concordi.

Sottrazione in complemento a 2

Sottrazione in complemento a 2: ci sono 3 casi.

1. Minuendo minore del sottraendo: il risultato è negativo, si considera l’eventuale riporto sul MSB. Non si ha overflow se il riporto su MSB è 0. Il modulo del risultato è il complemento a 2, cioè l’opposto, del risultato.

a = [40] = [00101000]

10 2C

b = [12] = [00001100]

10 2C

→ fare a – b = a + (- b), la sottrazione è uguale a fare la somma dell’opposto del sottraendo.

Calcolo di a + (-b):

Calcolo di -b:

. 0 0 1 0 1 0 0 0 +

0 0 0 0 1 1 0 0

. 1 1 1 1 0 1 0 0 =

1 1 1 1 0 0 1 1 +

1 0 0 0 1 1 1 0 0

0 0 0 0 0 0 0 1 = 00001100

1 1 1 1 0 1 0 0

In questo caso il riporto nel MSB non viene considerato quindi si ha: a + (-b) = [100011100] = [28].

2C 10

2. a) Minuendo minore del sottraendo: il risultato è negativo, si considera l’eventuale riporto sul MSB. Non si ha overflow se il riporto su MSB è 0. Il modulo del risultato è il complemento a 2, cioè l’opposto, del risultato.

a = [12] = [00001100]

10 2C

b = [40] = [00101000]

10 2C

a – b = a + (- b)

Calcolo di -b:

Calcolo di a + (-b):

0 0 1 0 1 0 0 0

0 0 0 0 1 1 0 0 +

1 1 0 1 0 1 1 1 +

1 1 0 1 1 0 0 0 =

0 0 0 0 0 0 0 1 = 1 1 1 0 0 1 0 0

1 1 0 1 1 0 0 0 00001100

Il riporto su MSB è 0 quindi NON si ha overflow.

a – b = [11100100] = 2C Complemento di 2 al risultato: -[0011100] = [-28]

2C 10

1 1 1 0 0 1 0 0

0 0 0 1 1 0 1 1 +

0 0 0 0 0 0 0 1 =

0 0 0 1 1 1 0 0

3. Minuendo minore del sottraendo: il risultato è negativo, si considera l’eventuale riporto su MSB. Si ha overflow se il riporto su MSB è 1.

a = [-65] = [10111111]

10 2C

b = [65] = [01000001]

10 2C

a – b = a + (- b) si ha overflow, infatti su rappresentazione a 8 bit:

Calcolo di -b:

Calcolo di a + (-b):

7 7

a – b = [-130] Є [-2, 2 -1] = [-128,127]

0 1 0 0 0 0 0 1

. 1 0 1 1 1 1 1 1 +

101 0 1 1 1 1 1 0 +

. 1 0 1 1 1 1 1 1 =

0 0 0 0 0 0 0 1 = 1 0 1 1 1 1 1 1 0

1 0 1 1 1 1 1 1 00001100

Il riporto su MSB è 1 quindi si ha overflow.

Numeri in virgola mobile

float x;

La rappresentazione in virgola mobile viene utilizzata nel linguaggio C per rappresentare i numeri float e double.

C

Un generico numero può essere rappresentato in forma esponenziale: s · m · B.

• S = bit che codifica il segno.
• M = valore reale non negativo detto mantissa.
• C = intero con segno detto caratteristica.
• B = base di rappresentazione.

2 3 1

Esistono più rappresentazioni in forma esponenziale dello stesso numero, esempio 29.15 · 10 = 2.915 · 10 = 291.5 · 10.

È necessario dunque stabilire una rappresentazione univoca.

Lo standard IEEE 754 stabilisce che la rappresentazione esponenziale di un numero si dice in FORMA NORMALE quando: 1 ≤ m ≤ B.

Secondo lo standard IEE 754, i float sono rappresentati su 32 bit, così ripartiti: 1 bit per segno s, 23 bit per mantissa m, 8 bit per la caratteristica c.

∈ ∈ [1,254])

I numeri con caratteristica C [126,127], ovvero e, prendono il nome di NUMERI NORMALIZZATI.

-126

Il minimo di ordine di grandezza rappresentabile per i numeri normalizzati è 2.

127

Il massimo ordine di grandezza rappresentabile per i numeri normalizzati è 2, un valore molto elevato che di fatto risolve il problema dell’overflow.

s c

Un numero normalizzato codifica il seguente numero decimale: (-1) · (1 + 0.m) · 2

- ∈ [1, 2)

- ∈ ∈ [1, 254], ovvero [-126, 127]

→ ├

- -126 128 ∈ ∙ 2 [2, 2);

128 -126 -126 128 ∈ ∪

Considerando che {0,1}, l’intervallo di numeri rappresentati è dato da: (-2, -2] [2, 2)

→ Valori che stanno oltre questi intervalli sono numeri troppo grandi per essere rappresentati, ovvero appartengono all’intervallo di OVERFLOW: (-∞, -2¹²⁸] ∪ [2¹²⁸, ∞)

→ Valori che rientrano tra questi due intervalli sono numeri troppo piccoli per essere rappresentati, sono minori della sensibilità di rappresentazione, ovvero appartengono all’intervallo di UNDERFLOW: (-2^-126, 2^-126).

Numeri in virgola mobile denormalizzati

Sono numeri in valore assoluto dei numeri normalizzati. In particolare, la rappresentazione in forma normale di un numero denormalizzato avrebbe un valore illegale della caratteristica.

e = 0, ovvero C = -127. Per convenzione è stato poi scelto C = -126 per non lasciare un gap tra numeri normalizzati e denormalizzati e m Є (0,1): in questo caso la mantissa codifica la sola parte frazionaria: 0.m m …m.

1 2 23

-23 -23

La più piccola mantissa rappresentabile è 2 → m Є [2, 1)

→ -23 c -149 -126

m Є [2, 1), C = -126 m · 2 Є [2, 2)

-126 -149 -149 -126 ∪

Considerando che S Є {0,1}, l’intervallo di numeri rappresentati è dato da: (-2, -2] [2, 2)

Questi valori ricadono nell’intervallo di underflow.

In questo senso si dice che la rappresentazione dei numeri denormalizzati permette un underflow più graduale.

Precisione finita ed errore relativo

La rappresentazione della mantissa con un numero finito di bit comporta un problema di precisione finita.

23

Per ogni ordine di grandezza identificato dalla caratteristica è possibile rappresentare 2 valori distinti.

→ errore RELATIVO:

→ errore ASSOLUTO:

Precisione finita nelle operazioni tra float

Il problema di precisione finita si presenta non solo nella codifica di float, ma anche nel caso di operazioni aritmetiche tra float, il cui risultato potrebbe non essere rappresentabile come float, ma va ulteriormente approssimato, in quanto l’insieme dei float non è chiuso rispetto alla somma e al prodotto.

Esempio: 3 -1 3 3

2.156 ∙ 10 + 1.902 ∙ 10 = (2.156 + 0.0001902) ∙ 10 = 2.1561902 ∙ 10

4 cifre troncate.

Differenza tra le mantisse.

Rappresentazione delle istruzioni

Linguaggio assembly

Il C è un linguaggio simbolico di alto livello.

La codifica di programma scritto in C, prima che il programma possa essere eseguito, deve essere tradotta in una sequenza di istruzioni, sempre simboliche ma di basso livello, codice ASSEMBLY; questa operazione prende il nome di COMPILAZIONE e viene eseguita dal COMPILATORE.

Assembly:

• Linguaggio simbolico.
• Linguaggio di basso livello: una singola istruzione corrisponde ad una singola operazione eseguibile dal processore.

Le istruzioni di basso livello vengono poi tradotte in forma numerica, codice MACCHINA, dall’ASSEMBLATORE.

Viene quindi eseguito il processo di collegamento, svolto dal Linker, che collega eventuali sezioni di codice compilate separatamente, librerie ecc..

Le sezioni di codice compilate se