Appunti Fondamenti teorici e programmazione (con quasi tutti esercizi risolti e indice)

FONDAMENTI TEORICI E

PROGRAMMAZIONE

(MODULO B e MODULO A)

Professori Filippo Bonchi e Claudio Gallicchio

N.B: della lezione 8 del MODULO B ho inserito solo l’IMPLICAZIONE (pag.59).

1

Sommario

LEZIONE 1 – MODULO B ______________________________________________________ 9

NUMERI ROMANI________________________________________________________________________ 9

NUMERI ARABI __________________________________________________________________________ 9

POTENZE DI 2 __________________________________________________________________________ 10

BASE 2 _________________________________________________________________________________ 10

DA BASE 2 A BASE 10 ____________________________________________________________________ 11

SOMME IN BASE 2_______________________________________________________________________ 12

BASE 16 ________________________________________________________________________________ 12

DA BASE 16 A BASE 10 ___________________________________________________________________ 12

TABELLA NUMERI ESADECIMALI – NUMERI DECIMALI (da 0 a 255) ________________________ 13

TABELLE NUMERI DECIMALI – NUMERI BINARI (da 0 a 255) _______________________________ 14

- ESERCIZI LEZIONE 1 (Conversioni e basi)_____________________________________________ 15

LEZIONE 2 - MODULO B _____________________________________________________ 16

ALGORITMI ____________________________________________________________________________ 16

LINGUAGGI DI PROGRAMMAZIONE _____________________________________________________ 16

LEZIONE 3 – MODULO B _____________________________________________________ 17

INSIEMI ________________________________________________________________________________ 17

RAPPRESENTAZIONE INSIEMI ___________________________________________________________ 17

APPARTENENZA _______________________________________________________________________ 17

OPERAZIONI SUGLI INSIEMI ____________________________________________________________ 17

INCLUSIONE E SOTTOINSIEMI _________________________________________________________ 18

INTERSEZIONE, UNIONE E DIFFERENZA SUGLI INSIEMI __________________________________ 18

PROPRIETA’ DELLE OPERAZIONI SUGLI INSIEMI _________________________________________ 18

DIAGRAMMI DI VENN __________________________________________________________________ 19

DIAGRAMMI DI VENN PER DE MORGAN _________________________________________________ 19

UNIVERSO U ___________________________________________________________________________ 20

DISGIUNZIONE _________________________________________________________________________ 20

PARTIZIONE____________________________________________________________________________ 21

INSIEME POTENZA _____________________________________________________________________ 21

ALGEBRA BOOLEANA __________________________________________________________________ 21

- ESERCIZI LEZIONE 3 (Insiemi) ______________________________________________________ 23

LEZIONE 4 – MODULO B _____________________________________________________ 25

PRODOTTO CARTESIANO _______________________________________________________________ 25

UNIONE DISGIUNTA ____________________________________________________________________ 26

RELAZIONI _____________________________________________________________________________ 26

PROPRIETA’ DI RELAZIONI _____________________________________________________________ 27

FUNZIONI ______________________________________________________________________________ 28

FUNZIONI PARZIALI ____________________________________________________________________ 28

- ESERCIZI LEZIONE 4 (Algebra booleana, relazioni, funzioni, funzioni parziali) ___________ 29

LEZIONE 5 – MODULO B _____________________________________________________ 30

COMPOSIZIONE DI RELAZIONI __________________________________________________________ 30

RELAZIONE IDENTITA’ _________________________________________________________________ 30

RELAZIONE OPPOSTA __________________________________________________________________ 31

RELAZIONE RIFLESSIVA ________________________________________________________________ 31

RELAZIONE TRANSITIVA _______________________________________________________________ 31

RELAZIONE SIMMETRICA _______________________________________________________________ 32

RELAZIONE ANTISIMMETRICA __________________________________________________________ 32

2

SPECCHIETTO RIASSUNTIVO PROPRIETA’ RELAZIONI PER CONSULTAZIONE VELOCE __ 32

LEZIONE 6 – MODULO B _____________________________________________________ 34

CHIUSURE ______________________________________________________________________________ 34

CLASSI DI EQUIVALENZE ________________________________________________________________ 34

