Fondamenti Di Informatica Per La Sicurezza

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

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]

Stefano Ferrari— Fondamenti di Informatica per la Sicurezza

1

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

Numeri Un numero è un ente astratto usato per indicare proprietà quantitative delle grandezze.

x

x

•

x

x x

• • • •

Contare Per contare, non è necessario conoscere i numeri. 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.

Stefano Ferrari— Fondamenti di Informatica per la Sicurezza

2

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

Astrazione Le esigenze pratiche possono portare a scoprire concetti 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 numeri richiede la loro rappresentazione su di un supporto fisico. Serve quindi: •

mezzo fisico (modificabile, ma stabile);

•

codifica.

Stefano Ferrari— Fondamenti di Informatica per la Sicurezza

3

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

Sistema di numerazione Codifica arbitraria per rappresentare un insieme infinito di oggetti utilizzando un insieme finito di simboli.

Numerale Al concetto astratto di numero si affianca la sua rappresentazione simbolica: il numerale. Interpretazione del numerale: •

un numerale ha significato solo all’interno di un sistema di numerazione.

Stefano Ferrari— Fondamenti di Informatica per la Sicurezza

4

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

Sistemi di numerazione I sistemi di numerazione si dividono principalmente 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 e mille); i simboli affiancati in ordine decrescente indicano il numero pari alla loro somma; se un simbolo precede un simbolo di valore superiore, deve essere sottratto.

Stefano Ferrari— Fondamenti di Informatica per la Sicurezza

5

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

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 poi introdotta in Europa da Fibonacci;

•

basata su dieci cifre;

•

il significato dipende dalla loro posizione.

•

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

Stefano Ferrari— Fondamenti di Informatica per la Sicurezza

6

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

In sintesi I numeri: •

•

sono gli elementi di informazione più semplici che siamo in grado di elaborare in modo automatico; per elaborarli, dobbiamo essere in grado di rappresentarli.

Chiusura

Stefano Ferrari— Fondamenti di Informatica per la Sicurezza

7

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

Lezione 2 - Rappresentazione posizionale 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

Numeri e rappresentazione Il concetto di “numero” è indipendente dalla sua rappresentazione. Esempio: + + + o + o + o o o + o + o o o + o + o

In questo caso, i simboli “+” sono posizionati in corrispondenza di un numero primo. La scelta della rappresentazione dipende dall’utilizzo che si vuol fare dei numeri rappresentati.

Stefano Ferrari— Fondamenti di Informatica per la Sicurezza

1

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

Scelta della notazione posizionale Se si devono fare calcoli, la notazione posizionale offre 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 10 trasla le cifre di una posizione; compattezza: la rappresentazione richiede un numero di cifre logaritmico.

Notazione posizionale

(1)

Formalizzazione:

(an . . . a1 a0 )b ≡

n X

ai · b i ,

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

i=0 •

• •

•

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 .

Stefano Ferrari— Fondamenti di Informatica per la Sicurezza

2

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

Notazione posizionale

(2)

Basi notevoli: •

decimale, b = 10

ai ∈ {0, . . . , 9};

•

binaria, b = 2

•

ottale, b = 8

•

esadecimale, b = 16

ai ∈ {0, 1}; ai ∈ {0, . . . , 7}; 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 base diversa 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!

Stefano Ferrari— Fondamenti di Informatica per la Sicurezza

3

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

Numeri frazionari Ogni numero intero è rappresentabile utilizzando una qualsiasi base, ma lo stesso non vale per i numeri frazionari: 1 ¯)10 ≡ (0.3 in base 10 3

in base 3

1 3

≡ (0.1)3

I numeri frazionari si possono rappresentare come: n X

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

ai · b i ,

b≥2

i=−m

In sintesi La notazione posizionale permette: •

•

di rappresentare in qualsiasi base qualsiasi numero intero; e anche alcuni numeri frazionari.

Stefano Ferrari— Fondamenti di Informatica per la Sicurezza

4

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

Chiusura

Stefano Ferrari— Fondamenti di Informatica per la Sicurezza

5

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

Lezione 3 - Cambio di base 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

Cambio di base

(1)

Come si scrive in base 12 il numero rappresentato dal numerale (32)4 ? NB: Cambia solo la rappresentazione del numero! Per rispondere alla domanda serve una piccola digressione: la divisione.

Stefano Ferrari— Fondamenti di Informatica per la Sicurezza

1

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

Divisione Dati due numeri naturali a, b (b > 0), la divisione permette di determinare due numeri q ed r tali che a = b · q + r, 0≤r
b è il divisore;

•

q è il quoziente (o quoto);

•

r è il resto.

Cambio di base

(2)

L’algoritmo per il cambio di base fa uso degli operatori di divisione intera (div) e di resto (mod): div è la parte intera della divisione tra due numeri interi (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

Stefano Ferrari— Fondamenti di Informatica per la Sicurezza

2

Modulo 2— U.D. 1— Lez. 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 , della divisione di n per b: q = n div b r = n mod b 2. Il resto, r , è l’ultima cifra del numerale che esprime n in base b. 3. Se il quoziente, q , è diverso da zero, le rimanenti cifre 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

Stefano Ferrari— Fondamenti di Informatica per la Sicurezza

3

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

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 · 5 3 + 0 · 52 + 1 · 5 + 3 = = 1 · 5 3 + 0 · 52 + 1 · 5 + 3 · 5 0

(133)10 = (1013)5

Numero di cifre

(1)

Quante cifre, k, bisogna usare per rappresentare in base b il numero n? Ragionando in base 10: con con con con

1 cifra: 2 cifre: 3 cifre: k cifre:

0...9 fino 10 . . . 99 fino 100 . . . 999 fino k−1 k 10 . . . 10 − 1 fino

a a a a

101 − 1 102 − 1 103 − 1 10k − 1

k deve essere il più piccolo numero intero tale per cui bk − 1 ≥ n. Per comodità: bk ≥ n + 1.

Stefano Ferrari— Fondamenti di Informatica per la Sicurezza

4

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

Numero di cifre

(2)

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

logb bk ≥ logb (n + 1) k ≥ logb (n + 1) k = dlogb (n + 1)e dove dxe indica il più piccolo numero intero maggiore o uguale a x.

Numero di cifre

(3)

Quante cifre sono necessarie per rappresentare 1145 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: log2 1146 ≈ 10.162 → 11 cifre. Infatti: 1145 = (10001111001)2 . c) 16: log16 1146 ≈ 2.5406 → 3 cifre. Infatti: 1145 = (479)16 .

Stefano Ferrari— Fondamenti di Informatica per la Sicurezza

5

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

In sintesi La notazione posizionale permette: •

•

in generale, il calcolo del numerale attraverso la divisione; il calcolo del numero di cifre necessarie basato sul logaritmo del numero da rappresentare.

Chiusura

Stefano Ferrari— Fondamenti di Informatica per la Sicurezza

6

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

Lezione 4 - Esercizi sul cambiamento di base 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

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

Stefano Ferrari— Fondamenti di Informatica per la Sicurezza

1

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

Da decimale a base n Come si rappresenta in base 3 il numero (1079)10 ? Algoritmo della divisione: quoziente 1079 359 119 39 13 4 1 0

resto 2 2 2 0 1 1 1

(1079)10 = (1110222)3

Da base m a base n

(1)

Come si rappresenta in base 5 il numero (106)7 ? 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.

Stefano Ferrari— Fondamenti di Informatica per la Sicurezza

2

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

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 55 11 2 0

resto 0 1 2

Quindi:

(106)7 = (210)5

Da binario ad ottale È un caso particolare di conversione da base m a base 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 base 8

101 5

001 1

Stefano Ferrari— Fondamenti di Informatica per la Sicurezza

3

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

Da binario ad esadecimale È un caso particolare di conversione da base m a base n: 16 = 24 . Esempio: (101001010)2 = (???)16 base 2 base 16

0001 1

0100 4

1010 A

(101001010)2 = (14A)16

Da ottale a binario È un caso particolare di conversione da base m a base n: 8 = 23 . 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 base 2

5 101

1 001

Stefano Ferrari— Fondamenti di Informatica per la Sicurezza

4

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

Da esadecimale a binario È un caso particolare di conversione da base m a base n: 16 = 24 . Esempio: (14A)16 = (???)2 base 16 base 2

1 0001

4 0100

A 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.

Stefano Ferrari— Fondamenti di Informatica per la Sicurezza

5

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

Chiusura

Stefano Ferrari— Fondamenti di Informatica per la Sicurezza

6

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

Lezione 1 - Bit e byte Fondamenti di Informatica per la Sicurezza

Modulo 2 - Rappresentazione dell’informazione

Unità didattica 2 - Rappresentazione binaria

Stefano Ferrari Università degli Studi di Milano - Ssri - CDL ONLINE

Binario è bello! Per ragioni tecnologiche di affidabilità, gli attuali calcolatori sono in grado di rappresentare e di elaborare solo informazione espressa utilizzando due stati. É perciò naturale descrivere le informazioni in notazione binaria. In particolare, un elemento di informazione viene chiamato bit.

Stefano Ferrari— Fondamenti di Informatica per la Sicurezza

1

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

Bit Binary Digit cifra binaria Un bit può valere (convenzionalmente) 0 o 1.

Sequenze di bit Per rappresentare oggetti che possono assumere più 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 2N combinazioni diverse. 2 × 2 × ··· × 2 ← −−−−−−−−− → N volte

Se abbiamo N bit, quali numeri rappresentiamo? •

Lo stabilisce la codifica (arbitraria).

Stefano Ferrari— Fondamenti di Informatica per la Sicurezza

2

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

Byte Una sequenza di otto bit viene detta byte. Quante configurazioni differenti può assumere un byte? •

28 = 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), 1 kilobyte vale 1000 byte. Poiché molto spesso in informatica ricorrono multipli di potenze di due, è stato trovato conveniente riferirsi a 1024 come 1 kilobyte (KB).

Stefano Ferrari— Fondamenti di Informatica per la Sicurezza

3

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

Multipli binari

(2)

Lo scarto tra i multipli di 210 e di 103 cresce esponenzialmente: •

•

•

Mega: 220 = 1 048 576 ≈ 1 000 000 = 106 uno scarto di circa 4.86%! Giga: 230 = 1 073 741 824 ≈ 1 000 000 000 = 109 uno scarto di circa 7.37%! Tera: 240 = 1 099 511 627 776 ≈ 1 000 000 000 000 = 1012 uno scarto di circa 9.95%!

Multipli binari

(3)

Sono stati proposti i seguenti nomi per i multipli binari: 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

Stefano Ferrari— Fondamenti di Informatica per la Sicurezza

4

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

In sintesi I bit: •

sono gli elementi di informazione minimi;

•

rappresentano due stati;

•

possono essere aggregati per rappresentare più di due 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 i numeri: •

naturali;

•

interi;

•

razionali;

•

reali.

Stefano Ferrari— Fondamenti di Informatica per la Sicurezza

5

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

Chiusura

Stefano Ferrari— Fondamenti di Informatica per la Sicurezza

6

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

Lezione 2 - Codifica binaria di interi Fondamenti di Informatica per la Sicurezza

Modulo 2 - Rappresentazione dell’informazione

Unità didattica 2 - Rappresentazione binaria

Stefano Ferrari Università degli Studi di Milano - Ssri - CDL ONLINE

Citazione

Ci sono 10 tipi di persone, chi capisce il binario e chi no. [Anonimo]

Stefano Ferrari— Fondamenti di Informatica per la Sicurezza

1

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

Numeri naturali È il tipo più naturale da rappresentare: rappresentazione in notazione posizionale in base due. Esempio: (13)10 = (1101)2 → 00001101, usando un byte. 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 e modulo): 0 0 0 0 1 1 1 1

0 0 1 1 0 0 1 1

0 1 0 1 0 1 0 1

+0 +1 +2 +3 -0 -1 -2 -3

•

•

•

il bit più significativo rappresenta il segno, gli altri bit rappresentano il modulo; lo stesso numero (lo zero) viene rappresentato con due numerali differenti; le operazioni aritmetiche sono macchinose.

Stefano Ferrari— Fondamenti di Informatica per la Sicurezza

2

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

Complemento a 2

(1)

Per rappresentare in complemento a 2 il numero x usando una sequenza di n bit, si rappresenta in binario (usando n + 1 bit) il numero 2n + x, e scartando poi il bit più significativo. Esempio Usando 4 bit (n = 4): compl. a 2

•

6 → 24 + 6 = (22)10 = (10110)2 −−−−−→ 0110

•

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

compl. a 2

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

Complemento a 2 1111 1110 -2 1101 -3

-1

0000 0

0001 1

0010 2 0011 3

1100 -4

4 0100

-5

5

1011 -6 1010

(2)

0101 6 -7 1001

-8 1000

7

0110

0111

Stefano Ferrari— Fondamenti di Informatica per la Sicurezza

3

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

Complemento a 2

(3)

Con questa rappresentazione: • •

•

•

•

lo zero ha rappresentazione unica; con n bit, si rappresentano i numeri interi dell’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 bit come numeri binari; la sottrazione si realizza invertendo il valore del sottraendo e poi sommandolo al minuendo in notazione binaria.

In sintesi Con due simboli possiamo rappresentare i numeri: •

naturali;

•

interi.

Stefano Ferrari— Fondamenti di Informatica per la Sicurezza

4

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

Prossimi passi Vantaggi nell’uso della notazione in complemento a 2.

Chiusura

Stefano Ferrari— Fondamenti di Informatica per la Sicurezza

5

Modulo 2— U.D. 2— Lez. 3

Lezione 3 - Complemento a 2 Fondamenti di Informatica per la Sicurezza

Modulo 2 - Rappresentazione dell’informazione

Unità didattica 2 - Rappresentazione binaria

Stefano Ferrari Università degli Studi di Milano - Ssri - CDL ONLINE

Decodifica in complemento a due 1111 1110 -2 1101 -3

-1

0000 0

Decodifica: 0001 1

0010

•

2 0011 3

1100 -4

4 0100 •

-5

5

1011 -6 1010

se il primo simbolo è 0 si considera semplicemente come un numero binario;

0101 6 -7 1001

-8

7

0111 1000 overflow

0110

se il primo simbolo è 1 lo si decodifica in binario e ad esso si sottrae il numero 2n .

Stefano Ferrari— Fondamenti di Informatica per la Sicurezza

1

Modulo 2— U.D. 2— Lez. 3

Inversione in complemento a 2 1111 1110 -2 1101 -3

-1

0000 0

Inversione: 0001 1

0010

•

2

si invertono tutte le singole cifre binarie;

0011 3

1100 -4

•

si somma 1.

4 0100

-5

5

1011

0101

-6 1010

6 -7 1001

-8

0110

7

0111 1000 overflow

Codifica in complemento a 2 1111 1110 -2 1101 -3

-1

0000 0

Codifica: 0001 1

0010 2 0011 3

1100 -4

4 0100

-5

5

1011 -6 1010

•

•

codifica del valore assoluto in notazione posizionale binaria; se è negativo, lo si inverte.

0101 6 -7 1001

-8

7

0110

0111 1000 overflow

Stefano Ferrari— Fondamenti di Informatica per la Sicurezza

2

Modulo 2— U.D. 2— Lez. 3

Operazioni algebriche in complemento a 2 1111 1110 -2 1101 -3

-1

0000 0

Somma: 0001 1

0010

•

2 0011 3

1100 -4

Sottrazione: 4 0100 •

-5

5

1011 -6 1010

normale somma binaria.

0101 6 -7 1001

-8

7

0110

•

si inverte il sottraendo; lo si somma al minuendo.

0111 1000 overflow

Overflow L’overflow si manifesta quando si cerca di rappresentare un numero troppo grande. Esempio Usiamo una rappresentazione in complemento a 2 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’overflow si rileva facilmente.

Stefano Ferrari— Fondamenti di Informatica per la Sicurezza

3

Modulo 2— U.D. 2— Lez. 3

Individuazione dell’overflow 1111 1110 -2 1101 -3

-1

0000 0

Overflow: 0001 1

0010 2 0011 3

1100 -4

4 0100

-5

5

1011 -6 1010

•

0101

•

6 -7 1001

-8

7

0110

0111 1000 overflow

somma di valori con segno opposto e sottrazione di valori con segni concordi non dà mai overflow; negli altri casi, c’è stato overflow se il segno del risultato è discorde con il segno del primo operando.

Overflow in complemento a 2 Si verifica un overflow se: C=A+B A B C + + - +

C=A-B A B C + - + +

Stefano Ferrari— Fondamenti di Informatica per la Sicurezza

4

Modulo 2— U.D. 2— Lez. 3

In sintesi La rappresentazione in complemento a 2 permette 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.

Stefano Ferrari— Fondamenti di Informatica per la Sicurezza

5

Modulo 2— U.D. 2— Lez. 3

Chiusura

Stefano Ferrari— Fondamenti di Informatica per la Sicurezza

6

Modulo 2— U.D. 2— Lez. 4

Lezione 4 - Esercizi sulla notazione in complemento a 2 Fondamenti di Informatica per la Sicurezza

Modulo 2 - Rappresentazione dell’informazione

Unità didattica 2 - Rappresentazione binaria

Stefano Ferrari Università degli Studi di Milano - Ssri - CDL ONLINE

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.

Stefano Ferrari— Fondamenti di Informatica per la Sicurezza

1

Modulo 2— U.D. 2— Lez. 4

Codifica

(2)

D Codificare il numero 10 in complemento a 2 a 3 bit, 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 3 bit, 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.

Stefano Ferrari— Fondamenti di Informatica per la Sicurezza

2

Modulo 2— U.D. 2— Lez. 4

Decodifica

(1)

D Quale numero è rappresentato dalla stringa binaria 10111, codificata in complemento a due? R (10111)2 = (23)10 . Poiché la prima cifra binaria è 1, 10111 viene decodificato come: 23 − 25 = −9.

Decodifica

(2)

D Quale numero è rappresentato dalla stringa binaria 01101, codificata in complemento a due? R (01101)2 = (13)10 . Poiché la prima cifra binaria è 0, 01101 viene decodificato come 13.

Stefano Ferrari— Fondamenti di Informatica per la Sicurezza

3

Modulo 2— U.D. 2— Lez. 4

Inversione

(1)

D Quale stringa binaria è l’inverso in complemento a due 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 a due 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.

Stefano Ferrari— Fondamenti di Informatica per la Sicurezza

4

Modulo 2— U.D. 2— Lez. 4

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 bit uguale, 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 6 bit è 011110. Poiché le due stringhe date hanno il primo bit uguale, ma diverso dal primo bit del risultato, si è verificato un overflow.

Stefano Ferrari— Fondamenti di Informatica per la Sicurezza

5

Modulo 2— U.D. 2— Lez. 4

Sottrazione

(1)

D Date le stringhe binarie A = 1011000 e B = 0101000, calcolare in complemento a due la loro differenza, specificando se si verifica un overflow. R Il complemento a 2 di 0101000 è 1011000. La somma binaria di 1011000 e 1011000, troncata a 7 bit è 0110000. Poiché le due stringhe date hanno il primo bit diverso, e il primo bit del risultato è uguale al primo bit della seconda stringa, si è verificato un overflow.

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 6 bit è 110011. Poiché le due stringhe date hanno il primo bit uguale, non si è verificato un overflow.

Stefano Ferrari— Fondamenti di Informatica per la Sicurezza

6

Modulo 2— U.D. 2— Lez. 4

Prossimi passi Come i bit si possono usare per rappresentare: •

numeri razionali;

•

numeri irrazionali.

Chiusura

Stefano Ferrari— Fondamenti di Informatica per la Sicurezza

7

Modulo 2— U.D. 2— Lez. 5

Lezione 5 - Codifica di numeri razionali Fondamenti di Informatica per la Sicurezza

Modulo 2 - Rappresentazione dell’informazione

Unità didattica 2 - Rappresentazione binaria

Stefano Ferrari Università degli Studi di Milano - Ssri - CDL ONLINE

Numeri “con la virgola” Per la rappresentazione dei numeri razionali e reali ci sono due impedimenti: •

•

per via della notazione posizionale, alcuni numeri non possono essere rappresentati con un numero limitato di cifre (e.g., 13 in base 10); alcuni numeri reali (gli irrazionali) non possono proprio essere rappresentati in nessuna base (e.g., π ).

Stefano Ferrari— Fondamenti di Informatica per la Sicurezza

1

Modulo 2— U.D. 2— Lez. 5

Numeri razionali Per gli usi pratici, i numeri irrazionali possono essere approssimati da un numero razionale: •

per esempio, 3.14 ≈ π .

Per rappresentare numeri razionali ci sono due notazioni, dette: •

virgola fissa;

•

virgola mobile.

Virgola fissa

(1)

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

k bit

←−−− −−→ ←−−−−−→ a n−1 · · · ak . ak−1 · · · a0 ← −−−−−−−−−−−−−−− → n bit

Equivale a dividere per 2k .

Stefano Ferrari— Fondamenti di Informatica per la Sicurezza

2

Modulo 2— U.D. 2— Lez. 5

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, la precisione relativa è 1/102 . 1.091 e 1.094 sono indistinguibili: vengono rappresentati con 1.09.

Stefano Ferrari— Fondamenti di Informatica per la Sicurezza

3

Modulo 2— U.D. 2— Lez. 5

Virgola fissa

(4)

Problema di underflow: può non essere possibile rappresentare un numero piccolo. Come si rappresenta 0.001? 0

0

0

0.

0

0 !

Virgola mobile

(1)

Un numero razionale può essere rappresentato nella 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 viene rappresentato tramite la coppia mantissa-esponente.

Stefano Ferrari— Fondamenti di Informatica per la Sicurezza

4

Modulo 2— U.D. 2— Lez. 5

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 per l’esponente e 23 per la mantissa); •

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

Fissa o mobile? Con lo stesso budget di bit, possiamo rappresentare lo stesso numero di valori. Virgola fissa e mobile si differenziano per come i valori vengono distribuiti sulla retta dei reali.

Stefano Ferrari— Fondamenti di Informatica per la Sicurezza

5

