Fondamenti di Informatica per la Sicurezza

Lezione 1 - Concetto di numero

Fondamenti di Informatica per la Sicurezza

Modulo 2 - Rappresentazione dell’informazione

Unità didattica 1 - Numeri e numerali

Stefano Ferrari

Università degli Studi di Milano - Ssri - CDL ONLINE

Citazione

Aritmetica è contare fino a venti

senza togliersi le scarpe

[Topolino]

Modulo 2— U.D. 1— Lez. 1

Stefano Ferrari— Fondamenti di Informatica per la Sicurezza 1

Numeri

Un numero è un ente astratto usato per indicareproprietà quantitative delle grandezze.

x x

x x

x

•

• •

• •

Contare

Per contare, non è necessario conoscere inumeri.

Basta ricorrere a delle relazioni:

• tra grandezze discrete:– sassolini e pecore;

– dita della mano e figli.

• tra grandezze continue:– tempo trascorso e candela che brucia;

– tempo trascorso e spazio percorso dall’ombra.



Astrazione

Le esigenze pratiche possono portare a scoprireconcetti più evoluti.

Alcuni esempi:

• confronto tra elementi numerici;

• proprietà delle operazioni;

• assegnazione di nomi a numeri particolari;

• concetto di ordine di grandezza.

Rappresentazione dei numeri

L’elaborazione (o la trasmissione) dei numeririchiede la loro rappresentazione su di unsupporto fisico.

Serve quindi:

• mezzo fisico (modificabile, ma stabile);

• codifica.



Sistema di numerazione

Codifica arbitraria per rappresentare un insiemeinfinito di oggetti utilizzando un insieme finito disimboli.

Numerale

Al concetto astratto di numero si affianca la suarappresentazione simbolica: il numerale.

Interpretazione del numerale:

• un numerale ha significato solo all’interno di unsistema di numerazione.



Sistemi di numerazione

I sistemi di numerazione si dividonoprincipalmente in:

• additivi;

• posizionali.

Sistemi di numerazione addittivi (1)

Sistema di numerazione romano:

• in uso nell’antica Roma;

• simboli letterali: I, V, X, L, C, D e M(uno, cinque, dieci, cinquanta, cento, cinquecento emille);

• i simboli affiancati in ordine decrescente indicano ilnumero pari alla loro somma;

• se un simbolo precede un simbolo di valoresuperiore, deve essere sottratto.



Sistemi di numerazione addittivi (2)

Sistema di numerazione romano:

• esempio:

MCMLXII

1000 + (1000 − 100) + 50 + 10 + 1 + 1

1962

Sistemi di numerazione posizionali

Notazione decimale:

• inventata in India, perfezionata dagli arabi e poiintrodotta in Europa da Fibonacci;

• basata su dieci cifre;

• il significato dipende dalla loro posizione.

• Esempio:

1203 = 1 ·103+ 2 ·102+ 0 ·101+ 3 ·100



In sintesi

I numeri:

• sono gli elementi di informazione più semplici chesiamo in grado di elaborare in modo automatico;

• per elaborarli, dobbiamo essere in grado dirappresentarli.

Chiusura



Lezione 2 - Rappresentazioneposizionale




Stefano Ferrari


Numeri e rappresentazione

Il concetto di “numero” è indipendente dalla suarappresentazione.

Esempio:

+ + + o + o + o o o + o + o o o + o + o

In questo caso, i simboli “+” sono posizionati incorrispondenza di un numero primo.

La scelta della rappresentazione dipendedall’utilizzo che si vuol fare dei numerirappresentati.



Scelta della notazione posizionale

Se si devono fare calcoli, la notazione posizionaleoffre alcuni indubbi vantaggi.

Proprietà della notazione posizionale:

• somma: viene operata agendo “localmente” (unitàcon unità, decine con decine e così via);

• traslazione (shift): moltiplicare o dividere per 10trasla le cifre di una posizione;

• compattezza: la rappresentazione richiede unnumero di cifre logaritmico.

Notazione posizionale (1)

Formalizzazione:

(an . . . a1 a0)b ≡

n∑

i=0

ai ·bi, b ≥ 2, ai ∈ {0, . . . , b−1}

• dato un numero intero maggiore o uguale a 2, b,detto base,

• la sequenza an . . . a1 a0,

• composta da n + 1 simboli scelti dall’insieme{0, . . . , b − 1},

• viene interpretata come an · bn + · · · + a1 · b1 + a0 · b0.



Notazione posizionale (2)

Basi notevoli:

• decimale, b = 10 ai ∈ {0, . . . , 9};

• binaria, b = 2 ai ∈ {0, 1};

• ottale, b = 8 ai ∈ {0, . . . , 7};

• esadecimale, b = 16 ai ∈ {0, . . . , 9, A, . . . , F}.

Esempi:

• (34)10 = 3 · 10 + 4 · 1 = 34

• (34)8 = 3 · 8 + 4 · 1 = 28

• (34)16 = 3 · 16 + 4 · 1 = 52

Tuttavia ...

In alcuni campi, è più comodo usare una basediversa da quella decimale.

Infatti:

• le uova si vendono a dozzine;

• le ore sono composte da 60 minuti;

• un giorno dura 24 ore.

12 è divisibile per 2, 3, 4 e 6!



Numeri frazionari

Ogni numero intero è rappresentabile utilizzandouna qualsiasi base, ma lo stesso non vale per inumeri frazionari:

in base 10 1

3≡ (0.3̄)10

in base 3 1

3≡ (0.1)3

I numeri frazionari si possono rappresentarecome:

(an . . . a2 a1 a0 . a−1 . . . a−m)b ≡

n∑

i=−m

ai · bi, b ≥ 2

In sintesi

La notazione posizionale permette:

• di rappresentare in qualsiasi base qualsiasi numerointero;

• e anche alcuni numeri frazionari.



Chiusura



Lezione 3 - Cambio di base




Stefano Ferrari


Cambio di base (1)

Come si scrive in base 12 il numerorappresentato dal numerale (32)4?

NB: Cambia solo la rappresentazione del numero!

Per rispondere alla domanda serve una piccoladigressione: la divisione.



Divisione

Dati due numeri naturali a, b (b > 0), la divisionepermette di determinare due numeri q ed r taliche

a = b · q + r, 0 ≤ r < b

dove:• a è il dividendo;

• b è il divisore;

• q è il quoziente (o quoto);

• r è il resto.

Cambio di base (2)

L’algoritmo per il cambio di base fa uso deglioperatori di divisione intera (div) e di resto(mod):

div è la parte intera della divisione tra due numeriinteri (quoziente):es: 13 div 5 = 2

mod è il resto della divisione tra due numeri interi:es: 13 mod 5 = 3

Infatti:

13 = 5 · 2 + 3



Cambio di base (3)

Algoritmo per trovare il numerale del numero n,in una data base, b:

1. Calcolare il quoziente, q, ed il resto, r, delladivisione di n per b:q = n div b

r = n mod b

2. Il resto, r, è l’ultima cifra del numerale che esprimen in base b.

3. Se il quoziente, q, è diverso da zero, le rimanenticifre si ottengono trasformando il quoziente,sostituendo nei passi precedenti q ad n.

4. Se il quoziente è zero, la conversione è terminata.

Cambio di base (4)

Esempio: (133)10 → (x)5

quoziente resto

133 133 = 26 · 5 + 3

26 3 26 = 5 · 5 + 1

5 1 5 = 1 · 5 + 0

1 0 1 = 0 · 5 + 1

0 1

(133)10 = (1013)5



Cambio di base (5)

Spiegazione:

133 = 26 · 5 + 3 =

= (5 · 5 + 1) · 5 + 3 =

= ((1 · 5 + 0) · 5 + 1) · 5 + 3 =

= (((0 · 5 + 1) · 5 + 0) · 5 + 1) · 5 + 3 =

= ((1 · 5 + 0) · 5 +1) · 5 + 3 =

= (1 ·52 + 0 · 5 + 1) · 5 + 3 =

= 1 · 53 + 0 · 52 + 1 · 5 + 3 =

= 1 · 53 + 0 · 52 + 1 · 5 + 3 · 50

(133)10 = (1013)5

Numero di cifre (1)

Quante cifre, k, bisogna usare per rappresentarein base b il numero n?

Ragionando in base 10:

con 1 cifra: 0 . . . 9 fino a 101 − 1

con 2 cifre: 10 . . . 99 fino a 102 − 1

con 3 cifre: 100 . . . 999 fino a 103 − 1

con k cifre: 10k−1 . . . 10k − 1 fino a 10k − 1

k deve essere il più piccolo numero intero taleper cui bk − 1 ≥ n.

Per comodità: bk ≥ n + 1.



Numero di cifre (2)

Applicando il logaritmo in base b ad entrambi imembri della disequazione precedente:

logbbk ≥ log

b(n + 1)

k ≥ logb(n + 1)

k = dlogb(n + 1)e

dove dxe indica il più piccolo numero interomaggiore o uguale a x.

Numero di cifre (3)

Quante cifre sono necessarie per rappresentare1145 in notazione posizionale in base:a) 10 b) 2 c) 16?

a) 10: log10

1146 ≈ 3.0592 → 4 cifre.

Infatti: 1145 = (1145)10.

b) 2: log21146 ≈ 10.162 → 11 cifre.

Infatti: 1145 = (10001111001)2.

c) 16: log16

1146 ≈ 2.5406 → 3 cifre.

Infatti: 1145 = (479)16.



In sintesi

La notazione posizionale permette:

• in generale, il calcolo del numerale attraverso ladivisione;

• il calcolo del numero di cifre necessarie basato sullogaritmo del numero da rappresentare.

Chiusura



Lezione 4 - Esercizi sul cambiamentodi base




Stefano Ferrari


Da base n a decimale

Come si rappresenta in base 10 il numero (412)5?

Dalla definizione di notazione posizionale:

(412)5 = 4 · 52 + 1 · 51 + 2 · 50 =

= 4 · 25 + 1 · 5 + 2 · 1 =

= 100 + 5 + 2 =

= 107

(412)5 = (107)10



Da decimale a base n


Algoritmo della divisione:

quoziente resto1079359 2119 239 213 04 11 10 1

(1079)10 = (1110222)3

Da base m a base n (1)


Si potrebbe applicare l’algoritmo di divisione, maè difficile fare i calcoli se la base non è 10.

Meglio risolvere il problema in due passi:

1. conversione da base 7 a decimale;

2. conversione da decimale a base 5.



Da base m a base n (2)

Conversione da base 7 a decimale:

(106)7 = 1 · 72 + 0 · 71 + 6 · 70 = 55

Conversione da decimale a base 5:

quoziente resto5511 02 10 2

Quindi:

(106)7 = (210)5

Da binario ad ottale

È un caso particolare di conversione da base m abase n: 8 = 23.

Se n = mk, il cambiamento di base si può operare

per blocchi.

Esempio: (101001)2 = (???)8

(101001)2 == 1 · 25 + 0 · 24 + 1 · 23 + 0 · 22 + 0 · 21 + 1 · 20 == (1 ·22 +0 ·21 +1 ·20) ·23 +(0 ·22 +0 ·21 +1 ·20) ·20 == (5) · 81 + (1) · 80 == (51)8

base 2 101 001base 8 5 1



Da binario ad esadecimale


Esempio: (101001010)2 = (???)16

base 2 0001 0100 1010base 16 1 4 A

(101001010)2 = (14A)16

Da ottale a binario


Se m = nk, il cambiamento di base si può operare

per blocchi.

Esempio: (51)8 = (???)2

= (51)8 = (5) · 81 + (1) · 80 == (1 ·22 +0 ·21 +1 ·20) ·23 +(0 ·22 +0 ·21 +1 ·20) ·20 == 1 · 25 + 0 · 24 + 1 · 23 + 0 · 22 + 0 · 21 + 1 · 20 == (101001)2

base 8 5 1base 2 101 001



Da esadecimale a binario


Esempio: (14A)16 = (???)2

base 16 1 4 Abase 2 0001 0100 1010

(14A)16 = (101001010)2

In sintesi

Esercizi di cambiamento di base:• da base 10 a base n;

• da base n a base 10;

• da base n a base m;

• da binario ad ottale/esadecimale;

• da ottale/esadecimale a binario.



Chiusura



Lezione 1 - Bit e byte



Unità didattica 2 - Rappresentazione binaria

Stefano Ferrari


Binario è bello!

Per ragioni tecnologiche di affidabilità, gli attualicalcolatori sono in grado di rappresentare e dielaborare solo informazione espressa utilizzandodue stati.

É perciò naturale descrivere le informazioni innotazione binaria.

In particolare, un elemento di informazioneviene chiamato bit.



Bit

Binary Digit

cifra binaria

Un bit può valere (convenzionalmente) 0 o 1.

Sequenze di bit

Per rappresentare oggetti che possono assumerepiù di due stati, si usano sequenze di bit.

Quanti numeri sono rappresentabili in N bit?• N simboli che, indipendentemente uno dall’altro,possono assumere due valori assumono 2

N

combinazioni diverse.

2× 2× · · · × 2←−−−−−−−−−→

N volte

Se abbiamo N bit, quali numeri rappresentiamo?• Lo stabilisce la codifica (arbitraria).



Byte

Una sequenza di otto bit viene detta byte.

Quante configurazioni differenti può assumereun byte?• 2

8= 256.

Una digressione:• il termine byte indica un gruppo di elementi binari(tipicamente 8) trattati congiuntamente;

• diverse le origini del termine:– variazione del termine bite per evitare confusione con bit;

– acronimo di Binary Yoked Transfer Element (elemento di

trasferimento di binari aggiogati).

Multipli binari (1)

210

= 1024 ≈ 1000 = 103 uno scarto del 2.4%!

Secondo il SI (basato su scala decimale), 1kilobyte vale 1000 byte.

Poiché molto spesso in informatica ricorronomultipli di potenze di due, è stato trovatoconveniente riferirsi a 1024 come 1 kilobyte(KB).



Multipli binari (2)

Lo scarto tra i multipli di 210 e di 103 cresceesponenzialmente:• Mega: 2

20= 1 048 576 ≈ 1 000 000 = 10

6

uno scarto di circa 4.86%!

• Giga: 230

= 1 073 741 824 ≈ 1 000 000 000 = 109


• Tera:2

40= 1 099 511 627 776 ≈ 1 000 000 000 000 = 10

12


Multipli binari (3)

Sono stati proposti i seguenti nomi per i multiplibinari:Fatt. Nome Simb. Origine derivazione SI

210 kibi Ki kilobinary (210)1 kilo (103)1 = 103

220 mebi Mi megabinary (210)2 mega (103)2 = 106

230 gibi Gi gigabinary (210)3 giga (103)3 = 109

240 tebi Ti terabinary (210)4 tera (103)4 = 1012

250 pebi Pi petabinary (210)5 peta (103)5 = 1015

260 exbi Ei exabinary (210)6 exa (103)6 = 1018

Fonte: http://www.iec.ch/zone/si/si_bytes.htm



In sintesi

I bit:• sono gli elementi di informazione minimi;

• rappresentano due stati;

• possono essere aggregati per rappresentare più didue stati.

I byte:• sono l’aggregazione di 8 bit;

• sono la base per i multipli binari.

Prossimi passi

Come i bit si possono usare per rappresentare inumeri:• naturali;

• interi;

• razionali;

• reali.



Chiusura



Lezione 2 - Codifica binaria di interi




Stefano Ferrari


Citazione

Ci sono 10 tipi di persone,

chi capisce il binario

e chi no.

[Anonimo]



Numeri naturali

È il tipo più naturale da rappresentare:rappresentazione in notazione posizionale inbase due.

Esempio: (13)10 = (1101)2 → 00001101, usando unbyte.

Il primo bit viene chiamato bit più significativo(Most Significant Bit, MSB).

L’ultimo bit viene chiamato bit meno significativo(Least Significant Bit, LSB).

MSB 00001101 LSB

Numeri interi con segno

Con bit di segno (rappresentazione segno emodulo):

0 0 0 +00 0 1 +10 1 0 +20 1 1 +31 0 0 -01 0 1 -11 1 0 -21 1 1 -3

• il bit più significativorappresenta il segno, gli altribit rappresentano il modulo;

• lo stesso numero (lo zero)viene rappresentato con duenumerali differenti;

• le operazioni aritmetiche sonomacchinose.



Complemento a 2 (1)

Per rappresentare in complemento a 2 il numerox usando una sequenza di n bit, si rappresenta inbinario (usando n + 1 bit) il numero 2n + x, escartando poi il bit più significativo.

Esempio

Usando 4 bit (n = 4):• 6 → 24 + 6 = (22)10 = (10110)2

compl. a 2−−−−−→ 0110

• −6 → 24− 6 = (10)10 = (01010)2

compl. a 2−−−−−→ 1010

−an · 2n + an−1 · 2n−1 + · · · + a1 · 21 + a0 · 20

Complemento a 2 (2)

0

0000

1

0001

2

0010

30011

4 0100

50101

6

01107

0111

-8

1000

-7

1001

-6

1010

-51011

-41100

-31101

-2

1110 -1

1111



Complemento a 2 (3)

Con questa rappresentazione:• lo zero ha rappresentazione unica;

• con n bit, si rappresentano i numeri interidell’intervallo [−2n−1

, 2n−1− 1];

• i numeri negativi hanno il MSB che vale 1, gli altri 0(di fatto, il MSB è il bit di segno);

• la somma si realizza considerando le sequenze di bitcome numeri binari;

• la sottrazione si realizza invertendo il valore delsottraendo e poi sommandolo al minuendo innotazione binaria.

In sintesi

Con due simboli possiamo rappresentare inumeri:• naturali;

• interi.



Prossimi passi

Vantaggi nell’uso della notazione incomplemento a 2.

Chiusura



Lezione 3 - Complemento a 2




Stefano Ferrari


Decodifica in complemento a due

0

0000

1

0001

2

0010

30011

4 0100

50101

6

01107

0111

-8

1000

-7

1001

-6

1010

-51011

-41100

-31101

-2

1110 -1

1111

overflow

Decodifica:

• se il primo simbolo è 0

si considerasemplicemente comeun numero binario;

• se il primo simbolo è 1

lo si decodifica inbinario e ad esso sisottrae il numero 2

n.



Inversione in complemento a 2

0

0000

1

0001

2

0010

30011

4 0100

50101

6

01107

0111

-8

1000

-7

1001

-6

1010

-51011

-41100

-31101

-2

1110 -1

1111

overflow

Inversione:

• si invertono tutte lesingole cifre binarie;

• si somma 1.

Codifica in complemento a 2

0

0000

1

0001

2

0010

30011

4 0100

50101

6

01107

0111

-8

1000

-7

1001

-6

1010

-51011

-41100

-31101

-2

1110 -1

1111

overflow

Codifica:

• codifica del valoreassoluto in notazioneposizionale binaria;

• se è negativo, lo siinverte.



Operazioni algebriche in complemento a 2

0

0000

1

0001

2

0010

30011

4 0100

50101

6

01107

0111

-8

1000

-7

1001

-6

1010

-51011

-41100

-31101

-2

1110 -1

1111

overflow

Somma:

• normale sommabinaria.

Sottrazione:

• si inverte il sottraendo;

• lo si somma alminuendo.

Overflow

L’overflow si manifesta quando si cerca dirappresentare un numero troppo grande.

Esempio

Usiamo una rappresentazione in complemento a2 a 4 bit per i numeri da -8 a 7.

Il risultato della somma 6+5 non èrappresentabile.

Analoghe considerazioni per il risultato di -7-4.

Con la notazione in complemento a 2, l’overflowsi rileva facilmente.



Individuazione dell’overflow

0

0000

1

0001

2

0010

30011

4 0100

50101

6

01107

0111

-8

1000

-7

1001

-6

1010

-51011

-41100

-31101

-2

1110 -1

1111

overflow

Overflow:

• somma di valori consegno opposto esottrazione di valori consegni concordi non dàmai overflow;

• negli altri casi, c’è statooverflow se il segno delrisultato è discorde conil segno del primooperando.

Overflow in complemento a 2

Si verifica un overflow se:

C = A + B

A B C

+ + -

- - +

C = A - B

A B C

+ - -

- + +



In sintesi

La rappresentazione in complemento a 2permette di:

• codificare e decodificare agevolmente i numeri;

• effettuare calcoli algebrici con lo stesso algoritmo;

• individuare le situazioni di overflow.

Prossimi passi

Esercizi sulla codifica in complemento a due.

Come i bit si possono usare per rappresentare:

• numeri razionali;

• numeri irrazionali.



Chiusura



Lezione 4 - Esercizi sulla notazione incomplemento a 2




Stefano Ferrari


Codifica (1)

D Codificare il numero 2 in complemento a 2 a 4 bit,specificando se si verifica un overflow.

R Poiché 2 ≤ 24−1 − 1, non ci sarà overflow.

Numero da codificare: 24 + 2 = 18.

Codifica binaria troncata a 4 bit: 0010.



Codifica (2)

D Codificare il numero 10 in complemento a 2 a 3bit, specificando se si verifica un overflow.

R Poiché 10 > 23−1 − 1, ci sarà overflow.

• Numero da codificare: 23 + 10 = 18

Codifica binaria troncata a 3 bit: 010

Codifica (3)

D Codificare il numero −13 in complemento a 2 a 3bit, specificando se si verifica un overflow.

R Poiché −13 < 23−1, ci sarà overflow.

Numero da codificare: 23 − 13 = −5.

Codifica binaria troncata a 3 bit del valore assoluto(5): 101.

Inversione in complemento a 2: 011.



Decodifica (1)

D Quale numero è rappresentato dalla stringabinaria 10111, codificata in complemento a due?

R (10111)2 = (23)10.

Poiché la prima cifra binaria è 1, 10111 vienedecodificato come: 23 − 25 = −9.

Decodifica (2)

D Quale numero è rappresentato dalla stringabinaria 01101, codificata in complemento a due?

R (01101)2 = (13)10.

Poiché la prima cifra binaria è 0, 01101 vienedecodificato come 13.



Inversione (1)

D Quale stringa binaria è l’inverso in complemento adue della stringa binaria 01101?

R Invertendo i bit di 01101, si ottiene 10010.

Sommando 1 a 10010, si ottiene 10011.

Troncando a 5 bit 10011, si ottiene 10011.

Inversione (2)

D Quale stringa binaria è l’inverso in complemento adue della stringa binaria 00?

R Invertendo i bit di 00, si ottiene 11.

Sommando 1 a 11, si ottiene 100.

Troncando a 2 bit 100, si ottiene 00.



Somma (1)

D Date le stringhe binarie A = 0000 e B = 0011,calcolare in complemento a due la loro somma,specificando se si verifica un overflow.

R La somma binaria di 0000 e 0011, troncata a 4 bitè 0011.

Poiché le due stringhe date hanno il primo bituguale, e uguale anche al primo bit del risultato,non si è verificato un overflow.

Somma (2)

D Date le stringhe binarie A = 111101 e B = 100001,calcolare in complemento a due la loro somma,specificando se si verifica un overflow.

R La somma binaria di 111101 e 100001, troncata a 6bit è 011110.

Poiché le due stringhe date hanno il primo bituguale, ma diverso dal primo bit del risultato, si èverificato un overflow.



Sottrazione (1)

D Date le stringhe binarie A = 1011000 e B =0101000, calcolare in complemento a due la lorodifferenza, specificando se si verifica un overflow.

R Il complemento a 2 di 0101000 è 1011000.

La somma binaria di 1011000 e 1011000, troncataa 7 bit è 0110000.

Poiché le due stringhe date hanno il primo bitdiverso, e il primo bit del risultato è uguale alprimo bit della seconda stringa, si è verificato unoverflow.

Sottrazione (2)

D Date le stringhe binarie A = 100011 e B = 110000,calcolare in complemento a due la loro differenza,specificando se si verifica un overflow.

