Appunti esame: Fondamenti di informatica

FONDAMENTI DI INFORMATICA

Rappresentazione

Tradurre un programma in C in una sequenza numerica eseguibile su un processore

Tipi

Ogni valore ha un tipo, definito da: l'insieme dei valori che rappresenta e dalle operazioni eseguibili su tali valori

1 byte = 8 bit 1 bit = 1 cifra binaria

Tipi nel linguaggio C:

• .char — rappresentazione dei 256 caratteri del codice ascii
• .int — interi con o senza segno

Es. interi con segno su 4 byte = 32 bit

• insieme degli interi rappresentati è dato da tutti e soli gli interi ≤ 2³¹ -1

32 bit = 32 cifre binarie → 2³² valori rappresentabili

Es. 4 bit → 2⁴ = 16 valori rappresentabili → [-8,7]

• .float — valori razionali in formato floating point (virgola mobile)
• .double — razionali in formato floating point con precisione doppia rispetto ai float
• .void — tipo nullo

Il tipo booleano in C non esiste

• 0 codifica falso
• 0 codifica vero (tipicamente 1)

Si possono includere librerie che definiscono il tipo booleano o l'utente può definirlo come nuovo tipo di dato

Variabile

locazione di memoria che contiene un valore di un tipo,il valore può cambiare mentre il tipo no.Si può associare un nome alla variabile per poterlareferenziare senza specificare l'indirizzo di memoria.Il nome è una sequenza arbitraria di caratteri alfanumerici,dove il primo carattere non è un numero (il compilatoreconsidera i primi 32 caratteri).

Dichiarazione di una variabile

• int a; — dichiara una variabile di tipo int e nome a

• a=7; — assegna 7 alla variabile a

Variabili array

insieme di variabili dello stesso tipo referenziateda un nome collettivo e da un indice numerico.int A[32]; — dichiara una variabile array di nome A compostada 32 variabili di tipo intA[0]=12; — assegna 12 alla prima variabile dell'array(0 indica il primo elemento)

Costanti

È un valore (di qualche tipo) che non cambia durante lacomputazione.Sono rappresentate in modo diverso a seconda del tipo

• 12 — int

• 12.0 — double

• 12.0F — float

Espressione