Modulo 2— U.D. 2— Lez. 5

In sintesi I numeri non interi possono essere rappresentati mediante le notazioni: •

a virgola fissa;

•

a virgola mobile.

Prossimi passi Come i bit si possono usare per rappresentare altre grandezze: •

insiemi non numerici;

•

suoni;

•

immagini;

•

animazioni.

Stefano Ferrari— Fondamenti di Informatica per la Sicurezza

6

Modulo 2— U.D. 2— Lez. 5

Chiusura

Stefano Ferrari— Fondamenti di Informatica per la Sicurezza

7

Modulo 2— U.D. 2— Lez. 6

Lezione 6 - Rappresentazione di grandezze numerabili Fondamenti di Informatica per la Sicurezza

Modulo 2 - Rappresentazione dell’informazione

Unità didattica 2 - Rappresentazione binaria

Stefano Ferrari Università degli Studi di Milano - Ssri - CDL ONLINE

Citazione

Il computer è un genio che può soddisfare qualsiasi desiderio. Però bisogna specificare il desiderio esattamente. E in binario. [Anonimo]

Stefano Ferrari— Fondamenti di Informatica per la Sicurezza

1

Modulo 2— U.D. 2— Lez. 6

Insiemi numerabili n bit possono assumere 2n configurazioni. Attraverso un’opportuna codifica, possiamo rappresentare un insieme di 2n elementi. Esempio: la codifica di caratteri: • •

•

EBCDIC, 8 bit: era usato sui mainframe IBM; ASCII (American Standard Code for Information Interchange), 7 bit + 1: adottata dall’ANSI (American National Standards Institute); Unicode, 16 bit: “a unique number for every character, no matter what the platform, no matter what 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

Stefano Ferrari— Fondamenti di Informatica per la Sicurezza

2

Modulo 2— U.D. 2— Lez. 6

Grandezze continue È possibile approssimare numericamente una grandezza continua tramite campionamento. Campionare significa collezionare ad intervalli regolari (di tempo o di spazio) i valori che la grandezza assume (nel tempo o nello spazio).

Campionamento In funzione delle caratteristiche del segnale, esiste la lunghezza massima dell’intervallo di campionamento per poter ricostruire fedelmente il segnale.

Stefano Ferrari— Fondamenti di Informatica per la Sicurezza

3

Modulo 2— U.D. 2— Lez. 6

Quantizzazione L’elaborazione digitale del suono (e più in generale dei segnali) richiede però di utilizzare una codifica digitale del valore di ogni campione. Questa operazione, chiamata quantizzazione, comporta una distorsione del segnale.

In sintesi Anche alcune grandezze non numeriche possono essere descritte tramite i numeri. Se possiamo descriverle tramite numeri, possiamo anche descriverle in binario.

Stefano Ferrari— Fondamenti di Informatica per la Sicurezza

4

Modulo 2— U.D. 2— Lez. 6

Prossimi passi Codifica di grandezze continue.

Chiusura

Stefano Ferrari— Fondamenti di Informatica per la Sicurezza

5

Modulo 2— U.D. 2— Lez. 7

Lezione 7 - Rappresentazione di grandezze continue Fondamenti di Informatica per la Sicurezza

Modulo 2 - Rappresentazione dell’informazione

Unità didattica 2 - Rappresentazione binaria

Stefano Ferrari Università degli Studi di Milano - Ssri - CDL ONLINE

Segnale audio

(1)

Un suono può essere rappresentato come una funzione continua: l’ampiezza dell’onda sonora nel tempo. Frequenza di campionamento: •

•

la voce umana deve essere campionata ad un ottavo di millesimo di secondo; la musica deve essere campionata 44 100 volte al secondo.

Stefano Ferrari— Fondamenti di Informatica per la Sicurezza

1

Modulo 2— U.D. 2— Lez. 7

Segnale audio

(2)

Una codifica del segnale sonoro deve quindi decidere: •

•

•

il numero di canali (mono? stereo? effetto surround?); frequenza di campionamento (quanti campioni per ogni secondo?); i livelli di quantizzazione (quanti bit per ogni campione?).

Segnale audio Esempio 1 La codifica a 8 bit di un segnale stereo della durata di 3 secondi, campionato a 16 kHz richiede:

8 × 16 000 × 2 × 3 = 768 000 bit. Esempio 2 Per i CD musicali viene utilizzata una codifica a 16 bit per canale e un campionamento a 44 100 Hz; per un’ora di registrazione servono:

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

Stefano Ferrari— Fondamenti di Informatica per la Sicurezza

2

Modulo 2— U.D. 2— Lez. 7

Codifiche audio particolari Per ottenere una codifica meno voluminosa, lo standard 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 digitale sono di due tipi: •

bitmap;

•

vettoriali.

Stefano Ferrari— Fondamenti di Informatica per la Sicurezza

3

Modulo 2— U.D. 2— Lez. 7

Bitmap

(1)

Una immagine digitale bitmap è descritta da una matrice di pixel (contrazione di picture element). Ogni pixel può assumere un singolo colore. Quindi: •

•

il numero di righe e di colonne determina la risoluzione spaziale dell’immagine; il numero di colori che il pixel può assumere determina 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.

Stefano Ferrari— Fondamenti di Informatica per la Sicurezza

4

Modulo 2— U.D. 2— Lez. 7

Codifiche video particolari Una rappresentazione più compatta può essere ottenuta sfruttando: • la ridondanza del segnale; •

le caratteristiche del sistema percettivo.

Queste tecniche sono utilizzate nelle codifiche più diffuse, quali GIF, PNG e JPEG. Sono molto utilizzate anche le codifiche a palette (tavolozza): • insieme alla bitmap viene codificata una tabella dei colori 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 geometriche senza degradare l’immagine descritta; permettono la visualizzazione alla risoluzione dei dispositivi.

Stefano Ferrari— Fondamenti di Informatica per la Sicurezza

5

Modulo 2— U.D. 2— Lez. 7

Animazioni Una animazione può essere ottenuta tramite una successione di immagini. Ogni singola immagine viene detta frame. Il frame-rate è il numero di immagini per secondo 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ò essere ampiamente ridotto sfruttando la ridondanza dovuta alla somiglianza tra frame consecutivi.

In sintesi Anche alcune grandezze non numeriche possono essere descritte tramite i numeri. Se possiamo descriverle tramite numeri, possiamo anche descriverle in binario. Se restringiamo il dominio di utilizzo, possiamo affinare la codifica.

Stefano Ferrari— Fondamenti di Informatica per la Sicurezza

6

Modulo 2— U.D. 2— Lez. 7

Prossimi passi Tecniche per il calcolo dei bit necessari per la codifica di grandezze numeriche e non numeriche.

Chiusura

Stefano Ferrari— Fondamenti di Informatica per la Sicurezza

7

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

Lezione 1 - Permutazioni e disposizioni Fondamenti di Informatica per la Sicurezza

Modulo 2 - Rappresentazione dell’informazione

Unità didattica 3 - Calcolo del numero di bit

Stefano Ferrari Università degli Studi di Milano - Ssri - CDL ONLINE

Codifica e numero di bit necessari La codifica è una scelta arbitraria basata su una convenzione che chi usa la codifica deve necessariamente conoscere. Una codifica può essere considerata buona se facilita: • l’elaborazione nella quale la si vuole utilizzare; •

le operazioni di codifica e decodifica.

Per stabilire quanti bit sono necessari, bisogna conoscere il numero di configurazioni che la codifica deve rappresentare. Qualche nozione di calcolo combinatorio è indispensabile.

Stefano Ferrari— Fondamenti di Informatica per la Sicurezza

1

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

Regola del prodotto Una regola generale: se una cosa può essere realizzata in n modi e per ciascuna di queste realizzazioni una seconda cosa può essere realizzata in m modi, allora il numero di realizzazioni 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 che si 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 in un raggruppamento; 3. due raggruppamenti sono tra loro distinti se differiscono per l’ordine con cui sono disposti gli elementi.

Stefano Ferrari— Fondamenti di Informatica per la Sicurezza

2

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

Permutazioni

(2)

n elementi danno luogo a n! permutazioni: P (n) = n! L’operatore indicato con il simbolo ! si chiama fattoriale e assume la seguente forma: ( 1 n=0 Qn n! = 1 · 2 · . . . · (n − 1) · 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 dlog2 720e = 10 bit.

Questo ragionamento fornisce il minimo numero di bit da utilizzare, ma non dice come effettuare la codifica.

Stefano Ferrari— Fondamenti di Informatica per la Sicurezza

3

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

Esercizio 1

(2)

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

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

In tal caso: • ogni atleta necessita di 3 bit (dlog 6e = 3); 2 •

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

La codifica scelta non sarebbe quella di ingombro minimo (10 bit), ma sarebbe semplice da costruire e utilizzare.

Disposizioni

(1)

Si dice disposizione semplice di n elementi distinti su k posizioni (n, k ∈ N, 0 < k ≤ n) una collezione di k degli n elementi che rispetti le seguenti proprietà: 1. ciascun raggruppamento contiene k elementi; 2. uno stesso elemento può figurare al più una volta in un raggruppamento; 3. due raggruppamenti sono da considerarsi distinti quando essi differiscono per almeno un elemento, o per l’ordine degli elementi.

Stefano Ferrari— Fondamenti di Informatica per la Sicurezza

4

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

Disposizioni

(2)

Le disposizioni semplici di n elementi presi k per n! volta sono in totale (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 di atleti 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 dlog2 120e = 7 bit.

Stefano Ferrari— Fondamenti di Informatica per la Sicurezza

5

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

In sintesi Per calcolare il numero di bit necessario per descrivere una situazione dobbiamo conoscere il numero di configurazioni possibili. Il calcolo combinatorio permette di modellare la maggior parte delle situazioni reali mediante: •

permutazioni;

•

disposizioni.

Prossimi passi Altri casi di calcolo combinatorio: •

disposizioni con ripetizione;

•

combinazioni;

•

combinazioni con ripetizione.

Stefano Ferrari— Fondamenti di Informatica per la Sicurezza

6

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

Chiusura

Stefano Ferrari— Fondamenti di Informatica per la Sicurezza

7

Modulo 2— U.D. 3— Lez. 2

Lezione 2 - Altri elementi di calcolo combinatorio Fondamenti di Informatica per la Sicurezza

Modulo 2 - Rappresentazione dell’informazione

Unità didattica 3 - Calcolo del numero di bit

Stefano Ferrari Università degli Studi di Milano - Ssri - CDL ONLINE

Disposizioni con ripetizione

(1)

Si dice disposizione con ripetizione (o reimmissione) di n elementi distinti su k posizioni (n, k ∈ N, n > 0, k > 0) una collezione di k degli n elementi che rispetti le seguenti proprietà: 1. ciascun raggruppamento contiene k elementi; 2. due qualsiasi raggruppamenti sono da considerarsi distinti quando essi differiscono per almeno un elemento, o per l’ordine degli elementi.

Stefano Ferrari— Fondamenti di Informatica per la Sicurezza

1

Modulo 2— U.D. 3— Lez. 2

Disposizioni con ripetizione

(2)

Rispetto ad una disposizione semplice, quindi, in una disposizione con ripetizione ogni elemento può 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 si possono 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 dlog2 216e = 8 bit.

Stefano Ferrari— Fondamenti di Informatica per la Sicurezza

2

Modulo 2— U.D. 3— Lez. 2

Combinazioni

(1)

Si dice combinazione semplice di n elementi distinti su k posizioni (n, k ∈ N, 0 < k ≤ n) una collezione di k degli n elementi che rispetti le seguenti proprietà: 1. ciascun raggruppamento contiene k elementi; 2. uno stesso elemento può figurare al più una volta in un raggruppamento; 3. due raggruppamenti sono da considerarsi diversi soltanto quando differiscono tra loro almeno per un elemento.

Combinazioni

(2)

L’ordine degli elementi non ha importanza in una combinazione. Le combinazioni semplici di n elementi su k posti sono:

C(n, k) =

D(n,k) P (k)

=

n·(n−1)· ··· (n−k+1) k!

n! La quantità (n−k)! è il coefficiente binomiale di n k! su k, e viene indicato con:
n k

Stefano Ferrari— Fondamenti di Informatica per la Sicurezza

3

Modulo 2— U.D. 3— Lez. 2

Esercizio 4 Un negozio ha in vetrina lo spazio per esporre solo tre manichini ed un campionario di sette modelli di giacca. •

Volendo mettere una giacca diversa su ogni manichino, quante vetrine può comporre? –

•

Si tratta di calcolare le combinazioni semplici di 7 elementi su 3 posti: C(7, 3) = 7·6·5 = 7 · 5 = 35. 3·2

Quanti bit servono per codificare tale composizione? –

Sono necessari dlog2 35e = 6 bit.

Combinazioni con ripetizione

(1)

Si dice combinazione con ripetizione (o con reimmissione) di n elementi distinti su k (n, k ∈ N, n > 0, k > 0) posizioni una collezione di k degli n elementi che rispetti le seguenti proprietà: 1. ciascun raggruppamento contiene k elementi; 2. due raggruppamenti sono da considerarsi diversi soltanto quando differiscono tra loro almeno per un elemento.

Stefano Ferrari— Fondamenti di Informatica per la Sicurezza

4

Modulo 2— U.D. 3— Lez. 2

Combinazioni con ripetizione

(2)

Uno stesso elemento può quindi comparire più di una volta. Le combinazioni con ripetizione di n elementi su k posti sono:
n+k−1 Cr (n, k) = C(n + k − 1, k) = k

Esercizio 5 Un negozio ha in vetrina lo spazio per esporre solo tre manichini ed un campionario di sette modelli di giacca. •

Quante vetrine potrebbe comporre, se ritenesse accettabile avere più copie della stessa giacca in vetrina? –

•

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 · 4 · 7 = 84. 3·2

Quanti bit servono per codificare tale composizione? –

Sono necessari dlog2 84e = 7 bit.

Stefano Ferrari— Fondamenti di Informatica per la Sicurezza

5

Modulo 2— U.D. 3— Lez. 2

Riassumendo Le permutazioni dicono in quanti modi possiamo scrivere la sequenza degli elementi di un insieme dato. Le disposizioni e le combinazioni dicono in quanti modi si possono scrivere sequenze di sottoinsiemi di cardinalità data. La differenza tra combinazioni e disposizioni è che queste ultime tengono in considerazione anche l’ordine degli elementi.

In sintesi Per calcolare il numero di bit necessario per descrivere una situazione dobbiamo conoscere il numero di configurazioni possibili. Il calcolo combinatorio permette di modellare la maggior parte delle situazioni reali mediante: •

permutazioni;

•

disposizioni (con ripetizione);

•

combinazioni (con ripetizione).

Stefano Ferrari— Fondamenti di Informatica per la Sicurezza

6

Modulo 2— U.D. 3— Lez. 2

Prossimi passi Un po’ di esercizi sulla codifica binaria.

Chiusura

Stefano Ferrari— Fondamenti di Informatica per la Sicurezza

7

Modulo 2— U.D. 3— Lez. 3

Lezione 3 - Esercizi sulla codifica binaria (parte 1) Fondamenti di Informatica per la Sicurezza

Modulo 2 - Rappresentazione dell’informazione

Unità didattica 3 - Calcolo del numero di bit

Stefano Ferrari Università degli Studi di Milano - Ssri - CDL ONLINE

Contare con le dita D Fino a quanto si può contare usando solo le dita di due mani? R Ipotizzando che ogni dito possa assumere solo due 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 a 1023!).

Stefano Ferrari— Fondamenti di Informatica per la Sicurezza

1

Modulo 2— U.D. 3— Lez. 3

Colori D Quanti colori possono essere rappresentati in una codifica RGB a 1 byte per canale? R Ognuno dei canali (R, G e B) ha a disposizione 8 bit. In totale, dunque, 8 × 3 = 24 bit. Sono quindi rappresentabili 224 = 16 777 216 colori. La codifica a 24 bit è chiamata comunemente “a 16 milioni di colori”.

Dimensione di una immagine digitale D Quanti bit servono per rappresentare un’immagine 1024 × 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).

Stefano Ferrari— Fondamenti di Informatica per la Sicurezza

2

Modulo 2— U.D. 3— Lez. 3

Codifica per le carte da briscola D Quale può essere una buona codifica per le carte di un mazzo da briscola? R Poiché il mazzo di carte da briscola è composto da 40 carte, si dovranno utilizzare 6 bit: –

5 ≤ log2 40 ≤ 6;

–

5 bit sarebbero troppo pochi.

Uno dei modi di ottenere una codifica è individuare una enumerazione degli elementi dell’insieme da rappresentare 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, si può 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 buona codifica in decimale: la prima cifra rappresenta il seme (0–3) e la seconda il valore (0–9).

Stefano Ferrari— Fondamenti di Informatica per la Sicurezza

3

Modulo 2— U.D. 3— Lez. 3

Codifica per le carte da briscola Una codifica migliore può essere ottenuta utilizzando le prime due cifre binarie per rappresentare il seme, e le rimanenti per il valore: 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 alla precedente è la facilità di codifica/decodifica.

Riassumendo ... Una carta è caratterizzata da seme e valore. Ogni seme può assumere 4 configurazioni, mentre ogni valore può assumere 10 configurazioni. oggetto seme valore carta

#config. 4 10 4 × 10 = 40

#bit 2 4 6

La codifica “seme+valore” usa lo stesso numero di bit della codifica “carta”, ma non è una regola generale.

Stefano Ferrari— Fondamenti di Informatica per la Sicurezza

4

Modulo 2— U.D. 3— Lez. 3

Codifica per le automobili Un’auto è prodotta in 3 motorizzazioni e 10 colori. Quanti bit sono necessari per descrivere un modello di questa automobile? oggetto motore colore automobile

#config. 3 10 3 × 10 = 30

#bit 2 4 5

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

Regola generale Sebbene:

logb mn = logb m + logb n In generale:

dlogb mne ≤ dlogb me + dlogb ne

Stefano Ferrari— Fondamenti di Informatica per la Sicurezza

5

Modulo 2— U.D. 3— Lez. 3

Prossimi passi Ancora esercizi sulla codifica binaria.

Chiusura

Stefano Ferrari— Fondamenti di Informatica per la Sicurezza

6

Modulo 2— U.D. 3— Lez. 4

Lezione 4 - Esercizi sulla codifica binaria (parte 2) Fondamenti di Informatica per la Sicurezza Modulo 2 - Rappresentazione dell’informazione Unità didattica 3 - Calcolo del numero di bit

Stefano Ferrari Università degli Studi di Milano - Ssri - CDL ONLINE

Una mano a briscola D Quanti bit servono per codificare una mano di briscola? 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 una combinazione di quaranta oggetti su tre posizioni. 40! = 40·39·38 = 9880, Poiché C(40, 3) = 37!·3! 3·2 serviranno dlog2 9880e = 14 bit.

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

Stefano Ferrari— Fondamenti di Informatica per la Sicurezza

1

Modulo 2— U.D. 3— Lez. 4

Rappresentare elementi e insiemi

(1)

D Gli oggetti sotto riportati sono elementi delle comuni interfacce grafiche. Come rappresentare in binario gli stati di tali oggetti? #

Qui

4

Qui



Quo

2

Quo

#

Qua

4

Qua

Radio button

Check box

R I radio button permettono di selezionare uno solo degli n elementi della lista, mentre le check box consentono di selezionare un sottoinsieme degli n elementi della lista.

Rappresentare elementi e insiemi

(2)

Quante configurazioni diverse può assume un gruppo di 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.

Stefano Ferrari— Fondamenti di Informatica per la Sicurezza

2

Modulo 2— U.D. 3— Lez. 4

Rappresentare elementi e insiemi

(3)

Lo stato di un gruppo di check box equivale ad un sottoinsieme delle voci. Il numero di sottoinsiemi di un insieme di n elementi è 2n . È necessario dedicare un bit per ogni voce per indicare se essa è attiva o no. Pertanto, saranno necessari n bit. Nel caso in esame, useremo 3 bit per i check box.

Rappresentare elementi e insiemi

(4)

Enumeriamo le voci come di seguito riportato: #

Qui

0

4

Qui



Quo

1

2

Quo

#

Qua

2

4

Qua

Possiamo individuare le seguenti codifiche: Radio button: la posizione della voce attiva (1) si può codificare con la stringa binaria 01; Check box: ponendo ad 1 i bit corrispondenti alle voci attive ed a 0 gli altri: posizione valore

210 101

Stefano Ferrari— Fondamenti di Informatica per la Sicurezza

3

Modulo 2— U.D. 3— Lez. 4

Gelateria

(1)

Una gelateria dispone di 12 gusti di gelato, 5 guarnizioni e 2 contenitori. I gelati che vende sono sempre composti da un contenitore, 3 gusti e 2 guarnizioni. I contenitori sono divisi in tre scomparti asimmetrici. Le guarnizioni vengono distribuite uniformemente sul gelato. 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 → dlog 12e = 4 bit; 2 •

5 guarnizioni → dlog2 5e = 3 bit;

•

2 contenitori → dlog2 2e = 1 bit.

Stefano Ferrari— Fondamenti di Informatica per la Sicurezza

4

Modulo 2— U.D. 3— Lez. 4

Gelateria

(3)

b) Codifica del gelato (3 gusti, 2 guarnizioni, 1 contenitore). I gusti possono essere ripetuti e l’ordine è importante: Dr (12, 3) = 123 configurazioni. Anche le guarnizioni possono essere ripetute, ma non 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, 1 contenitore). 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.

Stefano Ferrari— Fondamenti di Informatica per la Sicurezza

5

Modulo 2— U.D. 3— Lez. 4

Prossimi passi Una formalizzazione del concetto di informazione.

Chiusura

Stefano Ferrari— Fondamenti di Informatica per la Sicurezza

6

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

Lezione 1 - Natura dell’informazione Fondamenti di Informatica per la Sicurezza

Modulo 2 - Rappresentazione dell’informazione

Unità didattica 4 - Teoria dell’Informazione

Stefano Ferrari Università degli Studi di Milano - Ssri - CDL ONLINE