R Il complemento a 2 di 110000 è 010000.

La somma binaria di 100011 e 010000, troncata a 6bit è 110011.

Poiché le due stringhe date hanno il primo bituguale, non si è verificato un overflow.



Prossimi passi

Come i bit si possono usare per rappresentare:

• numeri razionali;

• numeri irrazionali.

Chiusura



Lezione 5 - Codifica di numerirazionali




Stefano Ferrari


Numeri “con la virgola”

Per la rappresentazione dei numeri razionali ereali ci sono due impedimenti:

• per via della notazione posizionale, alcuni numerinon possono essere rappresentati con un numerolimitato di cifre (e.g., 1

3in base 10);

• alcuni numeri reali (gli irrazionali) non possonoproprio essere rappresentati in nessuna base (e.g.,π).



Numeri razionali

Per gli usi pratici, i numeri irrazionali possonoessere approssimati da un numero razionale:

• per esempio, 3.14 ≈ π.

Per rappresentare numeri razionali ci sono duenotazioni, dette:

• virgola fissa;

• virgola mobile.

Virgola fissa (1)

Data una sequenza di n bit, viene stabilito apriori quanti di questi, m rappresenteranno laparte intera, e quanti, k, la parte frazionaria.

m bit←−−−−−→an−1 · · · ak .

k bit←−−−−−→ak−1 · · · a0

←−−−−−−−−−−−−−−−→

n bit

Equivale a dividere per 2k.



Virgola fissa (2)

Esempio:

(10.101)2 = 1 · 21 + 0 · 20 + 1 · 2−1 + 0 · 2−2 + 1 · 2−3 =1 · 2 + 0 · 1 + 1 · 0.5 + 0 · 0.25 + 1 · 0.125 = 2.625

(10101)2/23 = (1 · 24 + 0 · 23 + 1 · 22 + 0 · 21 + 1 · 20 =1 · 16 + 0 · 8 + 1 · 4 + 0 · 2 + 1 · 1)/8 = 21/8 = 2.625

Virgola fissa (3)

In virgola fissa, la precisione assoluta è fissata:

1 0 3 0. 2 7 e 0 0 0 1. 0 9

hanno la stessa precisione: 1/100.

Per il primo numero, la precisione relativa è1/105, mentre per il secondo numero, laprecisione relativa è 1/102.

1.091 e 1.094 sono indistinguibili: vengonorappresentati con 1.09.



Virgola fissa (4)

Problema di underflow: può non essere possibilerappresentare un numero piccolo.

Come si rappresenta 0.001?

0 0 0 0. 0 0 !

Virgola mobile (1)

Un numero razionale può essere rappresentatonella forma: m · be, b è una base intera.

Esempio

32.1 può essere scritto come 0.321 · 102.

m è detto mantissa, e è detto esponente.

In virgola mobile, un numero vienerappresentato tramite la coppiamantissa-esponente.



Virgola mobile (2)

In virgola mobile, la precisione relativa è fissata.

Il numero di bit dedicati a:

• m fissano la precisione relativa con cui il numero puòessere rappresentato;

• e fissano l’estensione dell’intervallo rappresentabile.

IEEE Standard 754 Floating Point Numbers:• singola precisione: 32 bit (1 per il segno, 8 perl’esponente e 23 per la mantissa);

• doppia precisione: 64 bit (1 per il segno, 11 perl’esponente e 52 per la mantissa).

Fissa o mobile?

Con lo stesso budget di bit, possiamorappresentare lo stesso numero di valori.

Virgola fissa e mobile si differenziano per come ivalori vengono distribuiti sulla retta dei reali.



In sintesi

I numeri non interi possono essere rappresentatimediante le notazioni:

• a virgola fissa;

• a virgola mobile.

Prossimi passi

Come i bit si possono usare per rappresentarealtre grandezze:

• insiemi non numerici;

• suoni;

• immagini;

• animazioni.



Chiusura



Lezione 6 - Rappresentazione digrandezze numerabili




Stefano Ferrari


Citazione

Il computer è un genio che può soddisfarequalsiasi desiderio.

Però bisogna specificare il desiderioesattamente.

E in binario.

[Anonimo]



Insiemi numerabili

n bit possono assumere 2n configurazioni.

Attraverso un’opportuna codifica, possiamorappresentare un insieme di 2n elementi.

Esempio: la codifica di caratteri:• EBCDIC, 8 bit: era usato sui mainframe IBM;

• ASCII (American Standard Code for InformationInterchange), 7 bit + 1: adottata dall’ANSI(American National Standards Institute);

• Unicode, 16 bit: “a unique number for everycharacter, no matter what the platform, no matterwhat the program, no matter what the language”.

Tabella ASCII

0 1 2 3 4 5 6 7 8 9

0 NUL SOH STX ETX EOT ENQ ACK BEL BS HT

1 LF VT FF CR SO SI DLE DC1 DC2 DC3

2 DC4 NAK SYN ETB CAN EM SUB ESC FS GS

3 RS US SP ! " # $ % & ’

4 ( ) * + , - . / 0 1

5 2 3 4 5 6 7 8 9 : ;

6 < = > ? @ A B C D E

7 F G H I J K L M N O

8 P Q R S T U V W X Y

9 Z [ \ ] ^ _ ‘ a b c

10 d e f g h i j k l m

11 n o p q r s t u v w

12 x y z { | } ~ DEL



Grandezze continue

È possibile approssimare numericamente unagrandezza continua tramite campionamento.

Campionare significa collezionare ad intervalliregolari (di tempo o di spazio) i valori che lagrandezza assume (nel tempo o nello spazio).

Campionamento

In funzione delle caratteristiche del segnale,esiste la lunghezza massima dell’intervallo dicampionamento per poter ricostruire fedelmenteil segnale.



Quantizzazione

L’elaborazione digitale del suono (e più ingenerale dei segnali) richiede però di utilizzareuna codifica digitale del valore di ogni campione.

Questa operazione, chiamata quantizzazione,comporta una distorsione del segnale.

In sintesi

Anche alcune grandezze non numeriche possonoessere descritte tramite i numeri.

Se possiamo descriverle tramite numeri,possiamo anche descriverle in binario.



Prossimi passi

Codifica di grandezze continue.

Chiusura



Lezione 7 - Rappresentazione digrandezze continue




Stefano Ferrari


Segnale audio (1)

Un suono può essere rappresentato come unafunzione continua: l’ampiezza dell’onda sonoranel tempo.

Frequenza di campionamento:

• la voce umana deve essere campionata ad un ottavodi millesimo di secondo;

• la musica deve essere campionata 44 100 volte alsecondo.



Segnale audio (2)

Una codifica del segnale sonoro deve quindidecidere:

• il numero di canali (mono? stereo? effettosurround?);

• frequenza di campionamento (quanti campioni perogni secondo?);

• i livelli di quantizzazione (quanti bit per ognicampione?).

Segnale audio

Esempio 1

La codifica a 8 bit di un segnale stereo delladurata di 3 secondi, campionato a 16 kHzrichiede:

8 × 16 000 × 2 × 3 = 768 000 bit.

Esempio 2

Per i CD musicali viene utilizzata una codifica a16 bit per canale e un campionamento a 44 100Hz; per un’ora di registrazione servono:

16 × 44 100 × 2 × 3600 = 5 080 320 000 bit.

Circa 606 MiB.



Codifiche audio particolari

Per ottenere una codifica meno voluminosa, lostandard MP3 sfrutta:

• la ridondanza del segnale audio;

• le particolarità del nostro sistema uditivo.

Il MIDI (Musical Instrument Digital Interface):

• codifica lo strumento, la nota e la sua durata;

• è l’analogo di uno spartito musicale.

Codifica di immagini

Le tecniche per descrivere un’immagine digitalesono di due tipi:

• bitmap;

• vettoriali.



Bitmap (1)

Una immagine digitale bitmap è descritta da unamatrice di pixel (contrazione di picture element).

Ogni pixel può assumere un singolo colore.

Quindi:

• il numero di righe e di colonne determina larisoluzione spaziale dell’immagine;

• il numero di colori che il pixel può assumeredetermina la risoluzione cromatica.

Bitmap (2)

Una bitmap può essere:• in bianco e nero:

– ogni pixel è codificato da 1 bit.

• a toni di grigio:– il pixel può assumere diversi livelli intermedi tra il bianco e il

nero;

– un’immagine a 16 livelli di grigio richiede 4 bit per pixel.

• a colori:– il colore può essere scomposto in termini di componente

rossa, verde e blu (rappresentazione RGB — Red, Green,

Blue);

– utilizzando tre canali è possibile rappresentare il colore.



Codifiche video particolari

Una rappresentazione più compatta può essereottenuta sfruttando:• la ridondanza del segnale;

• le caratteristiche del sistema percettivo.

Queste tecniche sono utilizzate nelle codifichepiù diffuse, quali GIF, PNG e JPEG.

Sono molto utilizzate anche le codifiche a palette(tavolozza):• insieme alla bitmap viene codificata una tabella deicolori usati;

• gli elementi della bitmap non contengono un colore,ma solo un riferimento ad un colore della tavolozza.

Immagini vettoriali

Una descrizione vettoriale indica:• una collezione di elementi grafici:

– per esempio, un cerchio o un rettangolo;

• loro caratteristiche:– per esempio, il tipo di tratto, il colore del bordo o dell’interno.

I formati vettoriali:• sono l’analogo del formato MIDI;

• sono molto usati nei sistemi CAD e nella grafica;

• si prestano a subire trasformazioni geometrichesenza degradare l’immagine descritta;

• permettono la visualizzazione alla risoluzione deidispositivi.



Animazioni

Una animazione può essere ottenuta tramite unasuccessione di immagini.

Ogni singola immagine viene detta frame.

Il frame-rate è il numero di immagini persecondo che vengono rappresentate.

Il numero di bit sufficiente per una animazione èquindi pari a:

numero di bit per frame × frame-rate × durata

In realtà, il numero di bit può essereampiamente ridotto sfruttando la ridondanzadovuta alla somiglianza tra frame consecutivi.

In sintesi

Anche alcune grandezze non numeriche possonoessere descritte tramite i numeri.

Se possiamo descriverle tramite numeri,possiamo anche descriverle in binario.

Se restringiamo il dominio di utilizzo, possiamoaffinare la codifica.



Prossimi passi

Tecniche per il calcolo dei bit necessari per lacodifica di grandezze numeriche e nonnumeriche.

Chiusura



Lezione 1 - Permutazioni edisposizioni



Unità didattica 3 - Calcolo del numero di bit

Stefano Ferrari


Codifica e numero di bit necessari

La codifica è una scelta arbitraria basata su unaconvenzione che chi usa la codifica devenecessariamente conoscere.

Una codifica può essere considerata buona sefacilita:• l’elaborazione nella quale la si vuole utilizzare;

• le operazioni di codifica e decodifica.

Per stabilire quanti bit sono necessari, bisognaconoscere il numero di configurazioni che lacodifica deve rappresentare.

Qualche nozione di calcolo combinatorio èindispensabile.



Regola del prodotto

Una regola generale:se una cosa può essere realizzata in n modi e perciascuna di queste realizzazioni una seconda cosapuò essere realizzata in m modi, allora il numero direalizzazioni possibili è n × m.

Esempio

Una signora ha cinque cappellini, due borsette,sei paia di scarpe e dodici vestiti.

In quanti modi diversi può abbigliarsi?

Per quanto detto sopra, la signora avrà:

5 × 2 × 6 × 12 = 720

possibilità di scelta.

Permutazioni (1)

Si chiamano permutazioni di n elementi distinti(n ∈ N, n > 0), tutti i raggruppamenti diversi chesi possono formare con gli elementi dati,rispettando le seguenti proprietà:

1. ciascun raggruppamento contiene n elementi;

2. uno stesso elemento non può figurare più volte inun raggruppamento;

3. due raggruppamenti sono tra loro distinti sedifferiscono per l’ordine con cui sono disposti glielementi.



Permutazioni (2)

n elementi danno luogo a n! permutazioni:

P (n) = n!

L’operatore indicato con il simbolo ! si chiamafattoriale e assume la seguente forma:

n! =

{

1 n = 0

1 · 2 · . . . · (n − 1) · n =∏

n

i=1 i n ≥ 1

Esercizio 1 (1)

Sei atleti partecipano ad una gara di corsa.

• Quante possono essere le classifiche finali della gara?– Poiché la classifica finale non sarà altro che una

permutazione della lista dei partecipanti, ci sono

P (6) = 6! = 720 ordini di arrivo possibili.

• Quanti bit servono per codificare l’ordine di arrivo?– Per codificare in binario 720 configurazioni possibili, servono

almeno dlog2720e = 10 bit.

Questo ragionamento fornisce il minimo numerodi bit da utilizzare, ma non dice come effettuarela codifica.



Esercizio 1 (2)

Si può immaginare una codifica del genere:• ogni atleta è descritto dal suo pettorale (i numeri da1 a 6);

• l’ordine di arrivo è rappresentato da una sequenza disei numeri di pettorale.

In tal caso:• ogni atleta necessita di 3 bit (dlog26e = 3);

• la codifica della classifica richiede 6 × 3 = 18 bit.

La codifica scelta non sarebbe quella di ingombrominimo (10 bit), ma sarebbe semplice dacostruire e utilizzare.

Disposizioni (1)

Si dice disposizione semplice di n elementidistinti su k posizioni (n, k ∈ N, 0 < k ≤ n) unacollezione di k degli n elementi che rispetti leseguenti proprietà:

1. ciascun raggruppamento contiene k elementi;

2. uno stesso elemento può figurare al più una volta inun raggruppamento;

3. due raggruppamenti sono da considerarsi distintiquando essi differiscono per almeno un elemento, oper l’ordine degli elementi.



Disposizioni (2)

Le disposizioni semplici di n elementi presi k pervolta sono in totale n!

(n−k)!:

D(n, k) = n!(n−k)!

= n · (n − 1) · . . . · (n − k + 1)

Esercizio 2

Sei atleti partecipano ad una gara di corsa.• In quanti modi diversi si può verificare la tripletta diatleti che arriva sul podio?– La classifica dei primi 3 arrivati è una disposizione di 6

elementi su 3 posti: ci possono essere D(6, 3) = 6 · 5 · 4 =

= 120 configurazioni diverse di atleti sul podio.

• Quanti bit servono per codificare il podio?– Per rappresentare 120 configurazioni diverse servono

dlog2120e = 7 bit.



In sintesi

Per calcolare il numero di bit necessario perdescrivere una situazione dobbiamo conoscere ilnumero di configurazioni possibili.

Il calcolo combinatorio permette di modellare lamaggior parte delle situazioni reali mediante:

• permutazioni;

• disposizioni.

Prossimi passi

Altri casi di calcolo combinatorio:

• disposizioni con ripetizione;

• combinazioni;

• combinazioni con ripetizione.



Chiusura



Lezione 2 - Altri elementi di calcolocombinatorio




Stefano Ferrari


Disposizioni con ripetizione (1)

Si dice disposizione con ripetizione (oreimmissione) di n elementi distinti su k

posizioni (n, k ∈ N, n > 0, k > 0) una collezione dik degli n elementi che rispetti le seguentiproprietà:


2. due qualsiasi raggruppamenti sono da considerarsidistinti quando essi differiscono per almeno unelemento, o per l’ordine degli elementi.



Disposizioni con ripetizione (2)

Rispetto ad una disposizione semplice, quindi, inuna disposizione con ripetizione ogni elementopuò essere ripetuto.

Le disposizioni con ripetizione di n su k saranno:

Dr(n, k) = nk

Esercizio 3

Sei atleti sono impegnati in una gara di triathlon.

• Quante terne dei vincitori in ogni singola gara sipossono verificare?– Poiché ogni atleta può vincere più di una gara, il numero

cercato sono le disposizioni con ripetizione di sei elementi su

tre posizioni: Dr(6, 3) = 63 = 216.

• Quanti bit servono per codificare tale tripletta?– Per codificare tale classifica, serviranno almeno

dlog2216e = 8 bit.



Combinazioni (1)

Si dice combinazione semplice di n elementidistinti su k posizioni (n, k ∈ N, 0 < k ≤ n) unacollezione di k degli n elementi che rispetti leseguenti proprietà:


2. uno stesso elemento può figurare al più una volta inun raggruppamento;

3. due raggruppamenti sono da considerarsi diversisoltanto quando differiscono tra loro almeno per unelemento.

Combinazioni (2)

L’ordine degli elementi non ha importanza in unacombinazione.

Le combinazioni semplici di n elementi su k postisono:

C(n, k) = D(n,k)

P (k)= n·(n−1)· ··· (n−k+1)

k!

La quantità n!(n−k)! k!

è il coefficiente binomiale di n

su k, e viene indicato con:(

n

k

)



Esercizio 4

Un negozio ha in vetrina lo spazio per esporresolo tre manichini ed un campionario di settemodelli di giacca.

• Volendo mettere una giacca diversa su ognimanichino, quante vetrine può comporre?– Si tratta di calcolare le combinazioni semplici di 7 elementi

su 3 posti: C(7, 3) = 7·6·5

3·2= 7 · 5 = 35.

• Quanti bit servono per codificare tale composizione?– Sono necessari dlog

235e = 6 bit.

Combinazioni con ripetizione (1)

Si dice combinazione con ripetizione (o conreimmissione) di n elementi distinti su k

(n, k ∈ N, n > 0, k > 0) posizioni una collezione dik degli n elementi che rispetti le seguentiproprietà:


2. due raggruppamenti sono da considerarsi diversisoltanto quando differiscono tra loro almeno per unelemento.



Combinazioni con ripetizione (2)

Uno stesso elemento può quindi comparire più diuna volta.

Le combinazioni con ripetizione di n elementi suk posti sono:

Cr(n, k) = C(n + k − 1, k) =(

n+k−1

k

)

Esercizio 5

Un negozio ha in vetrina lo spazio per esporresolo tre manichini ed un campionario di settemodelli di giacca.

• Quante vetrine potrebbe comporre, se ritenesseaccettabile avere più copie della stessa giacca invetrina?– In questo caso, si tratta di calcolare le combinazioni con

ripetizione di 7 elementi su 3 posti:

Cr(7, 3) = C(9, 3) = 9·8·7

3·2= 3 · 4 · 7 = 84.

• Quanti bit servono per codificare tale composizione?– Sono necessari dlog

284e = 7 bit.



Riassumendo

Le permutazioni dicono in quanti modi possiamoscrivere la sequenza degli elementi di un insiemedato.

Le disposizioni e le combinazioni dicono in quantimodi si possono scrivere sequenze disottoinsiemi di cardinalità data.

La differenza tra combinazioni e disposizioni èche queste ultime tengono in considerazioneanche l’ordine degli elementi.

In sintesi

Per calcolare il numero di bit necessario perdescrivere una situazione dobbiamo conoscere ilnumero di configurazioni possibili.

Il calcolo combinatorio permette di modellare lamaggior parte delle situazioni reali mediante:

• permutazioni;

• disposizioni (con ripetizione);

• combinazioni (con ripetizione).



Prossimi passi

Un po’ di esercizi sulla codifica binaria.

Chiusura



Lezione 3 - Esercizi sulla codificabinaria (parte 1)




Stefano Ferrari


Contare con le dita

D Fino a quanto si può contare usando solo le dita didue mani?

R Ipotizzando che ogni dito possa assumere solodue posizioni (disteso o chiuso):– si hanno 10 elementi indipendenti;

– ogni elemento può assumere due configurazioni;

– il numero di configurazioni totali è 210 = 1024.

Si può quindi contare da 1 a 1024 (o da 0 a1023!).



Colori

D Quanti colori possono essere rappresentati in unacodifica RGB a 1 byte per canale?

R Ognuno dei canali (R, G e B) ha a disposizione 8bit.

In totale, dunque, 8 × 3 = 24 bit.

Sono quindi rappresentabili 224 = 16 777 216

colori.

La codifica a 24 bit è chiamata comunemente “a16 milioni di colori”.

Dimensione di una immagine digitale

D Quanti bit servono per rappresentare un’immagine1024 × 768 a colori, 8 bit per canale colore?

R I pixel sono 1024 × 768 = 786 432.

Ogni pixel è rappresentato da 3 colori (rosso,verde e blu) e ogni colore occupa 8 bit.

Una immagine così fatta, occupa quindi:786 432 × 3 × 8 = 18 874 368 bit.

Essi equivalgono a 18 874 368/8 = 2 359 296 byte.

Cioè 2 359 296/1024 = 2304 kiB (kibibyte).

O 2304/1024 = 2, 25 MiB (mebibyte).



Codifica per le carte da briscola

D Quale può essere una buona codifica per le cartedi un mazzo da briscola?

R Poiché il mazzo di carte da briscola è composto da40 carte, si dovranno utilizzare 6 bit:– 5 ≤ log

240 ≤ 6;

– 5 bit sarebbero troppo pochi.

Uno dei modi di ottenere una codifica è individuareuna enumerazione degli elementi dell’insieme darappresentare e poi tradurre in binario tali valori.

Enumerazione per le carte da briscola

Per esempio, poiché il mazzo di carte da briscolaè composto 10 carte per ognuno dei 4 semi, sipuò scegliere:

seme carte ordine codifica

bastoni asso, 2–7, fante, cavallo, re 0–9 000000–001001

coppe asso, 2–7, fante, cavallo, re 10–19 001010–010011

denari asso, 2–7, fante, cavallo, re 20–29 010100–011101

spade asso, 2–7, fante, cavallo, re 30–39 011110–100111

L’enumerazione proposta sarebbe una buonacodifica in decimale: la prima cifra rappresenta ilseme (0–3) e la seconda il valore (0–9).



Codifica per le carte da briscola

Una codifica migliore può essere ottenutautilizzando le prime due cifre binarie perrappresentare il seme, e le rimanenti per ilvalore:

seme carte codifica

bastoni asso, 2–7, fante, cavallo, re 00 0000 – 00 1001

coppe asso, 2–7, fante, cavallo, re 01 0000 – 01 1001

denari asso, 2–7, fante, cavallo, re 10 0000 – 10 1001

spade asso, 2–7, fante, cavallo, re 11 0000 – 11 1001

Il vantaggio di questa codifica rispetto allaprecedente è la facilità di codifica/decodifica.

Riassumendo ...

Una carta è caratterizzata da seme e valore.

Ogni seme può assumere 4 configurazioni,mentre ogni valore può assumere 10configurazioni.

oggetto #config. #bit

seme 4 2

valore 10 4

carta 4 × 10 = 40 6

La codifica “seme+valore” usa lo stesso numerodi bit della codifica “carta”, ma non è una regolagenerale.



Codifica per le automobili

Un’auto è prodotta in 3 motorizzazioni e 10colori.

Quanti bit sono necessari per descrivere unmodello di questa automobile?

oggetto #config. #bit

motore 3 2

colore 10 4

automobile 3 × 10 = 30 5

In questo caso, la codifica “motore+colore” è piùingombrante della codifica “automobile”.

Regola generale

Sebbene:

logbmn = log

bm + log

bn

In generale:

dlogbmne ≤ dlog

bme + dlog

bne



Prossimi passi

Ancora esercizi sulla codifica binaria.

Chiusura



Lezione 4 - Esercizi sulla codificabinaria (parte 2)




Stefano Ferrari


Una mano a briscola

D Quanti bit servono per codificare una mano dibriscola?

R Una mano di briscola è composta da tre carte(diverse tra loro) prese da un mazzo di carte.

Una mano di briscola è quindi equivalente ad unacombinazione di quaranta oggetti su tre posizioni.

Poiché C(40, 3) = 40!

37!·3!= 40·39·38

3·2= 9880,

serviranno dlog2 9880e = 14 bit.

Nota: ripetere tre volte la codifica della singolacarta richiede 18 bit.



Rappresentare elementi e insiemi (1)

D Gli oggetti sotto riportati sono elementi dellecomuni interfacce grafiche. Come rappresentare inbinario gli stati di tali oggetti?

# Qui

� Quo

# Qua

4 Qui

2 Quo

4 Qua

Radio button Check box

R I radio button permettono di selezionare uno solodegli n elementi della lista, mentre le check boxconsentono di selezionare un sottoinsieme degli nelementi della lista.


Quante configurazioni diverse può assume un gruppodi n radio button?

Solo una voce può essere attiva.

Quindi, il numero di configurazioni sarà pari a n.

Pertanto, saranno necessari dlog2 ne bit.

Nel caso in esame, useremo 2 bit per i radio button.




Lo stato di un gruppo di check box equivale ad unsottoinsieme delle voci.

Il numero di sottoinsiemi di un insieme di n elementiè 2n.

È necessario dedicare un bit per ogni voce perindicare se essa è attiva o no.

Pertanto, saranno necessari n bit.

Nel caso in esame, useremo 3 bit per i check box.


Enumeriamo le voci come di seguito riportato:

# Qui

� Quo

# Qua

0

1

2

4 Qui

2 Quo

4 Qua

Possiamo individuare le seguenti codifiche:

Radio button: la posizione della voce attiva (1) sipuò codificare con la stringa binaria 01;

Check box: ponendo ad 1 i bit corrispondenti allevoci attive ed a 0 gli altri:

posizione 2 1 0valore 1 0 1



Gelateria (1)

Una gelateria dispone di 12 gusti di gelato, 5guarnizioni e 2 contenitori.

I gelati che vende sono sempre composti da uncontenitore, 3 gusti e 2 guarnizioni.

I contenitori sono divisi in tre scomparti asimmetrici.

Le guarnizioni vengono distribuite uniformemente sulgelato.

Calcolare i bit necessari per codificare:

a) i singoli elementi (gusti, guarnizioni, contenitori);