RELAZIONI DI EQUIVALENZE ____________________________________________________________ 35

- ESERCIZI LEZIONE 5 e 6 (funzioni, relazioni, classi di equivalenze, primi controesempi) ___ 35

LEZIONE 7 – MODULO B _____________________________________________________ 39

GRAFI ORIENTATI ______________________________________________________________________ 39

GRAFI NON ORIENTATI _________________________________________________________________ 40

CAMMINO IN UN GRAFO _______________________________________________________________ 40

CICLI IN UN GRAFO ORIENTATO ________________________________________________________ 41

CICLI IN UN GRAFO NON ORIENTATO ___________________________________________________ 42

GRAFO NON ORIENTATO CONNESSO ___________________________________________________ 42

GRAFO ORIENTATO FORTEMENTE CONNESSO ___________________________________________ 44

- ESERCIZI LEZIONE 7 (Grafi, Simmetria, Riflessività, Transitività) _______________________ 45

LEZIONE 9 – MODULO B _____________________________________________________ 46

ALBERI LIBERI __________________________________________________________________________ 46

FORESTE _______________________________________________________________________________ 46

ALBERI RADICATI ______________________________________________________________________ 47

ALBERI ORDINATI E ALBERI POSIZIONALI _______________________________________________ 48

ALBERI BINARI _________________________________________________________________________ 49

ALBERI BINARI DI RICERCA _____________________________________________________________ 51

ESERCIZI (TIPOLOGIA DEL 1° COMPITINO) ___________________________________ 52

IMPLICAZIONE _________________________________________________________________________ 59

LEZIONE 10 – MODULO B ____________________________________________________ 59

ALFABETI ______________________________________________________________________________ 59

PAROLA O STRINGA ____________________________________________________________________ 59

CONCATENAZIONE SU STRINGHE ______________________________________________________ 60

LEGGI ALGEBRICHE DELLE STRINGHE ___________________________________________________ 60

DEFINIZIONE INDUTTIVA DI PAROLA O STRINGA ________________________________________ 61

DEFINIZIONE RICORSIVA DI LUNGHEZZA _______________________________________________ 61

LINGUAGGIO___________________________________________________________________________ 62

LINGUAGGI ____________________________________________________________________________ 62

LEZIONE 11 – MODULO B ____________________________________________________ 62

OPERAZIONI INSIEMISTICHE SUI LINGUAGGI ____________________________________________ 62

CONCATENAZIONE DI LINGUAGGI _____________________________________________________ 63

PROPRIETA’ ALGEBRICHE DELLA CONCATENAZIONE DI LINGUAGGI ____________________ 63

LA STELLA DI KLEENE __________________________________________________________________ 64

ANALOGIA CON L’ALGEBRA RELAZIONALE _____________________________________________ 64

ESPRESSIONI REGOLARI ________________________________________________________________ 65

ESPRESSIONI REGOLARI: DEFINIZIONE INDUTTIVA ______________________________________ 65

SEMANTICA DELLE ESPRESSIONI REGOLARI: INTUIZIONE ________________________________ 66

SEMANTICA DELLE ESPRESSIONI REGOLARI _____________________________________________ 66

LINGUAGGI REGOLARI _________________________________________________________________ 67

GERARCHIA DI CHOMSKY_________________________________________________________ 67

- ESERCIZI LEZIONE 11 (Linguaggi ed espressioni regolari) ______________________________ 68

3

LEZIONE 12 – MODULO B ____________________________________________________ 70

AUTOMI DETERMINISTICI _______________________________________________________________ 70

RAPPRESENTAZIONE GRAFICA _________________________________________________________ 70

RAPPRESENTAZIONE A TABELLA _______________________________________________________ 71

NOTAZIONE PER LE TRANSIZIONI _______________________________________________________ 72

CURRYING _____________________________________________________________________________ 73

FUNZIONI CARATTERISTICHE ___________________________________________________________ 73

LINGUAGGI COME FUNZIONI ___________________________________________________________ 74

LINGUAGGIO ACCETTATO ______________________________________________________________ 75

TEOREMA DI KLEENE ___________________________________________________________________ 76