Informazione Il termine “informazione” è usato in molti contesti e con molte accezioni. Portano informazione: •

una certa distribuzione di gocce di inchiostro su un foglio;

•

una certa sequenza di lettere dell’alfabeto;

•

una certa sequenza di parole della lingua italiana.

Stefano Ferrari— Fondamenti di Informatica per la Sicurezza

1

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

Informazione Si individuano diversi livelli di informazione: •

sintattico: –

•

semantico: –

•

l’informazione sintattica è legata alle configurazioni del supporto fisico; 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.

Stefano Ferrari— Fondamenti di Informatica per la Sicurezza

2

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

Misura dell’informazione

(1)

Qual’è la natura dell’informazione? Come si può misurare l’informazione? Per rispondere a queste domande proviamo ad analizzare alcuni casi.

Misura dell’informazione

(2)

Poniamo il caso di dover comunicare se un determinato evento è accaduto oppure no. Consideriamo le seguenti modalità per comunicare l’evento: 1. organizziamo un falò da qualche decina di metri cubi di legna; 2. accendiamo un cerino. Quale modalità trasferisce più informazione?

Stefano Ferrari— Fondamenti di Informatica per la Sicurezza

3

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

Misura dell’informazione

(3)

La risposta è chiara: sia chi vede il cerino, sia chi vede 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!

Misura dell’informazione

(4)

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?

Stefano Ferrari— Fondamenti di Informatica per la Sicurezza

4

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

Misura dell’informazione

(5)

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.

Stefano Ferrari— Fondamenti di Informatica per la Sicurezza

5

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

Prossimi passi Una formalizzazione del concetto di informazione.

Chiusura

Stefano Ferrari— Fondamenti di Informatica per la Sicurezza

6

Modulo 2— U.D. 4— Lez. 2

Lezione 2 - Elementi di teoria dell’Informazione Fondamenti di Informatica per la Sicurezza

Modulo 2 - Rappresentazione dell’informazione

Unità didattica 4 - Teoria dell’Informazione

Stefano Ferrari Università degli Studi di Milano - Ssri - CDL ONLINE

Misura dell’informazione Ipotizziamo un messaggio che contenga un simbolo x scelto da un insieme X = {xi | 1 ≤ i ≤ n} di n simboli (detto alfabeto). Attraverso una funzione I(·), vorremmo misurare l’informazione contenuta nel messaggio, I(x). Quali proprietà deve avere la funzione I(·)?

Stefano Ferrari— Fondamenti di Informatica per la Sicurezza

1

Modulo 2— U.D. 4— Lez. 2

Proprietà dell’informazione

(1)

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

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

Proprietà dell’informazione

(2)

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

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

Stefano Ferrari— Fondamenti di Informatica per la Sicurezza

2

Modulo 2— U.D. 4— Lez. 2

Proprietà dell’informazione

(3)

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

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

Proprietà dell’informazione

(4)

Se è certo che un dato simbolo apparirà sul messaggio, allora l’informazione portata dal messaggio è nulla:

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

Stefano Ferrari— Fondamenti di Informatica per la Sicurezza

3

Modulo 2— U.D. 4— Lez. 2

Proprietà dell’informazione

(5)

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 se l’insieme di simboli portabili dal messaggio è costituito da soli due simboli equiprobabili. In tal caso, ogni messaggio porta 1 bit!

Stefano Ferrari— Fondamenti di Informatica per la Sicurezza

4

Modulo 2— U.D. 4— Lez. 2

Bit e informazione

(1)

A questo punto ci sono due significati per il termine bit: •

•

unità di misura della capacità (o dell’ingombro) di una rappresentazione binaria; unità di misura dell’informazione.

Bit e informazione

(2)

Per codificare 256 simboli equiprobabili, si usano 8 cifre binarie. Ogni cifra binaria porta 1 bit di informazione. Se i simboli non fossero equiprobabili, alcune cifre potrebbero portare (in media) più di 1 bit, e altre meno di 1 bit.

Stefano Ferrari— Fondamenti di Informatica per la Sicurezza

5

Modulo 2— U.D. 4— Lez. 2

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 delle domande; 3. a tali domande, la persona può rispondere solo “Sì” o “No”. Qual è il numero minimo di domande necessarie per indovinare il numero nascosto?

Indovinare un numero

(2)

Risposta: 7. Traccia: • la conoscenza del numero porta 7 bit di informazione; •

con ogni domanda possiamo ottenere 1 bit di informazione.

Stefano Ferrari— Fondamenti di Informatica per la Sicurezza

6

Modulo 2— U.D. 4— Lez. 2

Approfondimento Sciuto ed altri, "Introduzione ai sistemi Informatici", McGraw Hill, 1997, seconda edizione: capitolo 3, (pagg. 63–107). •

•

stessi argomenti del Modulo 2, trattati in ordine inverso; cenni di teoria della trasmissione.

In sintesi L’informazione: •

è legata all’incertezza;

•

si misura in bit.

Stefano Ferrari— Fondamenti di Informatica per la Sicurezza

7

Modulo 2— U.D. 4— Lez. 2

Chiusura

Stefano Ferrari— Fondamenti di Informatica per la Sicurezza

8

Modulo 3— U.D. 1— Lez. 1

Lezione 1 - Cenni di insiemistica Fondamenti di Informatica per la Sicurezza

Modulo 3 - Elaborazione delle informazioni

Unità didattica 1 - Insiemistica

Stefano Ferrari Università degli Studi di Milano - Ssri - CDL ONLINE

Teoria degli insiemi Insieme: collezione arbitraria di elementi reali e immaginari. Esempi: •

{1, 2, 4, 7}

descrizione intensionale

•

{x | x ≤ 5}

descrizione estensionale

Stefano Ferrari— Fondamenti di Informatica per la Sicurezza

1

Modulo 3— U.D. 1— Lez. 1

Descrizione grafica di un insieme 4

1 2 diagrammi di Venn

7 5

grafi cartesiani

Insiemi particolari L’insieme universo, U , contiene ogni elemento. L’insieme vuoto, ∅ = {}, non contiene alcun elemento.

Stefano Ferrari— Fondamenti di Informatica per la Sicurezza

2

Modulo 3— U.D. 1— Lez. 1

Insieme universo L’insieme universo deve essere definito all’inizio di 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)

A

L’appartenenza, ∈, indica che un elemento appartiene ad un dato insieme:

a

a∈A L’unione, ∪, compone due insiemi considerando gli elementi di entrambi:

A

B

A∪B

Stefano Ferrari— Fondamenti di Informatica per la Sicurezza

3

Modulo 3— U.D. 1— Lez. 1

Operatori L’intersezione, ∩, compone due insiemi considerando solo gli elementi comuni:

A

(2)

B

A∩B Il complemento, · , è l’insieme composto da tutti gli elementi che non appartengono all’insieme dato:

A

A

Operatori La differenza, −, compone due insiemi considerando gli elementi del primo che non appartengono al secondo:

A

(3)

B

A−B Il sottoinsieme, ⊆, indica che ogni elemento del primo insieme appartiene anche al secondo:

B A

A⊆B

Stefano Ferrari— Fondamenti di Informatica per la Sicurezza

4

Modulo 3— U.D. 1— Lez. 1

Operatori

(4)

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

|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 insieme potenza e viene indicato con 2A .

Stefano Ferrari— Fondamenti di Informatica per la Sicurezza

5

Modulo 3— U.D. 1— Lez. 1

Proprietà degli operatori •

(1)

Idempotenza A∪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)

•

Assorbimento A ∩ (A ∪ B) = A A ∪ (A ∩ B) = A

•

Doppio complemento A=A

•

Leggi di De Morgan A∩B =A∪B A∪B =A∩B

Stefano Ferrari— Fondamenti di Informatica per la Sicurezza

6

Modulo 3— U.D. 1— Lez. 1

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 ad alcuni elementi che già appartengono all’insieme.

L’insieme descritto è dato dalla chiusura dell’insieme base rispetto alle operazioni della regola 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

h1, 2, 3i 6≡ h1, 3, 2i 6≡ h1, 3, 2, 3i

Stefano Ferrari— Fondamenti di Informatica per la Sicurezza

7

Modulo 3— U.D. 1— Lez. 1

In sintesi L’insiemistica è alla base della formalizzazione della matematica moderna. Vanno ricordati i seguenti concetti: •

operatori insiemistici;

•

loro proprietà.

Chiusura

Stefano Ferrari— Fondamenti di Informatica per la Sicurezza

8

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

Lezione 2 - Funzioni Fondamenti di Informatica per la Sicurezza

Modulo 3 - Elaborazione delle informazioni

Unità didattica 1 - Insiemistica

Stefano Ferrari Università degli Studi di Milano - Ssri - CDL ONLINE

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

A = {a, b, c}

B = {1, 2}

A × B = {ha, 1i, ha, 2i, hb, 1i, hb, 2i, hc, 1i, hc, 2i}

B 2 1

Stefano Ferrari— Fondamenti di Informatica per la Sicurezza

a

b

c

A

1

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

Funzione Una funzione f : A → B è una regola per abbinare ad ogni elemento a dell’insieme A un elemento f (a) dell’insieme B . A

B f

A è il dominio di f a

f (a)

B è il codominio di f a è detto argomento

B

f (a) è la sua immagine

f

f (a) a

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) =

g : Z → N, I : U → U,



+x, −x,

x≥0 x<0

g(x) = 2x2 + x I(u) = u

Stefano Ferrari— Fondamenti di Informatica per la Sicurezza

2

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

Funzioni suriettive Una funzione si dice suriettiva se ogni elemento del codominio è immagine di un elemento del dominio.

Funzioni iniettive Una funzione si dice iniettiva se ad elementi distinti del dominio corrispondono immagini distinte nel codominio.

Stefano Ferrari— Fondamenti di Informatica per la Sicurezza

3

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

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 e quelli di B ; esistenza della funzione inversa f −1 : B → A.

Stefano Ferrari— Fondamenti di Informatica per la Sicurezza

4

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

Composizione di funzioni La composizione di due funzioni è l’applicazione di 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 sua inversa 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 : A 1 × A2 × A3 → B è una funzione ternaria (triadica) f : A1 × · · · × A n → B è una funzione n-aria (n-adica)

Stefano Ferrari— Fondamenti di Informatica per la Sicurezza

5

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

In sintesi L’insiemistica è alla base della formalizzazione della matematica moderna. Vanno ricordati i seguenti concetti relativi alle funzioni: •

suriettività;

•

iniettività.

•

biiettività.

Chiusura

Stefano Ferrari— Fondamenti di Informatica per la Sicurezza

6

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

Lezione 1 - Algebre di Boole Fondamenti di Informatica per la Sicurezza

Modulo 3 - Elaborazione delle informazioni

Unità didattica 2 - Algebre di Boole

Stefano Ferrari Università degli Studi di Milano - Ssri - CDL ONLINE

George Boole (1815–1864) Nel 1854, pubblica “An investigation into the Laws of Thought, on Which are founded the Mathematical Theories of Logic and Probabilities”. Boole riduce la logica a semplice algebra, incorporandola nella matematica. Evidenzia l’analogia tra i simboli algebrici e quelli delle forme logiche. L’algebra booleana trova applicazioni nella progettazione dei calcolatori.

Stefano Ferrari— Fondamenti di Informatica per la Sicurezza

1

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

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

Stefano Ferrari— Fondamenti di Informatica per la Sicurezza

2

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

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 5. esistenza degli elementi neutri di •

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

•

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

(3)

+e·

6. proprietà distributiva

∀ a, b, c ∈ K : •

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

•

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

Stefano Ferrari— Fondamenti di Informatica per la Sicurezza

3

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

Assiomi

(3)

7. complemento

∀a ∈ K ∃a ∈ K : •

a+a=1

•

a·a=0

Proprietà Idempotenza

a+a=a

Leggi di De Morgan

a+b=a·b

Doppio complemento Elemento nullo

a+1=1

e

a·a=a

e

a·b=a+b

a=a e

a·0=0

Tali proprietà possono essere verificate per: •

dimostrazione;

•

analisi esaustiva.

Stefano Ferrari— Fondamenti di Informatica per la Sicurezza

4

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

Principio di dualità I teoremi dell’algebra booleana possono essere dimostrati 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 a n termini.

X1 + X 2 + . . . + X n = X 1 · X 2 · . . . · X n 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.

Stefano Ferrari— Fondamenti di Informatica per la Sicurezza

5

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

Teorema di De Morgan

(2)

Dimostrazione per induzione: • caso base:

X1 + X 2 = X 1 · X 2 •

(Legge di De Morgan)

passo di induzione: Se per ipotesi, è vero che:

X1 + . . . + Xn−1 = X 1 · . . . · X n−1 allora: (X1 + . . . + Xn−1 ) + Xn = = (X1 + . . . + Xn−1 ) · X n = X 1 · . . . · X n−1 · X n

Cardinalità Si può dimostrare che in ogni algebra booleana finita, il numero di elementi di K è una potenza di due.

Stefano Ferrari— Fondamenti di Informatica per la Sicurezza

6

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

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 la formalizzazione del ragionamento; sono regolate da 7 assiomi.

Stefano Ferrari— Fondamenti di Informatica per la Sicurezza

7

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

Prossimi passi Algebre booleane e loro applicazioni: •

logica proposizionale;

•

logica dei predicati (cenni);

•

circuiti logici.

Chiusura

Stefano Ferrari— Fondamenti di Informatica per la Sicurezza

8

Modulo 3— U.D. 3— Lez. 1

Lezione 1 - Logica proposizionale Fondamenti di Informatica per la Sicurezza

Modulo 3 - Elaborazione delle informazioni

Unità didattica 3 - Logica proposizionale

Stefano Ferrari Università degli Studi di Milano - Ssri - CDL ONLINE

Logica formale La logica formale è una branca della matematica che studia i principi su cui si basa la formalizzazione di asserzioni e delle regole di inferenza. Semplificando, si può dire che la logica formale permette una formalizzazione del “ragionamento”.

Stefano Ferrari— Fondamenti di Informatica per la Sicurezza

1

Modulo 3— U.D. 3— Lez. 1

Formalizzazione Formalizzare significa tradurre dal linguaggio naturale in un linguaggio semplificato con una sintassi 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 molte discipline.

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 a partire da assunzioni; intuizionista: basata su un approccio costruttivo, utile per esigenze pratiche di realizzazione; temporale: arricchita da operatori per indicare intervalli temporali; fuzzy: infinite gradazioni di verità.

Stefano Ferrari— Fondamenti di Informatica per la Sicurezza

2

Modulo 3— U.D. 3— Lez. 1

Logica proposizionale La logica proposizionale studia gli schemi di composizione di frasi dichiarative. Queste frasi saranno chiamate proposizioni. La logica non indaga sul significato delle singole proposizioni, ma solo sugli schemi in cui le proposizioni possono essere composte mediante operatori detti connettivi logici. Si occupa di stabilire la verità o la falsità di asserzioni (espressioni linguistiche) ottenute componendo 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.

Stefano Ferrari— Fondamenti di Informatica per la Sicurezza

3

Modulo 3— U.D. 3— Lez. 1

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.

Stefano Ferrari— Fondamenti di Informatica per la Sicurezza

4

Modulo 3— U.D. 3— Lez. 1

Connettivi

(1)

Le proposizioni semplici sono composte per mezzo 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).

Stefano Ferrari— Fondamenti di Informatica per la Sicurezza

5

Modulo 3— U.D. 3— Lez. 1

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 una struttura rigida; può essere usata per descrivere concetti, situazioni e procedure.

La logica proposizionale studia: •

i connettivi;

•

gli schemi di composizione.

Stefano Ferrari— Fondamenti di Informatica per la Sicurezza

6

Modulo 3— U.D. 3— Lez. 1

Prossimi passi Formalizzazione di sintassi e semantica della logica proposizionale. Inferenza di asserzioni valide.

Chiusura

Stefano Ferrari— Fondamenti di Informatica per la Sicurezza

7

Modulo 3— U.D. 3— Lez. 2

Lezione 2 - Sintassi e semantica della logica proposizionale Fondamenti di Informatica per la Sicurezza

Modulo 3 - Elaborazione delle informazioni

Unità didattica 3 - Logica proposizionale

Stefano Ferrari Università degli Studi di Milano - Ssri - CDL ONLINE

Sintassi

(1)

Le proposizioni (o formule) sono definite induttivamente dalle regole: •

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

•

passo: ogni composizione di formule è una formula;

•

nient’altro è una formula.

Stefano Ferrari— Fondamenti di Informatica per la Sicurezza

1

Modulo 3— U.D. 3— Lez. 2

Sintassi

(2)

Più formalmente, detto L l’insieme dei simboli enunciativi e delle costanti, l’insieme P delle proposizioni è 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 di parentesi necessarie per interpretare correttamente 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)

Stefano Ferrari— Fondamenti di Informatica per la Sicurezza

2

Modulo 3— U.D. 3— Lez. 2

Semantica La semantica è l’insieme delle regole che permettono di associare un valore di verità ad una proposizione, a partire dai valori dei simboli enunciativi che vi compaiono. La semantica dei connettivi è illustrata dalle seguenti tabelle, dette tabelle di verità:

a F F V V

b F V F V

a∨b F V V V

a∧b F F F V

¬a V V F F

a→b V V F V

a↔b V F F V

Interpretazione

(1)

Diremo interpretazione di una proposizione una funzione che assegna uno dei due valori di verità, V o F , a ciascuna proposizione atomica componente e che quindi assegna un valore di verità alla proposizione composta sulla base delle tavole di verità. Formalmente, quindi, una interpretazione è una funzione v : P → {F, V }. L’interpretazione di una proposizione p può essere calcolata mediante la costruzione della tabella di verità di p.

Stefano Ferrari— Fondamenti di Informatica per la Sicurezza

3

Modulo 3— U.D. 3— Lez. 2

Interpretazione

(2)

Esempio: ¬p ∧ (q → p)

p F F V V

q F V F V

¬p q → p ¬p ∧ (q → p) V V V V F F F V F F V F

Ogni riga di una tabella di verità è una interpretazione. Se una proposizione ha n componenti atomici, esistono 2n interpretazioni per essa.

Soddisfacibilità Se una interpretazione, v(·), rende una proposizione, p, vera (v(p) = V ), si dice che v soddisfa p. Una proposizione, p, si dice soddisfacibile se esiste almeno una interpretazione, v(·), che la soddisfa. Una proposizione, p, si dice tautologia (o anche che è valida) se tutte le sue interpretazioni possibili la rendono vera: ∀v, v(p) = V . Una proposizione non soddisfacibile (cioè resa falsa da tutte le interpretazioni possibili) viene detta contraddizione.

Stefano Ferrari— Fondamenti di Informatica per la Sicurezza

4

Modulo 3— U.D. 3— Lez. 2

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 se a ↔ b è una tautologia: a ⇔ b NB: a ⇒ b e a ⇔ b sono relazioni tra la proposizione a e la proposizione b. Ad esse sono associabili rispettivamente le proposizioni a → b e a ↔ b.

In sintesi Sono state definite in modo ricorsivo la sintassi e la semantica della logica proposizionale. Sono state definiti i concetti di interpretazione e soddisfacibilità delle forme logiche.

Stefano Ferrari— Fondamenti di Informatica per la Sicurezza

5

Modulo 3— U.D. 3— Lez. 2

Prossimi passi Schemi di inferenza.

Chiusura

Stefano Ferrari— Fondamenti di Informatica per la Sicurezza

6

Modulo 3— U.D. 3— Lez. 3

Lezione 3 - Inferenza e dimostrazioni Fondamenti di Informatica per la Sicurezza

Modulo 3 - Elaborazione delle informazioni

Unità didattica 3 - Logica proposizionale

Stefano Ferrari Università degli Studi di Milano - Ssri - CDL ONLINE

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)

Stefano Ferrari— Fondamenti di Informatica per la Sicurezza

1

Modulo 3— U.D. 3— Lez. 3

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) Stefano •Ferrari— Fondamenti di Informatica per la Sicurezza ((a → b) ∧ (b → c)) ⇒ (a → c)

2

Modulo 3— U.D. 3— Lez. 3

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

Stefano Ferrari— Fondamenti di Informatica per la Sicurezza

3

Modulo 3— U.D. 3— Lez. 3

Teoremi Un teorema della logica proposizionale è composto da: •

•

una o più proposizioni , ak (1 ≤ k ≤ n), dette assunzioni o ipotesi; da una proposizione, t, detta tesi.

Un teorema è esprimibile come:

a1 ∧ · · · ∧ a n ⇒ t

Regole di inferenza Le regole di inferenza permettono di dedurre una proposizione valida: •

•

•

•

dato che p è vera e p ⇔ q , anche q è vera (equivalenza logica); se p è una tautologia e a è una sua proposizione componente, sostituendo a tutte le occorrenze di a in p la proposizione q , si ottiene ancora una tautologia (sostituzione); dato che sia a → b che a sono vere, si deduce che anche b è vera (modus ponens); dato che sia a → b che ¬b sono vere, si deduce che anche ¬a è vera (modus tollens).

Stefano Ferrari— Fondamenti di Informatica per la Sicurezza

4

Modulo 3— U.D. 3— Lez. 3

Dimostrazione di teoremi Una dimostrazione può essere formulata come una 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 siano vere: •

se è vacanza sto a casa o vado in montagna;

•

oggi sono al lavoro.

Date le precedenti assunzioni, dimostrare che: •

oggi è un giorno lavorativo.

Stefano Ferrari— Fondamenti di Informatica per la Sicurezza

5

Modulo 3— U.D. 3— Lez. 3

Esempio — formalizzazione Le proposizioni coinvolte possono essere formalizzate 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 : p2 : p3 :

¬(c ∨ m) → ¬v ¬(c ∨ m) ¬v

contrapposizione di a1 Legge di De Morgan da a2 modus ponens da p2 p1

Stefano Ferrari— Fondamenti di Informatica per la Sicurezza

6

Modulo 3— U.D. 3— Lez. 3

In sintesi Alcune forme logiche sono sempre valide: le tautologie. Possiamo utilizzarle per dedurre una proposizione valida da un insieme di asserzioni. Questo procedimento assume la struttura di una dimostrazione.