b) un gelato.

Gelateria (2)

a) Codifica dei singoli elementi (gusti, guarnizioni,contenitori):• 12 gusti → dlog2 12e = 4 bit;

• 5 guarnizioni → dlog2 5e = 3 bit;

• 2 contenitori → dlog2 2e = 1 bit.



Gelateria (3)

b) Codifica del gelato (3 gusti, 2 guarnizioni, 1contenitore).

I gusti possono essere ripetuti e l’ordine èimportante:Dr(12, 3) = 123 configurazioni.

Anche le guarnizioni possono essere ripetute, manon importa l’ordine:Cr(5, 2) = C(6, 2) = 15 configurazioni.

Il contenitore può essere solo uno:2 configurazioni.

Perciò si possono avere 123 · 15 · 2 possibili gelati.

Gelateria (4)

b) Codifica del gelato (3 gusti, 2 guarnizioni, 1contenitore).

Con qualche passaggio matematico:123 · 15 · 2 = 27 · 33 · 15 = 27 · 405

Serviranno quindi:dlog2 27 · 405e = dlog2 27 + log2 405e=d7 + log2 405e = 7 + dlog2 405e = 7 + 9 = 16 bit.



Prossimi passi

Una formalizzazione del concetto diinformazione.

Chiusura



Lezione 1 - Natura dell’informazione



Unità didattica 4 - Teoria dell’Informazione

Stefano Ferrari


Informazione

Il termine “informazione” è usato in molticontesti e con molte accezioni.

Portano informazione:

• una certa distribuzione di gocce di inchiostro su unfoglio;

• una certa sequenza di lettere dell’alfabeto;

• una certa sequenza di parole della lingua italiana.



Informazione

Si individuano diversi livelli di informazione:

• sintattico:– l’informazione sintattica è legata alle configurazioni del

supporto fisico;

• semantico:– l’informazione semantica è legata al significato attribuibile

alle diverse configurazioni del supporto fisico;

• pragmatico:– l’informazione pragmatica è legata al valore attribuibile alle

diverse configurazioni del supporto fisico.

Teoria dell’informazione

La branca dell’informatica nota come

teoria dell’informazione

studia l’informazione di tipo sintattico.



Misura dell’informazione (1)

Qual’è la natura dell’informazione?

Come si può misurare l’informazione?

Per rispondere a queste domande proviamo adanalizzare alcuni casi.


Poniamo il caso di dover comunicare se undeterminato evento è accaduto oppure no.

Consideriamo le seguenti modalità percomunicare l’evento:

1. organizziamo un falò da qualche decina di metricubi di legna;

2. accendiamo un cerino.

Quale modalità trasferisce più informazione?




La risposta è chiara: sia chi vede il cerino, sia chivede il falò hanno la stessa informazione.

Quindi, si può trarre una prima conclusione:

la quantità di informazione dipende dall’evento,non dal mezzo di comunicazione!


Consideriamo ora le seguenti domande:

a) Quanti sono i sette nani?

b) Quale lato della moneta che ho appena lanciato èuscito?

Quale risposta fornisce più informazione?




La risposta alla domanda a) è conosciuta.

La risposta alla domanda b), magari non èinteressante, ma toglie un dubbio.

Possiamo trarre una seconda conclusione:

l’informazione è legata all’incertezza.

In sintesi

L’informazione:

• è di diversi tipi;

• è legata all’incertezza.



Prossimi passi

Una formalizzazione del concetto diinformazione.

Chiusura



Lezione 2 - Elementi di teoriadell’Informazione



Unità didattica 4 - Teoria dell’Informazione

Stefano Ferrari


Misura dell’informazione

Ipotizziamo un messaggio che contenga unsimbolo x scelto da un insiemeX = {xi | 1 ≤ i ≤ n} di n simboli (detto alfabeto).

Attraverso una funzione I(·), vorremmo misurarel’informazione contenuta nel messaggio, I(x).

Quali proprietà deve avere la funzione I(·)?



Proprietà dell’informazione (1)

L’informazione portata da una sequenza disimboli deve essere la somma dell’informazioneportata dai singoli simboli che compongono lasequenza stessa:

I(xixj) = I(xi) + I(xj)


Se il simbolo xi è meno frequente (o menoprobabile) del simbolo xj, l’informazione portatada xi deve essere maggiore dell’informazioneportata da xj:

p(xi) ≤ p(xj) ⇒ I(xi) ≥ I(xj)




Se due simboli sono equiprobabili, l’informazioneda essi portata deve essere la stessa:

p(xi) = p(xj) ⇒ I(xi) = I(xj)


Se è certo che un dato simbolo apparirà sulmessaggio, allora l’informazione portata dalmessaggio è nulla:

p(xi) = 1 ⇒ I(xi) = 0




Meno probabile è un simbolo, maggiore èl’informazione da esso portata:

p(xi) → 0 ⇒ I(xi) → ∞

Funzione informazione

Una funzione che gode delle precedenti proprietàè:

I(x) =

{

− log2

p(x) p(x) > 0

0 p(x) = 0

Questa funzione ha il vantaggio di valere 1 sel’insieme di simboli portabili dal messaggio ècostituito da soli due simboli equiprobabili.

In tal caso, ogni messaggio porta 1 bit!



Bit e informazione (1)

A questo punto ci sono due significati per iltermine bit:

• unità di misura della capacità (o dell’ingombro) diuna rappresentazione binaria;

• unità di misura dell’informazione.

Bit e informazione (2)

Per codificare 256 simboli equiprobabili, si usano8 cifre binarie.

Ogni cifra binaria porta 1 bit di informazione.

Se i simboli non fossero equiprobabili, alcunecifre potrebbero portare (in media) più di 1 bit, ealtre meno di 1 bit.



Indovinare un numero (1)

Esempio

Regole del gioco “Indovina il numero”:

1. una persona pensa un numero tra 1 e 128;

2. per scoprire tale numero gli si possono fare delledomande;

3. a tali domande, la persona può rispondere solo “Sì”o “No”.

Qual è il numero minimo di domande necessarieper indovinare il numero nascosto?

Indovinare un numero (2)

Risposta: 7.

Traccia:• la conoscenza del numero porta 7 bit diinformazione;

• con ogni domanda possiamo ottenere 1 bit diinformazione.



Approfondimento

Sciuto ed altri, "Introduzione ai sistemiInformatici", McGraw Hill, 1997, secondaedizione: capitolo 3, (pagg. 63–107).

• stessi argomenti del Modulo 2, trattati in ordineinverso;

• cenni di teoria della trasmissione.

In sintesi

L’informazione:

• è legata all’incertezza;

• si misura in bit.



Chiusura



Lezione 1 - Cenni di insiemistica


Modulo 3 - Elaborazione delle informazioni

Unità didattica 1 - Insiemistica

Stefano Ferrari


Teoria degli insiemi

Insieme: collezione arbitraria di elementi reali eimmaginari.

Esempi:

• {1, 2, 4, 7} descrizione intensionale

• {x | x ≤ 5} descrizione estensionale



Descrizione grafica di un insieme

1 24

7 diagrammi di Venn

5

grafi cartesiani

Insiemi particolari

L’insieme universo, U, contiene ogni elemento.

L’insieme vuoto, ∅ = {}, non contiene alcunelemento.



Insieme universo

L’insieme universo deve essere definito all’iniziodi ogni trattazione.

Esempio:

A = {numeri minori di 3}

• U ≡ N ⇒ A1 = {numeri naturali minori di 3}

• U ≡ Z ⇒ A2 = {numeri interi minori di 3}

• U ≡ R ⇒ A3 = {numeri reali minori di 3}

Operatori (1)

L’appartenenza, ∈, indicache un elemento appartienead un dato insieme:

a ∈ A

a

A

L’unione, ∪, compone dueinsiemi considerando glielementi di entrambi:

A ∪ B

A B



Operatori (2)

L’intersezione, ∩, componedue insiemi considerandosolo gli elementi comuni:

A ∩ B

A B

Il complemento, · , èl’insieme composto da tuttigli elementi che nonappartengono all’insiemedato:

A

AA

Operatori (3)

La differenza, −, componedue insiemi considerando glielementi del primo che nonappartengono al secondo:

A − B

A B

Il sottoinsieme, ⊆, indicache ogni elemento del primoinsieme appartiene anche alsecondo:

A ⊆ B

A

B



Operatori (4)

La cardinalità, | · | di un insieme è il numero dei suoielementi:

|A|

Esempio:– se A = {a, b, c}, allora |A| = 3

– |∅| = 0

Operatori (5)

L’insieme delle parti di un dato insieme, P(·), èl’insieme dei suoi sottoinsiemi:

P(A)

Esempio:– se A = {a, b, c}, allora

P(A) = {∅, {a}, {b}, {c}, {a, b}, {a, c}, {b, c}, A}

L’insieme delle parti di A ha cardinalità pari a 2|A|.

Per questo motivo viene anche chiamato insiemepotenza e viene indicato con 2A.



Proprietà degli operatori (1)

• IdempotenzaA ∪ A = A

A ∩ A = A

• CommutativitàA ∩ B = B ∩ A

A ∪ B = B ∪ A

• AssociativitàA ∩ (B ∩ C) = (A ∩ B) ∩ C

A ∪ (B ∪ C) = (A ∪ B) ∪ C

Proprietà degli operatori (2)

• DistributivitàA ∩ (B ∪ C) = (A ∩ B) ∪ (A ∩ C)

A ∪ (B ∩ C) = (A ∪ B) ∩ (A ∪ C)

• AssorbimentoA ∩ (A ∪ B) = A

A ∪ (A ∩ B) = A

• Doppio complementoA = A

• Leggi di De MorganA ∩ B = A ∪ B

A ∪ B = A ∩ B



Descrizione ricorsiva di un insieme

Anche detta induttiva.

Esempio:

A = {x | x = 1 o x = 2 + y, y ∈ A}

Servono:

• elementi base;

• operazioni per individuare i nuovi elementi in base adalcuni elementi che già appartengono all’insieme.

L’insieme descritto è dato dalla chiusuradell’insieme base rispetto alle operazioni dellaregola ricorsiva.

Insiemi, bag e sequenze

Insieme {1, 2, 3} ≡ {1, 3, 2} ≡ {1, 3, 2, 3}

Bag {1, 2, 3} ≡ {1, 3, 2} 6≡ {1, 3, 2, 3}

Sequenza 〈1, 2, 3〉 6≡ 〈1, 3, 2〉 6≡ 〈1, 3, 2, 3〉



In sintesi

L’insiemistica è alla base della formalizzazionedella matematica moderna.

Vanno ricordati i seguenti concetti:

• operatori insiemistici;

• loro proprietà.

Chiusura



Lezione 2 - Funzioni



Unità didattica 1 - Insiemistica

Stefano Ferrari


Prodotto cartesiano

Il prodotto cartesiano A × B degli insiemi A e B èformato dalla combinazione degli elementi di A eB.

Esempio:

A = {a, b, c} B = {1, 2}

A × B = {〈a, 1〉, 〈a, 2〉, 〈b, 1〉,〈b, 2〉, 〈c, 1〉, 〈c, 2〉}

A

B

a b c

1

2



Funzione

Una funzione f : A → B è una regola perabbinare ad ogni elemento a dell’insieme A unelemento f(a) dell’insieme B.

A è il dominio di f

B è il codominio di f

a è detto argomento

f(a) è la sua immagine

A B

a f(a)

f

A

Bf

a

f(a)

Funzioni: esempi

square : Z → N, square(x) = x2

Esiste x tale per cui square(x) = 5?

Per quale x vale square(x) = 9?

abs : Z → N, abs(x) =

{

+x, x ≥ 0

−x, x < 0

g : Z → N, g(x) = 2x2 + x

I : U → U , I(u) = u



Funzioni suriettive

Una funzione si dice suriettiva se ogni elementodel codominio è immagine di un elemento deldominio.

Funzioni iniettive

Una funzione si dice iniettiva se ad elementidistinti del dominio corrispondono immaginidistinte nel codominio.



Funzioni biiettive

Una funzione si dice biiettività se la funzione èsuriettiva ed iniettiva.

Funzione inversa

Una funzione biiettiva f : A → B comporta:

• corrispondenza uno ad uno tra gli elementi di A equelli di B;

• esistenza della funzione inversa f−1 : B → A.



Composizione di funzioni

La composizione di due funzioni è l’applicazionedi una al risultato dell’altra.

Siano date le funzioni f e g:

f : A → B e g : B → C

Componendo f con g si ottiene la funzione h:

h : A → C, h(a) = g(f(a))

La composizione di una funzione e della suainversa dà la funzione identità, I:

f(f−1(a)) = a

Funzioni a più argomenti

f : A → Bè una funzione unaria (monadica)

f : A1 × A2 → Bè una funzione binaria (diadica)

f : A1 × A2 × A3 → Bè una funzione ternaria (triadica)

f : A1 × · · · × An → Bè una funzione n-aria (n-adica)



In sintesi

L’insiemistica è alla base della formalizzazionedella matematica moderna.

Vanno ricordati i seguenti concetti relativi allefunzioni:

• suriettività;

• iniettività.

• biiettività.

Chiusura



Lezione 1 - Algebre di Boole



Unità didattica 2 - Algebre di Boole

Stefano Ferrari


George Boole (1815–1864)

Nel 1854, pubblica “An investigationinto the Laws of Thought, on Whichare founded the MathematicalTheories of Logic and Probabilities”.

Boole riduce la logica a semplicealgebra, incorporandola nellamatematica.

Evidenzia l’analogia tra i simboli algebrici e quellidelle forme logiche.

L’algebra booleana trova applicazioni nellaprogettazione dei calcolatori.



Algebra booleana

Un’algebra booleana è basata su:

• un insieme di elementi K

• due operazioni chiuse su K (+, ·)

• una funzione complemento ( · )

Assiomi (1)

1. almeno due elementi

∃ a, b ∈ K : a 6= b

2. chiusura di + e ·

∀ a, b ∈ K :

• a + b ∈ K

• a · b ∈ K



Assiomi (2)

3. proprietà commutativa

∀ a, b ∈ K :

• a + b = b + a

• a · b = b · a

4. proprietà associativa

∀ a, b, c ∈ K :

• (a + b) + c = a + (b + c) = a + b + c

• (a · b) · c = a · (b · c) = a · b · c

Assiomi (3)

5. esistenza degli elementi neutri di + e ·

• ∃! 0 ∈ K : a + 0 = a, ∀ a ∈ K

• ∃! 1 ∈ K : a · 1 = a, ∀ a ∈ K

6. proprietà distributiva

∀ a, b, c ∈ K :

• a + (b · c) = (a + b) · (a + c)

• a · (b + c) = (a · b) + (a · c)



Assiomi (3)

7. complemento

∀ a ∈ K ∃ a ∈ K :

• a + a = 1

• a · a = 0

Proprietà

Idempotenza a + a = a e a · a = a

Leggi di De Morgan a + b = a · b e a · b = a + b

Doppio complemento a = a

Elemento nullo a + 1 = 1 e a · 0 = 0

Tali proprietà possono essere verificate per:

• dimostrazione;

• analisi esaustiva.



Principio di dualità

I teoremi dell’algebra booleana possono esseredimostrati a coppie, scambiando tra loro:

• le operazioni, + ↔ ·;

• gli elementi neutri, 0 ↔ 1.

Teorema di De Morgan (1)

La legge di De Morgan può essere generalizzata an termini.

X1 + X2 + . . . + Xn = X1 · X2 · . . . · Xn

Dimostrazione per induzione:• caso base:

– si dimostra vero il caso con il numero minimo di elementi;

• passo di induzione:

– si ipotizza vero il teorema per n − 1 elementi;

– si utilizza l’ipotesi aggiuntiva per dimostrare il teorema per n

elementi.



Teorema di De Morgan (2)

Dimostrazione per induzione:• caso base:

X1 + X2 = X1 · X2 (Legge di De Morgan)

• passo di induzione:

Se per ipotesi, è vero che:

X1 + . . . + Xn−1 = X1 · . . . · Xn−1

allora:

(X1 + . . . + Xn−1) + Xn=

= (X1 + . . . + Xn−1) · Xn = X1 · . . . · Xn−1 · Xn

Cardinalità

Si può dimostrare che in ogni algebra booleanafinita, il numero di elementi di K è una potenzadi due.



Esempi

Sono algebre di Boole:

• algebra binaria

• algebra di insiemi

• lo spazio degli eventi (calcolo delle probabilità)

• circuiti logici

• logica proposizionale

In sintesi

Le algebre booleane:

• sono uno strumento matematico per laformalizzazione del ragionamento;

• sono regolate da 7 assiomi.



Prossimi passi

Algebre booleane e loro applicazioni:

• logica proposizionale;

• logica dei predicati (cenni);

• circuiti logici.

Chiusura



Lezione 1 - Logica proposizionale



Unità didattica 3 - Logica proposizionale

Stefano Ferrari


Logica formale

La logica formale è una branca della matematicache studia i principi su cui si basa laformalizzazione di asserzioni e delle regole diinferenza.

Semplificando, si può dire che la logica formalepermette una formalizzazione del“ragionamento”.



Formalizzazione

Formalizzare significa tradurre dal linguaggionaturale in un linguaggio semplificato con unasintassi rigida e precisa.

Un linguaggio con regole rigide serve:

• per comunicare con le macchine;

• per comunicare con altre persone;

• per progettare algoritmi.

Questo procedimento è necessario in moltediscipline.

Logiche

Ambiti diversi hanno esigenze diverse.

A seconda della necessità ci si può appoggiare,fra le altre, alla logica:

• classica: studia i processi per trarre conclusioni apartire da assunzioni;

• intuizionista: basata su un approccio costruttivo,utile per esigenze pratiche di realizzazione;

• temporale: arricchita da operatori per indicareintervalli temporali;

• fuzzy: infinite gradazioni di verità.



Logica proposizionale

La logica proposizionale studia gli schemi dicomposizione di frasi dichiarative.

Queste frasi saranno chiamate proposizioni.

La logica non indaga sul significato delle singoleproposizioni, ma solo sugli schemi in cui leproposizioni possono essere composte medianteoperatori detti connettivi logici.

Si occupa di stabilire la verità o la falsità diasserzioni (espressioni linguistiche) ottenutecomponendo proposizioni semplici.

Linguaggio formale

Bisogna stabilire:

• cosa si vuole formalizzare;

• alfabeto:

elementi simbolici usati per la rappresentazione;

• sintassi:

come si rappresentano gli oggetti del discorso;

• semantica:

quale significato si dà a tali rappresentazioni.



Alfabeto

Le proposizioni sono costruite usando:

• costanti (valori di verità): {F, V }

(indicati anche come: {F, T}, {0, 1}, {⊥, >})

• simboli enunciativi: {a, b, . . . , z}

• connettivi: ¬, ∧, ∨, →, ↔

• simboli ausiliari: “(”, “)”

Proposizioni semplici

Una proposizione semplice (o atomica) èun’affermazione che:

• non dipende da variabili;

• può essere vera o falsa;

• viene formalizzata da un simbolo enunciativo.

Esempi:

• ogni triangolo si può inscrivere in un cerchio vera

• Roma è in Francia falsa

NB: non interessa il significato delle proposizioni,solo se sono vere o false.



Connettivi (1)

Le proposizioni semplici sono composte permezzo dei connettivi logici:

• congiunzione: ∧, et, AND, e

a ∧ b è vera se lo è sia a che b;

• disgiunzione: ∨, vel, OR, o

a ∨ b è vera quando lo è almeno uno fra a e b;

• negazione: ¬, ∼, non, NOT, non

¬a è vera quando a è falsa;

Connettivi (2)

• implicazione (condizionale): →, se ... allora

a → b ≡ ¬a ∨ b;

a viene detta premessa e b conseguenza;

• biimplicazione (bicondizionale): ↔, se e solo se

a ↔ b ≡ (a → b) ∧ (b → a) ≡ (a ∧ b) ∨ (¬a ∧ ¬b).



Proposizioni composte

Una proposizione composta può essere:

• sempre vera;

• sempre falsa;

• vera o falsa in funzione dei componenti.

Esempi:

• a ∨ ¬a vera

• a ∧ ¬a falsa

• a ∧ b da valutare

In sintesi

La logica formale:

• fornisce un linguaggio non ambiguo e con unastruttura rigida;

• può essere usata per descrivere concetti, situazioni eprocedure.

La logica proposizionale studia:

• i connettivi;

• gli schemi di composizione.



Prossimi passi

Formalizzazione di sintassi e semantica dellalogica proposizionale.

Inferenza di asserzioni valide.

Chiusura



Lezione 2 - Sintassi e semantica dellalogica proposizionale




Stefano Ferrari


Sintassi (1)

Le proposizioni (o formule) sono definiteinduttivamente dalle regole:

• caso base: ogni simbolo enunciativo o costante èuna formula;

• passo: ogni composizione di formule è una formula;

• nient’altro è una formula.



Sintassi (2)

Più formalmente, detto L l’insieme dei simbolienunciativi e delle costanti, l’insieme P delleproposizioni è così definito:

• ∀a ∈ L, (a) ∈ P

• ∀p ∈ P, ¬(p) ∈ P

• ∀p, q ∈ P, (p ∨ q), (p ∧ q), (p → q), (p ↔ q) ∈ P

Precedenze

Le precedenze permettono di ridurre il numero diparentesi necessarie per interpretarecorrettamente una proposizione.

¬ precede ∧ precede ∨ precede → precede ↔

Esempi:

• ((¬a) ∨ a) si può scrivere ¬a ∨ a

• (a ∨ (b ∧ c)) si può scrivere a ∨ b ∧ c

• (a ∧ (b ∨ c)) si può scrivere a ∧ (b ∨ c)



Semantica

La semantica è l’insieme delle regole chepermettono di associare un valore di verità aduna proposizione, a partire dai valori dei simbolienunciativi che vi compaiono.

La semantica dei connettivi è illustrata dalleseguenti tabelle, dette tabelle di verità:

a b a ∨ b a ∧ b ¬a a → b a ↔ b

F F F F V V V

F V V F V V F

V F V F F F F

V V V V F V V

Interpretazione (1)

Diremo interpretazione di una proposizione unafunzione che assegna uno dei due valori di verità,V o F , a ciascuna proposizione atomicacomponente e che quindi assegna un valore diverità alla proposizione composta sulla basedelle tavole di verità.

Formalmente, quindi, una interpretazione è unafunzione v : P → {F, V }.

L’interpretazione di una proposizione p puòessere calcolata mediante la costruzione dellatabella di verità di p.



Interpretazione (2)

Esempio: ¬p ∧ (q → p)

p q ¬p q → p ¬p ∧ (q → p)

F F V V V

F V V F F

V F F V F

V V F V F

Ogni riga di una tabella di verità è unainterpretazione.

Se una proposizione ha n componenti atomici,esistono 2n interpretazioni per essa.

Soddisfacibilità

Se una interpretazione, v(·), rende unaproposizione, p, vera (v(p) = V ), si dice che v

soddisfa p.

Una proposizione, p, si dice soddisfacibile seesiste almeno una interpretazione, v(·), che lasoddisfa.

Una proposizione, p, si dice tautologia (o ancheche è valida) se tutte le sue interpretazionipossibili la rendono vera: ∀v, v(p) = V .

Una proposizione non soddisfacibile (cioè resafalsa da tutte le interpretazioni possibili) vienedetta contraddizione.



Relazioni tra proposizioni

Implicazione logica :

a implica logicamente b se e solo se a → b èuna tautologia: a ⇒ b

Equivalenza logica :

a è logicamente equivalente a b se e solo sea ↔ b è una tautologia: a ⇔ b

NB: a ⇒ b e a ⇔ b sono relazioni tra laproposizione a e la proposizione b.

Ad esse sono associabili rispettivamente leproposizioni a → b e a ↔ b.

In sintesi

Sono state definite in modo ricorsivo la sintassi ela semantica della logica proposizionale.

Sono state definiti i concetti di interpretazione esoddisfacibilità delle forme logiche.



Prossimi passi

Schemi di inferenza.

Chiusura



Lezione 3 - Inferenza e dimostrazioni




Stefano Ferrari


Leggi logiche (1)

Le tautologie sono chiamate anche leggi logiche.

• Eliminazione di congiunzione

(a ∧ b) ⇒ a

• Introduzione di disgiunzione

a ⇒ (a ∨ b)

• Negazione della biimplicazione

¬(a ↔ b) ⇔ (¬a ↔ b)



Leggi logiche (2)

• Sillogismo disgiuntivo

(a ∨ b) ∧ ¬b ⇒ a

• Ex falso sequitur quodlibet

¬a ⇒ (a → b)

• Verum sequitur a quodlibet

a ⇒ (b → a)

• Terzo escluso

a ∨ ¬a

Leggi logiche (3)

• Non contraddizione

¬(a ∧ ¬a)

• Dimostrazione per casi

((a → b) ∧ (¬a → b)) ⇒ b

• Dimostrazione per assurdo

(¬b → a ∧ ¬a) ⇒ b

• Contrapposizione

a → b ⇔ ¬b → ¬a

• (De Morgan)¬(a ∧ b) ⇔ (¬a ∨ ¬b)

¬(a ∨ b) ⇔ (¬a ∧ ¬b)

• (Sillogismo ipotetico)((a → b) ∧ (b → c)) ⇒ (a → c)

(a → b) ⇒ ((b → c) → (a → c))

• (a → (b ∧ c)) ⇔ ((a → b) ∧ (a → c))



Leggi logiche (4)

• Leggi di De Morgan

¬(a ∧ b) ⇔ (¬a ∨ ¬b)¬(a ∨ b) ⇔ (¬a ∧ ¬b)

• Sillogismo ipotetico

((a → b) ∧ (b → c)) ⇒ (a → c)

• Transitività dell’implicazione

(a → b) ⇒ ((b → c) → (a → c))

Leggi logiche (5)

• Distributività delle conseguenze

a → (b ∧ c) ⇔ (a → b) ∧ (a → c)

• Esportazione/importazione delle premesse

(a ∧ b) → c ⇔ a → (b → c)

• Doppia negazione

¬¬a ⇔ a



Teoremi

Un teorema della logica proposizionale ècomposto da:

• una o più proposizioni , ak (1 ≤ k ≤ n), detteassunzioni o ipotesi;

• da una proposizione, t, detta tesi.

Un teorema è esprimibile come:

a1 ∧ · · · ∧ an ⇒ t

Regole di inferenza

Le regole di inferenza permettono di dedurre unaproposizione valida:

• dato che p è vera e p ⇔ q, anche q è vera(equivalenza logica);

• se p è una tautologia e a è una sua proposizionecomponente, sostituendo a tutte le occorrenze di a inp la proposizione q, si ottiene ancora una tautologia(sostituzione);

• dato che sia a → b che a sono vere, si deduce cheanche b è vera (modus ponens);

• dato che sia a → b che ¬b sono vere, si deduce cheanche ¬a è vera (modus tollens).



Dimostrazione di teoremi

Una dimostrazione può essere formulata comeuna sequenza di proposizioni vere p1, . . . , pm,dove pj, 1 ≤ j ≤ m:

• è un’assunzione;

• è una tautologia;

• è ottenuta per applicazione delle regole di inferenza;

• pm è la tesi.

Esempio — teorema

Assumiamo che le seguenti proposizioni sianovere:

• se è vacanza sto a casa o vado in montagna;

• oggi sono al lavoro.

Date le precedenti assunzioni, dimostrare che:

• oggi è un giorno lavorativo.



Esempio — formalizzazione

Le proposizioni coinvolte possono essereformalizzate come segue:

• v = “oggi è vacanza”

• c = “stare a casa”

• m = “andare in montagna”

e il teorema diventa:

a1: v → (c ∨ m)

a2: ¬c ∧ ¬m

t: ¬v

Esempio — dimostrazione

p1: ¬(c ∨ m) → ¬v contrapposizione di a1

p2: ¬(c ∨ m) Legge di De Morgan da a2

p3: ¬v modus ponens da p2 p1



In sintesi

Alcune forme logiche sono sempre valide: letautologie.

Possiamo utilizzarle per dedurre unaproposizione valida da un insieme di asserzioni.

Questo procedimento assume la struttura di unadimostrazione.

Prossimi passi

Esercizi sulla logica proposizionale.



Chiusura



Lezione 4 - Esercizi di logicaproposizionale




Stefano Ferrari


Formalizzazione (1)

Formalizzare le seguenti proposizioni:

a) se Aldo e Bruno non mangiano insieme, Carlocucina

b) se Aldo mangia, Bruno digiuna

