Prefazione xv

1 Architettura dei calcolatori 1
1.1 Calcolatori e applicazioni 1
1.1.1 Alcuni esempi di applicazioni 3
1.1.2 Applicazioni e interfacce 4
1.2 Architettura dei calcolatori 7
1.2.1 Hardware e software 8
1.2.2 Macchina di von Neumann 9
1.3 Tecnologia dei calcolatori 13
1.3.1 Codifica dei dati 13
1.3.2 Microprocessore 14
1.3.3 Memoria centrale 16
1.3.4 Memorie secondarie 16
1.4 Il sistema operativo 18
1.4.1 Architettura di un sistema operativo 19
1.5 Calcolatori e programmazione 21

2 Oggetti software 23
2.1 Programmi e programmazione 23
2.2 Introduzione agli oggetti software 24
2.3 Esempi di oggetti software 29
2.3.1 L'oggetto software System.out 29
2.3.2 L'oggetto software Math 33
2.3.3 Un oggetto software per la lettura dalla tastiera 36
2.3.4 Robot e labirinti 37
2.4 Oggetti software 43
2.5 Classi e costruzione di oggetti software 44
2.5.1 Costruzione di oggetti software 45
2.5.2 Componenti di una classe 47
2.6 Esempi di classi 48
2.6.1 La classe Math 48
2.6.2 Le classi Robot e Labirinto 49
2.7 Il linguaggio UML 50

3 Oggetti e Java 53
3.1 Introduzione alla programmazione in Java 53
3.1.1 Il linguaggio di programmazione Java 53
3.1.2 Classi Java 54
3.1.3 Programmi Java 54
3.1.4 API di Java 55
3.1.5 Programmazione in Java 55
3.2 Introduzione a Java (per esempi) 56
3.2.1 Scrittore sullo schermo 56
3.2.2 Calcolo di una radice quadrata 61
3.2.3 Perimetro di un triangolo 65
3.2.4 Lettura e somma di due numeri interi 71
3.2.5 Robot in un labirinto 74
3.2.6 Una classe per istanziare oggetti 82

4 Strumenti per la programmazione 87
4.1 Strumenti per la programmazione 87
4.1.1 Editing ed editor 87
4.1.2 Compilazione e compilatori 88
4.1.3 Esecuzione 89
4.1.4 Compilatori e interpreti 89
4.1.5 Compilazione ed esecuzione di programmi Java 91
4.1.6 Java 2 Software Development Kit 93
4.2 Che cosa fare in pratica 93
4.3 Errori di programmazione 95
4.4 Ambienti integrati di sviluppo 97

5 Problemi, algoritmi e oggetti 99
5.1 Problemi e algoritmi 99
5.1.1 Comprensione del problema 100
5.1.2 Identicazione di un algoritmo per il problema 101
5.1.3 Dall'algoritmo all'oggetto 102
5.1.4 Qualita' degli algoritmi 103
5.2 Introduzione agli algoritmi (per esempi) 106
5.2.1 Un linguaggio per scrivere algoritmi 106
5.2.2 Progettazione di algoritmi 109
5.2.3 Problemi di ingresso-uscita 110
5.2.4 Lettura e somma di due numeri interi 111
5.2.5 Somma di una sequenza di numeri interi 113
5.2.6 Lunghezza di una sequenza 117
5.2.7 Somma dei pari e dei dispari in una sequenza 119
5.2.8 Somma di una sequenza di dieci numeri 122
5.2.9 Somma dei primi N numeri interi positivi 127
5.2.10 Traccia dell'esecuzione di un metodo o di un algoritmo 129
5.2.11 La formula di Gauss 131
5.3 Attraversamento di labirinti 132
5.3.1 Attraversamento di labirinti lineari 132
5.3.2 Attraversamento di labirinti 135