Prossimi passi Esercizi sulla logica proposizionale.

Stefano Ferrari— Fondamenti di Informatica per la Sicurezza

7

Modulo 3— U.D. 3— Lez. 3

Chiusura

Stefano Ferrari— Fondamenti di Informatica per la Sicurezza

8

Modulo 3— U.D. 3— Lez. 4

Lezione 4 - Esercizi di logica proposizionale Fondamenti di Informatica per la Sicurezza

Modulo 3 - Elaborazione delle informazioni

Unità didattica 3 - Logica proposizionale

Stefano Ferrari Università degli Studi di Milano - Ssri - CDL ONLINE

Formalizzazione

(1)

Formalizzare le seguenti proposizioni: a) se Aldo e Bruno non mangiano insieme, Carlo cucina b) se Aldo mangia, Bruno digiuna c) Carlo cucina d) se Carlo cucina, Bruno e Aldo mangiano e) Bruno non mangia e Carlo cucina

Stefano Ferrari— Fondamenti di Informatica per la Sicurezza

1

Modulo 3— U.D. 3— Lez. 4

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

Stefano Ferrari— Fondamenti di Informatica per la Sicurezza

2

Modulo 3— U.D. 3— Lez. 4

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) (2) (3) (4)

(¬a → b) ∧ (¬a → c) ¬a → b ¬b → a a

distrib. conseg. di Ip1 elim. di cong. in (1) contrapp. di (2) MP da (3) e Ip2

Stefano Ferrari— Fondamenti di Informatica per la Sicurezza

3

Modulo 3— U.D. 3— Lez. 4

Teorema 2 Dimostrare la validità del seguente teorema: Assunzioni • Mario è architetto oppure è geometra. •

•

Se Mario fosse architetto, allora Mario sarebbe laureato. 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

Stefano Ferrari— Fondamenti di Informatica per la Sicurezza

4

Modulo 3— U.D. 3— Lez. 4

Dimostrazione del teorema 2 (1) (2) (3) (4) (5)

¬¬a ∨ g equiv. logica di Ip1 ¬a → g equiv. logica di 1 ¬l → ¬a contrapp. di Ip2 ¬a MP da Ip3 e 3 g MP da (4) e 2

Altri esercizi Altri esercizi si possono trovare su: •

sito del corso online;

•

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

Stefano Ferrari— Fondamenti di Informatica per la Sicurezza

5

Modulo 3— U.D. 3— Lez. 4

Prossimi passi Qualche approfondimento su: •

logica proposizionale;

•

logica dei predicati.

Chiusura

Stefano Ferrari— Fondamenti di Informatica per la Sicurezza

6

Modulo 3— U.D. 3— Lez. 5

Lezione 5 - Note aggiuntive sulla logica proposizionale Fondamenti di Informatica per la Sicurezza

Modulo 3 - Elaborazione delle informazioni

Unità didattica 3 - Logica proposizionale

Stefano Ferrari Università degli Studi di Milano - Ssri - CDL ONLINE

Connettivi binari A parte la negazione, un connettivo logico è un operatore binario. Ogni connettivo binario ha 22 = 4 possibili interpretazioni. Ogni interpretazione può assumere 2 valori. Quindi esistono 24 = 16 connettivi logici (binari). Analogamente, si può vedere che esistono 4 connettivi logici unari, e che la negazione è uno di questi.

Stefano Ferrari— Fondamenti di Informatica per la Sicurezza

1

Modulo 3— U.D. 3— Lez. 5

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

z = f (a1 , a2 , · · · , an ) è una legge che fa corrispondere ad ogni combinazione di valori logici di a1 , · · · , an uno e un solo valore di z . Esempi: • una proposizione con n simboli enunciativi è una funzione 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 connettivi binari sono stati scelti proprio ¬, ∨, ∧, → e ↔? Perché tramite di essi si possono ottenere tutte le funzioni logiche. Per esempio, il connettivo Y descritto dalla tabella di verità a lato equivale a (a ∧ ¬b) ∨ (¬a ∧ b). Esso è conosciuto anche come aut, XOR, o OR esclusivo.

a F F V V

Stefano Ferrari— Fondamenti di Informatica per la Sicurezza

b F V F V

Y F V V F

2

Modulo 3— U.D. 3— Lez. 5

Insiemi funzionalmente completi

(1)

Gli insiemi di connettivi che permettono di ottenere una qualsiasi funzione logica si dicono insiemi 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.

Stefano Ferrari— Fondamenti di Informatica per la Sicurezza

3

Modulo 3— U.D. 3— Lez. 5

Motivazioni Perché usare cinque connettivi quando ne basta uno? I motivi sono (almeno) due: •

•

formale: benché equivalenti, non tutti i connettivi hanno le stesse proprietà; pratico: alcuni connettivi hanno un significato più intuitivo.

Logica proposizionale e algebra booleana Si può dimostrare che

h{F, V }, {¬, ∨, ∧}i rispetta gli assiomi dell’algebra booleana. In particolare: •

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

•

∨ ≡ +

•

∧ ≡ ·

•

¬ ≡¯

Stefano Ferrari— Fondamenti di Informatica per la Sicurezza

4

Modulo 3— U.D. 3— Lez. 5

Logica e intuitività Alcuni connettivi hanno un significato più intuitivo di altri. Questo può essere fatto derivare dalla nostra cultura, ma ha anche delle basi fisiologiche. Wason (fine anni ‘60) ha condotto degli studi a riguardo. Un suo famoso esperimento richiede un mazzo di carte con una lettera su una faccia ed un numero sull’altra.

Esperimento di Wason

(1)

Date le carte:

A

R

6

7

Quali carte è necessario voltare per poter affermare che la regola “se c’è una vocale su una faccia, allora sull’altra c’è un numero pari” sia vera?

Stefano Ferrari— Fondamenti di Informatica per la Sicurezza

5

Modulo 3— U.D. 3— Lez. 5

Esperimento di Wason

(2)

Una percentuale molto bassa di soggetti risponde correttamente al test di Wason. È però sorprendente che lo stesso test con una mazzo di carte con un’età ed una bevanda sulle due 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 parte dei soggetti!

Implicazione L’implicazione viene generalmente associata all’inferenza. La proposizione “se oggi è martedì, domani piove oppure se domani piove, oggi è martedì” non pare aver senso. Eppure la sua formalizzazione ((a → b) ∨ (b → a)) è una tautologia. Istintivamente associamo la proposizione data a ciò che dovremmo formalizzare come:

(a ⇒ b) ∨ (b ⇒ a)

Stefano Ferrari— Fondamenti di Informatica per la Sicurezza

6

Modulo 3— U.D. 3— Lez. 5

Limiti del calcolo proposizionale La logica proposizionale si limita allo studio degli schemi di composizione di asserzioni. Non entra nel merito della semantica delle singole asserzioni. Non permette deduzioni legate solo ad alcuni elementi del dominio considerato. Per esempio, il famoso sillogismo “Tutti gli uomini sono mortali e 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.

Stefano Ferrari— Fondamenti di Informatica per la Sicurezza

7

Modulo 3— U.D. 3— Lez. 5

Chiusura

Stefano Ferrari— Fondamenti di Informatica per la Sicurezza

8

Modulo 3— U.D. 4— Lez. 1

Lezione 1 - Logica dei predicati Fondamenti di Informatica per la Sicurezza

Modulo 3 - Elaborazione delle informazioni

Unità didattica 4 - Approfondimenti

Stefano Ferrari Università degli Studi di Milano - Ssri - CDL ONLINE

Indovinello

Frase 1, 8, 5, 5

∃x(¬f reddo(y) ∧ piace(x, y))

Stefano Ferrari— Fondamenti di Informatica per la Sicurezza

1

Modulo 3— U.D. 4— Lez. 1

Limiti del calcolo proposizionale Alcune inferenze logiche non possono venire giustificate 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 è un coccodrillo.

Calcolo dei predicati

(1)

Estensione della logica delle proposizioni: •

costanti: sono gli elementi dell’universo del discorso; –

•

variabili: assumono un valore nell’universo del discorso; –

•

esempio: se si esprimono ragionamenti sulle persone, ogni singola persona è una costante;

esempio: nei discorsi comuni, gli ipotetici Tizio, Caio e Sempronio assumono la funzione di variabili;

funzioni: combinano gli elementi dell’universo del discorso; –

esempio: “la moglie di Tizio” è una funzione che applicata ad una persona restituisce un’altra persona;

Stefano Ferrari— Fondamenti di Informatica per la Sicurezza

2

Modulo 3— U.D. 4— Lez. 1

Calcolo dei predicati •

predicati: sono funzioni logiche che si applicano ad elementi dell’universo del discorso; –

•

(2)

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(lassu0 (x) ∧ ama(x, Io)) •

“Tutti pazzi per Mary” (1998):

∀x(uomo(x) → pazzo(x, M ary))

Stefano Ferrari— Fondamenti di Informatica per la Sicurezza

3

Modulo 3— U.D. 4— Lez. 1

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 di matricola.

Quantificatori

(2)

Sarebbe sufficiente definire un solo quantificatore: •

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

•

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

Esempi: •

•

“tutti i palloni sono tondi” ⇔ “non esiste un pallone che non sia tondo” “esiste un mammifero che vola” ⇔ “non tutti i mammiferi non sanno volare”

Stefano Ferrari— Fondamenti di Informatica per la Sicurezza

4

Modulo 3— U.D. 4— Lez. 1

Descrizione formale

(1)

La descrizione formale della sintassi della logica dei predicati è basata sulla definizione di termini e 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 sono termini; le espressioni del tipo: –

A∨B

–

A∧B

–

¬A

–

∀x A

–

∃x A

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

Stefano Ferrari— Fondamenti di Informatica per la Sicurezza

5

Modulo 3— U.D. 4— Lez. 1

Definizioni Nella formula ∀x A: •

•

A si chiama ambito o campo d’azione del quantificatore ∀; x si dice variabile vincolata (o quantificata).

Una variabile non vincolata di dice libera. Una formula che non contiene variabili libere si dice chiusa. Una formula che non contiene variabili si dice ground.

Dimostrazioni formali Possono essere eseguite usando le regole di inferenza della logica proposizionale e con le seguenti regole di inferenza aggiuntive: •

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

•

A ⇒ ∀x A (generalizzazione);

•

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

Stefano Ferrari— Fondamenti di Informatica per la Sicurezza

6

Modulo 3— U.D. 4— Lez. 1

In sintesi La logica dei predicati permette di analizzare gli elementi di cui la proposizione è composta. Essa è quindi uno strumento più potente (e più complesso) della logica proposizionale. Soluzione dell’indovinello ∃x(¬f reddo(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.

Stefano Ferrari— Fondamenti di Informatica per la Sicurezza

7

Modulo 3— U.D. 4— Lez. 1

Chiusura

Stefano Ferrari— Fondamenti di Informatica per la Sicurezza

8

Modulo 3— U.D. 4— Lez. 2

Lezione 2 - Predicati ed insiemi Fondamenti di Informatica per la Sicurezza

Modulo 3 - Elaborazione delle informazioni

Unità didattica 4 - Approfondimenti

Stefano Ferrari Università degli Studi di Milano - Ssri - CDL ONLINE

Predicati ed insiemi Esiste una corrispondenza tra i predicati e gli insiemi: •

i predicati definiscono insiemi; –

•

la disgiunzione definisce un’unione; –

•

esempio: gli elementi, x, per cui il predicato architetto(x) è vero, costituiscono l’insieme degli architetti; 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.

Stefano Ferrari— Fondamenti di Informatica per la Sicurezza

1

Modulo 3— U.D. 4— Lez. 2

Dimostrazioni grafiche Sfruttando la corrispondenza tra formule di logica posizionale e insiemi, è possibile effettuare o confutare la validità di inferenze con il 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 piano come nei diagrammi di Eulero-Venn.

Un’inferenza sarà valida se il grafico delle assunzioni descrive una situazione compatibile con 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))

M U

Ip2: U (s) Tesi: M (s)

s

Ip1: U ⊆ M Ip2: s ∈ U Tesi: s ∈ M

Stefano Ferrari— Fondamenti di Informatica per la Sicurezza

2

Modulo 3— U.D. 4— Lez. 2

Esempio 2 Ip1: Tutte le api ronzano. Ip2: Qualche insetto non ronza. Tesi: Qualche insetto non è un’ape. Ip1: ∀x(A(x) → R(x))

A

R

Ip2: ∃x(I(x) ∧ ¬R(x)) Tesi: ∃x(I(x) ∧ ¬A(x)) Ip1: A ⊆ R Ip2: ∃x ∈ I − R

x

I

Tesi: ∃x ∈ I − A

In sintesi La logica dei predicati permette di analizzare gli elementi di cui la proposizione è composta. I predicati possono essere messi in corrispondenza con opportuni insiemi. Questa corrispondenza può, in alcuni casi, essere sfruttata per effettuare delle dimostrazioni.

Stefano Ferrari— Fondamenti di Informatica per la Sicurezza

3

Modulo 3— U.D. 4— Lez. 2

Chiusura

Stefano Ferrari— Fondamenti di Informatica per la Sicurezza

4

Modulo 3— U.D. 4— Lez. 3

Lezione 3 - Reti logiche Fondamenti di Informatica per la Sicurezza

Modulo 3 - Elaborazione delle informazioni

Unità didattica 4 - Approfondimenti

Stefano Ferrari Università degli Studi di Milano - Ssri - CDL ONLINE

Algebre booleane Sono algebre booleane: Boole K · + ¯ 0 1

insiemi P(U ) ∩ ∪ ¯ ∅ U

proposizioni {F, V } ∧ ∨ ¬ F V

commutazione {aperto, chiuso} serie parallelo invertitore aperto chiuso

Esempio: •

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

Stefano Ferrari— Fondamenti di Informatica per la Sicurezza

1

Modulo 3— U.D. 4— Lez. 3

Algebra di commutazione Claude Shannon (1938) ha constatato che un circuito dotato di interrutori (switch) si comporta secondo le leggi dell’algebra booleana. Questa proprietà è indipendente dalla tecnologia usata, e infatti vale per circuiti: •

elettrici;

•

pneumatici;

•

ottici.

Reti logiche I circuiti degli attuali elaboratori digitali sono costituiti da componenti elementari, detti porte logiche, che realizzano i connettivi logici. Questi dispositivi, detti reti logiche, si dividono in 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).

Stefano Ferrari— Fondamenti di Informatica per la Sicurezza

2

Modulo 3— U.D. 4— Lez. 3

Approfondimenti Il corso di “Architetture e reti logiche” copre approfonditamente questi temi.

In sintesi Le reti logiche consentono di realizzare una macchina dotata di: •

capacità di effettuare calcoli;

•

memoria.

Stefano Ferrari— Fondamenti di Informatica per la Sicurezza

3

Modulo 3— U.D. 4— Lez. 3

Chiusura

Stefano Ferrari— Fondamenti di Informatica per la Sicurezza

4

Modulo 4— U.D. 1— Lez. 1

Lezione 1 - Architettura di von Neumann Fondamenti di Informatica per la Sicurezza

Modulo 4 - Sistemi di elaborazione

Unità didattica 1 - Architettura di von Neumann

Stefano Ferrari Università degli Studi di Milano - Ssri - CDL ONLINE

Scomposizione funzionale Il calcolatore può essere descritto scomponendolo iterativamente in una gerarchia di sottosistemi. Ogni componente: •

è responsabile di una funzionalità;

•

interagisce con gli altri componenti e con l’ambiente;

•

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

Stefano Ferrari— Fondamenti di Informatica per la Sicurezza

1

Modulo 4— U.D. 1— Lez. 1

Funzionalità principali Le funzionalità principali sono: •

scambio dati con l’esterno;

•

memorizzazione;

•

elaborazione;

•

controllo.

Trasferimento dati È la funzionalità che consente di scambiare dati con l’esterno: input/output (I/O). Si realizza mediante: •

dispositivi di I/O;

•

connessione in rete.

Stefano Ferrari— Fondamenti di Informatica per la Sicurezza

2

Modulo 4— U.D. 1— Lez. 1

Memorizzazione Vi sono almeno due tipi di memorizzazione: •

a breve termine;

•

a lungo termine.

Elaborazione Risulta come compromesso tra le diverse caratteristiche di un calcolatore: •

flessibilità;

•

modularità;

•

scalabilità;

•

standardizzazione;

•

costo;

•

semplicità;

•

disponibilità di applicazioni.

Stefano Ferrari— Fondamenti di Informatica per la Sicurezza

3

Modulo 4— U.D. 1— Lez. 1

Controllo È esercitato da: •

utente (ad alto livello);

•

CPU (a basso livello);

•

unità di controllo (a bassissimo livello).

Calcolatore programmabile Il calcolatore è una macchina estremamente flessibile: •

le funzionalità vengono fornite dall’hardware;

•

la specializzazione viene fornita dal software.

Stefano Ferrari— Fondamenti di Informatica per la Sicurezza

4

Modulo 4— U.D. 1— Lez. 1

Architettura di von Neumann La cosidetta architettura di von Neumann si compone di: •

•

•

•

una unità elaborazione centrale (Central Processing Unit — CPU); un dispositivo di memoria, costituito da un insieme di elementi identificabili tramite il loro indirizzo; alcuni dispositivi, detti periferiche, per l’interazione con l’esterno; una linea di interconnessione, detta bus, con modalità master/slave.

CPU È il componente principale, a cui sono affidate le funzioni di: •

controllo;

•

coordinamento;

•

elaborazione.

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

Stefano Ferrari— Fondamenti di Informatica per la Sicurezza

5

Modulo 4— U.D. 1— Lez. 1

Memoria centrale La memoria centrale: •

•

ospita i dati coinvolti nell’elaborazione (talvolta anche quelli delle periferiche); è costituita da insieme di celle adiacenti, ognuna delle quali è identificata da un indirizzo numerico.

Periferiche Le periferiche: •

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

•

comunicano tramite l’interfaccia di I/O.

Stefano Ferrari— Fondamenti di Informatica per la Sicurezza

6

Modulo 4— U.D. 1— Lez. 1

Bus Il bus è una linea a cui sono collegate contemporaneamente diverse unità: •

la CPU svolge il ruolo di master;

•

le altre unità funzionano da slave. Architettura master/slave vantaggi

svantaggi

•

semplicità;

•

lentezza;

•

estendibilità;

•

capacità del canale limitante;

•

standardizzabilità;

•

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.

Stefano Ferrari— Fondamenti di Informatica per la Sicurezza

7

Modulo 4— U.D. 1— Lez. 1

Prossimi passi Il funzionamento dei componenti della macchina di von Neumann.

Chiusura

Stefano Ferrari— Fondamenti di Informatica per la Sicurezza

8

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

Lezione 2 - Bus e CPU Fondamenti di Informatica per la Sicurezza

Modulo 4 - Sistemi di elaborazione

Unità didattica 1 - Architettura di von Neumann

Stefano Ferrari Università degli Studi di Milano - Ssri - CDL ONLINE

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.

Stefano Ferrari— Fondamenti di Informatica per la Sicurezza

1

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

Esecutore L’idea fondamentale ancora oggi seguita nella realizzazione 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 che permette lettura e scrittura; la memoria è costituita da celle uguali, indirizzate dalla loro posizione; le istruzioni vengono eseguite in modo sequenziale.

Linguaggio macchina I programmi vengono codificati in un linguaggio detto linguaggio macchina, o assembly, caratterizzato da: •

assenza di struttura o tipo di dato;

•

istruzioni semplici e in numero ridotto;

•

istruzioni composte dall’identificativo dell’operazione più eventuali operandi: –

esempio: <Somma> .

Stefano Ferrari— Fondamenti di Informatica per la Sicurezza

2

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

Codice operativo Il codice operativo è il valore numerico che identifica l’operazione effettuata da una istruzione assembly. Si ha che: •

•

CPU della stessa famiglia hanno lo stesso codice operativo; CPU di diversi produttori possono adottare lo stesso codice operativo (compatibilità).

Esecuzione del programma Quando il programma e i dati risiedono in memoria, la CPU opera in modo ciclico: •

• •

viene recuperata dalla memoria l’istruzione da eseguire (fetch); viene decodificata (decode); vengono eseguite le operazioni che compongono l’istruzione (execute).

Stefano Ferrari— Fondamenti di Informatica per la Sicurezza

3

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

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 dati bus indirizzi bus controllo MDR

IR

MAR

UC

REG1 ...

PC PSW

ALU

REGN

CPU

Fetch

Nella fase di fetch:

bus dati bus indirizzi bus controllo MDR

1. l’UC mette PC in MAR;

IR

2. l’UC mette il comando di lettura sul bus controllo; 3. MDR viene messo in IR — incremento di PC.

REG1 ... REGN

MAR

UC

PC PSW

ALU

CPU

Stefano Ferrari— Fondamenti di Informatica per la Sicurezza

4

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

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 da von Neumann: •

la memoria;

•

le periferiche.

Stefano Ferrari— Fondamenti di Informatica per la Sicurezza

5

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

Chiusura

Stefano Ferrari— Fondamenti di Informatica per la Sicurezza

6

Modulo 4— U.D. 1— Lez. 3

Lezione 3 - Memoria e periferiche Fondamenti di Informatica per la Sicurezza

Modulo 4 - Sistemi di elaborazione

Unità didattica 1 - Architettura di von Neumann

Stefano Ferrari Università degli Studi di Milano - Ssri - CDL ONLINE

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.

Stefano Ferrari— Fondamenti di Informatica per la Sicurezza

1

Modulo 4— U.D. 1— Lez. 3

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 a memoria.

Periferiche Modalità: •

seriale (USB, Firewire, Bluetooth);

•

parallelela.

Interfaccia di I/O è composta da: •

registro dati;

•

registro di controllo;

•

registro di stato.

Stefano Ferrari— Fondamenti di Informatica per la Sicurezza

2

Modulo 4— U.D. 1— Lez. 3

Controllo delle periferiche Ci sono due modalità di controllo delle periferiche: •

•