c) Carlo cucina

d) se Carlo cucina, Bruno e Aldo mangiano

e) Bruno non mangia e Carlo cucina



Formalizzazione (2)

Definiamo i seguenti simboli enunciativi:

a = “Aldo mangia”

b = “Bruno mangia”

c = “Carlo cucina”

Formalizzazione (3)

Le frasi date possono essere formalizzate come:

a) ¬(a ∧ b) → c

b) a → ¬b

c) c

d) c → (b ∧ a)

e) ¬b ∧ c



Tavola di verità

(¬r ∧ (¬p ∨ (¬q ∧ r))) ↔ (p ∨ q) è una tautologia?

p q r ¬q ¬q ∧ r ¬p ¬p ∨ α ¬r ¬r ∧ β p ∨ q γ ↔ δ

F F F V F V V V V F F

F F V V V V V F F F V

F V F F F V V V V V V

F V V F F V V F F V F

V F F V F F F V F V F

V F V V V F V F F V F

V V F F F F F V F V F

V V V F F F F F F V F

α β γ δ

Non è una tautologia.

Teorema 1

Dimostrare la validità del seguente teorema:

Ip1 ¬a → (b ∧ c)

Ip2 ¬b

Tesi a

(1) (¬a → b) ∧ (¬a → c) distrib. conseg. di Ip1

(2) ¬a → b elim. di cong. in (1)

(3) ¬b → a contrapp. di (2)

(4) a MP da (3) e Ip2



Teorema 2

Dimostrare la validità del seguente teorema:

Assunzioni• Mario è architetto oppure è geometra.

• Se Mario fosse architetto, allora Mario sarebbelaureato.

• Mario non è laureato.

Tesi• Mario è geometra.

Formalizzazione del teorema 2

Formalizziamo il problema come segue:

a = “Mario è architetto”

g = “Mario è geometra”

l = “Mario è laureato”

Il teorema può essere riscritto come:

Ip1 a ∨ g

Ip2 a → l

Ip3 ¬l

Tesi g



Dimostrazione del teorema 2

(1) ¬¬a ∨ g equiv. logica di Ip1

(2) ¬a → g equiv. logica di 1

(3) ¬l → ¬a contrapp. di Ip2

(4) ¬a MP da Ip3 e 3

(5) g MP da (4) e 2

Altri esercizi

Altri esercizi si possono trovare su:

• sito del corso online;

• http://www.dti.unimi.it/∼ferrari.



Prossimi passi

Qualche approfondimento su:

• logica proposizionale;

• logica dei predicati.

Chiusura



Lezione 5 - Note aggiuntive sullalogica proposizionale




Stefano Ferrari


Connettivi binari

A parte la negazione, un connettivo logico è unoperatore binario.

Ogni connettivo binario ha 22 = 4 possibiliinterpretazioni.

Ogni interpretazione può assumere 2 valori.

Quindi esistono 24 = 16 connettivi logici (binari).

Analogamente, si può vedere che esistono 4connettivi logici unari, e che la negazione è unodi questi.



Funzione logica

Una funzione logica è una funzione{F, V }n → {F, V }.

z = f(a1, a2, · · · , an) è una legge che facorrispondere ad ogni combinazione di valorilogici di a1, · · · , an uno e un solo valore di z.

Esempi:• una proposizione con n simboli enunciativi è unafunzione logica {F, V }n → {F, V };

• il connettivo binario ∨ è una funzione logica{F, V }2 → {F, V }.

Connettivi usati

Perché su 4 connettivi unari e 16 connettivibinari sono stati scelti proprio ¬, ∨, ∧, → e ↔?

Perché tramite di essi si possono ottenere tuttele funzioni logiche.

Per esempio, il connettivo Y

descritto dalla tabella di veritàa lato equivale a(a ∧ ¬b) ∨ (¬a ∧ b).

Esso è conosciuto anche comeaut, XOR, o OR esclusivo.

a b Y

F F F

F V V

V F V

V V F



Insiemi funzionalmente completi (1)

Gli insiemi di connettivi che permettono diottenere una qualsiasi funzione logica si diconoinsiemi funzionalmente completi.

Sono funzionalmente completi gli insiemi:• {¬, ∨}

• {¬, ∧}

• {¬, ∧, ∨}

Insiemi funzionalmente completi (2)

Anche gli insiemi di connettivi:

• {∨̄}, dove a∨̄b ≡ ¬(a ∨ b) (NOR o OR negato)

• {∧̄}, dove a∧̄b ≡ ¬(a ∧ b) (NAND o AND negato)

sono insiemi funzionalmente completi.



Motivazioni

Perché usare cinque connettivi quando ne bastauno?

I motivi sono (almeno) due:• formale: benché equivalenti, non tutti i connettivihanno le stesse proprietà;

• pratico: alcuni connettivi hanno un significato piùintuitivo.

Logica proposizionale e algebra booleana

Si può dimostrare che

〈{F, V }, {¬, ∨, ∧}〉

rispetta gli assiomi dell’algebra booleana.

In particolare:

• K = {F, V }, dove 0 ≡ F e 1 ≡ V

• ∨ ≡ +

• ∧ ≡ ·

• ¬ ≡ ¯



Logica e intuitività

Alcuni connettivi hanno un significato piùintuitivo di altri.

Questo può essere fatto derivare dalla nostracultura, ma ha anche delle basi fisiologiche.

Wason (fine anni ‘60) ha condotto degli studi ariguardo.

Un suo famoso esperimento richiede un mazzo dicarte con una lettera su una faccia ed un numerosull’altra.

Esperimento di Wason (1)

Date le carte:

A R 6 7

Quali carte è necessario voltare per poteraffermare che la regola

“se c’è una vocale su una faccia,allora sull’altra c’è un numero pari”

sia vera?



Esperimento di Wason (2)

Una percentuale molto bassa di soggettirisponde correttamente al test di Wason.

È però sorprendente che lo stesso test con unamazzo di carte con un’età ed una bevanda sulledue facce, le carte

Whisky Aranciata 19 16

e con la regola

“se la bevanda è un superalcolico,allora l’età deve essere maggiore di 18”

riceva una risposta corretta dalla maggior partedei soggetti!

Implicazione

L’implicazione viene generalmente associataall’inferenza.

La proposizione “se oggi è martedì, domani pioveoppure se domani piove, oggi è martedì” nonpare aver senso.

Eppure la sua formalizzazione ((a → b) ∨ (b → a))è una tautologia.

Istintivamente associamo la proposizione data aciò che dovremmo formalizzare come:

(a ⇒ b) ∨ (b ⇒ a)



Limiti del calcolo proposizionale

La logica proposizionale si limita allo studio deglischemi di composizione di asserzioni.

Non entra nel merito della semantica dellesingole asserzioni.

Non permette deduzioni legate solo ad alcunielementi del dominio considerato.

Per esempio, il famoso sillogismo

“Tutti gli uomini sono mortalie Socrate è un uomo,quindi Socrate è mortale”

può solo essere formalizzato come: a ∧ b → c

In sintesi

La logica proposizionale:

• permette una formalizzazione dei ragionamenti;

• si avvale dei teoremi validi per le algebre di Boole;

• non modella il comportamento intuitivo umano;

• non modella la totalità delle deduzioni matematiche.



Chiusura



Lezione 1 - Logica dei predicati



Unità didattica 4 - Approfondimenti

Stefano Ferrari


Indovinello

Frase 1, 8, 5, 5

∃x(¬freddo(y) ∧ piace(x, y))



Limiti del calcolo proposizionale

Alcune inferenze logiche non possono veniregiustificate sulla base del calcolo proposizionale.

Esempi:• Ogni architetto è laureato.Pietro non è laureato, quindi Pietro non è architetto.

• Nessun coccodrillo è un’orata.Le orate sono pesci, quindi qualche pesce non è uncoccodrillo.

Calcolo dei predicati (1)

Estensione della logica delle proposizioni:• costanti: sono gli elementi dell’universo del discorso;

– esempio: se si esprimono ragionamenti sulle persone, ogni

singola persona è una costante;

• variabili: assumono un valore nell’universo deldiscorso;– esempio: nei discorsi comuni, gli ipotetici Tizio, Caio e

Sempronio assumono la funzione di variabili;

• funzioni: combinano gli elementi dell’universo deldiscorso;– esempio: “la moglie di Tizio” è una funzione che applicata ad

una persona restituisce un’altra persona;



Calcolo dei predicati (2)

• predicati: sono funzioni logiche che si applicano adelementi dell’universo del discorso;– esempio: “Tizio è un architetto”, “Caio e Sempronio sono

amici”;

• quantificatori: precisano l’estensione di un predicato(vincolano i valori assumibili dagli argomenti);

quantificatore universale ∀, per ogni:– esempio: “Tutti i nuotatori sono sportivi”;

quantificatore esistenziale ∃, esiste (almeno un):– esempio: “a qualcuno piacciono gli spinaci”.

Esempi

• “Lassù qualcuno mi ama” (1956):

∃x(lassu′(x) ∧ ama(x, Io))

• “Tutti pazzi per Mary” (1998):

∀x(uomo(x) → pazzo(x, Mary))



Quantificatori (1)

I quantificatori non sono commutativi.

Esempio:

Ognuno degli iscritti ha un numero di matricola.

∀persona ∃numero (iscritto(persona) ∧ matricola(numero) →

immatricolato(persona, numero))

È diverso da:

∃numero ∀persona (iscritto(persona) ∧ matricola(numero) →

immatricolato(persona, numero))

Tutti gli iscritti hanno lo stesso numero dimatricola.

Quantificatori (2)

Sarebbe sufficiente definire un soloquantificatore:

• ∃x A(x) ⇔ ¬∀x ¬A(x)

• ∀x A(x) ⇔ ¬∃x ¬A(x)

Esempi:

• “tutti i palloni sono tondi” ⇔ “non esiste un palloneche non sia tondo”

• “esiste un mammifero che vola” ⇔ “non tutti imammiferi non sanno volare”



Descrizione formale (1)

La descrizione formale della sintassi della logicadei predicati è basata sulla definizione di terminie formule.

Sono termini:• una costante;

• una variabile;

• una funzione n-aria f(t1, . . . , tn), dove t1, . . . , tn

sono termini.

Descrizione formale (2)

Sono formule:• il predicato p(t1, . . . , tn), dove t1, . . . , tn sonotermini;

• le espressioni del tipo:– A ∨ B

– A ∧ B

– ¬A

– ∀x A

– ∃x A

dove A e B sono formule e x è una variabile.



Definizioni

Nella formula ∀x A:• A si chiama ambito o campo d’azione delquantificatore ∀;

• x si dice variabile vincolata (o quantificata).

Una variabile non vincolata di dice libera.

Una formula che non contiene variabili libere sidice chiusa.

Una formula che non contiene variabili si diceground.

Dimostrazioni formali

Possono essere eseguite usando le regole diinferenza della logica proposizionale e con leseguenti regole di inferenza aggiuntive:

• ∀x A(x) ⇒ A(t) (specializzazione);

• A ⇒ ∀x A (generalizzazione);

• (A(x) ∧ x = t) ⇒ A(t), se tutte le occorrenze liberedi t rimangono libere in A(t) (sostituzione).



In sintesi

La logica dei predicati permette di analizzare glielementi di cui la proposizione è composta.

Essa è quindi uno strumento più potente (e piùcomplesso) della logica proposizionale.

Soluzione dell’indovinello∃x(¬freddo(y) ∧ piace(x, y)):• A qualcuno piace caldo (Some Like It Hot, 1959)

Prossimi passi

Relazione tra predicati e insiemi.

Metodi grafici per le dimostrazioni.



Chiusura



Lezione 2 - Predicati ed insiemi




Stefano Ferrari


Predicati ed insiemi

Esiste una corrispondenza tra i predicati e gliinsiemi:

• i predicati definiscono insiemi;– esempio: gli elementi, x, per cui il predicato architetto(x) è

vero, costituiscono l’insieme degli architetti;

• la disgiunzione definisce un’unione;– esempio: gli elementi, x, che rendono vero il predicato

architetto(x) ∨ ingegnere(x), costituiscono l’insieme delle

persone che sono architetto o ingegnere (o entrambi);

• la congiunzione definisce un’intersezione;– esempio: gli elementi, x, che rendono vero il predicato

architetto(x) ∧ biondo(x), costituiscono l’insieme delle

persone che sono architetto e che sono bionde.



Dimostrazioni grafiche

Sfruttando la corrispondenza tra formule dilogica posizionale e insiemi, è possibileeffettuare o confutare la validità di inferenze conil solo supporto dei grafici di Eulero-Venn.

In particolare:

• le costanti e le variabili sono punti del piano;

• i predicati sono regioni del piano;

• le operazioni logiche combinano le regioni del pianocome nei diagrammi di Eulero-Venn.

Un’inferenza sarà valida se il grafico delleassunzioni descrive una situazione compatibilecon la tesi, ma non con la sua negazione.

Esempio 1

Ip1: Gli uomini sono mortali.

Ip2: Socrate è un uomo.

Tesi: Socrate è mortale.

Ip1: ∀x(U(x) → M(x))

Ip2: U(s)

Tesi: M(s)

Ip1: U ⊆ M

Ip2: s ∈ U

Tesi: s ∈ M

U

M

s



Esempio 2

Ip1: Tutte le api ronzano.

Ip2: Qualche insetto non ronza.

Tesi: Qualche insetto non è un’ape.

Ip1: ∀x(A(x) → R(x))

Ip2: ∃x(I(x) ∧ ¬R(x))

Tesi: ∃x(I(x) ∧ ¬A(x))

Ip1: A ⊆ R

Ip2: ∃x ∈ I − R

Tesi: ∃x ∈ I − A

A R

Ix

In sintesi

La logica dei predicati permette di analizzare glielementi di cui la proposizione è composta.

I predicati possono essere messi incorrispondenza con opportuni insiemi.

Questa corrispondenza può, in alcuni casi, esseresfruttata per effettuare delle dimostrazioni.



Chiusura



Lezione 3 - Reti logiche




Stefano Ferrari


Algebre booleane

Sono algebre booleane:

Boole insiemi proposizioni commutazione

K P(U) {F, V } {aperto, chiuso}

· ∩ ∧ serie

+ ∪ ∨ parallelo

¯ ¯ ¬ invertitore

0 ∅ F aperto

1 U V chiuso

Esempio:

• Idempotenza (a + a = a): mettere in parallelo dueinterrutori abbinati, equivale a usarne uno solo.



Algebra di commutazione

Claude Shannon (1938) haconstatato che un circuito dotatodi interrutori (switch) si comportasecondo le leggi dell’algebrabooleana.

Questa proprietà è indipendentedalla tecnologia usata, e infattivale per circuiti:

• elettrici;

• pneumatici;

• ottici.

Reti logiche

I circuiti degli attuali elaboratori digitali sonocostituiti da componenti elementari, detti portelogiche, che realizzano i connettivi logici.

Questi dispositivi, detti reti logiche, si dividonoin due famiglie:

• reti combinatorie:– circuiti descrivibili in termini di porte logiche senza

retroconnessioni (comportamento ingresso/uscita)

• reti sequenziali:– circuiti con retroconnessioni;

– in ogni istante, il valore di uscita dipende sia dagli ingressi,

sia dallo stato del circuito nell’istante precedente (memoria).



Approfondimenti

Il corso di “Architetture e reti logiche” copreapprofonditamente questi temi.

In sintesi

Le reti logiche consentono di realizzare unamacchina dotata di:

• capacità di effettuare calcoli;

• memoria.



Chiusura



Lezione 1 - Architettura divon Neumann


Modulo 4 - Sistemi di elaborazione

Unità didattica 1 - Architettura di von Neumann

Stefano Ferrari


Scomposizione funzionale

Il calcolatore può essere descrittoscomponendolo iterativamente in una gerarchiadi sottosistemi.

Ogni componente:

• è responsabile di una funzionalità;

• interagisce con gli altri componenti e con l’ambiente;

• è, a sua volta, dotato di una struttura interna.



Funzionalità principali

Le funzionalità principali sono:

• scambio dati con l’esterno;

• memorizzazione;

• elaborazione;

• controllo.

Trasferimento dati

È la funzionalità che consente di scambiare daticon l’esterno: input/output (I/O).

Si realizza mediante:

• dispositivi di I/O;

• connessione in rete.



Memorizzazione

Vi sono almeno due tipi di memorizzazione:

• a breve termine;

• a lungo termine.

Elaborazione

Risulta come compromesso tra le diversecaratteristiche di un calcolatore:

• flessibilità;

• modularità;

• scalabilità;

• standardizzazione;

• costo;

• semplicità;

• disponibilità di applicazioni.



Controllo

È esercitato da:

• utente (ad alto livello);

• CPU (a basso livello);

• unità di controllo (a bassissimo livello).

Calcolatore programmabile

Il calcolatore è una macchina estremamenteflessibile:

• le funzionalità vengono fornite dall’hardware;

• la specializzazione viene fornita dal software.



Architettura di von Neumann

La cosidetta architettura di von Neumann sicompone di:

• una unità elaborazione centrale (Central ProcessingUnit — CPU);

• un dispositivo di memoria, costituito da un insieme dielementi identificabili tramite il loro indirizzo;

• alcuni dispositivi, detti periferiche, per l’interazionecon l’esterno;

• una linea di interconnessione, detta bus, conmodalità master/slave.

