Riassunto esame Fondamenti di Informatica, prof. Sernani, libro consigliato Fondamenti di programmazione in C++, Aguilar

Università Politecnica delle Marche

Facoltà di Ingegneria

Corso di Laurea Triennale in Ingegneria Informatica e dell’Automazione

Riassunto di:

Fondamenti di Informatica Nicolò Bartolini

Basato sulle lezioni del Prof. Paolo Sernani

Indice

I Introduzione 8

1 La civiltà digitale 9

1.1 Numeri ricorrenti in informatica . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9

1.2 La digitalizzazione dei testi . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10

1.2.1 A.S.C.I.I. (1986) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10

1.2.2 ISO-8859 (1988) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11

1.2.3 UNICODE (1996) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11

1.3 La digitalizzazione dei suoni . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11

1.3.1 Formati di file audio . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12

1.4 La digitalizzazione delle immagini . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13

1.4.1 Formati "raster" di file immagine . . . . . . . . . . . . . . . . . . . . . . . . . 13

1.4.2 Formato vettoriale delle immagini . . . . . . . . . . . . . . . . . . . . . . . . . 14

1.5 La digitalizzazione dei video . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14

2 I numeri al calcolatore 16

2.1 Rappresentazione dei numeri naturali . . . . . . . . . . . . . . . . . . . . . . . . . . . 16

2.1.1 Algoritmo di conversione . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16

2.1.2 Notazione esadecimale . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18

2.1.3 Aritmetica "modulo " . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18

N

2

2.1.4 Addizione tra numeri naturali nei calcolatori . . . . . . . . . . . . . . . . . . . 19

2.1.5 Sottrazione tra numeri naturali nei calcolatori . . . . . . . . . . . . . . . . . . 20

2.1.6 Altre operazioni tra numeri naturali . . . . . . . . . . . . . . . . . . . . . . . 21

2.2 Rappresentazione dei numeri interi . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21

2.2.1 Modulo e segno . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21

2.2.2 Complemento a 1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21

2.2.3 Traslazione . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22

2.2.4 Complemento a 2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22

2.2.5 Operazioni in base 2 dei numeri interi . . . . . . . . . . . . . . . . . . . . . . 23

2.3 Rappresentazione dei numeri reali . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23

2.3.1 IEEE 754 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24

II L’architettura degli elaboratori 27

3 Von Neumann 28

2

INDICE 3.0.1 Architetture delle CPU . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29

3.0.2 La scheda madre (motherboard) . . . . . . . . . . . . . . . . . . . . . . . . . 29

3.1 Memorie gerarchiche . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30

3.1.1 Principi di località . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30

3.2 L’architettura funzionale della CPU . . . . . . . . . . . . . . . . . . . . . . . . . . . 31

4 Assembly 33

4.1 Operandi . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33

4.1.1 Esempi di istruzioni in Assembly . . . . . . . . . . . . . . . . . . . . . . . . . 34

4.2 Programmazione modulare . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34

4.3 Direttive . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35

4.3.1 Direttive per i dati . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36

4.4 Etichette (label) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36

4.5 Stack . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37

4.5.1 Push e pop . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37

4.6 Sottoprogrammi . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38

4.7 Endianess . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38

4.8 Conclusioni . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38

4.8.1 Input/Output (I/O) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38

4.8.2 Pro e contro di Assembly . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38

III Programmazione in C++ 40

5 Introduzione al C++ 41

5.1 I linguaggi imperativi . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41

5.2 Compilazione in C++ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41

5.3 Struttura di un programma in C++ . . . . . . . . . . . . . . . . . . . . . . . . . . . 42

5.4 Programmazione e "debugging" . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44

5.5 Software e copyright . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44

5.5.1 Software libero e open source . . . . . . . . . . . . . . . . . . . . . . . . . . . 44

5.5.2 Software semilibero . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45

5.5.3 Software chiuso . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45

6 Tipi di dato 47

6.1 Elementi di un programma in C++ . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47

6.1.1 Parole riservate in C++ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47

6.1.2 Segni d’interpunzione e separatori . . . . . . . . . . . . . . . . . . . . . . . . 48

6.1.3 Inclusione delle librerie . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48

6.2 Tipi di dato . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48

6.2.1 Tipi di dato semplici in C++ . . . . . . . . . . . . . . . . . . . . . . . . . . . 48