6 Le basi del linguaggio Java 141
6.1 Sintassi e semantica 141
6.2 Introduzione alla sintassi di Java 141
6.3 Introduzione alla semantica di Java 143
6.3.1 Semantica delle espressioni 145
6.3.2 Semantica delle istruzioni 145
6.4 Sintassi, semantica ed errori 146
6.5 Introduzione alle istruzioni di Java 148

7 Leggibilita' 151
7.1 Stile e convenzioni di codifica 151
7.2 Commenti 152
7.3 Scelta dei nomi 154
7.4 Indentazione 154
7.5 Ordine delle istruzioni e delle dichiarazioni 155
7.6 Repertorio di istruzioni 156

8 Uso di oggetti 157
8.1 Tipi ed espressioni 157
8.2 Uso di oggetti 159
8.2.1 Operazioni e messaggi 160
8.2.2 Operazioni e metodi 161
8.2.3 Invocazione di metodi 164
8.2.4 Accesso a proprieta' di oggetti 165
8.3 Descrizione di oggetti e classi 165
8.3.1 Descrizione di metodi 167
8.3.2 Descrizione di metodi che restituiscono un valore 171
8.3.3 Descrizione di variabili 172
8.3.4 Selezione di metodi 173
8.4 Creazione di oggetti e costruttori 174

9 Variabili e assegnazione 181
9.1 Variabili e assegnazione 181
9.1.1 Variabili e aree di memoria 183
9.1.2 Dichiarazione di variabili 183
9.1.3 Assegnazione e accesso 185
9.1.4 Costanti 187
9.2 Variabili riferimento 188

10 Errori di programmazione 191
10.1 Classificazione degli errori 191
10.2 Errori sintattici 192
10.3 Errori di semantica statica 193
10.4 Errori di semantica dinamica 194
10.5 Errori logici 195
10.6 Discussione 196

11 Tipi ed espressioni 197
11.1 Tipi 197
11.2 Espressioni 199
11.3 Tipi primitivi per numeri interi 200
11.3.1 Introduzione al tipo primitivo int 201
11.3.2 Valutazione delle espressioni 203
11.3.3 Rappresentazione dei numeri interi 205
11.3.4 Altri tipi primitivi numerici interi 206
11.4 Tipi primitivi per numeri reali 206
11.4.1 La classe Math 209
11.5 Conversione tra tipi 209
11.5.1 Conversione implicita 209
11.5.2 Conversione esplicita 211
11.6 Il tipo primitivo char 212
11.7 Algebra di Boole e tipo primitivo boolean 213
11.7.1 Algebra di Boole 214
11.7.2 Il tipo primitivo boolean 215

12 Tipi riferimento e stringhe 221
12.1 Tipi riferimento 221
12.2 Stringhe e oggetti String 222
12.3 Uso di variabili riferimento 223
12.4 Uso di oggetti String 225
12.5 Stringhe e tipi primitivi 229
12.5.1 Conversione da tipi primitivi a stringhe 229
12.5.2 Conversione da stringhe a tipi primitivi 229
12.5.3 Il metodo charAt 230
12.6 Concatenazione di stringhe 231
12.7 Confronto tra stringhe 232
12.8 Sulla composizione dell'invocazione di metodi 233
12.9 Riferimenti e uguaglianza 234
12.10 Il letterale null 235

13 Istruzioni condizionali e blocco 237
13.1 Introduzione alle istruzioni di controllo 237
13.2 Istruzione condizionale if-else 238
13.3 Blocco (istruzione composta) 241
13.4 Istruzione condizionale if 244
13.5 Istruzioni condizionali annidate 244
13.6 Cascata di istruzioni if-else 246
13.7 Il problema dell'else mancante 250
13.8 Uso di predicati complessi 251
13.9 Linee guida 252
13.10 Errori comuni 253