CPU

È il componente principale, a cui sono affidate lefunzioni di:

• controllo;

• coordinamento;

• elaborazione.

La tecnologia realizzativa è la microelettronica,le CPU vengono chiamate microprocessori.



Memoria centrale

La memoria centrale:

• ospita i dati coinvolti nell’elaborazione (talvolta anchequelli delle periferiche);

• è costituita da insieme di celle adiacenti, ognunadelle quali è identificata da un indirizzo numerico.

Periferiche

Le periferiche:

• interagiscono con l’utente (e l’ambiente);

• comunicano tramite l’interfaccia di I/O.



Bus

Il bus è una linea a cui sono collegatecontemporaneamente diverse unità:

• la CPU svolge il ruolo di master;

• le altre unità funzionano da slave.

Architettura master/slave

vantaggi svantaggi

• semplicità;

• estendibilità;

• standardizzabilità;

• lentezza;

• capacità del canale limitante;

• sovraccarico CPU.

In sintesi

L’architettura di von Neumann:

• descrive le funzionalità dei calcolatori:– elaborazione;

– scambio dati;

– memorizzazione;

– controllo;

• si compone di:– CPU;

– memoria;

– periferiche;

– bus.



Prossimi passi

Il funzionamento dei componenti della macchinadi von Neumann.

Chiusura



Lezione 2 - Bus e CPU




Stefano Ferrari


Bus

Sul bus transitano informazioni di tre tipi:• dati;

• indirizzi;

• segnali di controllo.

Esse viaggiano su linee separate.

Pertanto, il bus è scomponibile in:• bus dati;

• bus indirizzi;

• bus controllo.



Esecutore

L’idea fondamentale ancora oggi seguita nellarealizzazione dei sistemi di calcolo:• codificare le istruzioni in forma numerica;

• inserirle nella memoria centrale.

Nella macchina di von Neumann:• dati e istruzioni memorizzati in un’unica memoria chepermette lettura e scrittura;

• la memoria è costituita da celle uguali, indirizzatedalla loro posizione;

• le istruzioni vengono eseguite in modo sequenziale.

Linguaggio macchina

I programmi vengono codificati in un linguaggiodetto linguaggio macchina, o assembly,caratterizzato da:

• assenza di struttura o tipo di dato;

• istruzioni semplici e in numero ridotto;

• istruzioni composte dall’identificativo dell’operazionepiù eventuali operandi:

– esempio: <Somma> <Reg1> <Reg2>.



Codice operativo

Il codice operativo è il valore numerico cheidentifica l’operazione effettuata da unaistruzione assembly.

Si ha che:• CPU della stessa famiglia hanno lo stesso codiceoperativo;

• CPU di diversi produttori possono adottare lo stessocodice operativo (compatibilità).

Esecuzione del programma

Quando il programma e i dati risiedono inmemoria, la CPU opera in modo ciclico:

• viene recuperata dalla memoria l’istruzione daeseguire (fetch);

• viene decodificata (decode);

• vengono eseguite le operazioni che compongonol’istruzione (execute).



CPU

È composta da:• ALU (Arithmetic-Logic Unit)

• registri:– Program Counter (PC)

– Instruction Register (IR)

– Memory Address Register (MAR)

– Memory Data Register (MDR)

– Processor Status Word (PSW)

– Registri di lavoro

• unità di controllo

bus datibus indirizzibus controllo

MDR MAR

ALU

UCPC

IRPSW

REG1

...

REGN

CPU

Fetch

Nella fase di fetch:

1. l’UC mette PC in MAR;

2. l’UC mette il comando dilettura sul bus controllo;

3. MDR viene messo in IR —incremento di PC.

bus datibus indirizzibus controllo

MDR MAR

ALU

UCPC

IRPSW

REG1

...

REGN

CPU



In sintesi

La macchina di von Neumann si basa su:• compresenza di dati e istruzioni in memoria;

• sequenzialità dei programmi;

• ruolo di master della CPU.

Prossimi passi

Gli altri componenti della macchina descritta davon Neumann:• la memoria;

• le periferiche.



Chiusura



Lezione 3 - Memoria e periferiche




Stefano Ferrari


Memoria

Si divide in:• memoria centrale;

• memoria di massa.

Si classifica per:• velocità d’accesso;

• densità;

• volatilità;

• costo per bit.

Diverse tecnologie hanno caratteristiche diverse.



Gerarchia di memoria

Dalla più rapida alla più lenta:

• memoria interna alla CPU: registri, cache (a volte èesterna, ma non passa per il bus);

• memoria interna al calcolatore: memoria centrale;

• memoria esterna al calcolatore: memoria di massa(dischi, nastri).

L’uso della della cache è motivato dalle proprietàdi località spaziale e temporale degli accessi amemoria.

Periferiche

Modalità:

• seriale (USB, Firewire, Bluetooth);

• parallelela.

Interfaccia di I/O è composta da:

• registro dati;

• registro di controllo;

• registro di stato.



Controllo delle periferiche

Ci sono due modalità di controllo delleperiferiche:

• in modalità memory mapped, la CPU accede airegistri della periferica con un’operazione di lettura oscrittura in memoria, ma lo fa in indirizzi che lamemoria non riconosce come propri;

• tramite istruzioni dedicate, previste nell’instructionset della CPU.

Modalità di I/O

Gestione I/O a controllo di programma:• la CPU controlla direttamente lo stato della periferica(polling).

Gestione I/O a interrupt:• la periferica avvisa la CPU.

Gestione I/O tramite DMA:• la CPU controlla il controllore DMA.



Approfondimento

Istruzioni particolari possono alterare il prelievodelle istruzioni da celle consecutive (e quindi lasequenzialità):• istruzioni di salto;

• istruzioni di chiamata a sotto-programmi;

• istruzioni di interruzione.

In sintesi

La macchina di von Neumann si basa su:• compresenza di dati e istruzioni in memoria;

• sequenzialità dei programmi;

• ruolo di master della CPU.



Prossimi passi

Elementi software dei calcolatori:• elementi di programmazione;

• cenni di sistemi operativi.

Chiusura



Lezione 1 - Soluzione automatizzata diproblemi



Unità didattica 2 - Elementi di programmazione

Stefano Ferrari


Definizione

virtuale [vir-tu-à-le] agg.

1. Che esiste in potenza, ma non si è ancorarealizzato;

2. Fittizio, non reale.



Macchina virtuale

Si usa il termine macchina virtuale per indicarel’astrazione della macchina fisica realizzata dalsoftware ai vari livelli.

Esempio:

• per le periferiche mappate in memoria si usano delleoperazioni che non hanno nulla a che vedere con larealtà fisica, ma facilitano l’uso dei dispositivi.

Virtualizzazione

A livello di utente:

• sistema operativo;

• interfaccia:

– tira l’angolino;

– schiaccia il pulsante.

A livello di programmatore:

• paradigmi di programmazione;

• linguaggi.



Risolvere un problema

Dato un problema, l’individuazione delleprocedure necessarie alla sua soluzione richiedele seguenti fasi:

• descrizione dei requisiti che la soluzione dovràsoddisfare per essere considerata corretta(specifiche);

• procedimento con cui si individua o si inventa unasoluzione (progetto);

• tecnica che consente di risolvere il problema(soluzione).

Nell’informatica, la soluzione è espressa tramiteun algoritmo.

Algoritmo

Dato un problema e un esecutore, l’algoritmo:

• è una successione finita di passi elementari(direttive);

• eseguibile senza ambiguità dall’esecutore;

• risolve il problema dato.



Caratteristiche di un algoritmo

Ogni algoritmo possiede le seguenticaratteristiche:

• sequenzialità:– viene eseguito un passo dopo l’altro secondo un ordine

specificato (flusso di esecuzione);

• univocità:– i passi elementari devono poter essere eseguiti in modo

univoco dall’esecutore, e quindi devono essere descritti in

una forma eseguibile per l’esecutore.

Algoritmo e programmazione

Un buon algoritmo deve prevedere tutti i casisignificativi che derivano dall’esecuzione di ognipasso elementare.

La descrizione di un algoritmo per un esecutoreautomatico deve avere una formulazionegenerale: la soluzione individuata non devedipendere solo da valori predefiniti dei dati.



Esempi

Esempio negativo:

• programma che calcola l’area del cerchio di raggio 3cm.

Esempio positivo:

• programma che calcola l’area del cerchio di raggiodato dall’utente.

Elementi di un algoritmo

“Oggetti”: le entità su cui opera l’algoritmo vengonogeneralmente chiamate dati, e comprendono sia idati iniziali del problema che i risultati intermedi.

Operazioni: gli interventi che si possono effettuaresugli oggetti, cioè sui dati sono calcoli, confronti,assegnamenti ed operazioni di I/O.

Flusso di controllo: indica le possibili evoluzionidell’esecuzione delle operazioni, cioè le possibilisuccessioni dei passi dell’algoritmo.



Esempi di algoritmi

Algoritmi adatti ad un esecutore umano:

• ricette di cucina;

• spartiti musicali;

• istruzioni di montaggio di un mobile.

Generalmente contengono riferimenti a:

• quantità soggettive;

• descrizioni approssimative;

• informazioni mancanti perché implicite.

In sintesi

L’individuazione di una soluzione prevede trefasi:

• specifica;

• progetto;

• realizzazione.

Una soluzione adatta ad un esecutore automaticodeve essere:

• sequenziale;

• non ambigua.



Prossimi passi

Elementi di programmazione di un calcolatore.

Chiusura



Lezione 2 - Programmazione di uncalcolatore




Stefano Ferrari


Descrizione di un algoritmo

Un algoritmo adatto per un esecutore automaticodeve essere descritto tramite un formalismo(linguaggio) rigoroso e non ambiguo costituitoda:

• vocabolario: insieme di elementi per la descrizionedi oggetti, operazioni e flusso di controllo;

• sintassi: insieme di regole per la composizione deglielementi del linguaggio in frasi eseguibili e costruttidi controllo;

• semantica: insieme di regole per l’interpretazionedegli elementi e delle istruzioni sintatticamentecorrette.



Linguaggio di programmazione

In un linguaggio di programmazione:

• gli oggetti vengono descritti tramite nomi simbolici(detti anche identificatori);

• le operazioni vengono descritte tramite operatori,funzioni e procedure;

• il flusso di controllo viene descritto tramite opportunicostrutti di controllo.

Flusso di controllo vs. flusso di esecuzione

Il flusso di controllo è differente dal flusso diesecuzione.

Il flusso di controllo descrive tutte le possibilisuccessioni di operazioni che possono essererealizzate dal programma nella sua esecuzione.

Il flusso di esecuzione è la sequenza dioperazioni percorsa durante una particolareesecuzione del programma.



Linguaggi di programmazione (1)

I linguaggi di programmazione sono classificabiliin almeno quattro grandi categorie, parzialmentesovrapposte:

Imperativi: le istruzioni descrivono in modoesplicito le modifiche del contenuto dellamemoria;• esempi: Basic, Pascal, C, Fortran, Cobol;

Funzionali: il programma è costituito da unafunzione che ha per argomenti altresottofunzioni;• esempio: Lisp;

Linguaggi di programmazione (2)

Dichiarativi (o logici): il programma è costituitoda una serie di asserzioni e di regole, e la suaesecuzione consiste in una dimostrazione diveridicità di un’asserzione, senza indicare ilflusso di esecuzione;• esempio: Prolog;

Orientati agli oggetti: il programma è costituitoda entità (oggetti) che comunicano tra loroscambiandosi messaggi e che godono delleproprietà di incapsulamento, ereditarietà epolimorfismo;• esempi: Ada, Smalltalk, Java.



Linguaggi di descrizione

I linguaggi semiformali hanno regole bendefinite, ma permettono descrizioni in linguaggionaturale, non rigorose.

Sono usati nella fase di sviluppo di algoritmi:

schema a blocchi (diagramma di flusso): usablocchi di varie forme geometriche connessida archi orientati la cui direzione indica ilflusso di controllo, mentre la forma dei blocchiindica la natura del blocco stesso (operazione,confronto, operazione di I/O);

pseudocodice: usa strutture di controllo di unlinguaggio di programmazione e operazionidescritte in linguaggio naturale.

Sottoprogrammi

Programmi complessi vengono progettatiseguendo uno schema gerarchico in cui ilproblema iniziale viene suddiviso insottoproblemi e così via (metodologiatop-down).

Questo approccio ha i seguenti vantaggi:

• chiarezza del programma principale;

• sintesi;

• efficienza.



Vantaggi

Chiarezza: i dettagli di basso livello sonodescritti a parte nei sottoprogrammi,evidenziando la struttura di controllogenerale;

Sintesi: per i sottoproblemi presenti in più partidel problema principale, richiamando ilsottoprogramma, si evitano di ripetere lestesse sequenze di operazioni;

Efficienza: sottoproblemi di uso comune sonodisponibili, già risolti da espertiprogrammatori, raccolti nelle cosiddettelibrerie.

Programma eseguibile

Perché un algoritmo sia eseguibile da uncalcolatore, esso deve essere tradotto in unasequenza di istruzioni codificate nel codiceoperativo caratteristico della CPU del calcolatoreche lo eseguirà (binario).

L’operazione di traduzione da un linguaggio diprogrammazione ad un altro è una proceduraripetitiva, che può essere automatizzata.



Traduzione in binario

La traduzione in codice eseguibile è effettuata daun programma apposito, che può essere di duetipi:

• interprete: traduce solo le istruzioni del flusso diesecuzione;– la traduzione viene effettuata ad ogni esecuzione;

• compilatore: traduce l’intero programma;– la traduzione viene effettuata una sola volta.

In sintesi

I programmi per i calcolatori devono essereespressi in forma rigorosa e non ambigua.

I linguaggi di programmazione rispettano questecaratteristiche.

I paradigmi e le metodologie di programmazioneaiutano a sviluppare programmi corretti efacilmente gestibili.

I programmi devono infine essere tradotti nelcodice binario della macchina esecutrice.



Prossimi passi

La catena di programmazione, ovvero come siproduce un programma eseguibile.

Chiusura



Lezione 3 - Catena di programmazione




Stefano Ferrari


Programmare

La generazione di un programma eseguibileconsiste nella traduzione automatica

• di un algoritmo espresso in un linguaggio simbolico(programma sorgente)

• nello stesso algoritmo espresso in codice macchina(programma eseguibile).



Catena di programmazione

Le fasi che portano un algoritmo ad essereeseguito sono:

editing: composizione del programma sorgente;

compiling: traduzione in codice binario;

linking: collegamento con i sottoprogrammi dilibreria;

loading: caricamento in memoria;

esecuzione: esecuzione del programma.

Editing

Generalmente un algoritmo viene codificato in unprogramma sorgente.

Lo strumento utilizzato per la scrittura è unapposito programma chiamato editor.

Questa fase ha termine con la produzione di unfile di testo detto file programma sorgente.



Compiling

La fase di traduzione, o compilazione, utilizza unprogramma (detto compilatore).

Esso elabora il file sorgente, riconoscendo isimboli, le parole e i costrutti del linguaggio eproducendo:

• la forma binaria del codice macchina corrispondente(file programma oggetto);

• oppure, una segnalazione degli errori sintattici.

Errore sintattico

Gli errori sintattici sono violazioni delle regolesintattiche del linguaggio di programmazione.

Essi rendono il programma non associabile ad unsignificato e quindi ne impediscono la traduzione.

Esempio:

3 * (5 +/ 2)



Linking

Nella fase di linking (collegamento), unprogramma (detto linker) collega il file oggettocon le funzioni di libreria.

Esso produce:

• un programma eseguibile;

• oppure, una segnalazione di errore nella citazionedelle routine di libreria (linker error).

Loading

Per poter essere eseguito, un file eseguibile deveessere caricato in memoria centrale.

Questa funzione viene svolta da un programmachiamato loader (caricatore), che individua unaregione di memoria adeguata all’esecuzione delprogramma.

Se tale spazio in memoria non esiste, segnala unerrore di caricamento per memoria insufficiente.



Esecuzione

Il programma in esecuzione elabora i dati iningresso e produce i risultati in uscita.

Possibili errori (non di tipo sintattico!):

• calcoli matematicamente impossibili (run-time error);– esempio: divisione per zero;

• operazioni fisicamente impossibili (run-time error);– esempio: memoria insufficiente;

• calcoli scorretti;– esempio: overflow;

• errori semantici;– esempio: errore nella scrittura di un’operazione.

In sintesi

Il percorso che porta un algoritmo ad essereeseguito è scandito dalle seguenti fasi:

• editing;

• compiling;

• linking;

• caricamento;

• esecuzione.

In ogni fase, la descrizione dell’algoritmo subisceuna trasformazione.



Prossimi passi

Alcuni cenni sui principi di funzionamento deisistemi operativi.

Chiusura



Lezione 1 - Struttura del sistemaoperativo



Unità didattica 3 - Cenni di sistemi operativi

Stefano Ferrari


Motivazioni

Il sistema operativo (SO) è un insieme diprogrammi che:

• gestiscono l’hardware;

• forniscono un’interfaccia semplificata all’utente ed aiprogrammi utente verso l’hardware.

Il SO è utile perché:

• l’uso diretto dell’HW non è agevole;

• i programmi devono essere riscritti se si cambial’HW;

• la gestione della macchina è trasparente per l’utente.



Modello a buccia di cipolla

Il modello di SO più diffuso ha una strutturamodulare a strati (modello a buccia di cipolla):

utente/programmi utente

interprete dei comandi (shell)

file system

gestore della periferiche SO

gestore della memoria

nucleo (kernel)

hardware

Ogni strato fornisce un’astrazione (macchinavirtuale) agli strati più esterni.

Kernel

Il kernel:

• è lo strato a contatto diretto con la CPU (se si cambiaHW, solo il kernel va modificato);

• gestisce l’uso della CPU da parte dei programmi;

• permette ad ogni processo (programma+dati)/utentedi considerarsi unico utilizzatore della CPU.



Gestore della memoria

Il gestore della memoria:

• fornisce uno spazio virtuale di indirizzamento;

• protegge dati/istruzioni;

• maschera la collocazione fisica (e.g., swap);

• controlla la sovrapposizione degli spazi di memoriaassociati ai vari programmi.

Gestore delle periferiche

Il gestore delle periferiche:

• fornisce una visione semplificata delle periferiche;

• fornisce ai programmi delle primitive ad alto livelloper l’uso delle periferiche;

• gestisce i conflitti nell’uso delle periferiche (ogniprogramma “vede” un insieme di periferichededicate).



File system

Il file system:

• è uno strato dedicato ad una classe di periferichepeculiari;

• organizza i dispositivi di memoria di massa;

• gestisce la corrispondenza tra locazione fisica eidentificatore del file;

• gestisce i permessi di uso dei file.

Shell

L’interprete dei comandi (shell):

• è il modulo accessibile all’utente (tramite leperiferiche);

• interpreta i comandi dell’utente;

• si occupa del caricamento e dell’esecuzione deiprogrammi.



Rete

La connessione di rete non è stata considerata:quando il modello è stato formulato, la reteveniva vista come una una funzionalitàaggiuntiva esterna al SO.

La rete può essere consideratasemplicisticamente come una perifericaparticolare.

Tuttavia, l’appartenenza ad una rete dicalcolatori è un aspetto che investe i vari stratidel SO.

In sintesi

Il sistema operativo è un insieme di programmiche facilitano l’uso del calcolatore.

Il suo scopo è:

• gestire l’hardware;

• fornire un’interfaccia semplificata per l’utente.

Una struttura gerarchica di moduli forniscediversi gradi di astrazione.



Prossimi passi

Classificazione dei vari tipi di sistema operativo.

Cenni sul funzionamento dei moduli principali.

Chiusura



Lezione 2 - Classificazione dei sistemioperativi




Stefano Ferrari


Tipi di SO

I SO si possono classificare a seconda delle lorocaratteristiche:

• monoutente monoprogrammato;

• monoutente multiprogrammato;

• multiutente multiprogrammato.

Fra i sistemi multiprogrammati sono diffusi:

• time-sharing (i processi usano alternativamente laCPU per un quanto di tempo);

• real-time.

Inoltre, ci sono sistemi dedicati.



Parallelismo

L’architettura di von Neumann prevedeun’esecuzione sequenziale dedicata.

Alcune operazioni, però, possono essere eseguitein parallelo.

Il parallelismo può essere individuato a diversilivelli:

• dati (esempio: cambiare la luminosità a tutti i pixeldell’immagine);

• istruzioni (a=b+c e z =1);

• programmi (lettore mp3 e word processing).

Parallelismo: motivazioni

I principali motivi a supporto del parallelismosono:

• efficienza: mentre un processo attende un input,può lasciare l’uso della CPU ad un altro;

• interattività: l’interazione con l’utente richiedebrevi, ma frequenti intervalli di utilizzo della CPU;

• sincronizzazione/cooperazione: si puòsemplificare la descrizione di molti programmiutilizzando attività concorrenti, aumentando anchel’efficienza della CPU (e.g., modelloproduttore-consumatore).



In sintesi

I sistemi operativi si differenziano per lamodalità con cui gestiscono le risorse.

Particolare attenzione su come viene gestita laCPU.

Una gestione multiprocesso favorisce un altoutilizzo della CPU.

Prossimi passi

Cenni sul funzionamento di:

• kernel;

• gestore della memoria;

• file system.



Chiusura



Lezione 3 - Gestione dei processi




Stefano Ferrari


Processo

Un processo (entità dinamica) è un programma(entità statica) in esecuzione.

Il dinamismo è espresso da:

• evoluzione dei dati;

• flusso di esecuzione.

Ad ogni programma possono corrispondere piùprocessi (figli): ognuno afferisce a diversesezioni del programma (processo padre).



Stati di un processo (1)

Un processo si trova in uno dei seguenti tre stati:

• pronto — ready (coda dei processi pronti)

• esecuzione — running (uso della CPU)

• attesa — waiting (code delle periferiche)

inizio esecuzione

selezione per esecuzione

interrupt esterno

interrupt interno

terminazione

evento esterno

pronto esecuzione

attesa

Stati di un processo (2)

Il processore viene utilizzato a turno dai processiin esecuzione, ciclando fra i tre stati:

• la transizione da pronto a esecuzione avviene quandoil processo prende uso della CPU (scheduler);

• transita da esecuzione a pronto quando lo schedulergli toglie l’uso della CPU (e.g., quando scade il suoquanto di tempo, evento esterno da gestire);

• passa da esecuzione a attesa quando il processodeve attendere un evento (e.g., carattere datastiera);

• passa da attesa a pronto quando l’evento atteso si èverificato.



Classificazione dei processi

I processi si dividono in due categorie:

• I/O bound, caratterizzati da frequenti operazioni diI/O (e.g., programma di scrittura);– lunghi periodi di attesa di eventi esterni intervallati da brevi

elaborazioni;

• CPU bound, che fanno calcoli (e.g., simulazione);– lunghi periodi di calcolo intervallati da brevi operazioni di I/O.

Multiprogrammazione

La multiprogrammazione è vantaggiosa perché:

• sfrutta i tempi morti;

– mentre un processo attende un carattere da tastiera, la CPU

può continuare ad eseguire un programma di puro calcolo;

• esegue lo switch tra processi già in memoria;

– l’operazione di cambio di contesto (salvataggio dei valori dei

registri del processo che lascia la CPU e ripristino di tali valori

per il processo che subentra) è relativamentre veloce perché

avviene per processi che sono già in memoria centrale.



Politiche di scheduling

L’obiettivo dello scheduling è la massimizzazionedell’utilizzo della CPU.

I più diffusi algoritmi di scheduling sono:

• round robin: ad ogni processo è assegnata la CPUper un quanto di tempo prefissato (sufficientementegrande rispetto al tempo di cambio del contesto);

• priorità statica: priorità fissata alla creazione deiprocessi in base alle loro caratteristiche (altà prioritàper i processi interattivi, bassa priorità per i processiCPU bound);