6.3 Costanti in C++ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49

6.4 Variabili in C++ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49

6.4.1 Definizione di una variabile . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50

6.4.2 Istruzione di assegnamento . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50

6.5 Il tipo int . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51

6.5.1 Operazioni con il tipo int . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51

6.5.2 L’istruzione cin . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52

3 INDICE

6.6 Il tipo bool . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52

6.6.1 Operatori booleani . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53

6.7 Il tipo unsigned . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 54

6.7.1 Operatori specifici "bit a bit" (bitwise) . . . . . . . . . . . . . . . . . . . . . . 54

6.8 I tipi float e double . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 54

6.8.1 Esempio di un programma che risolve un’equazione di secondo grado . . . . . 55

6.9 Il tipo char . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 56

6.10 L’istruzione enum . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57

6.11 Conversioni di tipo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 58

6.11.1 Operazioni con tipi numerici misti . . . . . . . . . . . . . . . . . . . . . . . . 58

6.11.2 Conversioni di tipo implicite . . . . . . . . . . . . . . . . . . . . . . . . . . . . 59

6.11.3 Conversioni di tipo esplicite (casting) . . . . . . . . . . . . . . . . . . . . . . . 59

6.12 L’operatore sizeof() . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 60

7 Operatori, I/O, visibilità 61

7.1 Operatori ed espressioni . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61

7.1.1 Le espressioni . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61

7.1.2 Gli operatori in C++ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61

7.1.3 Precedenza ed associatività . . . . . . . . . . . . . . . . . . . . . . . . . . . . 62

7.2 Operatore di assegnamento (=) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 63

7.2.1 Errori di assegnamento . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 64

7.2.2 Assegnamento composto . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 64

7.2.3 Incrementi e decrementi di 1 . . . . . . . . . . . . . . . . . . . . . . . . . . . 65

7.3 Operatori relazionali e logici . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 65

7.3.1 Operatori relazionali . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 65

7.3.2 Operatori logici . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 66

7.4 Operatore condizionale e operatore virgola . . . . . . . . . . . . . . . . . . . . . . . . 67

7.4.1 Operatore condizionale . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 67

7.4.2 Operatore virgola . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 67

7.5 La libreria iostream . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 68

7.6 Il concetto di "flusso" (stream) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 68

7.7 Lettura e scrittura . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 68

7.7.1 L’oggetto cin . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 69

7.7.2 L’oggetto cout . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 69

7.8 Redirezione dei flussi . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 69

7.9 Flussi di file. La libreria <fstream> (file stream) . . . . . . . . . . . . . . . . . . . . 70

7.10 La libreria <iomanip> . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 71

7.10.1 Gestione delle basi numeriche . . . . . . . . . . . . . . . . . . . . . . . . . . . 71

7.10.2 La funzione setprecision() . . . . . . . . . . . . . . . . . . . . . . . . . . . 71

7.10.3 Le funzioni setw(), setfill() e setiosflags() . . . . . . . . . . . . . . . . 72

7.11 Blocchi e visibilità degli identificatori . . . . . . . . . . . . . . . . . . . . . . . . . . . 73

7.11.1 Blocchi e blocchi innestati . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 73

7.11.2 Visibilità di un identificatore . . . . . . . . . . . . . . . . . . . . . . . . . . . 73

7.11.3 Oggetti globali e locali . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 74

7.12 Spazio dei nomi . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 74

7.12.1 La direttiva using . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 75

4

INDICE

8 Programmazione strutturata 77

8.1 Strutture di selezione . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 77

8.1.1 Il costrutto if . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 77

8.1.2 Il costrutto if else . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 78

8.1.3 Istruzioni if else annidate . . . . . . . . . . . . . . . . . . . . . . . . . . . . 79

8.1.4 Il costrutto switch . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 79

8.2 Le strutture cicliche . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 80

8.2.1 Il costrutto while . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 81

8.2.2 Il costrutto do while . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 82

8.2.3 Il costrutto for . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 83

8.2.4 Cicli annidati . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 85

8.2.5 Confronto tra i tre costrutti ciclici . . . . . . . . . . . . . . . . . . . . . . . . 85

8.3 Istruzioni di salto . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 85

8.3.1 L’istruzione continue . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 85