Per ogni automa deterministico a stati finiti (S, t, o) e per ogni stato x Viceversa, per ogni linguaggio

∈ .

regolare L esiste un automa deterministico a stati finiti (S, t, o) ed un x tale che

∈ = . __________ 76

LEZIONE 13 – MODULO B ____________________________________________________ 76

ESPRESSIONI REGOLARI ED AUTOMI A STATI FINITI ______________________________________ 76

AUTOMI COME SCATOLE NERE _________________________________________________________ 77

RASS: RICONOSCITORE AUTOMATICO DI SEQUENZE DI NUMERI (su moodle) ______________ 77

- ESERCIZI LEZIONE 12 (Automi deterministici) ________________________________________ 78

LEZIONE 14 – MODULO B ____________________________________________________ 79

AUTOMI NON DETERMINISTICI _________________________________________________________ 79

VERSO UNA DEFINIZIONE DI LINGUAGGIO ACCETTATO _________________________________ 80

LINGUAGGIO ACCETTATO_____________________________________________________________ 81

DEFINIZIONE ALTERNATIVE DI AUTOMI ________________________________________________ 81

CORRISPONDENZE CON LA DISPENSA BARBUTI (AUTOMI fino a pag. 12) ___________________ 82

- ESERCIZI LEZIONE 14 (Automi non deterministici) ____________________________________ 83

LEZIONE 15 – MODULO B ____________________________________________________ 86

COSTRUZIONE DEI SOTTOINSIEMI (Dispensa BARBUTI fino a pag.17) ________________________ 86

Esempi: _________________________________________________________________________________ 87

TEOREMA DI CORRISPONDENZA ________________________________________________________ 89

Esempi: _________________________________________________________________________________ 89

GRANDEZZA DELL’AUTOMA Det(A) _____________________________________________________ 90

AUTOMA RAGGIUNGIBILE ______________________________________________________________ 91

- ESERCIZI LEZIONE 15 (Costruzione dei sottoinsiemi) __________________________________ 91

LEZIONE 16 – MODULO B ____________________________________________________ 92

LINGUAGGI NON REGOLARI ____________________________________________________________ 92

GRAMMATICA DELLE ESPRESSIONI ARITMETICHE _______________________________________ 92

PRODUZIONI ___________________________________________________________________________ 93

NOTAZIONE BREVE PER LE PRODUZIONI ________________________________________________ 93

GRAMMATICA LIBERA DA CONTESTO ___________________________________________________ 94

Esempi: _________________________________________________________________________________ 94

ALBERO DI DERIVAZIONE SINTATTICA __________________________________________________ 95

ESEMPI DI ALBERO DI DERIVAZIONE SINTATTICA _______________________________ 96

LINGUAGGIO GENERATO (Dispensa BARBUTI pagg. 19-32) _________________________________ 97

ESEMPIO: ________________________________________________________________________ 97

- ESERCIZI LEZIONE 16 (Costruzione dei sottoinsiemi) __________________________________ 97

LEZIONE 17 – MODULO B ___________________________________________________ 100

4

AMBIGUITA’________________________________________________________________ 100

GRAMMATICA AMBIGUA ___________________________________________________ 101

GRAMMATICA DI UN SEMPLICE LINGUAGGIO IMPERATIVO _________________ 101

- ESERCIZI LEZIONE 17 (Grammatiche) _______________________________________________ 102

ESERCIZI (TIPOLOGIA DEL 2° COMPITINO) __________________________________ 104

LEZIONE 1 – MODULO A ____________________________________________________ 106

ALGORITMI ________________________________________________________________ 106

JAVASCRIPT ___________________________________________________________________________ 106

COMANDO DI STAMPA: _________________________________________________________ 107

LETTURA DI STRINGHE E NUMERI: ______________________________________________ 107

• Esercizi lezione 1 – Modulo A (Conversione, Stampa a video, Fattoriale, Verifica se un numero è

pari, Perimetro del quadrato, Circonferenza del cerchio)_____________________________________ 110

Esercizi LABORATORIO 1 (Stampa a video, Concatenazione, Scrittura di un numero in unità,

-

decine e centinaia, Anno bisestile) ________________________________________________________ 111