• priorità dinamica: la priorità può essere modificatadurante l’esecuzione dei processi.

Vantaggi della concorrenza

L’esecuzione concorrente di processi ha diversivantaggi, tra i quali:

• aumento del tempo di utilizzo effettivo della CPU;

• suddivisione dei processi su più CPU o su piùcalcolatori;

• condivisione (controllata) delle stesse risorse.



Problemi della concorrenza

Le interazioni tra processi concorrenti possonocausare due problemi:

• starvation (morte per inedia): processi di prioritàpiù elevata possono ritardare indefinitamentel’esecuzione di un processo a bassa priorità;

• deadlock (blocco infinito): se due processirichiedono entrambi una risorsa (o un risultato)occupata dall’altro, nessuno dei due processi puòterminare.

Esempio: un idraulico ed un elettricista devonorifare gli impianti di una casa, ma entrambi esigonoche sia prima sistemato l’altro impianto.

Processi concorrenti

La concorrenza tra processi assume la forma di:

• competizione per le risorse, quando i processidevono svolgere compiti differenti, con lo scopo diportare a termine il loro compito il prima possibile;

• cooperazione, quando i compiti che devono portare atermine sono tra loro correlati (per esempio, spoolingdi stampa); in questo caso si presentano problemi di:

– sincronizzazione delle attività: sono necessari dispositivi per

controllare l’ordinamento degli eventi (semafori);

Esempio: non versare l’acqua se non c’è sotto il bicchiere;

– comunicazione: serve per lo scambio di dati tra i processi

(memoria condivisa, messaggi).



In sintesi

Il processo è una entità dinamica prodottadall’esecuzione di un programma.

L’esecuzione concorrente di più processipermette un maggiore sfruttamento della CPU,ma causa i problemi di:

• competizione (starvation, deadlock);

• cooperazione (sincronia,comunicazione).

Prossimi passi

Cenni sul funzionamento di:

• gestore della memoria;

• file system.



Chiusura



Lezione 4 - Gestore della memoria




Stefano Ferrari


Gestione della memoria centrale

Il gestore della memoria è il modulo di sistemaoperativo che fornisce ad ogni processo unospazio di indirizzamento virtuale.

Per ottimizzare l’utilizzo della memoria, ilgestore della memoria consente:

• il caricamento di un programma a partire da unqualsiasi indirizzo;

• il caricamento in memoria (fisica) solo di porzioni diprogramma o dati;

• la condivisione di istruzioni da parte di processidifferenti (generati dallo stesso programma).



Spazio di indirizzamento

La memoria disponibile per un programma puòessere descritta in termini di:

• spazio logico: è lo spazio di indirizzamento virtuale incui gli indirizzi delle celle partono da 0;

• spazio fisico: è lo spazio di indirizzamento deldispositivo di memoria.

Rilocabilità del codice

La rilocazione della memoria:

• è realizzata dal gestore della memoria;

• consiste in un mappaggio degli indirizzi da logici afisici;

• permette di eseguire un processo in qualsiasi zonadella memoria fisica;

• definisce lo spiazzamento di un processo: indirizzofisico della cella 0 dello spazio logico.



Rilocazione

La rilocazione può essere:

• statica, quando lo spiazzamento viene calcolato almomento del linking;

• dinamica, quando:– i programmi vengono caricati in memoria con gli indirizzi

calcolati da 0;

– il contenuto di un particolare registro (registro base) viene

aggiunto ad ogni istruzione.

Rilocazione dinamica

La rilocazione dinamica:

• è necessaria in sistemi multiprogramma;

• richiede la disponibilità di apposito HW;

• può essere effettuata separatamente su dati eistruzioni mediante due registri base (diversi processipossono avere lo stesso registro base istruzioni).



Memoria virtuale

La memoria è una risorsa preziosa.

Generalmente, si dispone di meno memoria diquanta ne sarebbe necessaria ai processi attivi.

La memoria virtuale è una tecnica che consentedi ampliare lo spazio di indirizzamente usandouna parte della memoria di massa (swap) percoprire la mancanza di memoria centrale.

Se un processo richiede più memoria di quantane sia disponibile al momento, il gestore dellamemoria salva i dati di uno dei processi in attesanell’area di swap, liberando così la memoria daessi occupata.

Stati di un processo con swapping

inizio esecuzione

selezione per esecuzione

carica su

disco interrupt esterno

interrupt interno

terminazione

interrupt esterno e carica su disco

evento esterno

caricasudisco

evento esterno

carica in m

emoria

pronto esecuzione

attesa

attesa

disco

attesa

disco

pronto

disco

pronto

disco



Frammentazione

Il gestore della memoriaassegna la memoriadisponibile aiprogrammi che devonoessere eseguiti.

Si può verificare unasituazione in cui vi èsufficiente memoriadisponibile, ma nonessendo contigua nonpuò essere utilizzata.

P1

P2

P3

t1

P1

P2

t2

P1

P2

P4

t3

P1

P4

P5

t4

Paginazione

Si suddivide la memoria (sia fisica che logica) inblocchi di ugual dimensione (pagine).

Ad ogni processo si allocano solo un numerointero di pagine.

In questo modo:

• si guadagna la possibilità di allocare zone noncontigue di memoria;

• si può attenuare il problema della frammentazionedella memoria.



Segmentazione

La segmentazione è una tecnica basata sullasuddivisione della memoria usata da unprogramma a secondo il tipo di informazionecontenuta:

• segmento codice;

• segmento dati;

• segmento pila.

Ogni segmento viene trattato in modoindipendente dal gestore della memoria.

Permette la condivisione dello stesso segmentocodice da parte di più processi.

In sintesi

La memoria è una risorsa costosa.

Il gestore della memoria ne ottimizzal’assegnazione ai processi:

• rendendo trasparente al processo la sua locazionefisica;

• mantenendo in memoria solo la porzione di dati e diistruzioni necessarie all’esecuzione;

• evitando la duplicazione di informazioni.



Prossimi passi

Cenni sulla struttura e sulle funzioni del filesystem.

Chiusura



Lezione 5 - File system




Stefano Ferrari


File system

Presenta all’utente e ai programmi una visionesemplificata ed omogenea dei dispositivi per lamemoria di massa:

• attraverso un’organizzazione logica (directory,volumi);

• mediante operazioni sui dati memorizzati, quali:

– il recupero;

– la cancellazione;

– la modifica;

– la copia.



Dati e metadati

Oltre ai dati ed i programmi degli utenti, lamemoria di massa deve memorizzare ancheinformazioni che riguardano il file system stesso:

• aree libere o allocate;

• directory.

Allocazione

L’allocazione dello memoria di massa condivide iproblemi di allocazione della memoria centrale.

Per esempio:

• frammentazione;

• allocazione contigua (supporti write-once);

• allocazione a blocchi (supporti riscrivibili).



Allocazione a lista concatenata

Un file è una concatenazione di blocchi.

Ciò comporta che:• una porzione di ogni blocco è impegnata dallaposizione fisica del blocco seguente;

• l’accesso al blocco N-esimo richiede l’accesso aN − 1 blocchi;

• il danneggiamento di un blocco impedisce direcuperare il resto del file.

File Allocation Table

La File Allocation Table (FAT) è una mappa diallocazione dei blocchi della memoria di massa.

0FAT

1

3

2

5

3

6

4

-1

5

9

6

0

7

-1

8

8

9

Ogni elemento della mappa contiene uno fra iseguenti valori:

• l’identificatore di blocco vuoto;

• la posizione del prossimo blocco del file;

• l’identificatore di ultimo blocco.



Svantaggi della FAT

L’approccio basato su FAT comporta i seguentisvantaggi:

• per essere efficiente, la FAT deve stare in memoria;

• l’accesso al blocco N-esimo richiede N accessi inmemoria centrale (più uno in memoria di massa);

• la dimensione della FAT cresce più che linearmentecon la dimensione del dispositivo.

Esercizio: Quanto occupa la FAT di un disco da 20 GiBi, con

blocchi da 2 KiBi?

– Il disco dato ha 10 · 220 blocchi: la FAT avrà 10 · 2

20 elementi.

– Ciascun elemento richiede almeno 24 bit, quindi la FAT

occuperà non meno di 30 MiBi.

Allocazione indicizzata

Con l’allocazione indicizzata, ogni file è descrittoda un blocco detto blocco indice.

Il blocco indice contiene l’elenco dei blocchi checompongono il file.

L’approccio può essere gerarchizzato(indicizzazione multilivello):

• nei file piccoli, il blocco indice punta ai blocchi dati;

• nei file grandi, il blocco indice punta a blocchi indicedi livello inferiore.

Solo i blocchi indice dei file aperti devono starein memoria.



File system di rete

I sistemi distribuiti presentano problemiaggiuntivi nei seguenti campi:

• denominazione dei file;

• accesso remoto trasparente all’utente;

• consistenza dei dati;

• sicurezza.

In sintesi

Il file system deve assicurare:

• un’organizzazione logica semplice per gli utenti;

• accesso ai dati efficente, ma controllato.



Approfondimenti

Sciuto ed altri, "Introduzione ai sistemiInformatici", McGraw Hill, 1997, secondaedizione:

• architetture: cap. 4 , pagg. 111–180;

• programmazione: cap. 2, pagg. 17–62;

• sistema operativo: cap. 5 , pagg. 181–242.

Chiusura



Lezione 1 - Teoria computazionale


Modulo 5 - Elementi di teoria computazionale

Unità didattica 1 - Inquadramento storico-scientifico

Stefano Ferrari


Aforisma

Computer Science is no more about computers

than astronomy is about telescopes.

Edsger Dijkstra



Scienza informatica

Ogni disciplina scientifica richiede uninquadramento teorico che ne definisca:

• gli scopi;

• i limiti;

• le potenzialità.

La nascita dell’informatica risale agli anni ’30.

Dagli anni ’40 la tecnologia ha prodottostrumenti di calcolo sempre più potenti.

È una mera (e fortunata) coincidenza.

Scopi e potenzialità dell’informatica

L’informatica descrive:

• la codifica

• l’analisi

• la manipolazione

• la trasmissione

dell’informazione a prescindere dal particolarestrumento di calcolo.

I principi dell’informatica saranno validi ancheper i calcolatori che soppianterano gli attuali.



Storia della matematica

Semplificando e senza pretese di completezza:

• Greci:– numeri: entità di interesse pratico (pitagorici a parte);

– geometria: entità intuitive e assiomi ragionevoli;

• Descartes, Newton e tanti altri (1600–1700):

– geometria analitica;

– calcolo differenziale e integrale;

• Lobacevskij, Cantor, Boole (1700–1900):

– geometrie non euclidee;

– assiomatizzazione degli insiemi;

– infinito.

Quadro storico del 1900

• Hilbert (1879)

Programma formalista della matematica:– una teoria matematica formata da un insieme di assiomi e di

regole di deduzione;

– una teoria coerente e completa;

– sviluppo meccanico della matematica.

• Russel (1902)

Paradosso che mina la coerenza della teoria degliinsiemi (sui quali è costruito tutto il resto!):

– l’insieme degli insiemi che non hanno se stessi come

elemento, ha se stesso come elemento?



Incompletezza

• Gödel (1931)

Creare un sistema matematico completo e coerente èimpossibile:

– è possibile formulare asserzioni che non possono essere

dimostrate né vere, né false;

– non si può esser certi che gli assiomi dell’aritmetica non

portino a contraddizioni.

In altre parole: non si può ridurre la matematicaal calcolo automatico di teoremi a partire daassiomi e regole di deduzione.

Ma allora cosa è calcolabile?

Teoria computazionale

• Turing, Church (1936)

Formalizzazione del processo di calcolo:

– macchina calcolatrice ideale;

– sistemi formali di calcolo;

– esistenza di funzioni non calcolabili.



Tesi di Church

Tesi di Church-Turing

La classe delle funzioni intuitivamente calcolabilicoincide con quella delle funzioni calcolabili dallamacchina di Turing.

È un’asserzione praticamente indimostrabile!

Ciò è dovuto all’impossibilità di formalizzare ilconcetto di “calcolabilità intuitiva”.

È possibile dimostrarne la falsità, però nessunoc’è ancora riuscito.

Viene comunemente utilizzata come ipotesi.

Formulazioni equivalenti

• λ-calcolo (Church, 1936);

• macchina di Turing (Turing, 1936);

• funzioni ricorsive parziali (Kleene, 1936);

• macchina di Post (Post, 1936);

• calcolo dei combinatori (Schofinkel, 1924; Curry,1958);

• algoritmi di Markov (Markov, 1960).



Calcolabilità e algoritmi

Ci sono diversi gradi di calcolabilità:

• funzioni facili da calcolare;

• funzioni difficili da calcolare;

• funzioni che non si sa come calcolare:

f(x) =

{

1 esistono almeno x “5” in π

0 altrimenti

• funzioni che non si sa se si possono calcolare:

g(x) =

{

1 esistono esattamente x “5” in π

0 altrimenti

In sintesi

La teoria della computazione dice che:

• esistono funzioni definibili matematicamente che nonsi possono calcolare;

• esistono diversi formalismi (equivalenti) per ladescrizione del calcolo;

• esistono funzioni calcolabili che non si sannocalcolare;

• esistono funzioni che non si sa se si possonocalcolare;

• esistono diversi gradi di calcolabilità.



Prossimi passi

Approfondimento sulla calcolabilità.

Elementi della teoria computazionale:

• linguaggi;

• grammatiche;

• automi;

• classi di complessità.

Chiusura



Lezione 2 - Computabilità



Unità didattica 1 - Inquadramento storico-scientifico

Stefano Ferrari


Algoritmi e funzioni

Un algoritmo è una sequenza univoca diistruzioni che manipola i dati in ingresso efornisce i dati in uscita.

Come tale, è rappresentabile come una funzione.

Non è restrittivo limitare i dati in ingresso e inuscita ai soli numeri naturali.

Quindi un algoritmo, A, realizza una funzione suN, fA : N → N.



Relazione algoritmo-funzione

Una funzione f associa ad un valore x un valoref(x).

Un algoritmo che calcola f è un metodo pertrovare f(x) dato x.

È una relazione simile a quella che lega unteorema e una sua dimostrazione:

• possono esserci più algoritmi che calcolano la stessafunzione;

• se non conosciamo un algoritmo di calcolo, non èdetto che la funzione non sia calcolabile.

Numerabilità degli algoritmi

Gli algoritmi sono composti da una successionefinita di istruzioni.

Ci sono un numero finito di istruzioni.

È quindi possibile assegnare un codice ad ognialgoritmo.

Indicheremo con Pn, l’n-esimo algoritmo.



Funzioni calcolabili

Non tutte le funzioni su N sono calcolabili.

Definiamo la funzione h : N → N come:

1. input k;

2. trova Pk;

3. output Pk(k) + 1.

Non esiste j tale che Pj calcola h(·)!

Infatti Pj(j) varrebbe Pj(j) + 1: impossibile.

Alcune considerazioni

Abbiamo definito una funzione su N che non èpossibile calcolare.

Tale funzione sembrerebbe ben definita:

• ogni singolo passo è matematicamente ben definito;

• ogni singolo passo è intuitivamente calcolabile.

La conclusione è:

• non tutto ciò che possiamo definirematematicamente è calcolabile;

• serve qualche definizione più formale di ciò che èintuitivamente calcolabile.



Teoria della computazione

La teoria della computazione studia le funzioniastrattamente calcolabili, senza preoccuparsidell’efficienza dell’algoritmo che le computa.

Nasce negli anni ’30, a seguito dell’esigenza,sorta nell’ambito degli studi di logica:

• di fornire un equivalente rigoroso al concetto dialgoritmo;

• di indagare le possibilità ed i limiti dei metodi dicalcolo effettivi.

Caratteristiche della computazione (1)

Il processo di calcolo è definito dalle seguenticaratteristiche:

1. un algoritmo è di lunghezza finita;

2. esiste un esecutore che può effettuare le istruzionidell’algoritmo;

3. il calcolo è deterministico;

4. l’esecuzione avviene per passi discreti;

5. l’esecutore dispone di una memoria ausiliaria perimmagazzinare i risultati intermedidell’elaborazione;



Caratteristiche della computazione (2)

6. non c’è limite alla lunghezza dei dati;

7. non c’è limite alla quantità di memoria ausiliaria;

8. le istruzioni hanno una complessità finita;

9. l’esecuzione termina dopo un numero di passifinito, ma illimitato;

10. l’esecuzione può non terminare.

Nota: la caratteristica 10 dice che una funzionecalcolabile può essere non definita per alcunielementi del dominio.

In sintesi

Non tutte le funzioni sono calcolabili.

La teoria computazionale studia i limiti deimetodi di calcolo.



Prossimi passi

Elementi della teoria computazionale:

• linguaggi;

• grammatiche;

• automi;

• classi di complessità.

Chiusura



Lezione 1 - Linguaggi



Unità didattica 2 - Linguaggi formali

Stefano Ferrari


Alfabeto

Un alfabeto è un insieme finito e non vuoto disimboli.

Esempi:

• A = {a, b, c}

• A = { 0, 1}



Stringa

Una stringa (o parola) è una sequenza finita disimboli.

Esempio:

• se A = {a, b, c}, aaabacab è una stringa su A.

La lunghezza di una stringa w, denotata con |w|,è il numero di simboli che la compongono.

Esempio:

• |aaabacab| = 8

La stringa vuota ε è composta da zero simboli:

|ε| = 0

Sottostringhe

Sia w = a1 · · · an:

• a1 · · · aj, con j ∈ {1, . . . , n} è un prefisso di w;

• aj · · · an, con j ∈ {1, . . . , n} è un suffisso di w;

• ai · · · aj, con i, j ∈ {1, . . . , n} è una sottostringa diw;

• ε è prefisso, suffisso e sottostringa di w.



Concatenazione

La concatenazione di v e w è vw:

• la concatenazione è un’operazione associativa;

• ε ne è l’elemento neutro.

La concatenazione si estende agli alfabeti.

Per esempio, se A = {a, b, c}:

• A0 = {ε}

• A1 = {a, b, c}

• A2 = {aa, ab, ac, . . . , cc}

• A∗ = A0 ∪ A1 ∪ A2 ∪ A3 ∪ · · · = ∪iAi (chiusura di A)

Linguaggio

Un linguaggio (formale) L definito su un alfabetoA è un sottoinsieme di A∗.

Una frase di un linguaggio è una stringaappartenente al linguaggio stesso.



Esempi

Esempi:

• il linguaggio delle frasi in italiano:

– alfabeto: A = {a, b, . . . , z, <spazio>}

– stringhe su A: cosa, il porto, ghsde afe li

– frasi: la gatta corre

• il linguaggio delle espressioni aritmetiche:

– alfabeto: A = {0, . . . , 9, +, −, :, ×, (, )}

– stringhe su A: 980, 34 + 61, : ()345+)

– frasi: (25 + 12) : 3

Operazioni sui linguaggi (1)

Se L, L1 e L2 sono linguaggi su Σ, si possonodefinire le seguenti operazioni:

unione , L1 ∪ L2:

• L1 ∪ L2 = {w | w ∈ L1 ∨ w ∈ L2}

• |L1 ∪ L2| ≤ |L1| + |L2|

intersezione , L1 ∩ L2:

• L1 ∩ L2 = {w | w ∈ L1 ∧ w ∈ L2}

• |L1 ∩ L2| ≤ min(|L1|, |L2|)




differenza , L1 − L2:

• L1 − L2 = {w | w ∈ L1 ∧ w 6∈ L2}

• |L1 − L2| ≤ |L1|

complemento , L:

• Σ∗ − L

• |L| ≤ ∞


concatenazione , L1L2:

• L1L2 = {vw | v ∈ L1, w ∈ L2}

• |L1L2| = |L1| · |L2|

potenza , Ln:

• L0 = {ε}

• L1 = L

• Lk = {v1v2 . . . vk | v1, v2, . . . , vk ∈ L}

• |Lk| = |L|k




chiusura (di Kleene) , L∗:• L∗ = ∪iL

i

• se L = {ε}, |L∗| = 1

• altrimenti, |L∗| = ∞

chiusura positiva , L+:

• L+ = ∪iLi, i > 0

• L∗ = L+ ∪ {ε}

• |L+| = ∞

In sintesi

Le parole:

• sono sequenze di simboli di un alfabeto finito;

• supportano l’operazione di concatenazione.

I linguaggi:

• sono insiemi di parole;

• supportano l’operazione di concatenazione;

• supportano il concetto di chiusura.



Prossimi passi

Come definire e classificare i linguaggi:

• grammatiche;

• automi.

Chiusura



Lezione 2 - Grammatiche




Stefano Ferrari


Grammatica

Una grammatica (formale) definisce in modorigoroso un linguaggio su un alfabeto, Σ.

Tecnicamente è una quadrupla 〈Σ, V, P, S〉:• Σ, insieme finito di simboli terminali:

– può anche includere la stringa vuota, ε ;

• V , insieme finito di simboli non terminali:– sono meta-simboli di appoggio (V ∩ Σ = ∅);

– rappresentano categorie sintattiche;

• P , insieme di regole di riscrittura del tipo α → β, conα, β stringhe su Σ ∪ V , con α 6= ε;

• S ∈ V , simbolo iniziale, detto scopo.



Generazione del linguaggio

Per ottenere una frase del linguaggio:

1. si parte dallo scopo, S;

2. si applica una regola di produzione α → β:(a) si cerca la presenza della sotto-sequenza α;

(b) la si sostituisce con β;

(c) α e β sono chiamate forme di frase;

3. si procede finché non si ottiene una stringa con solisimboli terminali.

Tutte le frasi del linguaggio si ottengono conquesto procedimento.

Esempio

Grammatica: 〈Σ, V, P, S〉

• Σ = {0, 1}

• V = {X}

• P = {X → 0, X → 1X, X → 0X}

• S = X

Linguaggio: {0, 10, . . . , 0110, . . . }

• S = X → 0

• S = X → 1X → 10

• S = X → 0X → 01X → 011X → 0110



Grammatiche BNF

La notazione BNF (Backus-Naur Form) è piùconveniente per rappresentare le grammatiche:

• le regole di produzione sono della forma α ::= β;

• i meta-simboli in V sono della forma 〈nome〉;

• il meta-simbolo speciale | (pipe) è usato perl’alternativa:

– α ::= β1, α ::= β2, . . . , α ::= βn;

– α ::= β1|β2| . . . |βn.

Su http://www.faqs.org/rfcs/rfc2234.html sitrova la definizione di Augmented BNF (ABFN).

Esempio

Grammatica: 〈Σ, V, P, S〉

– Σ = {il, gatto, topo, sasso, mangia, beve}

– V = {〈frase〉, 〈sogg〉, 〈art〉, 〈nome〉, 〈verbo〉, 〈c_ogg〉}

– P = {

〈frase〉 ::= 〈sogg〉〈verbo〉〈c_ogg〉

〈sogg〉 ::= 〈art〉〈nome〉

〈art〉 ::= il

〈nome〉 ::= gatto|topo|sasso

〈verbo〉 ::= mangia|beve

〈c_ogg〉 ::= 〈art〉〈nome〉 }

– S = 〈frase〉



Albero sintattico

Esempio: il gatto mangia il sasso

il

〈art〉

gatto

〈nome〉

〈sogg〉

mangia

〈verbo〉

il

〈art〉

sasso

〈nome〉

〈c_ogg〉

〈frase〉

S

In sintesi

Una grammatica:

• definisce un insieme di regole per generare unlinguaggio;

• fa uso di metasimboli;

• fa uso di regole di produzione.



Prossimi passi

Una classificazione delle grammatiche e deilinguaggi da esse generati.

Chiusura



Lezione 3 - Classificazione di Chomsky




Stefano Ferrari


Classificazione di Chomsky

È possibile caratterizzare le grammatiche sullabase della forma delle loro regole di produzione:

• Tipo 3 (regolari);

• Tipo 2 (context-free);

• Tipo 1 (context-sensitive);

• Tipo 0 (a struttura di frase).



Grammatiche di tipo 3

Le grammatiche regolari si dividono in:

• lineari a destra, F ::= α, F ::= αG;

• lineari a sinistra, F ::= α, F ::= Gα;

con F, G ∈ V, α ∈ Σ∗.

Esempi:

• F ::= aG|a, G ::= bG|b|aF

• F ::= Fa|a

Il linguaggio generato si dice di tipo 3 (olinguaggio regolare).


Le grammatiche context-free (libere dalcontesto) hanno produzioni della forma:

F ::= α, con F ∈ V e α ∈ (Σ ∪ V )∗.

Esempi:• F ::= aG|a, G ::= Gb|b|Fc

• F ::= aFc|b

Si dice che il linguaggio è di tipo 2 (o linguaggiolibero dal contesto).

Tipicamente, i linguaggi di programmazioneappartengono a questo tipo.




Le grammatiche context-sensitive (dipendentidal contesto) hanno produzioni della forma:• αFβ ::= αγβ, α, β, γ ∈ (Σ ∪ V )∗, γ 6= ε, F ∈ V ;

• S ::= ε.

Note:• α e β definiscono il “contesto” in cui la sostituzione

F ::= γ può avvenire;

• per una produzione della prima forma, la lunghezzadella stringa generata non può diminuire.

Esempio: aFb ::= aFbGb


Le grammatiche di tipo 0 ammettono produzionidi qualsiasi forma:

• α ::= β, con α, β ∈ (Σ ∪ V )∗.

Nota: sono ammesse anche produzioni che possonodiminuire la lunghezza della stringa generata.



Gerarchia di grammatiche e linguaggi

Ogni grammatica di tipo n è anche unagrammatica di tipo n − 1.

Un linguaggio è di tipo n se esiste unagrammatica di tipo n che lo genera, ma nonnessuna di tipo n + 1 è in grado di generarlo.

Esempi:

• linguaggio di tipo 3: {ambn | m, n ≥ 0}

• linguaggio di tipo 2: {anbn | n ≥ 0}

• linguaggio di tipo 1: {anbncn | n ≥ 0}

• linguaggio di tipo 0: {an | n è un numero primo}

Grammatiche ambigue

Una grammatica si dice ambigua se qualchestringa del linguaggio da essa generato puòessere generata mediante più alberi sintattici.

Esempio: con la regola F ::= FaF |FbF |f , lagenerazione della stringa fafbf non è univoca.

Infatti:• F → FaF → faF → faFbF → fafbF → fafbf

• F → FbF → Fbf → FaFbf → faFbf → fafbf

Un linguaggio si dice inerentemente ambiguo senon esiste alcuna grammatica non ambigua chelo generi.



In sintesi

Le grammatiche sono descrizioni induttive dilinguaggi.

Secondo la classificazione di Chomsky, essecostituiscono una gerarchia di quattro livelli.

Ogni livello:

• è caratterizzato da qualche vincolo alle regole diproduzione;

• genera una classe di linguaggi.

Prossimi passi

Esercizi su linguaggi e grammatiche.



Chiusura



Lezione 4 - Esercizi su linguaggi egrammatiche




Stefano Ferrari


Esercizio 1 (1)

Definiti i linguaggi:

• L1 = {aa, ab, bc, c}

• L2 = {1, 22, 31}

descrivere i linguaggi:

a) L3 = L∗