8.3.2 L’istruzione break . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 86

8.3.3 L’istruzione goto . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 86

8.3.4 Problemi delle istruzioni di salto . . . . . . . . . . . . . . . . . . . . . . . . . 87

8.3.5 Teorema di Böhm-Jacopini (1966) . . . . . . . . . . . . . . . . . . . . . . . . 87

9 Funzioni 88

9.1 Componenti di una funzione . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 88

9.1.1 Definizione di una funzione . . . . . . . . . . . . . . . . . . . . . . . . . . . . 88

9.1.2 Dichiarazione (o prototipo) di una funzione . . . . . . . . . . . . . . . . . . . 89

9.1.3 Chiamata di una funzione . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 89

9.2 Procedure . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 90

9.3 Il main() . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 90

9.4 Tipo del dato di ritorno e risultati di una funzione . . . . . . . . . . . . . . . . . . . 90

9.4.1 Proprietà . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 90

9.5 Chiamata di una funzione . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 91

9.5.1 Passaggio di argomenti . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 91

9.5.2 Funzioni ricorsive . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 91

9.6 Argomenti di default . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 92

9.7 Funzioni inline . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 92

9.8 Storage classes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 92

9.9 Compilazione modulare . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 93

9.10 Funzioni di libreria . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 93

9.10.1 Funzioni di carattere. La libreria <ctype> . . . . . . . . . . . . . . . . . . . . 94

9.10.2 Funzioni numeriche. La libreria <cmath> . . . . . . . . . . . . . . . . . . . . . 94

9.10.3 Funzioni varie . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 95

9.11 Overload delle funzioni . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 95

9.12 Template di funzioni . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 96

10 Puntatori e riferimenti 97

10.1 Puntatori al tipo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 97

10.2 Operazioni con i puntatori . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 98

10.3 Puntatori a puntatori . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 99

10.4 Puntatori come parametri di funzioni . . . . . . . . . . . . . . . . . . . . . . . . . . . 99

10.4.1 Errore tipico: segmentation fault . . . . . . . . . . . . . . . . . . . . . . . . . 100

5 INDICE

10.5 Puntatori e oggetti non modificabili . . . . . . . . . . . . . . . . . . . . . . . . . . . . 100

10.5.1 Puntatori costanti . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 100

10.5.2 Puntatori a costanti . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 101

10.5.3 L’operatore const_cast . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 101

10.6 Riferimenti al tipo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 102

10.7 Riferimenti come parametri di funzioni . . . . . . . . . . . . . . . . . . . . . . . . . . 102

10.7.1 Restituzione di riferimenti . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 103

10.8 Riferimenti: dietro le quinte . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 103

10.9 Puntatori a void . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 103

10.10Puntatori a funzioni . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 105

10.11Aritmetica dei puntatori . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 106

11 Vettori e strutture 107

11.1 Definizione di un vettore . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 107

11.1.1 Definizione e inizializzazione . . . . . . . . . . . . . . . . . . . . . . . . . . . . 107

11.2 Accesso agli elementi di un vettore . . . . . . . . . . . . . . . . . . . . . . . . . . . . 108

11.2.1 Assegnamento di un elemento . . . . . . . . . . . . . . . . . . . . . . . . . . . 108

11.3 Allocamento in memoria dei vettori . . . . . . . . . . . . . . . . . . . . . . . . . . . . 108

11.4 Limiti dei vettori . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 109

11.4.1 Offset tra due vettori . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 109

11.5 Stringhe . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 110

11.5.1 Stringhe e I/O . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 110

11.6 Vettori multidimensionali . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 110

11.7 Vettori come argomenti di funzioni . . . . . . . . . . . . . . . . . . . . . . . . . . . . 111

11.8 Vettori e puntatori . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 111

11.9 Ordinamento dei vettori . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 111

11.9.1 Insertion sort . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 112

11.9.2 Selection sort . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 114

11.9.3 Bubble sort . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 115

11.9.4 Bubble sort: versione 2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 116

11.9.5 Quick sort . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 117

11.9.6 Le librerie <algorithm> e <array> . . . . . . . . . . . . . . . . . . . . . . . . 118

11.10Strutture . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 118

11.10.1 Accesso ai campi della struttura . . . . . . . . . . . . . . . . . . . . . . . . . . 119

11.10.2 Defini