Combinazione di variabili e costanti attraverso operatori; è caratterizzatada: un valore restituito (3+2 è un'espressione il cui valorerestituito è 5) e da side effects prodotte sulle variabili.

Esempio: a = 7;espressione il cui valore restituito è 7 ed il sideeffect è assegnare 7 alla variabile aUn'espressione seguita da ; è un'istruzione

Operatori

• aritmetici: +, -, *, /, % resto della divisione intera (modulo)

• relazionali: <, <=, >, >=, ==, !=

• logici: &&, ||, ! ¹ congiunzione (and) ² disgiunzione (or) negazione (not)

int count=2;

int sum=1;

do {

sum=sum+count;

count++;

} while (count<10);

Graffe necessarie perché il corpo di istruzioni è dato dalla sequenza di due istruzioni

- for si usa quando il # iterazioni è noto a priori e il corpo di istruzioni può non essere mai eseguito

- while si usa quando il # iterazioni non è noto a priori e quando il corpo di istruzioni può non essere mai eseguito

- do while si usa quando il # iterazioni non è noto a priori e il corpo di istruzioni viene eseguito almeno una volta

Es

calcolo del fattoriale di un intero

main è una funzione; tutti i programmi hanno una funzione main; all'avvio di un programma il controllo è trasferito alla funzione main; il codice di una funzione è contenuto tra parentesi graffe

N: intero di cu voglio calcolare il fattoriale

n: variabile usata per indicizzare i passi della istruzione di iterazione che calcola N!

nome della funzione

la funzione deve restituire un intero (tipo da restituire)

int main( ) {

fra parentesi tonde c'è la lista dei parametri (qui vuota)

int N, n, fact;

N=8;

for (n=3, fact=2; n<=N; n++) {

fact=fact*n;

}

printf ("Fattoriale di %d=%d", N, fact);

return 0;

(espressione che restituisce un valore di tipo int)

}

istruzione che restituisce il controllo alla funzione chiamante

Algoritmo di conversione della base di rappresentazione che impiega l'aritmetica della base di partenza

• Base 10 → Base 2

Dato x < 1 esiste unica una successione di valori binari {a_k}_-∞^-1 tale che

x = ∑_k=1^∞ a_k 2^-k

a_k ∈ {0,1}

2x = ∑_k=1^∞ a_k 2^-k+1 = a₁ + ∑_k=2^∞ a_k 2^-k+1

∈ [0, 2]

(con un numero finito di cifre x < 1)

2 x →1 (parte intera di 2x, possiamo quindi iterare il procedimento considerando 2x - a₁ e determinando a₂ e così via

Algoritmo delle moltiplicazioni successive

ad ogni passo la parte frazionaria è moltiplicata per 2 e si sottrae la parte intera, e la sequenza delle parti intere sottratte è la rappresentazione cercata

Es (0,7)₁₀→(0,101110)₂

x = 0.7

• 0.7 × 2 = 1.4 → 1 (0.4)
• 0.4 × 2 = 0.8 → 0 (0.8)
• 0.8 × 2 = 1.6 → 1 (0.6)
• 0.6 × 2 = 1.2 → 1 (0.2)
• 0.2 × 2 = 0.4 → 0 (0.4)
• 0.4 × 2 = 0.8 → 0 (0.8)
• 0.8 × 2 = 1.6 → 1 (0.6)
• 0.6 × 2 = 1.2 → ...

numero periodico

Interi senza segno (unsigned int)

Codifica posizionale in base 2 su N bit

A = ∑_n=0^N-1 a_n 2ⁿ   a_n ∈ {0,1} ∀ n = 0,1,...,N-1

codifica tutti e soli i naturali ∈[0,2^N-1]

N varia a seconda dell'architettura del calcolatore, tipicamente N=32

Interi con segno

int: rappresentazione in complemento a 2 su N bit (cioè dimin nel bit che ha peso negativo e quelli con peso positivo)

Codifica dei float nello standard IEEE 754

S.m.2^c

• e ∈ [0, 255]
• e = 255 (c = 128)
  • m = 0 S = 0 → +∞
  • S = 1 → -∞
• m ≠ 0 → NaN (not a number), è restituito come risultato di operazioni illegali tra float (divisione per zero)
• e ∈ [1, 254] (c ∈ [-126, 127]) numero normalizzato
  • m.2^c ∈ [2^-126, 2¹²⁷) il dato che m ∈ [1,2), l'intervallo al quale appartengono i numeri rappresentati risulta (-2^-126, -2¹²⁷) ∪ [2^-126, 2¹²⁷)
  • L'intervallo (-∞, -2^-126) ∪ [2¹²⁷, ∞) è dell'intervallo d'overflow
• e = 0 (c = -127)
  • m = 0
    • S = 0 → +0
    • S = 1 → -0
  • m ≠ 0 → numero denormalizzato
    • sono numeri più piccoli in valore assoluto dei numeri normalizzati (la rappresentazione in forma normale di un numero denormalizzato avrebbe un valore illegale della caratteristica)
    • m ∈ (0,1) dove 0.m1...m23 → m ∈ [2^-23, 1])
    • e = 0 ma codifica il valore convenzionale 4. m.2^c ∈ [2^-149, 2^-126)
• S ∈ {0,1}
  • Intervallo dei valori rappresentabili [-2^-126, -2^-149) ∪ [2^-149, 2^-126)

Rappresentazione delle istruzioni

Codice sorgente: file c, contiene il codice c in un linguaggio simbolico in cui operatori e variabili sono denotati con simboli, è un linguaggio di alto livello: ogni istruzione in linguaggio c corrisponde a più istruzioni eseguite dal processore

Codice assembly: linguaggio simbolico di basso livello: ogni istruzione corrisponde a un'istruzione eseguita dal processore (semantic gap: non c'è corrispondenza unica tra i due linguaggi nel processo di compilazione, un problema di ...