in modalità memory mapped, la CPU accede ai registri della periferica con un’operazione di lettura o scrittura in memoria, ma lo fa in indirizzi che la memoria non riconosce come propri; tramite istruzioni dedicate, previste nell’instruction set 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.

Stefano Ferrari— Fondamenti di Informatica per la Sicurezza

3

Modulo 4— U.D. 1— Lez. 3

Approfondimento Istruzioni particolari possono alterare il prelievo delle istruzioni da celle consecutive (e quindi la sequenzialità): •

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.

Stefano Ferrari— Fondamenti di Informatica per la Sicurezza

4

Modulo 4— U.D. 1— Lez. 3

Prossimi passi Elementi software dei calcolatori: •

elementi di programmazione;

•

cenni di sistemi operativi.

Chiusura

Stefano Ferrari— Fondamenti di Informatica per la Sicurezza

5

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

Lezione 1 - Soluzione automatizzata di problemi Fondamenti di Informatica per la Sicurezza

Modulo 4 - Sistemi di elaborazione

Unità didattica 2 - Elementi di programmazione

Stefano Ferrari Università degli Studi di Milano - Ssri - CDL ONLINE

Definizione

virtuale

[vir-tu-à-le] agg.

1. Che esiste in potenza, ma non si è ancora realizzato; 2. Fittizio, non reale.

Stefano Ferrari— Fondamenti di Informatica per la Sicurezza

1

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

Macchina virtuale Si usa il termine macchina virtuale per indicare l’astrazione della macchina fisica realizzata dal software ai vari livelli. Esempio: •

per le periferiche mappate in memoria si usano delle operazioni che non hanno nulla a che vedere con la realtà 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.

Stefano Ferrari— Fondamenti di Informatica per la Sicurezza

2

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

Risolvere un problema Dato un problema, l’individuazione delle procedure necessarie alla sua soluzione richiede le seguenti fasi: •

•

•

descrizione dei requisiti che la soluzione dovrà soddisfare per essere considerata corretta (specifiche); procedimento con cui si individua o si inventa una soluzione (progetto); tecnica che consente di risolvere il problema (soluzione).

Nell’informatica, la soluzione è espressa tramite un 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.

Stefano Ferrari— Fondamenti di Informatica per la Sicurezza

3

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

Caratteristiche di un algoritmo Ogni algoritmo possiede le seguenti caratteristiche: •

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 casi significativi che derivano dall’esecuzione di ogni passo elementare. La descrizione di un algoritmo per un esecutore automatico deve avere una formulazione generale: la soluzione individuata non deve dipendere solo da valori predefiniti dei dati.

Stefano Ferrari— Fondamenti di Informatica per la Sicurezza

4

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

Esempi Esempio negativo: •

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

Esempio positivo: •

programma che calcola l’area del cerchio di raggio dato dall’utente.

Elementi di un algoritmo “Oggetti”: le entità su cui opera l’algoritmo vengono generalmente chiamate dati, e comprendono sia i dati iniziali del problema che i risultati intermedi. Operazioni: gli interventi che si possono effettuare sugli oggetti, cioè sui dati sono calcoli, confronti, assegnamenti ed operazioni di I/O. Flusso di controllo: indica le possibili evoluzioni dell’esecuzione delle operazioni, cioè le possibili successioni dei passi dell’algoritmo.

Stefano Ferrari— Fondamenti di Informatica per la Sicurezza

5

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

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 tre fasi: •

specifica;

•

progetto;

•

realizzazione.

Una soluzione adatta ad un esecutore automatico deve essere: •

sequenziale;

•

non ambigua.

Stefano Ferrari— Fondamenti di Informatica per la Sicurezza

6

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

Prossimi passi Elementi di programmazione di un calcolatore.

Chiusura

Stefano Ferrari— Fondamenti di Informatica per la Sicurezza

7

Modulo 4— U.D. 2— Lez. 2

Lezione 2 - Programmazione di un calcolatore Fondamenti di Informatica per la Sicurezza

Modulo 4 - Sistemi di elaborazione

Unità didattica 2 - Elementi di programmazione

Stefano Ferrari Università degli Studi di Milano - Ssri - CDL ONLINE

Descrizione di un algoritmo Un algoritmo adatto per un esecutore automatico deve essere descritto tramite un formalismo (linguaggio) rigoroso e non ambiguo costituito da: •

•

•

vocabolario: insieme di elementi per la descrizione di oggetti, operazioni e flusso di controllo; sintassi: insieme di regole per la composizione degli elementi del linguaggio in frasi eseguibili e costrutti di controllo; semantica: insieme di regole per l’interpretazione degli elementi e delle istruzioni sintatticamente corrette.

Stefano Ferrari— Fondamenti di Informatica per la Sicurezza

1

Modulo 4— U.D. 2— Lez. 2

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 opportuni costrutti di controllo.

Flusso di controllo vs. flusso di esecuzione Il flusso di controllo è differente dal flusso di esecuzione. Il flusso di controllo descrive tutte le possibili successioni di operazioni che possono essere realizzate dal programma nella sua esecuzione. Il flusso di esecuzione è la sequenza di operazioni percorsa durante una particolare esecuzione del programma.

Stefano Ferrari— Fondamenti di Informatica per la Sicurezza

2

Modulo 4— U.D. 2— Lez. 2

Linguaggi di programmazione

(1)

I linguaggi di programmazione sono classificabili in almeno quattro grandi categorie, parzialmente sovrapposte: Imperativi: le istruzioni descrivono in modo esplicito le modifiche del contenuto della memoria; • esempi: Basic, Pascal, C, Fortran, Cobol; Funzionali: il programma è costituito da una funzione che ha per argomenti altre sottofunzioni; • esempio: Lisp;

Linguaggi di programmazione

(2)

Dichiarativi (o logici): il programma è costituito da una serie di asserzioni e di regole, e la sua esecuzione consiste in una dimostrazione di veridicità di un’asserzione, senza indicare il flusso di esecuzione; • esempio: Prolog; Orientati agli oggetti: il programma è costituito da entità (oggetti) che comunicano tra loro scambiandosi messaggi e che godono delle proprietà di incapsulamento, ereditarietà e polimorfismo; • esempi: Ada, Smalltalk, Java.

Stefano Ferrari— Fondamenti di Informatica per la Sicurezza

3

Modulo 4— U.D. 2— Lez. 2

Linguaggi di descrizione I linguaggi semiformali hanno regole ben definite, ma permettono descrizioni in linguaggio naturale, non rigorose. Sono usati nella fase di sviluppo di algoritmi: schema a blocchi (diagramma di flusso): usa blocchi di varie forme geometriche connessi da archi orientati la cui direzione indica il flusso di controllo, mentre la forma dei blocchi indica la natura del blocco stesso (operazione, confronto, operazione di I/O); pseudocodice: usa strutture di controllo di un linguaggio di programmazione e operazioni descritte in linguaggio naturale.

Sottoprogrammi Programmi complessi vengono progettati seguendo uno schema gerarchico in cui il problema iniziale viene suddiviso in sottoproblemi e così via (metodologia top-down). Questo approccio ha i seguenti vantaggi: •

chiarezza del programma principale;

•

sintesi;

•

efficienza.

Stefano Ferrari— Fondamenti di Informatica per la Sicurezza

4

Modulo 4— U.D. 2— Lez. 2

Vantaggi Chiarezza: i dettagli di basso livello sono descritti a parte nei sottoprogrammi, evidenziando la struttura di controllo generale; Sintesi: per i sottoproblemi presenti in più parti del problema principale, richiamando il sottoprogramma, si evitano di ripetere le stesse sequenze di operazioni; Efficienza: sottoproblemi di uso comune sono disponibili, già risolti da esperti programmatori, raccolti nelle cosiddette librerie.

Programma eseguibile Perché un algoritmo sia eseguibile da un calcolatore, esso deve essere tradotto in una sequenza di istruzioni codificate nel codice operativo caratteristico della CPU del calcolatore che lo eseguirà (binario). L’operazione di traduzione da un linguaggio di programmazione ad un altro è una procedura ripetitiva, che può essere automatizzata.

Stefano Ferrari— Fondamenti di Informatica per la Sicurezza

5

Modulo 4— U.D. 2— Lez. 2

Traduzione in binario La traduzione in codice eseguibile è effettuata da un programma apposito, che può essere di due tipi: •

interprete: traduce solo le istruzioni del flusso di esecuzione; –

•

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 essere espressi in forma rigorosa e non ambigua. I linguaggi di programmazione rispettano queste caratteristiche. I paradigmi e le metodologie di programmazione aiutano a sviluppare programmi corretti e facilmente gestibili. I programmi devono infine essere tradotti nel codice binario della macchina esecutrice.

Stefano Ferrari— Fondamenti di Informatica per la Sicurezza

6

Modulo 4— U.D. 2— Lez. 2

Prossimi passi La catena di programmazione, ovvero come si produce un programma eseguibile.

Chiusura

Stefano Ferrari— Fondamenti di Informatica per la Sicurezza

7

Modulo 4— U.D. 2— Lez. 3

Lezione 3 - Catena di programmazione Fondamenti di Informatica per la Sicurezza

Modulo 4 - Sistemi di elaborazione

Unità didattica 2 - Elementi di programmazione

Stefano Ferrari Università degli Studi di Milano - Ssri - CDL ONLINE

Programmare La generazione di un programma eseguibile consiste nella traduzione automatica •

•

di un algoritmo espresso in un linguaggio simbolico (programma sorgente) nello stesso algoritmo espresso in codice macchina (programma eseguibile).

Stefano Ferrari— Fondamenti di Informatica per la Sicurezza

1

Modulo 4— U.D. 2— Lez. 3

Catena di programmazione Le fasi che portano un algoritmo ad essere eseguito sono: editing: composizione del programma sorgente; compiling: traduzione in codice binario; linking: collegamento con i sottoprogrammi di libreria; loading: caricamento in memoria; esecuzione: esecuzione del programma.

Editing Generalmente un algoritmo viene codificato in un programma sorgente. Lo strumento utilizzato per la scrittura è un apposito programma chiamato editor. Questa fase ha termine con la produzione di un file di testo detto file programma sorgente.

Stefano Ferrari— Fondamenti di Informatica per la Sicurezza

2

Modulo 4— U.D. 2— Lez. 3

Compiling La fase di traduzione, o compilazione, utilizza un programma (detto compilatore). Esso elabora il file sorgente, riconoscendo i simboli, le parole e i costrutti del linguaggio e producendo: •

•

la forma binaria del codice macchina corrispondente (file programma oggetto); oppure, una segnalazione degli errori sintattici.

Errore sintattico Gli errori sintattici sono violazioni delle regole sintattiche del linguaggio di programmazione. Essi rendono il programma non associabile ad un significato e quindi ne impediscono la traduzione. Esempio: 3 * (5 +/ 2)

Stefano Ferrari— Fondamenti di Informatica per la Sicurezza

3

Modulo 4— U.D. 2— Lez. 3

Linking Nella fase di linking (collegamento), un programma (detto linker) collega il file oggetto con le funzioni di libreria. Esso produce: • •

un programma eseguibile; oppure, una segnalazione di errore nella citazione delle routine di libreria (linker error).

Loading Per poter essere eseguito, un file eseguibile deve essere caricato in memoria centrale. Questa funzione viene svolta da un programma chiamato loader (caricatore), che individua una regione di memoria adeguata all’esecuzione del programma. Se tale spazio in memoria non esiste, segnala un errore di caricamento per memoria insufficiente.

Stefano Ferrari— Fondamenti di Informatica per la Sicurezza

4

Modulo 4— U.D. 2— Lez. 3

Esecuzione Il programma in esecuzione elabora i dati in ingresso e produce i risultati in uscita. Possibili errori (non di tipo sintattico!): •

calcoli matematicamente impossibili (run-time error); –

•

operazioni fisicamente impossibili (run-time error); –

•

esempio: memoria insufficiente;

calcoli scorretti; –

•

esempio: divisione per zero;

esempio: overflow;

errori semantici; –

esempio: errore nella scrittura di un’operazione.

In sintesi Il percorso che porta un algoritmo ad essere eseguito è scandito dalle seguenti fasi: •

editing;

•

compiling;

•

linking;

•

caricamento;

•

esecuzione.

In ogni fase, la descrizione dell’algoritmo subisce una trasformazione.

Stefano Ferrari— Fondamenti di Informatica per la Sicurezza

5

Modulo 4— U.D. 2— Lez. 3

Prossimi passi Alcuni cenni sui principi di funzionamento dei sistemi operativi.

Chiusura

Stefano Ferrari— Fondamenti di Informatica per la Sicurezza

6

Modulo 4— U.D. 3— Lez. 1

Lezione 1 - Struttura del sistema operativo Fondamenti di Informatica per la Sicurezza

Modulo 4 - Sistemi di elaborazione

Unità didattica 3 - Cenni di sistemi operativi

Stefano Ferrari Università degli Studi di Milano - Ssri - CDL ONLINE

Motivazioni Il sistema operativo (SO) è un insieme di programmi che: • •

gestiscono l’hardware; forniscono un’interfaccia semplificata all’utente ed ai programmi utente verso l’hardware.

Il SO è utile perché: • •

•

l’uso diretto dell’HW non è agevole; i programmi devono essere riscritti se si cambia l’HW; la gestione della macchina è trasparente per l’utente.

Stefano Ferrari— Fondamenti di Informatica per la Sicurezza

1

Modulo 4— U.D. 3— Lez. 1

Modello a buccia di cipolla Il modello di SO più diffuso ha una struttura modulare a strati (modello a buccia di cipolla): utente/programmi utente interprete dei comandi (shell) file system gestore della periferiche gestore della memoria nucleo (kernel)

SO

hardware Ogni strato fornisce un’astrazione (macchina virtuale) agli strati più esterni.

Kernel Il kernel: •

• •

è lo strato a contatto diretto con la CPU (se si cambia HW, solo il kernel va modificato); gestisce l’uso della CPU da parte dei programmi; permette ad ogni processo (programma+dati)/utente di considerarsi unico utilizzatore della CPU.

Stefano Ferrari— Fondamenti di Informatica per la Sicurezza

2

Modulo 4— U.D. 3— Lez. 1

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 memoria associati ai vari programmi.

Gestore delle periferiche Il gestore delle periferiche: • •

•

fornisce una visione semplificata delle periferiche; fornisce ai programmi delle primitive ad alto livello per l’uso delle periferiche; gestisce i conflitti nell’uso delle periferiche (ogni programma “vede” un insieme di periferiche dedicate).

Stefano Ferrari— Fondamenti di Informatica per la Sicurezza

3

Modulo 4— U.D. 3— Lez. 1

File system Il file system: •

• •

•

è uno strato dedicato ad una classe di periferiche peculiari; organizza i dispositivi di memoria di massa; gestisce la corrispondenza tra locazione fisica e identificatore del file; gestisce i permessi di uso dei file.

Shell L’interprete dei comandi (shell): •

• •

è il modulo accessibile all’utente (tramite le periferiche); interpreta i comandi dell’utente; si occupa del caricamento e dell’esecuzione dei programmi.

Stefano Ferrari— Fondamenti di Informatica per la Sicurezza

4

Modulo 4— U.D. 3— Lez. 1

Rete La connessione di rete non è stata considerata: quando il modello è stato formulato, la rete veniva vista come una una funzionalità aggiuntiva esterna al SO. La rete può essere considerata semplicisticamente come una periferica particolare. Tuttavia, l’appartenenza ad una rete di calcolatori è un aspetto che investe i vari strati del SO.

In sintesi Il sistema operativo è un insieme di programmi che facilitano l’uso del calcolatore. Il suo scopo è: •

gestire l’hardware;

•

fornire un’interfaccia semplificata per l’utente.

Una struttura gerarchica di moduli fornisce diversi gradi di astrazione.

Stefano Ferrari— Fondamenti di Informatica per la Sicurezza

5

Modulo 4— U.D. 3— Lez. 1

Prossimi passi Classificazione dei vari tipi di sistema operativo. Cenni sul funzionamento dei moduli principali.

Chiusura

Stefano Ferrari— Fondamenti di Informatica per la Sicurezza

6

Modulo 4— U.D. 3— Lez. 2

Lezione 2 - Classificazione dei sistemi operativi Fondamenti di Informatica per la Sicurezza

Modulo 4 - Sistemi di elaborazione

Unità didattica 3 - Cenni di sistemi operativi

Stefano Ferrari Università degli Studi di Milano - Ssri - CDL ONLINE

Tipi di SO I SO si possono classificare a seconda delle loro caratteristiche: •

monoutente monoprogrammato;

•

monoutente multiprogrammato;

•

multiutente multiprogrammato.

Fra i sistemi multiprogrammati sono diffusi: •

•

time-sharing (i processi usano alternativamente la CPU per un quanto di tempo); real-time.

Inoltre, ci sono sistemi dedicati.

Stefano Ferrari— Fondamenti di Informatica per la Sicurezza

1

Modulo 4— U.D. 3— Lez. 2

Parallelismo L’architettura di von Neumann prevede un’esecuzione sequenziale dedicata. Alcune operazioni, però, possono essere eseguite in parallelo. Il parallelismo può essere individuato a diversi livelli: •

dati (esempio: cambiare la luminosità a tutti i pixel dell’immagine);

•

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

•

programmi (lettore mp3 e word processing).

Parallelismo: motivazioni I principali motivi a supporto del parallelismo sono: •

•

•

efficienza: mentre un processo attende un input, può lasciare l’uso della CPU ad un altro; interattività: l’interazione con l’utente richiede brevi, ma frequenti intervalli di utilizzo della CPU; sincronizzazione/cooperazione: si può semplificare la descrizione di molti programmi utilizzando attività concorrenti, aumentando anche l’efficienza della CPU (e.g., modello produttore-consumatore).

Stefano Ferrari— Fondamenti di Informatica per la Sicurezza

2

Modulo 4— U.D. 3— Lez. 2

In sintesi I sistemi operativi si differenziano per la modalità con cui gestiscono le risorse. Particolare attenzione su come viene gestita la CPU. Una gestione multiprocesso favorisce un alto utilizzo della CPU.

Prossimi passi Cenni sul funzionamento di: •

kernel;

•

gestore della memoria;

•

file system.

Stefano Ferrari— Fondamenti di Informatica per la Sicurezza

3

Modulo 4— U.D. 3— Lez. 2

Chiusura

Stefano Ferrari— Fondamenti di Informatica per la Sicurezza

4

Modulo 4— U.D. 3— Lez. 3

Lezione 3 - Gestione dei processi Fondamenti di Informatica per la Sicurezza

Modulo 4 - Sistemi di elaborazione

Unità didattica 3 - Cenni di sistemi operativi

Stefano Ferrari Università degli Studi di Milano - Ssri - CDL ONLINE

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 diverse sezioni del programma (processo padre).

Stefano Ferrari— Fondamenti di Informatica per la Sicurezza

1

Modulo 4— U.D. 3— Lez. 3

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) selezione per esecuzione inizio esecuzione

terminazione pronto

interrupt esterno

esecuzione

interrupt interno

evento esterno attesa

Stati di un processo

(2)

Il processore viene utilizzato a turno dai processi in esecuzione, ciclando fra i tre stati: •

•

•

•

la transizione da pronto a esecuzione avviene quando il processo prende uso della CPU (scheduler); transita da esecuzione a pronto quando lo scheduler gli toglie l’uso della CPU (e.g., quando scade il suo quanto di tempo, evento esterno da gestire); passa da esecuzione a attesa quando il processo deve attendere un evento (e.g., carattere da tastiera); passa da attesa a pronto quando l’evento atteso si è verificato.

Stefano Ferrari— Fondamenti di Informatica per la Sicurezza

2

Modulo 4— U.D. 3— Lez. 3

Classificazione dei processi I processi si dividono in due categorie: •

I/O bound, caratterizzati da frequenti operazioni di I/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.

Stefano Ferrari— Fondamenti di Informatica per la Sicurezza

3

Modulo 4— U.D. 3— Lez. 3

Politiche di scheduling L’obiettivo dello scheduling è la massimizzazione dell’utilizzo della CPU. I più diffusi algoritmi di scheduling sono: •

•

•

round robin: ad ogni processo è assegnata la CPU per un quanto di tempo prefissato (sufficientemente grande rispetto al tempo di cambio del contesto); priorità statica: priorità fissata alla creazione dei processi in base alle loro caratteristiche (altà priorità per i processi interattivi, bassa priorità per i processi CPU bound); priorità dinamica: la priorità può essere modificata durante l’esecuzione dei processi.

Vantaggi della concorrenza L’esecuzione concorrente di processi ha diversi vantaggi, 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.

Stefano Ferrari— Fondamenti di Informatica per la Sicurezza

4

Modulo 4— U.D. 3— Lez. 3

Problemi della concorrenza Le interazioni tra processi concorrenti possono causare due problemi: •

•

starvation (morte per inedia): processi di priorità più elevata possono ritardare indefinitamente l’esecuzione di un processo a bassa priorità; deadlock (blocco infinito): se due processi richiedono entrambi una risorsa (o un risultato) occupata dall’altro, nessuno dei due processi può terminare. Esempio: un idraulico ed un elettricista devono rifare gli impianti di una casa, ma entrambi esigono che sia prima sistemato l’altro impianto.

Processi concorrenti La concorrenza tra processi assume la forma di: •

•

competizione per le risorse, quando i processi devono svolgere compiti differenti, con lo scopo di portare a termine il loro compito il prima possibile; cooperazione, quando i compiti che devono portare a termine sono tra loro correlati (per esempio, spooling di 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).

Stefano Ferrari— Fondamenti di Informatica per la Sicurezza

5

Modulo 4— U.D. 3— Lez. 3

In sintesi Il processo è una entità dinamica prodotta dall’esecuzione di un programma. L’esecuzione concorrente di più processi permette 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.

Stefano Ferrari— Fondamenti di Informatica per la Sicurezza

6

Modulo 4— U.D. 3— Lez. 3

Chiusura

Stefano Ferrari— Fondamenti di Informatica per la Sicurezza

7

Modulo 4— U.D. 3— Lez. 4