14 Istruzioni ripetitive 255
14.1 Istruzioni ripetitive 255
14.2 Istruzione ripetitiva while 255
14.3 Istruzione ripetitiva for 259
14.3.1 Istruzione for con variabile contatore 262
14.4 Istruzione ripetitiva do-while 265
14.5 Confronto tra istruzioni ripetitive 267
14.6 Linee guida 269
14.7 Istruzioni ripetitive e cicli 274
14.8 Errori comuni 274
14.8.1 Ciclo infinito 274
14.8.2 Errore di uno 276
14.9 Istruzioni ripetitive annidate 276
14.10 Terminazione precoce 280

15 Definizione di metodi 283
15.1 Introduzione alla definizione di metodi 283
15.1.1 Denizione di un semplice metodo 284
15.1.2 Uso di classi e metodi 285
15.2 Metodi e variabili locali 287
15.3 Metodi con parametri 289
15.4 Metodi che restituiscono un valore 292
15.5 Sovraccarico di nomi 296
15.6 Auto-referenziazione 298
15.7 Classi e applicazioni 298
15.8 Visibilita' delle variabili 299
15.9 Programmazione strutturata (e non) 301
15.10 Effetti collaterali 302
15.11 Metodi di supporto 304
15.11.1 Il modificatore private 306
15.12 Legame dei parametri 307
15.12.1 Legame dei parametri per valore 307
15.12.2 Legame dei parametri per riferimento 312
15.13 Linee guida 315

16 Correttezza 319
16.1 Introduzione alla correttezza 319
16.2 Correttezza dei metodi 322
16.2.1 Specifica di un metodo 322
16.2.2 Correttezza di un metodo 324
16.2.3 Correttezza e responsabilita' 326
16.3 Verifica di correttezza 327
16.3.1 Test a scatola nera 329
16.3.2 Test a scatola trasparente 331
16.3.3 Metodi di test 331
16.4 Individuazione e correzione degli errori 334
16.5 Test di un insieme di metodi 335

17 Iterazione 339
17.1 Accesso a sequenze 339
17.2 Accumulazione 340
17.3 Conteggio 343
17.4 Verifica esistenziale 344
17.5 Verifica universale 346
17.6 Ricerca 350
17.7 File di testo 354

18 Definizione di classi 359
18.1 Classi per istanziare oggetti 359
18.2 Esempio: la classe Punto 360
18.3 Variabili d'istanza 361
18.3.1 Accesso a variabili d'istanza 363
18.4 Metodi d'istanza 364
18.5 Costruttori 367
18.6 Ulteriori aspetti nella denizione di classi 369
18.6.1 Auto-referenziazione 370
18.6.2 Il metodo toString 370
18.6.3 Il metodo equals 371
18.6.4 Sovraccarico del costruttore 371
18.6.5 Metodi di classe 372
18.6.6 Variabili di classe 372
18.6.7 Classi e oggetti 373
18.6.8 Occultamento dell'informazione 374
18.7 Esempio: la classe Rettangolo 375
18.8 Classi per oggetti dati 380

19 Array 383
19.1 Il problema degli studenti da promuovere 383
19.2 Array 386
19.3 Array in Java 387
19.4 Uso di array 388
19.4.1 Dichiarazione di variabili array e tipi array 388
19.4.2 Creazione di array 389
19.4.3 Accesso a un array 389
19.4.4 Il problema degli studenti da promuovere 390
19.4.5 Lunghezza di un array 390
19.4.6 Array e metodi 392
19.4.7 Letterali array 392
19.5 Array e accesso posizionale 393
19.5.1 Somma degli elementi di un array 393
19.5.2 Visualizzazione degli elementi di un array 394
19.5.3 Calcolo del massimo elemento di un array di interi 395
19.5.4 Verifica se un array e' crescente 396
19.5.5 Coppia di elementi uguali 397
19.5.6 Array paralleli 398
19.5.7 Clonazione di array 398
19.5.8 Uguaglianza tra array 400
19.5.9 Elementi positivi di un array di interi 401
19.6 Array e oggetti 403
19.7 Parametro del metodo main 404
19.8 Ricerca sequenziale 407
19.9 Ricerca binaria 408
19.10 Fusione di sequenze ordinate 413