LEZIONE 2 – MODULO A ____________________________________________________ 114

LIBRERIA MATH _______________________________________________________________________ 114

- Esercizi LABORATORIO 2 (Lettura da input di stringhe e numeri, libreria Math) ____________ 114

LEZIONE 3 – MODULO A ____________________________________________________ 118

VARIABILI ED ASSEGNAMENTO ________________________________________________ 118

VARIABILI _____________________________________________________________________________ 118

IDENTIFICATORI ______________________________________________________________________ 119

DICHIARAZIONI DI VARIABILI _________________________________________________________ 119

CONCETTO DI STATO __________________________________________________________________ 119

EVOLUZIONE DELLO __________________________________________________________________ 120

STATO ________________________________________________________________________________ 120

ASSEGNAMENTO ______________________________________________________________________ 120

ABBREVIAZIONI _______________________________________________________________________ 121

FUNZIONI _____________________________________________________________________________ 121

• DICHIARAZIONE DI FUNZIONE ___________________________________________________ 121

• INVOCAZIONE DI FUNZIONE _____________________________________________________ 122

• RETURN __________________________________________________________________________ 123

STATO DURANTE L’INVOCAZIONE DI UNA FUNZIONE __________________________________ 123

FUNZIONI DI CONVERSIONE ___________________________________________________________ 125

VISIBILITA’ ____________________________________________________________________________ 125

VARIABILI LOCALI E GLOBALI _________________________________________________________ 125

VISIBILITA’ DELLE VARIABILI DEFINITE NEI BLOCCHI ___________________________________ 127

NAME MASKING ______________________________________________________________________ 128

• Esercizi LABORATORIO 3 (funzione bisestile, funzione area rettangolo e cerchio, funzione xor,

funzione media aritmetica, funzione party, funzione polinomio, funzione equazione di 2° grado,

funzioni unità, decine, centinaia, funzione inverti3) ________________________________________ 130

LEZIONE 4 – MODULO A ____________________________________________________ 136

ISTRUZIONI CONDIZIONALI ___________________________________________________________ 136

IF-ELSE _________________________________________________________________________________ 136

5

IF _____________________________________________________________________________________ 137

BLOCCO ________________________________________________________________________________ 137

IF ANNIDATI _____________________________________________________________________________ 137

AMBIGUITA’ DELL’ELSE ____________________________________________________________________ 138

SWITCH ________________________________________________________________________________ 138

RAGGRUPPARE I CASE __________________________________________________________ 142

CASE CONSECUTIVI _____________________________________________________________ 142

SWITCH: SINTASSI GENERALE __________________________________________________ 142

SWITCH: SEMANTICA ___________________________________________________________ 143

RETURN AL POSTO DI BREAK ___________________________________________________ 144

ISTRUZIONI ITERATIVE _______________________________________________________________ 146

WHILE __________________________________________________________________________________ 146

WHILE – ITERAZIONE DETERMINATA __________________________________________________________ 147

ALTERNATIVA 1: INIZIAMO A CONTARE DA 0 ___________________________________________________ 148

ALTERNATIVA 2: CONTIAMO QUANTE ITERAZIONI MANCANO ____________________________________ 149

WHILE – ITERAZIONE INDETERMINATA ________________________________________________________ 150

• Esercizi LABORATORIO 4 (Istruzioni condizionali, Istruzioni iterative) ____________ 151

4.1) VALORE ASSOLUTO (if-else) ___________________________________________________ 151

RECT

4.2) FUNZIONE (if) ___________________________________________________________ 152

4.3) VELOCITA’ – MULTA (if annidati) ____________________________________________ 152

4.4) GRADO ALCOLICO DI UNA BEVANDA (if annidati, stessa struttura

dell’esercizio 4.3) ________________________________________________________________ 153

4.5) TIPO TRIANGOLO (if e if annidati) _________________________________________ 154

4.6) NUMERI CASUALI TRA -1 e 1, restituendo il minimo (Math.random*** (vedi

tabella lezione 2) e while) _______________________________________________________ 155

4.7) NUMERI CASUALI TRA -1 e 1, restituendo il massimo (Math.random*** (vedi

tabella lezione 2) e while) _______________________________________