Lezione 4 - Gestore della memoria Fondamenti di Informatica per la Sicurezza

Modulo 4 - Sistemi di elaborazione

Unità didattica 3 - Cenni di sistemi operativi

Stefano Ferrari Università degli Studi di Milano - Ssri - CDL ONLINE

Gestione della memoria centrale Il gestore della memoria è il modulo di sistema operativo che fornisce ad ogni processo uno spazio di indirizzamento virtuale. Per ottimizzare l’utilizzo della memoria, il gestore della memoria consente: •

•

•

il caricamento di un programma a partire da un qualsiasi indirizzo; il caricamento in memoria (fisica) solo di porzioni di programma o dati; la condivisione di istruzioni da parte di processi differenti (generati dallo stesso programma).

Stefano Ferrari— Fondamenti di Informatica per la Sicurezza

1

Modulo 4— U.D. 3— Lez. 4

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

•

spazio logico: è lo spazio di indirizzamento virtuale in cui gli indirizzi delle celle partono da 0; spazio fisico: è lo spazio di indirizzamento del dispositivo di memoria.

Rilocabilità del codice La rilocazione della memoria: • •

•

•

è realizzata dal gestore della memoria; consiste in un mappaggio degli indirizzi da logici a fisici; permette di eseguire un processo in qualsiasi zona della memoria fisica; definisce lo spiazzamento di un processo: indirizzo fisico della cella 0 dello spazio logico.

Stefano Ferrari— Fondamenti di Informatica per la Sicurezza

2

Modulo 4— U.D. 3— Lez. 4

Rilocazione La rilocazione può essere: •

•

statica, quando lo spiazzamento viene calcolato al momento 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 e istruzioni mediante due registri base (diversi processi possono avere lo stesso registro base istruzioni).

Stefano Ferrari— Fondamenti di Informatica per la Sicurezza

3

Modulo 4— U.D. 3— Lez. 4

Memoria virtuale La memoria è una risorsa preziosa. Generalmente, si dispone di meno memoria di quanta ne sarebbe necessaria ai processi attivi. La memoria virtuale è una tecnica che consente di ampliare lo spazio di indirizzamente usando una parte della memoria di massa (swap) per coprire la mancanza di memoria centrale. Se un processo richiede più memoria di quanta ne sia disponibile al momento, il gestore della memoria salva i dati di uno dei processi in attesa nell’area di swap, liberando così la memoria da essi occupata.

Stati di un processo con swapping interrupt esterno e carica su disco inizio esecuzione

selezione per esecuzione

oria

em in m arica

c

terminazione pronto

disco pronto

esecuzione

disco a su caric

interrupt esterno

interrupt interno

evento esterno evento esterno

attesa

o

disco attesa

su ica car

c dis

Stefano Ferrari— Fondamenti di Informatica per la Sicurezza

4

Modulo 4— U.D. 3— Lez. 4

Frammentazione Il gestore della memoria assegna la memoria disponibile ai programmi che devono essere eseguiti. Si può verificare una situazione in cui vi è sufficiente memoria disponibile, ma non essendo contigua non può essere utilizzata.

P1

P1

P1

P2

P2

P2

P1

P5 P4

P4

t3

t4

P3

t1

t2

Paginazione Si suddivide la memoria (sia fisica che logica) in blocchi di ugual dimensione (pagine). Ad ogni processo si allocano solo un numero intero di pagine. In questo modo: •

•

si guadagna la possibilità di allocare zone non contigue di memoria; si può attenuare il problema della frammentazione della memoria.

Stefano Ferrari— Fondamenti di Informatica per la Sicurezza

5

Modulo 4— U.D. 3— Lez. 4

Segmentazione La segmentazione è una tecnica basata sulla suddivisione della memoria usata da un programma a secondo il tipo di informazione contenuta: •

segmento codice;

•

segmento dati;

•

segmento pila.

Ogni segmento viene trattato in modo indipendente dal gestore della memoria. Permette la condivisione dello stesso segmento codice da parte di più processi.

In sintesi La memoria è una risorsa costosa. Il gestore della memoria ne ottimizza l’assegnazione ai processi: •

•

•

rendendo trasparente al processo la sua locazione fisica; mantenendo in memoria solo la porzione di dati e di istruzioni necessarie all’esecuzione; evitando la duplicazione di informazioni.

Stefano Ferrari— Fondamenti di Informatica per la Sicurezza

6

Modulo 4— U.D. 3— Lez. 4

Prossimi passi Cenni sulla struttura e sulle funzioni del file system.

Chiusura

Stefano Ferrari— Fondamenti di Informatica per la Sicurezza

7

Modulo 4— U.D. 3— Lez. 5

Lezione 5 - File system Fondamenti di Informatica per la Sicurezza

Modulo 4 - Sistemi di elaborazione

Unità didattica 3 - Cenni di sistemi operativi

Stefano Ferrari Università degli Studi di Milano - Ssri - CDL ONLINE

File system Presenta all’utente e ai programmi una visione semplificata ed omogenea dei dispositivi per la memoria di massa: •

•

attraverso un’organizzazione logica (directory, volumi); mediante operazioni sui dati memorizzati, quali: –

il recupero;

–

la cancellazione;

–

la modifica;

–

la copia.

Stefano Ferrari— Fondamenti di Informatica per la Sicurezza

1

Modulo 4— U.D. 3— Lez. 5

Dati e metadati Oltre ai dati ed i programmi degli utenti, la memoria di massa deve memorizzare anche informazioni che riguardano il file system stesso: •

aree libere o allocate;

•

directory.

Allocazione L’allocazione dello memoria di massa condivide i problemi di allocazione della memoria centrale. Per esempio: •

frammentazione;

•

allocazione contigua (supporti write-once);

•

allocazione a blocchi (supporti riscrivibili).

Stefano Ferrari— Fondamenti di Informatica per la Sicurezza

2

Modulo 4— U.D. 3— Lez. 5

Allocazione a lista concatenata Un file è una concatenazione di blocchi.

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

•

l’accesso al blocco N -esimo richiede l’accesso a N − 1 blocchi; il danneggiamento di un blocco impedisce di recuperare il resto del file.

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

FAT

0

3

5

6

-1

9

0

-1

8

1

2

3

4

5

6

7

8

9

Ogni elemento della mappa contiene uno fra i seguenti valori: •

l’identificatore di blocco vuoto;

•

la posizione del prossimo blocco del file;

•

l’identificatore di ultimo blocco.

Stefano Ferrari— Fondamenti di Informatica per la Sicurezza

3

Modulo 4— U.D. 3— Lez. 5

Svantaggi della FAT L’approccio basato su FAT comporta i seguenti svantaggi: • •

•

per essere efficiente, la FAT deve stare in memoria; l’accesso al blocco N -esimo richiede N accessi in memoria centrale (più uno in memoria di massa); la dimensione della FAT cresce più che linearmente con 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 · 220 elementi.

–

Ciascun elemento richiede almeno 24 bit, quindi la FAT occuperà non meno di 30 MiBi.

Allocazione indicizzata Con l’allocazione indicizzata, ogni file è descritto da un blocco detto blocco indice. Il blocco indice contiene l’elenco dei blocchi che compongono 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 indice di livello inferiore.

Solo i blocchi indice dei file aperti devono stare in memoria.

Stefano Ferrari— Fondamenti di Informatica per la Sicurezza

4

Modulo 4— U.D. 3— Lez. 5

File system di rete I sistemi distribuiti presentano problemi aggiuntivi 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.

Stefano Ferrari— Fondamenti di Informatica per la Sicurezza

5

Modulo 4— U.D. 3— Lez. 5

Approfondimenti Sciuto ed altri, "Introduzione ai sistemi Informatici", McGraw Hill, 1997, seconda edizione: •

architetture: cap. 4 , pagg. 111–180;

•

programmazione: cap. 2, pagg. 17–62;

•

sistema operativo: cap. 5 , pagg. 181–242.

Chiusura

Stefano Ferrari— Fondamenti di Informatica per la Sicurezza

6

Modulo 5— U.D. 1— Lez. 1

Lezione 1 - Teoria computazionale Fondamenti di Informatica per la Sicurezza

Modulo 5 - Elementi di teoria computazionale

Unità didattica 1 - Inquadramento storico-scientifico

Stefano Ferrari Università degli Studi di Milano - Ssri - CDL ONLINE

Aforisma

Computer Science is no more about computers than astronomy is about telescopes.

Edsger Dijkstra

Stefano Ferrari— Fondamenti di Informatica per la Sicurezza

1

Modulo 5— U.D. 1— Lez. 1

Scienza informatica Ogni disciplina scientifica richiede un inquadramento teorico che ne definisca: •

gli scopi;

•

i limiti;

•

le potenzialità.

La nascita dell’informatica risale agli anni ’30. Dagli anni ’40 la tecnologia ha prodotto strumenti 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 particolare strumento di calcolo. I principi dell’informatica saranno validi anche per i calcolatori che soppianterano gli attuali.

Stefano Ferrari— Fondamenti di Informatica per la Sicurezza

2

Modulo 5— U.D. 1— Lez. 1

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 degli insiemi (sui quali è costruito tutto il resto!): –

l’insieme degli insiemi che non hanno se stessi come elemento, ha se stesso come elemento?

Stefano Ferrari— Fondamenti di Informatica per la Sicurezza

3

Modulo 5— U.D. 1— Lez. 1

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 matematica al calcolo automatico di teoremi a partire da assiomi 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.

Stefano Ferrari— Fondamenti di Informatica per la Sicurezza

4

Modulo 5— U.D. 1— Lez. 1

Tesi di Church Tesi di Church-Turing La classe delle funzioni intuitivamente calcolabili coincide con quella delle funzioni calcolabili dalla macchina di Turing. È un’asserzione praticamente indimostrabile! Ciò è dovuto all’impossibilità di formalizzare il concetto di “calcolabilità intuitiva”. È possibile dimostrarne la falsità, però nessuno c’è 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).

Stefano Ferrari— Fondamenti di Informatica per la Sicurezza

5

Modulo 5— U.D. 1— Lez. 1

Calcolabilità e algoritmi Ci sono diversi gradi di calcolabilità: •

funzioni facili da calcolare;

•

funzioni difficili da calcolare;

•

•

funzioni che non si sa come calcolare: ( 1 esistono almeno x “5” in π f (x) = 0 altrimenti funzioni che non si sa se si possono calcolare: ( 1 esistono esattamente x “5” in π g(x) = 0 altrimenti

In sintesi La teoria della computazione dice che: •

•

•

•

•

esistono funzioni definibili matematicamente che non si possono calcolare; esistono diversi formalismi (equivalenti) per la descrizione del calcolo; esistono funzioni calcolabili che non si sanno calcolare; esistono funzioni che non si sa se si possono calcolare; esistono diversi gradi di calcolabilità.

Stefano Ferrari— Fondamenti di Informatica per la Sicurezza

6

Modulo 5— U.D. 1— Lez. 1

Prossimi passi Approfondimento sulla calcolabilità. Elementi della teoria computazionale: •

linguaggi;

•

grammatiche;

•

automi;

•

classi di complessità.

Chiusura

Stefano Ferrari— Fondamenti di Informatica per la Sicurezza

7

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

Lezione 2 - Computabilità Fondamenti di Informatica per la Sicurezza

Modulo 5 - Elementi di teoria computazionale

Unità didattica 1 - Inquadramento storico-scientifico

Stefano Ferrari Università degli Studi di Milano - Ssri - CDL ONLINE

Algoritmi e funzioni Un algoritmo è una sequenza univoca di istruzioni che manipola i dati in ingresso e fornisce i dati in uscita. Come tale, è rappresentabile come una funzione. Non è restrittivo limitare i dati in ingresso e in uscita ai soli numeri naturali. Quindi un algoritmo, A, realizza una funzione su N, fA : N → N.

Stefano Ferrari— Fondamenti di Informatica per la Sicurezza

1

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

Relazione algoritmo-funzione Una funzione f associa ad un valore x un valore f (x). Un algoritmo che calcola f è un metodo per trovare f (x) dato x. È una relazione simile a quella che lega un teorema e una sua dimostrazione: •

•

possono esserci più algoritmi che calcolano la stessa funzione; se non conosciamo un algoritmo di calcolo, non è detto che la funzione non sia calcolabile.

Numerabilità degli algoritmi Gli algoritmi sono composti da una successione finita di istruzioni. Ci sono un numero finito di istruzioni. È quindi possibile assegnare un codice ad ogni algoritmo. Indicheremo con Pn , l’n-esimo algoritmo.

Stefano Ferrari— Fondamenti di Informatica per la Sicurezza

2

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

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 definire matematicamente è calcolabile; serve qualche definizione più formale di ciò che è intuitivamente calcolabile.

Stefano Ferrari— Fondamenti di Informatica per la Sicurezza

3

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

Teoria della computazione La teoria della computazione studia le funzioni astrattamente calcolabili, senza preoccuparsi dell’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 di algoritmo; di indagare le possibilità ed i limiti dei metodi di calcolo effettivi.

Caratteristiche della computazione

(1)

Il processo di calcolo è definito dalle seguenti caratteristiche: 1. un algoritmo è di lunghezza finita; 2. esiste un esecutore che può effettuare le istruzioni dell’algoritmo; 3. il calcolo è deterministico; 4. l’esecuzione avviene per passi discreti; 5. l’esecutore dispone di una memoria ausiliaria per immagazzinare i risultati intermedi dell’elaborazione;

Stefano Ferrari— Fondamenti di Informatica per la Sicurezza

4

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

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 passi finito, ma illimitato; 10. l’esecuzione può non terminare. Nota: la caratteristica 10 dice che una funzione calcolabile può essere non definita per alcuni elementi del dominio.

In sintesi Non tutte le funzioni sono calcolabili. La teoria computazionale studia i limiti dei metodi di calcolo.

Stefano Ferrari— Fondamenti di Informatica per la Sicurezza

5

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

Prossimi passi Elementi della teoria computazionale: •

linguaggi;

•

grammatiche;

•

automi;

•

classi di complessità.

Chiusura

Stefano Ferrari— Fondamenti di Informatica per la Sicurezza

6

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

Lezione 1 - Linguaggi Fondamenti di Informatica per la Sicurezza

Modulo 5 - Elementi di teoria computazionale

Unità didattica 2 - Linguaggi formali

Stefano Ferrari Università degli Studi di Milano - Ssri - CDL ONLINE

Alfabeto Un alfabeto è un insieme finito e non vuoto di simboli. Esempi: •

A = {a, b, c}

•

A = { 0, 1}

Stefano Ferrari— Fondamenti di Informatica per la Sicurezza

1

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

Stringa Una stringa (o parola) è una sequenza finita di simboli. 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 di w;  è prefisso, suffisso e sottostringa di w.

Stefano Ferrari— Fondamenti di Informatica per la Sicurezza

2

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

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 ∪ · · · = ∪i Ai (chiusura di A)

Linguaggio Un linguaggio (formale) L definito su un alfabeto A è un sottoinsieme di A∗ . Una frase di un linguaggio è una stringa appartenente al linguaggio stesso.

Stefano Ferrari— Fondamenti di Informatica per la Sicurezza

3

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

Esempi Esempi: •

•

il linguaggio delle frasi in italiano: –

alfabeto: A = {a, b, . . . , z, <spazio>}

–

stringhe su A: cosa, il porto, ghsde af e 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 possono definire 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 |)

Stefano Ferrari— Fondamenti di Informatica per la Sicurezza

4

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

Operazioni sui linguaggi

(2)

differenza , L1 − L2 : •

L1 − L2 = {w | w ∈ L1 ∧ w 6∈ L2 }

•

|L1 − L2 | ≤ |L1 |

complemento , L: •

Σ∗ − L

•

|L| ≤ ∞

Operazioni sui linguaggi

(3)

concatenazione , L1 L2 : •

L1 L2 = {vw | v ∈ L1 , w ∈ L2 }

•

|L1 L2 | = |L1 | · |L2 |

potenza , Ln : •

L0 = {}

•

L1 = L

•

Lk = {v1 v2 . . . vk | v1 , v2 , . . . , vk ∈ L}

•

|Lk | = |L|k

Stefano Ferrari— Fondamenti di Informatica per la Sicurezza

5

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

Operazioni sui linguaggi

(4)

chiusura (di Kleene) , L∗ : • L∗ = ∪ Li i •

se L = {}, |L∗ | = 1

•

altrimenti, |L∗ | = ∞

chiusura positiva , L+ : •

L+ = ∪i Li , 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.

Stefano Ferrari— Fondamenti di Informatica per la Sicurezza

6

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

Prossimi passi Come definire e classificare i linguaggi: •

grammatiche;

•

automi.

Chiusura

Stefano Ferrari— Fondamenti di Informatica per la Sicurezza

7

Modulo 5— U.D. 2— Lez. 2

Lezione 2 - Grammatiche Fondamenti di Informatica per la Sicurezza

Modulo 5 - Elementi di teoria computazionale

Unità didattica 2 - Linguaggi formali

Stefano Ferrari Università degli Studi di Milano - Ssri - CDL ONLINE

Grammatica Una grammatica (formale) definisce in modo rigoroso un linguaggio su un alfabeto, Σ. Tecnicamente è una quadrupla hΣ, V, P, Si: •

Σ, 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.

Stefano Ferrari— Fondamenti di Informatica per la Sicurezza

1

Modulo 5— U.D. 2— Lez. 2

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 soli simboli terminali. Tutte le frasi del linguaggio si ottengono con questo procedimento.

Esempio Grammatica: hΣ, V, P, Si •

Σ = {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

Stefano Ferrari— Fondamenti di Informatica per la Sicurezza

2

Modulo 5— U.D. 2— Lez. 2

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 hnomei;

•

il meta-simbolo speciale | (pipe) è usato per l’alternativa: –

α ::= β1 , α ::= β2 , . . . , α ::= βn ;

–

α ::= β1 |β2 | . . . |βn .

Su http://www.faqs.org/rfcs/rfc2234.html si trova la definizione di Augmented BNF (ABFN).

Esempio Grammatica: hΣ, V, P, Si –

Σ = {il, gatto, topo, sasso, mangia, beve}

–

V = {hf rasei, hsoggi, harti, hnomei, hverboi, hc_oggi}

–

P ={ hf rasei ::= hsoggihverboihc_oggi hsoggi ::= hartihnomei harti ::= il hnomei ::= gatto|topo|sasso hverboi ::= mangia|beve hc_oggi ::= hartihnomei }

–

S = hf rasei

Stefano Ferrari— Fondamenti di Informatica per la Sicurezza

3

Modulo 5— U.D. 2— Lez. 2

Albero sintattico Esempio: il gatto mangia il sasso S

hf rasei

hsoggi

hc_oggi hverboi

harti

hnomei

il

gatto

mangia

harti

hnomei

il

sasso

In sintesi Una grammatica: •

definisce un insieme di regole per generare un linguaggio;

•

fa uso di metasimboli;

•

fa uso di regole di produzione.

Stefano Ferrari— Fondamenti di Informatica per la Sicurezza

4

Modulo 5— U.D. 2— Lez. 2

Prossimi passi Una classificazione delle grammatiche e dei linguaggi da esse generati.

Chiusura

Stefano Ferrari— Fondamenti di Informatica per la Sicurezza

5

Modulo 5— U.D. 2— Lez. 3

Lezione 3 - Classificazione di Chomsky Fondamenti di Informatica per la Sicurezza

Modulo 5 - Elementi di teoria computazionale

Unità didattica 2 - Linguaggi formali

Stefano Ferrari Università degli Studi di Milano - Ssri - CDL ONLINE

Classificazione di Chomsky È possibile caratterizzare le grammatiche sulla base della forma delle loro regole di produzione: •

Tipo 3 (regolari);

•

Tipo 2 (context-free);

•

Tipo 1 (context-sensitive);

•

Tipo 0 (a struttura di frase).

Stefano Ferrari— Fondamenti di Informatica per la Sicurezza

1

Modulo 5— U.D. 2— Lez. 3

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 ::= F a|a

Il linguaggio generato si dice di tipo 3 (o linguaggio regolare).

Grammatiche di tipo 2 Le grammatiche context-free (libere dal contesto) hanno produzioni della forma:

F ::= α, con F ∈ V e α ∈ (Σ ∪ V )∗ . Esempi: •

F ::= aG|a, G ::= Gb|b|F c

•

F ::= aF c|b

Si dice che il linguaggio è di tipo 2 (o linguaggio libero dal contesto). Tipicamente, i linguaggi di programmazione appartengono a questo tipo.

Stefano Ferrari— Fondamenti di Informatica per la Sicurezza

2

Modulo 5— U.D. 2— Lez. 3

Grammatiche di tipo 1 Le grammatiche context-sensitive (dipendenti dal contesto) hanno produzioni della forma: •

αF β ::= αγβ ,

•

S ::= .

α, β, γ ∈ (Σ ∪ V )∗ , γ 6= , F ∈ V ;

Note: •

•

α e β definiscono il “contesto” in cui la sostituzione F ::= γ può avvenire; per una produzione della prima forma, la lunghezza della stringa generata non può diminuire.

Esempio:

aF b ::= aF bGb

Grammatiche di tipo 0 Le grammatiche di tipo 0 ammettono produzioni di qualsiasi forma: •

α ::= β , con α, β ∈ (Σ ∪ V )∗ . Nota: sono ammesse anche produzioni che possono diminuire la lunghezza della stringa generata.

Stefano Ferrari— Fondamenti di Informatica per la Sicurezza

3

Modulo 5— U.D. 2— Lez. 3

Gerarchia di grammatiche e linguaggi Ogni grammatica di tipo n è anche una grammatica di tipo n − 1. Un linguaggio è di tipo n se esiste una grammatica di tipo n che lo genera, ma non nessuna di tipo n + 1 è in grado di generarlo. Esempi: •

linguaggio di tipo 3: {am bn | m, n ≥ 0}

•

linguaggio di tipo 2: {an bn | n ≥ 0}

•

linguaggio di tipo 1: {an bn cn | n ≥ 0}

•

linguaggio di tipo 0: {an | n è un numero primo}

Grammatiche ambigue Una grammatica si dice ambigua se qualche stringa del linguaggio da essa generato può essere generata mediante più alberi sintattici. Esempio: con la regola F ::= F aF |F bF |f , la generazione della stringa f af bf non è univoca. Infatti: •

F → F aF → f aF → f aF bF → f af bF → f af bf

•

F → F bF → F bf → F aF bf → f aF bf → f af bf

Un linguaggio si dice inerentemente ambiguo se non esiste alcuna grammatica non ambigua che lo generi.

Stefano Ferrari— Fondamenti di Informatica per la Sicurezza

4

Modulo 5— U.D. 2— Lez. 3

In sintesi Le grammatiche sono descrizioni induttive di linguaggi. Secondo la classificazione di Chomsky, esse costituiscono una gerarchia di quattro livelli. Ogni livello: •

•

è caratterizzato da qualche vincolo alle regole di produzione; genera una classe di linguaggi.

Prossimi passi Esercizi su linguaggi e grammatiche.

Stefano Ferrari— Fondamenti di Informatica per la Sicurezza

5

Modulo 5— U.D. 2— Lez. 3

Chiusura

Stefano Ferrari— Fondamenti di Informatica per la Sicurezza

6

Modulo 5— U.D. 2— Lez. 4

Lezione 4 - Esercizi su linguaggi e grammatiche Fondamenti di Informatica per la Sicurezza Modulo 5 - Elementi di teoria computazionale Unità didattica 2 - Linguaggi formali

Stefano Ferrari Università degli Studi di Milano - Ssri - CDL ONLINE

Esercizio 1

(1)

Definiti i linguaggi: •

L1 = {aa, ab, bc, c}

•

L2 = {1, 22, 31}

descrivere i linguaggi: a) L3 = L∗1

d) L6 = L1 ∪ L2