20 Array di array 417
20.1 Array bidimensionali 417
20.1.1 Creazione e uso di array bidimensionali 418
20.2 Array di array 420
20.3 Gestione di array di array 422
20.3.1 Visualizzazione degli elementi di un array di array 423
20.3.2 Somma degli elementi di un array di array 423
20.3.3 Uguaglianza tra array di array 424
20.3.4 Clonazione di array di array 425

21 Modello runtime 429
21.1 Modello runtime e gestione della memoria 429
21.2 Esecuzione di metodi e costruttori 430
21.2.1 Esecuzione di metodi: un esempio 432
21.2.2 Esecuzione di metodi: discussione 439
21.3 Gestione degli oggetti 440
21.3.1 Gestione di oggetti: un esempio 441
21.3.2 Gestione di oggetti: discussione 447
21.4 Vita delle variabili 447

22 Ricorsione 449
22.1 Definizioni induttive 449
22.1.1 Definizione induttiva di insiemi 449
22.1.2 Definizione induttiva di funzioni 450
22.2 Metodi ricorsivi 452
22.2.1 Definizione di metodi ricorsivi 452
22.2.2 Esecuzione di metodi ricorsivi 453
22.2.3 Progettazione di metodi ricorsivi 456
22.2.4 Errori comuni 457
22.2.5 Ricorsione lineare e non lineare 459
22.3 Tipi ricorsivi 461
22.3.1 Tipi ricorsivi e metodi ricorsivi 462
22.4 Ricorsione e stringhe 463
22.5 Ricorsione e array 464
22.6 Ricerca binaria 466
22.7 Quando usare (o non usare) la ricorsione 466

23 Complessita' 471
23.1 Complessita' dei metodi 471
23.1.1 Modello di costo 473
23.1.2 Analisi di caso peggiore 476
23.2 Complessita' asintotica 479
23.2.1 Modello di costo asintotico 480
23.2.2 Operazione dominante 481
23.3 Complessita' di algoritmi e problemi 483
23.4 Complessita' della ricerca in un array 483
23.4.1 Complessita' della ricerca sequenziale 484
23.4.2 Complessita' della ricerca binaria 484
23.5 Discussione 485

24 Ordinamento 487
24.1 Ordinamento di un array 487
24.2 Ordinamento di array e API di Java 487
24.3 Ordinamento per selezione 488
24.3.1 Complessita' dell'ordinamento per selezione 493
24.4 Ordinamento a bolle 494
24.4.1 Complessita' dell'ordinamento a bolle 498
24.5 Ordinamento per inserzione 499
24.5.1 Complessita' dell'ordinamento per inserzione 501
24.6 Ordinamento per fusione 502
24.6.1 Complessita' dell'ordinamento per fusione 505
24.7 Ordinamento veloce 507
24.7.1 Complessita' dell'ordinamento veloce 508
24.8 Risultati sperimentali 509

25 Ereditarieta' e polimorfismo 511
25.1 Estensione di classi 511
25.2 Polimorfismo 515
25.2.1 L'operatore instanceof 517
25.2.2 Conversione esplicita 518
25.3 La classe Object 518
25.4 Estensione di classi e progettazione di classi 520
25.5 Il modificatore protected 520
25.6 Classi astratte 521
25.7 Interfacce 524

26 Collezioni 527
26.1 Introduzione al Java Collections Framework 527
26.2 Collezioni 528
26.3 Insiemi 529
26.4 Iteratori 531
26.5 Liste 533
26.6 Mappe 536

27 Interfacce grafiche 539
27.1 Interfacce grafiche 539
27.2 La classe JFrame 541
27.3 Componenti 542
27.4 Struttura di una interfaccia grafica 543
27.5 Gestori di layout 546
27.6 Eventi, sorgenti e ascoltatori 548
27.7 Gestione di eventi 549
27.8 Gestione di piu' sorgenti di eventi 553
27.9 Programmazione ad eventi 555
27.10 Programmazione visuale 555