1

b) L4 = L1L2

c) L5 = L1L∗

2

d) L6 = L1 ∪ L2

e) L7 = (L1L2)∗

f) L8 = (L1 ∪ L2)∗



Esercizio 1 (2)

a) L3 = L∗

1è formato dalla concatenazione di un

numero arbitrario (anche nullo) di elementi di L1.

L3 = {ε, aa, c, cababc, . . . }

b) L4 = L1L2 è formato dalla concatenazione di unelemento di L1 con un elemento di L2.

L4 = {aa1, ab1, bc1, c1, aa22, ab22,

bc22, c22, aa31, ab31, bc31, c31}

c) L5 = L1L∗

2è formato dalla concatenazione di un

elemento di L1 con un numero arbitrario (anchenullo) di elementi di L2.

L5 = {aa, . . . , c, bc1223131, ab111312222, . . . }

Esercizio 1 (3)

d) L6 = L1 ∪ L2 è l’unione di L1 e L2.

L6 = {aa, ab, bc, c, 1, 22, 31}

e) L7 = (L1L2)∗ è la chiusura di L4.

È pertanto formato da una sequenza(eventualmente vuota) di elementi di L4.

L7 = {ε, aa22c1, ab1aa1, . . . }

f) L8 = (L1 ∪ L2)∗ è la chiusura di L6.

È pertanto formato da una sequenza(eventualmente vuota) di elementi di L6.

L8 = {ε, c1122aaccbc, 22131311aa, aa, 1, . . . }



Esercizio 2 (1)

Data la grammatica G = 〈Σ, V, P, S〉:

• Σ = {a, b}

• V = {S, A, B}

• P = {S ::= B|a, B ::= bA|aA, A ::= aB|b}

mostrare la sequenza di regole da applicare pergenerare le seguenti frasi:

a) bb

b) aababb

c) babaab

Esercizio 2 (2)

a) bb S ::= B|a, B ::= bA|aA, A ::= aB|b

bb

S

S ::= B B

B ::= bA bA

A ::= b bb



Esercizio 2 (3)

b) aababb S ::= B|a, B ::= bA|aA, A ::= aB|b

aababb

S

S ::= B B

B ::= aA aA

A ::= aB aaB

B ::= bA aabA

A ::= aB aabaB

B ::= bA aababA

A ::= b aababb

Esercizio 2 (4)

c) babaab S ::= B|a, B ::= bA|aA, A ::= aB|b

babaab

S

S ::= B B

B ::= bA bA

A ::= aB baB

B ::= bA babA

A ::= aB babaB

B ::= aA babaaA

A ::= b babaab



Esercizio 3 (1)


• Σ = {a, b, c}

• V = {S, A, B}

• P = {S ::= A|aA, A ::= Ab|bAB|b, B ::= cB|c}


a) bbb

b) abbcc

c) abbbcc

Esercizio 3 (2)

a) bbb S ::= A|aA, A ::= Ab|bAB|b, B ::= cB|c

bbb

S

S ::= A A

A ::= Ab Ab

A ::= Ab Abb

A ::= b bbb



Esercizio 3 (3)

b) abbcc S ::= A|aA, A ::= Ab|bAB|b, B ::= cB|c

abbcc

S

S ::= aA aA

A ::= bAB abAB

A ::= b abbB

B ::= cB abbcB

B ::= c abbcc

Esercizio 3 (4)

c) abbbcc S ::= A|aA, A ::= Ab|bAB|b, B ::= cB|c

abbbcc

S

S ::= aA aA

A ::= bAB abAB

A ::= bAB abbABB

A ::= b abbbBB

B ::= c abbbcB

B ::= c abbbcc

abbbcc

S

S ::= aA aA

A ::= bAB abAB

A ::= Ab abAbB

A ::= b abbbB

B ::= cB abbbcB

B ::= c abbbcc

Ambigua!



Esercizio 4 (1)


• Σ = {a, b, c}

• V = {S, A, B}

• P = {S ::= A|aA, A ::= aAb|b|AB, B ::= b|ABa|c}


a) aabbcbb

b) aabbbca

Esercizio 4 (2)

a) b)

aabbcbb

S

S ::= A A

A ::= aAb aAb

A ::= aAb aaAbb

A ::= AB aaABbb

B ::= c aaAcbb

A ::= AB aaABcbb

A ::= b aabBcbb

B ::= b aabbcbb

aabbbca

S

S ::= aA aA

A ::= AB aAB

B ::= ABa aAABa

B ::= c aAAca

A ::= b aAbca

A ::= aAb aaAbbca

A ::= b aabbbca



In sintesi

La descrizione insiemistica di linguaggi.

Le grammatiche come descrizione generativa dilinguaggi:

• sequenze di regole di produzione per la generazionedi stringhe di un linguaggio.

Se la grammatica è regolare, la generazione èsemplice.

Se la grammatica non è regolare, la generazioneè complicata.

Prossimi passi

Modelli di macchine da calcolo.

Espressioni regolari.



Chiusura



Lezione 1 - Automi a stati finiti



Unità didattica 3 - Automi

Stefano Ferrari


Automa a stati finiti (1)

Un automa a stati finiti è un modello matematicocaratterizzato da:

• un input costituito da una sequenza di elementidiscreti;

• eventualmente, un output (anch’esso a valoridiscreti);

• un insieme finito di stati nei quali l’automa puòtrovarsi durante l’esecuzione.



Automa a stati finiti (2)

Un automa a stati finiti si può immaginare comeun dispositivo dotato di una testina.

L’automa legge spostandosi sempre nella stessadirezione lungo un nastro di lunghezza illimitatacontenente dei simboli.

A seconda del simbolo letto, l’automa si porta inun altro stato.

Ripete queste operazioni fino a quando non leggeun simbolo terminale.

Definizione formale

Un automa a stati finiti deterministico (DFA) èuna quintupla 〈Q, Σ, δ, q0, F 〉 dove:

• Q è l’insieme degli stati (finito);

• Σ è l’alfabeto di input;

• δ : Q × Σ → Q è la funzione di transizione;

• q0 è lo stato iniziale;

• F ⊂ Q è l’insieme degli stati finali.



Funzione di transizione

La funzione di transizione può essererappresentata in forma tabellare.

Esempio:

δ a b c d e

q0 q0 q0 q2 q1 q1

q1 q1 q3 q1 q1 q1

q2 q3 q2 q2 q0 q1

q3 q0 q1 q1 q0 q1

dove:

• Q = {q0, q1, q2, q3}

• Σ = {a, b, c, d, e}

Rappresentazione grafica

Un DFA può essere rappresentato da un grafo:

q0

d, e

c

a, b

q1

a, c, d, e

b

q2a

b, c

d

e

q3

a, d

b, c, e

dove:

• Q = {q0, q1, q2, q3}

• Σ = {a, b, c, d, e}

• F = {q1}



Linguaggio accettato da un DFA (1)

Il concetto di funzione di transizione può essereestesa in modo da essere applicataripetutamente ad una successione di simboli ininput.

Si dice che un DFA accetta una stringa se, dopoaverla letta, esso si ritrova in uno stato finale.

L’insieme delle stringhe accettate da un DFAviene detto linguaggio accettato dal DFA stesso.

Linguaggio accettato da un DFA (2)

Più formalmente:

• l’estensione di δ alle stringhe, δ̂ : Q × Σ∗ → Q, sidefinisce in modo univoco come:

δ̂(q, x) =