b) L4 = L1 L2

e) L7 = (L1 L2 )∗

c) L5 = L1 L∗2

f) L8 = (L1 ∪ L2 )∗

Stefano Ferrari— Fondamenti di Informatica per la Sicurezza

1

Modulo 5— U.D. 2— Lez. 4

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 = L1 L2 è formato dalla concatenazione di un elemento di L1 con un elemento di L2 .

L4 = {aa1, ab1, bc1, c1, aa22, ab22, bc22, c22, aa31, ab31, bc31, c31} c) L5 = L1 L∗2 è formato dalla concatenazione di un elemento di L1 con un numero arbitrario (anche nullo) 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 = (L1 L2 )∗ è 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, . . . }

Stefano Ferrari— Fondamenti di Informatica per la Sicurezza

2

Modulo 5— U.D. 2— Lez. 4

Esercizio 2

(1)

Data la grammatica G = hΣ, V, P, Si: •

Σ = {a, b}

•

V = {S, A, B}

•

P = {S ::= B|a, B ::= bA|aA, A ::= aB|b}

mostrare la sequenza di regole da applicare per generare le seguenti frasi: a) bb b) aababb c) babaab

Esercizio 2 a) bb

(2)

S ::= B|a, B ::= bA|aA, A ::= aB|b bb S B S ::= B B ::= bA bA bb A ::= b

Stefano Ferrari— Fondamenti di Informatica per la Sicurezza

3

Modulo 5— U.D. 2— Lez. 4

Esercizio 2 b) aababb

(3)

S ::= B|a, B ::= bA|aA, A ::= aB|b aababb S B S ::= B B ::= aA aA A ::= aB aaB B ::= bA aabA A ::= aB aabaB B ::= bA aababA aababb A ::= b

Esercizio 2 c) babaab

(4)

S ::= B|a, B ::= bA|aA, A ::= aB|b babaab S B S ::= B B ::= bA bA A ::= aB baB B ::= bA babA A ::= aB babaB B ::= aA babaaA babaab A ::= b

Stefano Ferrari— Fondamenti di Informatica per la Sicurezza

4

Modulo 5— U.D. 2— Lez. 4

Esercizio 3

(1)

Data la grammatica G = hΣ, V, P, Si: •

Σ = {a, b, c}

•

V = {S, A, B}

•

P = {S ::= A|aA, A ::= Ab|bAB|b, B ::= cB|c}

mostrare la sequenza di regole da applicare per generare le seguenti frasi: a) bbb b) abbcc c) abbbcc

Esercizio 3 a) bbb

(2)

S ::= A|aA, A ::= Ab|bAB|b, B ::= cB|c bbb S A S ::= A A ::= Ab Ab A ::= Ab Abb bbb A ::= b

Stefano Ferrari— Fondamenti di Informatica per la Sicurezza

5

Modulo 5— U.D. 2— Lez. 4

Esercizio 3 b) abbcc

(3)

S ::= A|aA, A ::= Ab|bAB|b, B ::= cB|c abbcc S ::= aA A ::= bAB A ::= b B ::= cB B ::= c

S aA abAB abbB abbcB abbcc

Esercizio 3 c) abbbcc

(4)

S ::= A|aA, A ::= Ab|bAB|b, B ::= cB|c

abbbcc S aA S ::= aA A ::= bAB abAB A ::= bAB abbABB abbbBB A ::= b abbbcB B ::= c abbbcc B ::= c

abbbcc S aA S ::= aA A ::= bAB abAB abAbB A ::= Ab abbbB A ::= b abbbcB B ::= cB abbbcc B ::= c

Ambigua!

Stefano Ferrari— Fondamenti di Informatica per la Sicurezza

6

Modulo 5— U.D. 2— Lez. 4

Esercizio 4

(1)

Data la grammatica G = hΣ, V, P, Si: •

Σ = {a, b, c}

•

V = {S, A, B}

•

P = {S ::= A|aA, A ::= aAb|b|AB, B ::= b|ABa|c}

mostrare la sequenza di regole da applicare per generare le seguenti frasi: a) aabbcbb b) aabbbca

Esercizio 4

(2)

a)

b)

aabbcbb S A S ::= A A ::= aAb aAb A ::= aAb aaAbb A ::= AB aaABbb aaAcbb B ::= c A ::= AB aaABcbb aabBcbb A ::= b aabbcbb B ::= b

aabbbca S aA S ::= aA aAB A ::= AB B ::= ABa aAABa aAAca B ::= c aAbca A ::= b A ::= aAb aaAbbca aabbbca A ::= b

Stefano Ferrari— Fondamenti di Informatica per la Sicurezza

7

Modulo 5— U.D. 2— Lez. 4

In sintesi La descrizione insiemistica di linguaggi. Le grammatiche come descrizione generativa di linguaggi: •

sequenze di regole di produzione per la generazione di 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.

Stefano Ferrari— Fondamenti di Informatica per la Sicurezza

8

Modulo 5— U.D. 2— Lez. 4

Chiusura

Stefano Ferrari— Fondamenti di Informatica per la Sicurezza

9

Modulo 5— U.D. 3— Lez. 1

Lezione 1 - Automi a stati finiti Fondamenti di Informatica per la Sicurezza

Modulo 5 - Elementi di teoria computazionale

Unità didattica 3 - Automi

Stefano Ferrari Università degli Studi di Milano - Ssri - CDL ONLINE

Automa a stati finiti

(1)

Un automa a stati finiti è un modello matematico caratterizzato da: •

un input costituito da una sequenza di elementi discreti;

•

eventualmente, un output (anch’esso a valori discreti);

•

un insieme finito di stati nei quali l’automa può trovarsi durante l’esecuzione.

Stefano Ferrari— Fondamenti di Informatica per la Sicurezza

1

Modulo 5— U.D. 3— Lez. 1

Automa a stati finiti

(2)

Un automa a stati finiti si può immaginare come un dispositivo dotato di una testina. L’automa legge spostandosi sempre nella stessa direzione lungo un nastro di lunghezza illimitata contenente dei simboli. A seconda del simbolo letto, l’automa si porta in un altro stato. Ripete queste operazioni fino a quando non legge un simbolo terminale.

Definizione formale Un automa a stati finiti deterministico (DFA) è una quintupla hQ, Σ, δ, q0 , F i 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.

Stefano Ferrari— Fondamenti di Informatica per la Sicurezza

2

Modulo 5— U.D. 3— Lez. 1

Funzione di transizione La funzione di transizione può essere rappresentata in forma tabellare. Esempio:

δ q0 q1 q2 q3

a q0 q1 q3 q0

b q0 q3 q2 q1

c q2 q1 q2 q1

d q1 q1 q0 q0

e q1 q1 q1 q1

dove: •

Q = {q0 , q1 , q2 , q3 }

•

Σ = {a, b, c, d, e}

Rappresentazione grafica Un DFA può essere rappresentato da un grafo: a, c, d, e

a, b d, e q0

q1 c

dove: b

•

Q = {q0 , q1 , q2 , q3 }

•

Σ = {a, b, c, d, e}

•

F = {q1 }

e

a, d b, c, e

q3

a

d q2 b, c

Stefano Ferrari— Fondamenti di Informatica per la Sicurezza

3

Modulo 5— U.D. 3— Lez. 1

Linguaggio accettato da un DFA

(1)

Il concetto di funzione di transizione può essere estesa in modo da essere applicata ripetutamente ad una successione di simboli in input. Si dice che un DFA accetta una stringa se, dopo averla letta, esso si ritrova in uno stato finale. L’insieme delle stringhe accettate da un DFA viene detto linguaggio accettato dal DFA stesso.

Linguaggio accettato da un DFA

(2)

Più formalmente: •

•

•

l’estensione di δ alle stringhe, δˆ : Q × Σ∗ → Q, si definisce in modo univoco come: ( se x =  q ˆ δ(q, x) = ˆ δ(δ(q, w), y) se x = wy, w ∈ Σ∗ , y ∈ Σ una stringa x viene accettata dal DFA ˆ 0 , x) ∈ F ; M = hQ, Σ, δ, q0 , F i se δ(q

ˆ 0 , x) ∈ F } è il il linguaggio L(M ) = {x ∈ Σ∗ | δ(q linguaggio accettato da M .

Stefano Ferrari— Fondamenti di Informatica per la Sicurezza

4

Modulo 5— U.D. 3— Lez. 1

Automa non-deterministico Un automa a stati finiti non-deterministico (NFA) è una quintupla hQ, Σ, δ, q0 , F i 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 qualche q ∈ Q e a ∈ Σ.

Linguaggio accettato da un NFA Dalla funzione δ si definisce in modo univoco δˆ : Q × Σ∗ → ℘(Q):

 {q} S ˆ x) = δ(q,  ˆ

δ(p, y)

se x =  se x = wy, w ∈ Σ∗ , y ∈ Σ

p∈δ(q, w)

Una stringa x viene accettata dal NFA ˆ 0 , x) ∩ F 6= ∅. M = hQ, Σ, δ, q0 , F i se δ(q

ˆ 0 , x) ∩ F 6= ∅} è il Il linguaggio L(M ) = {x ∈ Σ∗ | δ(q linguaggio accettato da M .

Stefano Ferrari— Fondamenti di Informatica per la Sicurezza

5

Modulo 5— U.D. 3— Lez. 1

Confronto DFA-NFA La “potenza di calcolo” di un NFA è la stessa di un DFA. Ciò significa che per ogni linguaggio accettato da un NFA, esiste un DFA che accetta lo stesso linguaggio. La classe di linguaggi accettati dai DFA è la classe dei linguaggi regolari. Si può generare in modo automatico il DFA equivalente di un dato NFA. A volte è più comodo progettare un NFA e poi convertirlo.

Limiti dei DFA Un DFA è un dispositivo a memoria finita, quindi è adatto a risolvere solo quei problemi che consentono di limitare a priori la lunghezza delle sequenze d’ingresso di cui tenere memoria. Da cosa deriva la mancanza di espressività? •

Il numero di stati è fissato a priori non consente di trattare quei problemi che richiedono un conteggio senza limite fissato. –

•

Esempio: un DFA a 4 stati può riconoscere aaacbbb ma non aaaacbbbb.

Rendere il numero degli stati infinito non è praticabile.

Stefano Ferrari— Fondamenti di Informatica per la Sicurezza

6

Modulo 5— U.D. 3— Lez. 1

In sintesi Un automa a stati finiti è un modello di calcolo che permette di effettuare semplici elaborazioni su una stringa di simboli data di ingresso. L’elaborazione più semplice è il riconoscimento di una stringa come appartenente ad un dato linguaggio. Esistono varianti del DFA, ma tutte hanno la stessa espressività.

Prossimi passi Esercizi sui DFA. Modelli di calcolo più potenti.

Stefano Ferrari— Fondamenti di Informatica per la Sicurezza

7

Modulo 5— U.D. 3— Lez. 1

Chiusura

Stefano Ferrari— Fondamenti di Informatica per la Sicurezza

8

Modulo 5— U.D. 3— Lez. 2

Lezione 2 - Esercizi sugli automi a stati finiti Fondamenti di Informatica per la Sicurezza

Modulo 5 - Elementi di teoria computazionale

Unità didattica 3 - Automi

Stefano Ferrari Università degli Studi di Milano - Ssri - CDL ONLINE

Esercizio 1

(1)

Costruire un DFA su Σ = {0, 1} che accetti l’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”.

Stefano Ferrari— Fondamenti di Informatica per la Sicurezza

1

Modulo 5— U.D. 3— Lez. 2

Esercizio 1

(2)

Indicando con qi lo stato in cui l’automa si troverà dopo aver letto i simboli “0” consecutivi: •

situazione (a) ↔ q3 ;

•

situazione (c) ↔ q1 ;

•

situazione (b) ↔ q2 ;

•

situazione (d) ↔ q0 ;

Note: •

dopo aver letto tre “0”, l’automa accetterà la stringa qualunque 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 La funzione di transizione può essere:

δ q0 q1 q2 q3

0 q1 q2 q3 q3

(3)

1 q0 q0 q0 q3

e il grafico: 0, 1

1 0 q0

0 q1

0 q2

q3

1 1

Stefano Ferrari— Fondamenti di Informatica per la Sicurezza

2

Modulo 5— U.D. 3— Lez. 2

Esercizio 2

(1)

Costruire un DFA su Σ = {0, 1} che accetti l’insieme di tutte le stringhe che se interpretate in notazione binaria risultino divisibili per 2. Osservazioni: •

l’alfabeto è dato (Σ = {0, 1});

•

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 accetta solo le stringhe binarie che terminano per 0.

Esercizio 2

(2)

Se, banalmente, indichiamo con qi lo stato in cui viene a trovarsi l’automa dopo aver letto il simbolo i: •

•

ponendo q0 come unico stato finale facciamo sì che l’automa accetti la stringa solo se l’ultimo simbolo che ha letto è stato 0; ponendo q1 come stato iniziale evitiamo che venga accettata la stringa vuota.

Stefano Ferrari— Fondamenti di Informatica per la Sicurezza

3

Modulo 5— U.D. 3— Lez. 2

Esercizio 2

(3)

Quindi, l’automa può essere formalizzato come: •

•

Q = {q0 , q1 }

•

Σ = {0, 1}

•

q1 è lo stato iniziale

•

F = {q0 } δ q0 q1

0 q0 q0

1 q1 q1 0

1 0 q1

q0 1

Esercizio 3

(1)

Costruire un DFA su Σ = {0, 1} che accetti l’insieme di tutte le stringhe che hanno come penultimo simbolo “0”. Osservazioni: • •

•

l’alfabeto è dato (Σ = {0, 1}); abbiamo bisogno di una finestra di due simboli (gli ultimi due simboli letti); consideriamo quindi quattro situazioni: 00, 01, 10 e 11.

Stefano Ferrari— Fondamenti di Informatica per la Sicurezza

4

Modulo 5— U.D. 3— Lez. 2

Esercizio 3

(2)

Ad esempio, se l’automa si trova nello stato 01 e legge “1”, si deve portare nello stato corrispondente a 11. Con questa regola: • •

•

le situazioni accettate saranno 00 e 01; scegliendo 11 come situazione iniziale, evitiamo di accettare stringhe con meno di due caratteri; codifichiamo con lo stato qi la situazione in cui gli ultimi due simboli letti sono interpretati come la rappresentazione 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 }

•

δ q0 q1 q2 q3

0 q0 q2 q0 q2

1 q1 q3 q1 q3

Stefano Ferrari— Fondamenti di Informatica per la Sicurezza

5

Modulo 5— U.D. 3— Lez. 2

In sintesi Progettazione di automi su stringhe binarie con semplici regole di accettazione. Altri esercizi: •

regole più complesse: –

•

alfabeti più estesi: –

•

accettare le stringhe binarie divisibili per 3;

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.

Stefano Ferrari— Fondamenti di Informatica per la Sicurezza

6

Modulo 5— U.D. 3— Lez. 2

Chiusura

Stefano Ferrari— Fondamenti di Informatica per la Sicurezza

7

Modulo 5— U.D. 3— Lez. 3

Lezione 3 - Altri modelli di calcolo Fondamenti di Informatica per la Sicurezza

Modulo 5 - Elementi di teoria computazionale

Unità didattica 3 - Automi

Stefano Ferrari Università degli Studi di Milano - Ssri - CDL ONLINE

Automa a pila

(1)

Un automa a pila è una macchina ideale che estende le possibilità degli automi a stati finiti. Si tratta di un automa a stati finiti dotato di una struttura dati aggiuntiva per la memorizzazione delle informazioni, la pila: •

struttura dati di tipo Last In First Out (LIFO).

Stefano Ferrari— Fondamenti di Informatica per la Sicurezza

1

Modulo 5— U.D. 3— Lez. 3

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 pila contemporaneamente. Ogni passo di esecuzione comporta: •

la lettura di un simbolo da nastro e l’avanzamento della 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).

Stefano Ferrari— Fondamenti di Informatica per la Sicurezza

2

Modulo 5— U.D. 3— Lez. 3

Stringhe accettate dall’automa a pila L’automa ha due possibili condizioni per l’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 ne può costruire uno che termina per stato finale.

Linguaggi accettati dall’automa a pila Il non-determinismo, aggiunge potenza espressiva all’automa a pila. L’automa a pila deterministico riconosce un sottoinsieme dei linguaggi context-free (tipo 2). L’automa a pila non-deterministico riconosce i linguaggi context-free. Per esempio: •

•

un automa a pila riesce a riconoscere le parentesi ben accoppiate (an bn ); solo un automa non-deterministico riesce a riconoscere le stringhe palindrome.

Stefano Ferrari— Fondamenti di Informatica per la Sicurezza

3

Modulo 5— U.D. 3— Lez. 3

Limiti degli automa a pila Da cosa deriva la mancanza di espressività? •

la struttura dati di supporto, la pila, ha un accesso limitato, che si limita alla testa della pila; –

come accedere al primo degli elementi inseriti?

Per poter riconoscere linguaggi di tipo 1 o 0 bisogna disporre di una struttura dati più flessibile.

Macchina di Turing Macchina ideale pensata da Alan Turing negli anni ’30 per formalizzare la nozione di agente di calcolo (computer). Una macchina di Turing (MdT) è composta da: •

•

nastro: infinito, abilitato alla lettura ed alla scrittura; controllo: automa a stati finiti deterministico.

Stefano Ferrari— Fondamenti di Informatica per la Sicurezza

4

Modulo 5— U.D. 3— Lez. 3

Funzionamento della MdT Ad ogni passo di computazione, una MdT: •

•

legge il simbolo sul nastro in corrispondenza della testina; 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 coppia stato-simbolo.

Varianti della MdT Esistono diverse varianti della MdT deterministica. Ad esempio: •

multinastro;

•

multitestina;

•

nastro semi-infinito;

•

non-deterministica.

Si può dimostrare che per ognuna di queste varianti si può costruire una MdT deterministica equivalente.

Stefano Ferrari— Fondamenti di Informatica per la Sicurezza

5

Modulo 5— U.D. 3— Lez. 3

MdT universale È possibile costruire una MdT che simuli una qualsiasi 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 parte di controllo); il suo input.

Linguaggi accettati Una MdT riconosce i linguaggi di tipo 0. Una MdT non deterministica con lunghezza del nastro limitata in modo proporzionale alla lunghezza dell’input riconosce i linguaggi di tipo 1.

Stefano Ferrari— Fondamenti di Informatica per la Sicurezza

6

Modulo 5— U.D. 3— Lez. 3

In sintesi Gli automi a pila e la MdT sono potenziamenti degli automi a stati finiti. Gli automi a pila non-deterministici sono abbastanza potenti da riconoscere i linguaggi context free. La macchina di Turing non-deterministica con nastro limitato è in grado di riconoscere i linguaggi dipendenti dal contesto. La macchina di Turing è in grado di riconoscere i linguaggi di tipo 0.

Prossimi passi Qualche osservazione aggiuntiva su linguaggi, grammatiche e computabilità. Approfondimento sui linguaggi regolari: espressioni regolari.

Stefano Ferrari— Fondamenti di Informatica per la Sicurezza

7

Modulo 5— U.D. 3— Lez. 3

Chiusura

Stefano Ferrari— Fondamenti di Informatica per la Sicurezza

8

Modulo 5— U.D. 3— Lez. 4

Lezione 4 - Linguaggi e computabilità Fondamenti di Informatica per la Sicurezza

Modulo 5 - Elementi di teoria computazionale

Unità didattica 3 - Automi

Stefano Ferrari Università degli Studi di Milano - Ssri - CDL ONLINE

Caratteristiche della MdT

(1)

La MdT è stata ideata per modellare il processo di calcolo. Infatti, ha le seguenti caratteristiche: 1. il controllo è costituito da un numero finito di istruzioni; –

un algoritmo è di lunghezza finita;

2. la MdT è l’agente di calcolo che esegue l’elaborazione; –

esiste un esecutore che può effettuare le istruzioni dell’algoritmo;

3. il controllo è affidato ad un automa deterministico; –

il calcolo è deterministico;

Stefano Ferrari— Fondamenti di Informatica per la Sicurezza

1

Modulo 5— U.D. 3— Lez. 4

Caratteristiche della MdT

(2)

4. la MdT opera per passi discreti; –

l’esecuzione avviene per passi discreti;

5. il nastro è un dispositivo di memorizzazione per l’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;

Caratteristiche della MdT

(3)

8. le istruzioni che la MdT può eseguire ad ogni passo sono semplici e ben definite; –

le istruzioni hanno una complessità finita;

9. non esiste nessuna limitazione al numero di passi di calcolo; –

l’esecuzione termina dopo un numero di passi finito, ma illimitato;

10. è possibile creare una MdT che continua ad eseguire delle istruzioni senza terminare mai; –

l’esecuzione può non terminare.

Stefano Ferrari— Fondamenti di Informatica per la Sicurezza

2

Modulo 5— U.D. 3— Lez. 4

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 possono essere modificati per effettuare dei calcoli (cioè generare un output).

Terminazione La computazione di un automa a stati finiti o a pila termina sempre. La computazione di una MdT per un certo dato di input può non terminare. È l’equivalente algoritmico di una funzione non definita per un dato argomento (funzione parziale).

Stefano Ferrari— Fondamenti di Informatica per la Sicurezza

3

Modulo 5— U.D. 3— Lez. 4

Linguaggi, grammatiche, automi

(1)

Le grammatiche danno una descrizione generativa 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 di riconoscimento della stringa come appartenente al linguaggio. La MdT ha la potenza computazionale necessaria e sufficiente per l’accettazione dei linguaggi di tipo 0: •

•

se G è una grammatica di tipo 0 e L = L(G) è il linguaggio 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 che L = L(G).

Stefano Ferrari— Fondamenti di Informatica per la Sicurezza

4

Modulo 5— U.D. 3— Lez. 4

Linguaggi e computabilità Restringere lo studio della computabilità ai linguaggi non è restrittivo. Inoltre, lo studio dei vari tipi di linguaggi è utile perché 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 una ulteriore distinzione: •

un linguaggio viene detto accettabile (o riconoscibile) da un automa se esso è in grado di accettare tutte le sue parole; –

•

nulla viene richiesto se la parola in input non appartiene al linguaggio dato;

un linguaggio viene detto decidibile da un automa se esso è in grado di accettare tutte le sue parole e di rifiutare tutte le altre parole.

In altri termini, se un linguaggio è decidibile, lo deve essere anche il suo complemento.

Stefano Ferrari— Fondamenti di Informatica per la Sicurezza

5

Modulo 5— U.D. 3— Lez. 4

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 non sono di tipo 1. Ogni definizione finita della decidibilità non può comprendere tutti gli insiemi decidibili.

In sintesi Lo studio dei linguaggi non è riduttivo nel contesto 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, ma non decidibili.

Stefano Ferrari— Fondamenti di Informatica per la Sicurezza

6

Modulo 5— U.D. 3— Lez. 4

Prossimi passi Dalla calcolabilità alla complessità.

Chiusura

Stefano Ferrari— Fondamenti di Informatica per la Sicurezza

7

Modulo 5— U.D. 3— Lez. 5

Lezione 5 - Decidibilità e complessità Fondamenti di Informatica per la Sicurezza

Modulo 5 - Elementi di teoria computazionale

Unità didattica 3 - Automi

Stefano Ferrari Università degli Studi di Milano - Ssri - CDL ONLINE

Problemi indecidibili

(1)

È noto un certo insieme di problemi non decidibili: •

•

•

halting problem: non esiste alcuna MdT, MH , che, data la descrizione di una MdT, M , e una stringa di input, w, decida se la computazione M (w) termina, oppure no; non esiste nessuna MdT, ME , che, data la descrizione di una MdT, M , possa decidere se il linguaggio riconosciuto da M , L(M ), sia vuoto, oppure no; non esiste alcuna MdT, MR , che, data la descrizione di una MdT, M , decida se il linguaggio da essa riconosciuto, L(M ), sia di un tipo dato;

Stefano Ferrari— Fondamenti di Informatica per la Sicurezza

1

Modulo 5— U.D. 3— Lez. 5

Problemi indecidibili

(2)

Anche nella pratica si incontrano problemi indecidibili: •

•

un programma chiamerà una sua procedura nel corso dell’esecuzione per un dato input? una variabile assumerà un dato valore durante l’esecuzione? –

•

•

uscirà dal ciclo?

un dato programma, in presenza di un dato input, fornirà un particolare output? due programmi dati calcolano la stessa funzione?

Problemi indecidibili •

un programma calcola una funzione costante? –

•

•

•

il suo output è indipendente dall’input?

un programma calcola una funzione totale? –

•

(3)

termina per ogni input?

un programma calcola una funzione positiva? una data formula del calcolo dei predicati è un teorema? una data formula dell’aritmetica, è un teorema?

Stefano Ferrari— Fondamenti di Informatica per la Sicurezza

2

Modulo 5— U.D. 3— Lez. 5

Limite del calcolo La MdT rappresenta il limite per i dispositivi finiti. Non è l’unico paradigma del genere, ma tutti gli altri si sono dimostrati equivalenti. La dimostrazione dell’indecidibilità di alcuni problemi equivale infatti al teorema di Gödel. Tuttavia, tra la maggior parte dei problemi pratici 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 conto dell’efficienza: ogni computazione è istantanea perché ogni passo di computazione è tale. La teoria della complessità studia le risorse computazionali necessarie per l’esecuzione di un algoritmo.

Stefano Ferrari— Fondamenti di Informatica per la Sicurezza

3

Modulo 5— U.D. 3— Lez. 5

Complessità La complessità di un algoritmo è definibile principalmente in due modi: •

•

come il numero di operazioni che esso deve fare per giungere alla soluzione (complessità temporale); come il numero di celle di memoria necessarie per il calcolo (complessità spaziale).

È evidente che in entrambi i casi la misura della complessità 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 di complessità temporale: •

•

la complessità spaziale non può superare quella temporale; nella pratica, generalmente lo spazio è una risorsa meno preziosa del tempo; –

però, per esempio, a volte è utile usare la compressione dei dati!

Stefano Ferrari— Fondamenti di Informatica per la Sicurezza

4

Modulo 5— U.D. 3— Lez. 5

Misura di complessità La complessità viene misurata con la notazione O(·), in relazione alla dimensione dei dati iniziali. Tale notazione indica il comportamento asintottico rispetto alla dimensione dell’input. Per esempio, se gli algoritmi A1 , A2 e A3 sono, rispettivamente, O(n), O(n2 ) e O(2n ), sono di complessità, lineare, quadratica ed esponenziale. Perciò, se per elaborare una lista di 10 nomi impiegano tutti 1 s, dobbiamo aspettarci che per 30 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(k n ) al progresso; b. l’invarianza delle classi rispetto ai differenti paradigmi di calcolo.

Stefano Ferrari— Fondamenti di Informatica per la Sicurezza

5

Modulo 5— U.D. 3— Lez. 5

Problemi intrattabili a. A fronte di un progresso tecnologico che renda i calcolatori 1000 volte più veloci, le nuove dimensioni dei problemi risolubili in 1 s dagli algoritmi 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 un paradigma di calcolo equivalente è polinomiale. Anche cambiando il paradigma di riferimento la trattabilità di un algoritmo non può cambiare.

Problemi P e N P La trattabilità dei problemi si formalizza con le classi di problemi P e N P : •

•

P : classe dei problemi risolvibili in tempo polinomiale da una MdT deterministica; N P : classe dei problemi risolvibili in tempo polinomiale da una MdT non-deterministica.

Stefano Ferrari— Fondamenti di Informatica per la Sicurezza

6

Modulo 5— U.D. 3— Lez. 5

P vs NP problem Uno dei problemi aperti dell’informatica è:

P 6= N P ? È uno dei sette Millennium Problems posti dal Clay Mathematics Institute (USA): •

un premio da un milione di dollari a chi lo risolve;

•

http://www.claymath.org/millennium/

Esistono problemi detti N P -completi a cui possono essere ricondotti gli altri problemi N P .

Dimostrare che un problema N P -completo è in P implicherebbe P = N P .

In sintesi I problemi si dividono in: •

indecidibili;

•

intrattabili;

•

trattabili.

Stefano Ferrari— Fondamenti di Informatica per la Sicurezza

7

Modulo 5— U.D. 3— Lez. 5

Prossimi passi Le espressioni regolari.

Chiusura

Stefano Ferrari— Fondamenti di Informatica per la Sicurezza

8

Modulo 5— U.D. 4— Lez. 1

Lezione 1 - Espressioni regolari Fondamenti di Informatica per la Sicurezza

Modulo 5 - Elementi di teoria computazionale

Unità didattica 4 - Espressioni regolari

Stefano Ferrari Università degli Studi di Milano - Ssri - CDL ONLINE

Espressioni regolari Le espressioni regolari (ER) sono un metodo alternativo per descrivere i linguaggi regolari. L’insieme delle ER descrive quindi la stessa classe di linguaggi delle grammatiche regolari e degli automi a stati finiti. Esse presentano i seguenti vantaggi: •

offrono una notazione compatta;

•

sono facilmente intelleggibili;

•

offrono una descrizione di tipo costruttivo/operazionale.

Stefano Ferrari— Fondamenti di Informatica per la Sicurezza

1

Modulo 5— U.D. 4— Lez. 1

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 da essa descritto, Σ; un insieme di metasimboli usati per indicare le operazioni sui linguaggi,{∅, +, ∗ , (, )}.

Sintassi e semantica delle ER L’insieme delle stringhe denotate da una ER è definito ricorsivamente come: espressione regolare

insieme descritto

∅

∅



{}

a

{a}

(r + s) (rs)

R∪S RS

(r ∗ )

R∗

note

a∈Σ r e s sono ER che denotano rispettivamente gli insiemi R e S

Stefano Ferrari— Fondamenti di Informatica per la Sicurezza

2

Modulo 5— U.D. 4— Lez. 1

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 terminata con 0.

Esempio 2 L’ER (0 + 1)∗ 111(0 + 1)∗ indica le stringhe binarie che 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.

Stefano Ferrari— Fondamenti di Informatica per la Sicurezza

3

Modulo 5— U.D. 4— Lez. 1

Esempio 3 L’ER ((0 + 1)2 )∗ (0 + 1) indica le stringhe binarie di lunghezza dispari. Infatti: •

•

•

(0 + 1)2 è una qualsiasi stringa binaria di lunghezza 2; ((0 + 1)2 )∗ è una qualsiasi stringa binaria di lunghezza pari; ((0 + 1)2 )∗ (0 + 1) è una qualsiasi stringa binaria di lunghezza dispari.

L’ER data descrive anche le stringhe di lunghezza 1.

Estensioni La sintassi ER può essere arricchita: ER

insieme descritto

(r + ) (r?)

R+ = R∗ − {} R ∪ {}

note

r denota l’insieme R

Inoltre, a seconda delle situazioni d’uso: •

• •

metasimboli per l’indicazione di Σ o di suoi sottoinsiemi; altri operatori (complemento, sottoespressioni); eliminazione di parentesi superflue (regole di precedenza, associatività di alcune operazioni).

Stefano Ferrari— Fondamenti di Informatica per la Sicurezza

4

Modulo 5— U.D. 4— Lez. 1

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 a grammatiche e automi; vengono usate in molteplici ambienti.

Stefano Ferrari— Fondamenti di Informatica per la Sicurezza

5

Modulo 5— U.D. 4— Lez. 1

Prossimi passi Utilizzo di espressioni regolari: •

esercizi;

•

esempi d’uso pratico.

Chiusura

Stefano Ferrari— Fondamenti di Informatica per la Sicurezza

6

Modulo 5— U.D. 4— Lez. 2

Lezione 2 - Esercizi sulle espressioni regolari Fondamenti di Informatica per la Sicurezza Modulo 5 - Elementi di teoria computazionale Unità didattica 4 - Espressioni regolari

Stefano Ferrari Università degli Studi di Milano - Ssri - CDL ONLINE

Esercizio 1

(1)

Scrivere una espressione regolare (ER) per stringhe binarie che descriva tutte le stringhe che contengono almeno tre 1. Soluzione L’ER richiesta può essere descritta discorsivamente come una stringa che ha tre simboli 1: •

intervallati da una qualsiasi stringa binaria;

•

preceduti da una qualsiasi stringa binaria;

•

seguiti da una qualsiasi stringa binaria.

Stefano Ferrari— Fondamenti di Informatica per la Sicurezza

1

Modulo 5— U.D. 4— Lez. 2

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: alcuni simboli delle generiche stringhe binarie intercalanti 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 .

Stefano Ferrari— Fondamenti di Informatica per la Sicurezza

2

Modulo 5— U.D. 4— Lez. 2

Esercizio 2

(1)

Scrivere una espressione regolare per stringhe di testo che descriva le date in formato GG/MM/AAAA. Soluzione Per comodità, definiamo l’insieme delle cifre decimali:

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 essere espressa come: D 2 /D 2 /D 4 Nota: Oltre alle date, l’ER data descrive anche stringhe che non hanno significato, se interpretate come date. Per esempio, 00/00/0000 o 62/91/3456. È possibile costruire una ER che descriva tutte e sole le date significative, ma non è semplice. Tale ER dovrebbe incorporare tutte le regole per il numero di giorni per mese e per gli anni bisestili.

Stefano Ferrari— Fondamenti di Informatica per la Sicurezza

3

Modulo 5— U.D. 4— Lez. 2

Esercizio 3

(1)

Scrivere una espressione regolare per i numeri telefonici italiani di sei o otto cifre, che comprenda 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 e definiamo S = {“ ”} e P = {“+”}.

Esercizio 3

(2)

Il prefisso internazionale può essere in due forme: •

02 39

•

P 39

Il prefisso urbano può essere costituito da una a tre cifre, precedute da 0: •

0(D + D 2 + D 3 )

Infine, il numero può essere composto da tre o da quattro coppie di decimali, separate da uno spazio: •

((D 2 S)2 + (D 2 S)3 )D 2

Stefano Ferrari— Fondamenti di Informatica per la Sicurezza

4

Modulo 5— U.D. 4— Lez. 2

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:

(02 39+P 39+)S0(D +D 2 +D 3 )S((D 2 S)2 +(D 2 S)3 )D 2

Esercizio 4

(1)

Sia data l’espressione regolare su Σ = {a, b, c}:

E = (a∗ b2 )∗ (b + abc∗ )∗ Quali fra le seguenti stringhe vengono descritte da E ? a) aabc

d) bac

b) bb

e) abbabbbabc

c) abc

Stefano Ferrari— Fondamenti di Informatica per la Sicurezza

5

Modulo 5— U.D. 4— Lez. 2

Esercizio 4

(2)

Soluzione Si può notare che E = E1 E2 , dove E1 = (a∗ b2 )∗ e E2 = (b + abc∗ )∗ . a) aabc

aabc non può essere descritta da E perché: • la c finale potrebbe essere generata solo da E , 2 ma può esserlo solo se preceduta da ab; •

la sottostringa abc potrebbe essere descritta da E2 , ma in nessun modo la singola a potrebbe essere ricavata.

Esercizio 4

(3)

b) bb L’espressione regolare bb può essere coinvolta nella catena di inclusioni:

bb = b2 ⊂ a∗ b2 ⊂ (a∗ b2 )∗ ⊂ (a∗ b2 )∗ (b + abc∗ )∗ c) abc L’espressione regolare abc può essere coinvolta nella catena di inclusioni:

abc ⊂ abc∗ ⊂ b + abc∗ ⊂ (b + abc∗ )∗ ⊂ (a∗ b2 )∗ (b + abc∗ )∗

Stefano Ferrari— Fondamenti di Informatica per la Sicurezza

6

Modulo 5— U.D. 4— Lez. 2

Esercizio 4

(4)

d) bac

bac non può essere descritta da E perché la c finale potrebbe essere generata solo da E2 , ma può esserlo solo se preceduta da ab. e) abbabbbabc L’espressione regolare abbabbbabc può essere coinvolta 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 le seguenti stringhe: •

bbccaaa

•

bbcca

•

bbb

•

bbbaa

ma non le seguenti: •

bbcbac

•

cbbaa

•

bbcabc

•

abbcab

Stefano Ferrari— Fondamenti di Informatica per la Sicurezza

7

Modulo 5— U.D. 4— Lez. 2

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 sono tutte 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 descritte dall’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∗ .

Stefano Ferrari— Fondamenti di Informatica per la Sicurezza

8

Modulo 5— U.D. 4— Lez. 2

Esercizio 5

(4)

Nessuna delle stringhe del secondo gruppo viene descritta da b∗ c∗ a∗ : •

•

bbcbac: ha una c che inframezza la potenziale sequenza di b; bbcabc: dopo la sequenza bbca iniziale (che verrebbe descritta dall’espressione regolare considerata) inizia una 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 espressioni regolari.

Stefano Ferrari— Fondamenti di Informatica per la Sicurezza

9

Modulo 5— U.D. 4— Lez. 2

Chiusura

Stefano Ferrari— Fondamenti di Informatica per la Sicurezza

10

Modulo 5— U.D. 4— Lez. 3

Lezione 3 - Uso di espressioni regolari Fondamenti di Informatica per la Sicurezza

Modulo 5 - Elementi di teoria computazionale

Unità didattica 4 - Espressioni regolari

Stefano Ferrari Università degli Studi di Milano - Ssri - CDL ONLINE

Pattern matching Le espressioni regolari (ER) sono lo strumento ideale per le operazioni di pattern matching (corrispondenza al modello) su informazioni testuali. L’ER descrive un modello e i programmi cercano nei dati le stringhe che corrispondono a tale modello. Esempi: •

analisi di log;

•

sostituzione di stringhe di testo;

•

ricerca in database.

Stefano Ferrari— Fondamenti di Informatica per la Sicurezza

1

Modulo 5— U.D. 4— Lez. 3

Motivazioni Le espressioni regolari (ER) permettono di specificare un insieme di stringhe in modo: •

compatto: –

•

simile all’oggetto descritto: –

•

ripetizioni, alternative; 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: –

•

shell: –

•

apache, procmail, majordomo;

programmi di utilità: –

•

DOS, bash;

file di configurazione: –

•

C, Java, PHP, Python, Perl;

sed, awk, grep;

programmi avanzati di elaborazione testi: –

vi, emacs.

Stefano Ferrari— Fondamenti di Informatica per la Sicurezza

2

Modulo 5— U.D. 4— Lez. 3

Espressioni regolari standard Non esiste uno standard, ma molte convenzioni sono condivise. IEEE POSIX 1003.2 definisce: •

basic regular expression (BRE);

•

extended regular expression (ERE). Nota: POSIX sta per Portable Operating System Interface.

Faremo riferimento principalmente alla notazione ERE.

Metasimboli In un file di testo possono essere utilizzati tutti i caratteri consentiti dalla codifica. L’alfabeto delle ER è composto dall’alfabeto delle stringhe da specificare e da metasimboli. Le ER sono specificate tramite caratteri di testo. Questo comporta che alcuni simboli devono essere realizzati tramite una coppia di caratteri consecutivi: le sequenze di escape. Esempio: “\*” può significare “*”.

Stefano Ferrari— Fondamenti di Informatica per la Sicurezza

3

Modulo 5— U.D. 4— Lez. 3

Operazioni di base Gli operatori di base delle ER si traducono: •

potenza: la ripetizione di una sottoespressione si indica con il numero di ripetizioni fra parentesi graffe; –

•

chiusura: analogamente, la chiusura viene indicata con l’asterisco; –

•

esempio: ab* corrisponde all’ER ab∗ ;

sottoespressioni: le sottoespressioni si delimitano con le parentesi tonde; –

•

esempio: ab{3} corrisponde all’ER ab3 = abbb;

esempio: (ab)*cd corrisponde all’ER (ab)∗ cd;

unione: sottoespressioni alternative vengono indicate 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 indicato tramite il punto; –

•

: la stringa nulla si indica come una sottoespressione vuota; –

•

esempio: .* corrisponde all’ER Σ∗ ;

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.

Stefano Ferrari— Fondamenti di Informatica per la Sicurezza

4

Modulo 5— U.D. 4— Lez. 3

Sottoinsiemi di caratteri •

elenco di caratteri: una sequenza di caratteri fra una coppia di parentesi quadre indica un insieme; –

•

intervallo: sfruttando l’ordinamento dei caratteri ASCII, si possono indicare intervalli di caratteri; –

•

esempio: [a-d] corrisponde all’insieme {a, b, c, d};

complemento: l’operatore di complemento insiemistico si indica ponendo l’accento circonflesso come primo elemento di un sottoinsieme di caratteri; –

•

esempio: [abd] corrisponde all’insieme {a, b, d};

esempio: [^abd] corrisponde all’insieme Σ − {a, b, d};

classi: esistono identificatori per i sottoinsiemi comunemente utilizzati; –

esempio: [:digit:] corrisponde all’insieme {0, . . . , 9}.

Ancoraggi La posizione di una stringa nel testo può essere un fattore discriminante. Esempio: l’IP del client viene posto all’inizio della riga di log. I metasimboli di ancoraggio servono per indicare una posizione relativa all’interno del testo: •

“^” indica l’inizio della riga;

•

“$” indica la fine della riga; –

e “\^” e “\$” indicano, rispettivamente, i caratteri “^” e “$”.

Stefano Ferrari— Fondamenti di Informatica per la Sicurezza

5

Modulo 5— U.D. 4— Lez. 3

Riferimenti I riferimenti a precedenti sottospressioni (solo BRE) sono usati per poter usare la sottostringa che corrisponde al sottomodello. Esempio: •

(a*)b\1 corrisponde ad aabaa, ma non ad aaba.

I riferimenti vengono utilizzati soprattutto per le sostituzioni. Esempio: •

cambiare il path a tutti i file di un file di configurazione; –

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

Stefano Ferrari— Fondamenti di Informatica per la Sicurezza

6

Modulo 5— U.D. 4— Lez. 3

In sintesi Le espressioni regolari sono un utile e pratico strumento per indicare pattern di caratteri. Sono utilizzate in: •

linguaggi di programmazione;

•

shell;

•

file di configurazione;

•

programmi di utilità;

•

programmi di elaborazione testi.

Chiusura

Stefano Ferrari— Fondamenti di Informatica per la Sicurezza

7