{

q se x = ε

δ(δ̂(q, w), y) se x = wy, w ∈ Σ∗, y ∈ Σ

• una stringa x viene accettata dal DFA

M = 〈Q, Σ, δ, q0, F 〉 se δ̂(q0, x) ∈ F ;

• il linguaggio L(M) = {x ∈ Σ∗ | δ̂(q0, x) ∈ F} è illinguaggio accettato da M .



Automa non-deterministico

Un automa a stati finiti non-deterministico (NFA)è una quintupla 〈Q, Σ, δ, q0, F 〉 dove:

• Q è un insieme finito di stati;

• Σ è un alfabeto (alfabeto di input);

• δ : Q × Σ → ℘(Q) è la funzione di transizione;

• q0 è lo stato iniziale;

• F ⊂ Q è l’insieme degli stati finali.

Nota: ora è ammesso δ(q, a) = ∅ per qualcheq ∈ Q e a ∈ Σ.

Linguaggio accettato da un NFA

Dalla funzione δ si definisce in modo univocoδ̂ : Q × Σ∗ → ℘(Q):

δ̂(q, x) =

{q} se x = ε⋃

p∈δ̂(q, w)

δ(p, y) se x = wy, w ∈ Σ∗, y ∈ Σ

Una stringa x viene accettata dal NFA

M = 〈Q, Σ, δ, q0, F 〉 se δ̂(q0, x) ∩ F 6= ∅.

Il linguaggio L(M) = {x ∈ Σ∗ | δ̂(q0, x) ∩ F 6= ∅} è illinguaggio accettato da M .



Confronto DFA-NFA

La “potenza di calcolo” di un NFA è la stessa diun DFA.

Ciò significa che per ogni linguaggio accettato daun NFA, esiste un DFA che accetta lo stessolinguaggio.

La classe di linguaggi accettati dai DFA è laclasse dei linguaggi regolari.

Si può generare in modo automatico il DFAequivalente di un dato NFA.

A volte è più comodo progettare un NFA e poiconvertirlo.

Limiti dei DFA

Un DFA è un dispositivo a memoria finita, quindiè adatto a risolvere solo quei problemi checonsentono di limitare a priori la lunghezza dellesequenze d’ingresso di cui tenere memoria.

Da cosa deriva la mancanza di espressività?

• Il numero di stati è fissato a priori non consente ditrattare quei problemi che richiedono un conteggiosenza limite fissato.– Esempio: un DFA a 4 stati può riconoscere aaacbbb ma non

aaaacbbbb.

• Rendere il numero degli stati infinito non èpraticabile.



In sintesi

Un automa a stati finiti è un modello di calcoloche permette di effettuare semplici elaborazionisu una stringa di simboli data di ingresso.

L’elaborazione più semplice è il riconoscimentodi una stringa come appartenente ad un datolinguaggio.

Esistono varianti del DFA, ma tutte hanno lastessa espressività.

Prossimi passi

Esercizi sui DFA.

Modelli di calcolo più potenti.



Chiusura



Lezione 2 - Esercizi sugli automi astati finiti




Stefano Ferrari


Esercizio 1 (1)

Costruire un DFA su Σ = {0, 1} che accettil’insieme di tutte le stringhe aventi tre 0

consecutivi.

Osservazioni:

• l’alfabeto è dato (Σ = {0, 1});

• si possono individuare le seguenti possibili situazioni:

(a) sono già stati letti tre (o più) “0” consecutivi;

(b) gli ultimi due simboli letti sono “0”;

(c) l’ultimo simbolo letto è “0”;

(d) l’ultimo simbolo letto è “1”.



Esercizio 1 (2)

Indicando con qi lo stato in cui l’automa sitroverà dopo aver letto i simboli “0” consecutivi:

• situazione (a) ↔ q3;

• situazione (b) ↔ q2;

• situazione (c) ↔ q1;

• situazione (d) ↔ q0;

Note:

• dopo aver letto tre “0”, l’automa accetterà la stringaqualunque siano i simboli ancora da leggere;

• q3 assume quindi il ruolo di stato finale;

• q0 assume il ruolo di stato iniziale;

• uno stato dal quale non si esce viene detto “pozzo”.

Esercizio 1 (3)

La funzione di transizionepuò essere:

δ 0 1

q0 q1 q0

q1 q2 q0

q2 q3 q0

q3 q3 q3

e il grafico:

q0

1

0

q1

1

0

q2

1

0

q3

0, 1



Esercizio 2 (1)

Costruire un DFA su Σ = {0, 1} che accettil’insieme di tutte le stringhe che se interpretatein notazione binaria risultino divisibili per 2.

Osservazioni:


• i numeri pari in notazione binaria terminano per 0;

• un numero in notazione binaria che termina per 0 èpari;

• il problema diventa costruire l’automa che accettasolo le stringhe binarie che terminano per 0.

Esercizio 2 (2)

Se, banalmente, indichiamo con qi lo stato in cuiviene a trovarsi l’automa dopo aver letto ilsimbolo i:

• ponendo q0 come unico stato finale facciamo sì chel’automa accetti la stringa solo se l’ultimo simboloche ha letto è stato 0;

• ponendo q1 come stato iniziale evitiamo che vengaaccettata la stringa vuota.



Esercizio 2 (3)

Quindi, l’automa può essere formalizzato come:

• Q = {q0, q1}

• Σ = {0, 1}

• q1 è lo stato iniziale

• F = {q0}

• δ 0 1

q0 q0 q1

q1 q0 q1

q0

1

0

q1

1

0

Esercizio 3 (1)

Costruire un DFA su Σ = {0, 1} che accettil’insieme di tutte le stringhe che hanno comepenultimo simbolo “0”.

Osservazioni:


• abbiamo bisogno di una finestra di due simboli (gliultimi due simboli letti);

• consideriamo quindi quattro situazioni: 00, 01, 10 e11.



Esercizio 3 (2)

Ad esempio, se l’automa si trova nello stato 01 elegge “1”, si deve portare nello statocorrispondente a 11.

Con questa regola:

• le situazioni accettate saranno 00 e 01;

• scegliendo 11 come situazione iniziale, evitiamo diaccettare stringhe con meno di due caratteri;

• codifichiamo con lo stato qi la situazione in cui gliultimi due simboli letti sono interpretati come larappresentazione binaria di i.

Esercizio 3 (3)

Quindi, l’automa può essere formalizzato come:

• Q = {q0, q1, q2, q3}

• Σ = {0, 1}

• q3 è lo stato iniziale

• F = {q0, q1}

• δ 0 1

q0 q0 q1

q1 q2 q3

q2 q0 q1

q3 q2 q3



In sintesi

Progettazione di automi su stringhe binarie consemplici regole di accettazione.

Altri esercizi:

• regole più complesse:

– accettare le stringhe binarie divisibili per 3;

• alfabeti più estesi:

– accettare le stringhe decimali divisibili per 2 (o per 3);

• casi reali:

– unità per il controllo di un distributore di bevande.

Prossimi passi

Modelli di calcolo più espressivi.



Chiusura



Lezione 3 - Altri modelli di calcolo




Stefano Ferrari


Automa a pila (1)

Un automa a pila è una macchina ideale cheestende le possibilità degli automi a stati finiti.

Si tratta di un automa a stati finiti dotato di unastruttura dati aggiuntiva per la memorizzazionedelle informazioni, la pila:

• struttura dati di tipo Last In First Out (LIFO).



Automa a pila (2)

Un automa a pila è quindi composto da:

• controllo (stati + funzione di transizione);

• input (nastro);

• output (pila):

– push(w): pone la stringa w sulla pila;

– pop(w): preleva la stringa in testa alla pila;

– empty: verifica se la pila è vuota (restituisce un valore

booleano).

Funzionamento dell’automa a pila

L’automa legge dal nastro e dalla pilacontemporaneamente.

Ogni passo di esecuzione comporta:

• la lettura di un simbolo da nastro e l’avanzamentodella testina di una posizione;

• la lettura di un simbolo dalla testa della pila;

• il cambio dello stato di controllo;

• la scrittura in testa alla pila.

Nota: alcune operazioni possono essere saltate(lettura/scrittura della stringa vuota).



Stringhe accettate dall’automa a pila

L’automa ha due possibili condizioni perl’accettazione della stringa:

• se si trova in uno stato finale;

• se la pila è vuota.

Le due condizioni sono equivalenti:

• dato un automa che termina per pila vuota, se nepuò costruire uno che termina per stato finale.

Linguaggi accettati dall’automa a pila

Il non-determinismo, aggiunge potenzaespressiva all’automa a pila.

L’automa a pila deterministico riconosce unsottoinsieme dei linguaggi context-free (tipo 2).

L’automa a pila non-deterministico riconosce ilinguaggi context-free.

Per esempio:

• un automa a pila riesce a riconoscere le parentesiben accoppiate (an

bn);

• solo un automa non-deterministico riesce ariconoscere le stringhe palindrome.



Limiti degli automa a pila

Da cosa deriva la mancanza di espressività?

• la struttura dati di supporto, la pila, ha un accessolimitato, che si limita alla testa della pila;

– come accedere al primo degli elementi inseriti?

Per poter riconoscere linguaggi di tipo 1 o 0bisogna disporre di una struttura dati piùflessibile.

Macchina di Turing

Macchina ideale pensata da Alan Turing neglianni ’30 per formalizzare la nozione di agente dicalcolo (computer).

Una macchina di Turing (MdT) è composta da:

• nastro: infinito, abilitato alla lettura ed allascrittura;

• controllo: automa a stati finiti deterministico.



Funzionamento della MdT

Ad ogni passo di computazione, una MdT:

• legge il simbolo sul nastro in corrispondenza dellatestina;

• in base alla coppia stato-simbolo:

– eventualmente modifica il simbolo;

– sposta il nastro di una casella, a destra o a sinistra;

– eventualmente cambia lo stato.

La computazione della MdT termina quando nonè definita alcuna transizione per la coppiastato-simbolo.

Varianti della MdT

Esistono diverse varianti della MdTdeterministica.

Ad esempio:

• multinastro;

• multitestina;

• nastro semi-infinito;

• non-deterministica.

Si può dimostrare che per ognuna di questevarianti si può costruire una MdT deterministicaequivalente.



MdT universale

È possibile costruire una MdT che simuli unaqualsiasi MdT!

Questa MdT viene detta universale.

All’inizio, sul nastro della MdT universale,opportunamente codificati, si trovano:

• la descrizione della MdT da simulare (cioè della partedi controllo);

• il suo input.

Linguaggi accettati

Una MdT riconosce i linguaggi di tipo 0.

Una MdT non deterministica con lunghezza delnastro limitata in modo proporzionale allalunghezza dell’input riconosce i linguaggi di tipo1.



In sintesi

Gli automi a pila e la MdT sono potenziamentidegli automi a stati finiti.

Gli automi a pila non-deterministici sonoabbastanza potenti da riconoscere i linguaggicontext free.

La macchina di Turing non-deterministica connastro limitato è in grado di riconoscere ilinguaggi dipendenti dal contesto.

La macchina di Turing è in grado di riconoscere ilinguaggi di tipo 0.

Prossimi passi

Qualche osservazione aggiuntiva su linguaggi,grammatiche e computabilità.

Approfondimento sui linguaggi regolari:espressioni regolari.



Chiusura



Lezione 4 - Linguaggi e computabilità




Stefano Ferrari


Caratteristiche della MdT (1)

La MdT è stata ideata per modellare il processodi calcolo.

Infatti, ha le seguenti caratteristiche:

1. il controllo è costituito da un numero finito diistruzioni;– un algoritmo è di lunghezza finita;

2. la MdT è l’agente di calcolo che eseguel’elaborazione;– esiste un esecutore che può effettuare le istruzioni

dell’algoritmo;

3. il controllo è affidato ad un automa deterministico;– il calcolo è deterministico;




4. la MdT opera per passi discreti;– l’esecuzione avviene per passi discreti;

5. il nastro è un dispositivo di memorizzazione perl’MdT;– l’esecutore dispone di una memoria ausiliaria per

immagazzinare i risultati intermedi dell’elaborazione;

6. i dati sono memorizzati sul nastro, il quale èillimitato;– non c’è limite alla lunghezza dei dati;

7. la capacità del nastro è illimitata;– non c’è limite alla quantità di memoria ausiliaria;


8. le istruzioni che la MdT può eseguire ad ogni passosono semplici e ben definite;– le istruzioni hanno una complessità finita;

9. non esiste nessuna limitazione al numero di passi dicalcolo;– l’esecuzione termina dopo un numero di passi finito, ma

illimitato;

10. è possibile creare una MdT che continua ad eseguiredelle istruzioni senza terminare mai;– l’esecuzione può non terminare.



Calcolo

Una MdT calcola funzioni (su N):

• funzioni intuitivamente calcolabili;

• l’input è sul nastro all’inizio del calcolo;

• l’output è sul nastro alla fine del calcolo.

Anche gli altri automi meno potenti possonoessere modificati per effettuare dei calcoli (cioègenerare un output).

Terminazione

La computazione di un automa a stati finiti o apila termina sempre.

La computazione di una MdT per un certo dato diinput può non terminare.

È l’equivalente algoritmico di una funzione nondefinita per un dato argomento (funzioneparziale).



Linguaggi, grammatiche, automi (1)

Le grammatiche danno una descrizionegenerativa dei linguaggi.

Una grammatica è simile ad una teoria:

• assiomi (simboli iniziali);

• regole di inferenza (regole di produzione);

• predicati validi (stringhe del linguaggio);

• dimostrazioni (produzioni).

Linguaggi, grammatiche, automi (2)

Un automa realizza una funzione diriconoscimento della stringa come appartenenteal linguaggio.

La MdT ha la potenza computazionale necessariae sufficiente per l’accettazione dei linguaggi ditipo 0:

• se G è una grammatica di tipo 0 e L = L(G) è illinguaggio da essa generato, allora esiste una MdT,ML, che accetta L;

• se L è un linguaggio accettato da una MdT, ML,allora esiste una grammatica di tipo 0, G, tale cheL = L(G).



Linguaggi e computabilità

Restringere lo studio della computabilità ailinguaggi non è restrittivo.

Inoltre, lo studio dei vari tipi di linguaggi è utileperché fornisce:

• una scala di complessità di calcolo;

• uno strumento di descrizione di algoritmi:

– riconoscibilità (sintassi);

– interpretazione (semantica).

Accettabilità e decidibilità

La non terminazione rende necessaria unaulteriore distinzione:

• un linguaggio viene detto accettabile (o riconoscibile)da un automa se esso è in grado di accettare tutte lesue parole;

– nulla viene richiesto se la parola in input non appartiene al

linguaggio dato;

• un linguaggio viene detto decidibile da un automa seesso è in grado di accettare tutte le sue parole e dirifiutare tutte le altre parole.

In altri termini, se un linguaggio è decidibile, lodeve essere anche il suo complemento.



Decidibilità dei linguaggi

I linguaggi di tipo 1, 2 e 3 sono decidibili.

I linguaggi di tipo 0 sono riconoscibili.

Tuttavia esistono linguaggi decidibili che nonsono di tipo 1.

Ogni definizione finita della decidibilità non puòcomprendere tutti gli insiemi decidibili.

In sintesi

Lo studio dei linguaggi non è riduttivo nelcontesto della calcolabilità.

La non terminazione della MdT:

• rende possibile il calcolo delle funzioni parziali (e,quindi, di tutte le funzioni intuitivamente calcolabili);

• evidenzia l’esistenza di funzioni non calcolabili;

• evidenzia l’esistenza di linguaggi riconoscibili, manon decidibili.



Prossimi passi

Dalla calcolabilità alla complessità.

Chiusura



Lezione 5 - Decidibilità e complessità




Stefano Ferrari


Problemi indecidibili (1)

È noto un certo insieme di problemi nondecidibili:• halting problem: non esiste alcuna MdT, MH, che,data la descrizione di una MdT, M , e una stringa diinput, w, decida se la computazione M(w) termina,oppure no;

• non esiste nessuna MdT, ME, che, data la descrizionedi una MdT, M , possa decidere se il linguaggioriconosciuto da M , L(M), sia vuoto, oppure no;

• non esiste alcuna MdT, MR, che, data la descrizionedi una MdT, M , decida se il linguaggio da essariconosciuto, L(M), sia di un tipo dato;




Anche nella pratica si incontrano problemiindecidibili:

• un programma chiamerà una sua procedura nel corsodell’esecuzione per un dato input?

• una variabile assumerà un dato valore durantel’esecuzione?

– uscirà dal ciclo?

• un dato programma, in presenza di un dato input,fornirà un particolare output?

• due programmi dati calcolano la stessa funzione?


• un programma calcola una funzione costante?

– il suo output è indipendente dall’input?

• un programma calcola una funzione totale?

– termina per ogni input?

• un programma calcola una funzione positiva?

• una data formula del calcolo dei predicati è unteorema?

• una data formula dell’aritmetica, è un teorema?



Limite del calcolo

La MdT rappresenta il limite per i dispositivi finiti.

Non è l’unico paradigma del genere, ma tutti glialtri si sono dimostrati equivalenti.

La dimostrazione dell’indecidibilità di alcuniproblemi equivale infatti al teorema di Gödel.

Tuttavia, tra la maggior parte dei problemipratici sono decidibili (e, quindi, calcolabili).

Teoria della complessità

Nella pratica dato un problema computabile:• bisogna sapere come calcolare la soluzione(algoritmo);

• bisogna sapere scegliere la soluzione meno onerosa.

La teoria della computazione non tiene contodell’efficienza: ogni computazione è istantaneaperché ogni passo di computazione è tale.

La teoria della complessità studia le risorsecomputazionali necessarie per l’esecuzione di unalgoritmo.



Complessità

La complessità di un algoritmo è definibileprincipalmente in due modi:

• come il numero di operazioni che esso deve fare pergiungere alla soluzione (complessità temporale);

• come il numero di celle di memoria necessarie per ilcalcolo (complessità spaziale).

È evidente che in entrambi i casi la misura dellacomplessità dipenda da:

• l’agente di calcolo impiegato;

• la dimensione del dato di input.

Misura di complessità

Il paradigma di calcolo di riferimento è la MdT.

Tipicamente, l’attenzione è posta sulle misure dicomplessità temporale:• la complessità spaziale non può superare quellatemporale;

• nella pratica, generalmente lo spazio è una risorsameno preziosa del tempo;– però, per esempio, a volte è utile usare la compressione dei

dati!



Misura di complessità

La complessità viene misurata con la notazioneO(·), in relazione alla dimensione dei dati iniziali.

Tale notazione indica il comportamentoasintottico rispetto alla dimensione dell’input.

Per esempio, se gli algoritmi A1, A2 e A3 sono,rispettivamente, O(n), O(n2) e O(2n), sono dicomplessità, lineare, quadratica ed esponenziale.

Perciò, se per elaborare una lista di 10 nomiimpiegano tutti 1 s, dobbiamo aspettarci che per30 nomi A1 impieghi 3 s, A2 9 s e A3 260 s.

Classificazione dei problemi

Ci sono infinite classi di complessità:

O(1) < O(log n) < O(√

n) < O(n) < O(n log n) <

< O(n√

n) < O(n2) < O(n3) < O(2n) < O(n2n) < . . .

Però, la classificazione principale è in problemi:• trattabili: O(nk), per qualche k;

• intrattabili: O(f(n)), con f(n) > nk ∀k, n → ∞.

La suddivisione è arbitraria, ma ben motivata:

a. l’insensibilità degli algoritmi O(kn) al progresso;

b. l’invarianza delle classi rispetto ai differentiparadigmi di calcolo.



Problemi intrattabili

a. A fronte di un progresso tecnologico che renda icalcolatori 1000 volte più veloci, le nuovedimensioni dei problemi risolubili in 1 s daglialgoritmi A1, A2 e A3 precedenti, sarebbero:

– A1, O(n): 10 000 nomi;

– A2, O(n2): 100 nomi;

– A3, O(2n): 20 nomi.

b. La complessità di conversione di una MdT in unparadigma di calcolo equivalente è polinomiale.

Anche cambiando il paradigma di riferimento latrattabilità di un algoritmo non può cambiare.

Problemi P e NPLa trattabilità dei problemi si formalizza con leclassi di problemi P e NP:• P: classe dei problemi risolvibili in tempopolinomiale da una MdT deterministica;

• NP: classe dei problemi risolvibili in tempopolinomiale da una MdT non-deterministica.



P vs NP problem

Uno dei problemi aperti dell’informatica è:

P 6= NP?

È uno dei sette Millennium Problems posti dalClay Mathematics Institute (USA):

• un premio da un milione di dollari a chi lo risolve;

• http://www.claymath.org/millennium/

Esistono problemi detti NP-completi a cuipossono essere ricondotti gli altri problemi NP.Dimostrare che un problema NP-completo è in Pimplicherebbe P = NP.

In sintesi

I problemi si dividono in:

• indecidibili;

• intrattabili;

• trattabili.



Prossimi passi

Le espressioni regolari.

Chiusura



Lezione 1 - Espressioni regolari



Unità didattica 4 - Espressioni regolari

Stefano Ferrari


Espressioni regolari

Le espressioni regolari (ER) sono un metodoalternativo per descrivere i linguaggi regolari.

L’insieme delle ER descrive quindi la stessaclasse di linguaggi delle grammatiche regolari edegli automi a stati finiti.

Esse presentano i seguenti vantaggi:

• offrono una notazione compatta;

• sono facilmente intelleggibili;

• offrono una descrizione di tipocostruttivo/operazionale.



Alfabeto di una espressione regolare

Una espressione regolare:

• è una stringa su un alfabeto Σ ∪ {∅, +, ∗, (, )};

• denota un insieme di stringhe di Σ∗.

Una espressione regolare è dunque composta di:

• simboli dell’alfabeto su cui definito il linguaggio daessa descritto, Σ;

• un insieme di metasimboli usati per indicare leoperazioni sui linguaggi,{∅, +, ∗, (, )}.

Sintassi e semantica delle ER

L’insieme delle stringhe denotate da una ER èdefinito ricorsivamente come:

espressioneregolare

insiemedescritto

note

∅ ∅

ε {ε}

a {a} a ∈ Σ

(r + s) R ∪ S r e s sono ER chedenotanorispettivamente gliinsiemi R e S

(rs) RS

(r∗) R∗



Esempio 1

L’ER (0 + 1)∗0 indica le stringhe binarie pari.

Infatti:

• 0 + 1 è l’insieme dei simboli binari;

• (0 + 1)∗ è una qualsiasi stringa binaria(eventualmente vuota);

• (0 + 1)∗0 è una qualsiasi stringa binaria terminatacon 0.

Esempio 2

L’ER (0 + 1)∗111(0 + 1)∗ indica le stringhe binarieche contengono almeno tre simboli 1 consecutivi.

Infatti:

• (0 + 1)∗ è una qualsiasi stringa binaria;

• 111 è la stringa costituita da tre 1 consecutivi.

L’ER data descrive anche:

• le stringhe che iniziano per 111;

• le stringhe che terminano per 111;

• la stringa 111.



Esempio 3

L’ER ((0 + 1)2)∗(0 + 1) indica le stringhe binarie dilunghezza dispari.

Infatti:

• (0 + 1)2 è una qualsiasi stringa binaria di lunghezza2;

• ((0 + 1)2)∗ è una qualsiasi stringa binaria dilunghezza pari;

• ((0 + 1)2)∗(0 + 1) è una qualsiasi stringa binaria dilunghezza dispari.

L’ER data descrive anche le stringhe di lunghezza1.

Estensioni

La sintassi ER può essere arricchita:

ER insieme descritto note

(r+) R+ = R∗ − {ε} r denotal’insieme R(r?) R ∪ {ε}

Inoltre, a seconda delle situazioni d’uso:

• metasimboli per l’indicazione di Σ o di suoisottoinsiemi;

• altri operatori (complemento, sottoespressioni);

• eliminazione di parentesi superflue (regole diprecedenza, associatività di alcune operazioni).



Uso delle espressioni regolari

Le ER vengono utilizzate in diversi ambienti:

• linguaggi di programmazione (Perl, PHP, Python,JavaScript, Java);

• shell (DOS, bash);

• programmi di utilità (grep, expr, sed, awk).

Esempi:

• lista di tutti i file eseguibili (in DOS shell):

C:> dir *.EXE

• lista degli accessi dal dominio 159.149 (con grep):

grep -E "^159\.149(\.[0-9]{1,3}\){2}" access.log

In sintesi

Le espressioni regolari:

• descrivono i linguaggi regolari;

• sono costituite da stringhe di simboli e metasimboli;

• nella pratica, sono di più facile utilizzo rispetto agrammatiche e automi;

• vengono usate in molteplici ambienti.



Prossimi passi

Utilizzo di espressioni regolari:

• esercizi;

• esempi d’uso pratico.

Chiusura



Lezione 2 - Esercizi sulle espressioniregolari




Stefano Ferrari


Esercizio 1 (1)

Scrivere una espressione regolare (ER) perstringhe binarie che descriva tutte le stringheche contengono almeno tre 1.

Soluzione

L’ER richiesta può essere descrittadiscorsivamente come una stringa che ha tresimboli 1:

• intervallati da una qualsiasi stringa binaria;

• preceduti da una qualsiasi stringa binaria;

• seguiti da una qualsiasi stringa binaria.



Esercizio 1 (2)

Quindi, una ER che risponde ai requisiti è:

(0 + 1)∗1(0 + 1)∗1(0 + 1)∗1(0 + 1)∗

che può essere scritta più sinteticamente come:

((0 + 1)∗1)3(0 + 1)∗

o, equivalentemente:

(0 + 1)∗(1(0 + 1)∗)3

Tuttavia, tale descrizione è ridondante: alcunisimboli delle generiche stringhe binarieintercalanti potrebbero essere 1.

Esercizio 1 (3)

Quindi, la descrizione informale può diventare:

• una stringa che ha tre simboli 1;

• intervallati da una qualsiasi sequenza di 0;

• preceduti da una qualsiasi sequenza di 0;

• seguiti da una qualsiasi stringa binaria.

Usando la sintassi ER:

(0∗1)3(0 + 1)∗

Con ragionamento analogo: (0 + 1)∗(10∗)3.



Esercizio 2 (1)

Scrivere una espressione regolare per stringhe ditesto che descriva le date in formatoGG/MM/AAAA.

Soluzione

Per comodità, definiamo l’insieme delle cifredecimali:

D = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}

e l’espressione regolare corrispondente:

D = (0 + 1 + 2 + 3 + 4 + 5 + 6 + 7 + 8 + 9)

Esercizio 2 (2)

L’espressione regolare cercata può ora essereespressa come:

D2/D2/D4

Nota: Oltre alle date, l’ER data descrive anchestringhe che non hanno significato, se interpretatecome date.

Per esempio, 00/00/0000 o 62/91/3456.

È possibile costruire una ER che descriva tutte e solele date significative, ma non è semplice.

Tale ER dovrebbe incorporare tutte le regole per ilnumero di giorni per mese e per gli anni bisestili.



Esercizio 3 (1)

Scrivere una espressione regolare per i numeritelefonici italiani di sei o otto cifre, checomprenda recapiti del tipo:

• 0039 0373 89 80 62;

• +39 0373 89 80 62;

• 02 50 33 00 62;

Soluzione

Per comodità, riutilizziamo l’insieme D edefiniamo S = {“ ”} e P = {“+”}.

Esercizio 3 (2)

Il prefisso internazionale può essere in dueforme:• 0239

• P39

Il prefisso urbano può essere costituito da una atre cifre, precedute da 0:• 0(D + D2 + D3)

Infine, il numero può essere composto da tre oda quattro coppie di decimali, separate da unospazio:• ((D2S)2 + (D2S)3)D2



Esercizio 3 (3)

Per unire il tutto bisogna tener conto che:

• il prefisso internazionale può non esserci;

• tra le varie parti del numero ci vanno gli spazi.

Quindi:

(0239+P39+ε)S0(D+D2+D3)S((D2S)2+(D2S)3)D2

Esercizio 4 (1)

Sia data l’espressione regolare su Σ = {a, b, c}:

E = (a∗b2)∗(b + abc∗)∗

Quali fra le seguenti stringhe vengono descritteda E?

a) aabc

b) bb

c) abc

d) bac

e) abbabbbabc



Esercizio 4 (2)

Soluzione

Si può notare che E = E1E2, dove E1 = (a∗b2)∗ eE2 = (b + abc∗)∗.

a) aabc

aabc non può essere descritta da E perché:• la c finale potrebbe essere generata solo da E2,ma può esserlo solo se preceduta da ab;

• la sottostringa abc potrebbe essere descritta daE2, ma in nessun modo la singola a potrebbeessere ricavata.

Esercizio 4 (3)

b) bb

L’espressione regolare bb può essere coinvolta nellacatena di inclusioni:

bb = b2 ⊂ a∗b2 ⊂ (a∗b2)∗ ⊂ (a∗b2)∗(b + abc∗)∗

c) abc

L’espressione regolare abc può essere coinvoltanella catena di inclusioni:

abc ⊂ abc∗ ⊂ b + abc∗ ⊂ (b + abc∗)∗ ⊂(a∗b2)∗(b + abc∗)∗



Esercizio 4 (4)

d) bac

bac non può essere descritta da E perché la c finalepotrebbe essere generata solo da E2, ma puòesserlo solo se preceduta da ab.

e) abbabbbabc

L’espressione regolare abbabbbabc può esserecoinvolta nella catena di inclusioni:

abbabbbabc = (abb)(abb)(b)(abc) =(ab2)(ab2)(b)(abc) = (ab2)2(b)(abc) ⊂(a∗b2)2(b)(abc∗) ⊂ (a∗b2)∗(b + abc∗)2 ⊂(a∗b2)∗(b + abc∗)∗

Esercizio 5 (1)

Indicare una ER su Σ = {a, b, c} che descriva leseguenti stringhe:

• bbccaaa

• bbb

• bbcca

• bbbaa

ma non le seguenti:

• bbcbac

• bbcabc

• cbbaa

• abbcab



Esercizio 5 (2)

Soluzione

Soluzioni banali (da non considerare):

• {bbccaaa, bbb, bbcca, bbbaa}

• Σ∗ − {bbcbac, bbcabc, cbbaa, abbcab}

Si può notare che le stringhe da includere sonotutte composte da:

• una sequenza di b,

• seguita eventualmente da una sequenza di c,

• terminata da un’eventuale sequenza di a.

Esercizio 5 (3)

Queste caratteristiche possono essere descrittedall’espressione regolare b∗c∗a∗:

• sequenza iniziale di b come prefisso: b∗c∗a∗;

• eventuale sequenza di c: b∗c∗a∗;

• ed eventuale sequenza di a: b∗c∗a∗.



Esercizio 5 (4)

Nessuna delle stringhe del secondo gruppo vienedescritta da b∗c∗a∗:

• bbcbac: ha una c che inframezza la potenzialesequenza di b;

• bbcabc: dopo la sequenza bbca iniziale (che verrebbedescritta dall’espressione regolare considerata) iniziauna nuova sequenza bc;

• cbbaa: antepone c alla sequenza di b;

• abbcab: antepone a alla sequenza di b iniziale.

Prossimi passi

Esempi di applicazioni che usano le espressioniregolari.



Chiusura



Lezione 3 - Uso di espressioni regolari




Stefano Ferrari


Pattern matching

Le espressioni regolari (ER) sono lo strumentoideale per le operazioni di pattern matching(corrispondenza al modello) su informazionitestuali.

L’ER descrive un modello e i programmi cercanonei dati le stringhe che corrispondono a talemodello.

Esempi:

• analisi di log;

• sostituzione di stringhe di testo;

• ricerca in database.



Motivazioni

Le espressioni regolari (ER) permettono dispecificare un insieme di stringhe in modo:

• compatto:– ripetizioni, alternative;

• simile all’oggetto descritto:– l’alfabeto delle stringhe è parte dell’alfabeto delle ER;

• costruttivo:– combinazione di ER mediante operatori di stringhe.

Dove si usano le espressioni regolari

Le ER sono comunemente usate in molti ambiti:

• linguaggi di programmazione:– C, Java, PHP, Python, Perl;

• shell:– DOS, bash;

• file di configurazione:– apache, procmail, majordomo;

• programmi di utilità:– sed, awk, grep;

• programmi avanzati di elaborazione testi:– vi, emacs.



Espressioni regolari standard

Non esiste uno standard, ma molte convenzionisono condivise.

IEEE POSIX 1003.2 definisce:

• basic regular expression (BRE);

• extended regular expression (ERE).

Nota: POSIX sta per Portable Operating SystemInterface.

Faremo riferimento principalmente allanotazione ERE.

Metasimboli

In un file di testo possono essere utilizzati tutti icaratteri consentiti dalla codifica.

L’alfabeto delle ER è composto dall’alfabeto dellestringhe da specificare e da metasimboli.

Le ER sono specificate tramite caratteri di testo.

Questo comporta che alcuni simboli devonoessere realizzati tramite una coppia di carattericonsecutivi: le sequenze di escape.

Esempio: “\*” può significare “*”.



Operazioni di base

Gli operatori di base delle ER si traducono:

• potenza: la ripetizione di una sottoespressione siindica con il numero di ripetizioni fra parentesi graffe;– esempio: ab{3} corrisponde all’ER ab3 = abbb;

• chiusura: analogamente, la chiusura viene indicatacon l’asterisco;– esempio: ab* corrisponde all’ER ab∗;

• sottoespressioni: le sottoespressioni si delimitanocon le parentesi tonde;– esempio: (ab)*cd corrisponde all’ER (ab)∗cd;

• unione: sottoespressioni alternative vengonoindicate con il simbolo “pipe”;– esempio: a|b corrisponde all’ER a + b.

Estensioni

Le estensioni facilitano la specifica dei pattern:

• Σ: un qualsiasi carattere di testo viene indicatotramite il punto;– esempio: .* corrisponde all’ER Σ∗;

• ε: la stringa nulla si indica come unasottoespressione vuota;– esempio: (a|()) corrisponde all’ER (a + ε);

• corrispondenze multiple:– “+”: a+b corrisponde all’insieme (a∗ − ε)b;

– “?”: a?b corrisponde all’ER (a + ε)b;

– “{n,}”: a{2,}b corrisponde all’insieme (a∗ − a − ε)b;

– “{n,m}”: a{2,4}b corrisponde all’insieme (a2 + a3 + a4)b.



Sottoinsiemi di caratteri

• elenco di caratteri: una sequenza di caratteri frauna coppia di parentesi quadre indica un insieme;– esempio: [abd] corrisponde all’insieme {a, b, d};

• intervallo: sfruttando l’ordinamento dei caratteriASCII, si possono indicare intervalli di caratteri;– esempio: [a-d] corrisponde all’insieme {a, b, c, d};

• complemento: l’operatore di complementoinsiemistico si indica ponendo l’accento circonflessocome primo elemento di un sottoinsieme di caratteri;– esempio: [^abd] corrisponde all’insieme Σ − {a, b, d};

• classi: esistono identificatori per i sottoinsiemicomunemente utilizzati;– esempio: [:digit:] corrisponde all’insieme {0, . . . , 9}.

Ancoraggi

La posizione di una stringa nel testo può essereun fattore discriminante.

Esempio: l’IP del client viene posto all’iniziodella riga di log.

I metasimboli di ancoraggio servono per indicareuna posizione relativa all’interno del testo:

• “^” indica l’inizio della riga;

• “$” indica la fine della riga;– e “\^” e “\$” indicano, rispettivamente, i caratteri “^” e “$”.



Riferimenti

I riferimenti a precedenti sottospressioni (soloBRE) sono usati per poter usare la sottostringache corrisponde al sottomodello.

Esempio:

• (a*)b\1 corrisponde ad aabaa, ma non ad aaba.

I riferimenti vengono utilizzati soprattutto per lesostituzioni.

Esempio:

• cambiare il path a tutti i file di un file diconfigurazione;– sed ’s/olddir\/$.*$/newdir\/\1/g’ config.txt

Esempi

Alcuni esempi di impiego delle ER:

• analisi degli accessi (grep):

grep -E "^159\.149(\.[:digit:]{1,3}){2}" access.log

• controllo (php):

eregi ("(ozilla.[23]|MSIE.3)", $HTTP_USER_AGENT);

/* Returns true if client browser is

Netscape 2, 3 or MSIE 3. */

• rewriting (apache):

RewriteRule ^/rim(/.*)? http://rim.dti.unimi.it/$1



In sintesi

Le espressioni regolari sono un utile e praticostrumento per indicare pattern di caratteri.

Sono utilizzate in:

• linguaggi di programmazione;

• shell;

• file di configurazione;

• programmi di utilità;

• programmi di elaborazione testi.

Chiusura



Fondamenti di Informatica per la Sicurezza

Documents

Transcript of Fondamenti di Informatica per la Sicurezza