|
|
Progetto di algoritmi e strutture dati in Java
|
| Editore | Mc Graw Hill |
| Autore | Demetrescu Camil ; Ferraro Petrillo Umberto ; Finocchi Irene ; Italiano Giuseppe F. |
| Collana | Istruzione scientifica |
| Pagine | 433 |
| Volumi | 1 |
| Livello | Intermedio-Avanzato |
| Lingua | Italiano |
| Data pubblicazione | 03 - 2007 |
| ISBN | 8838663742 |
|
|
| Prezzo di copertina | Sconto | Prezzo Librinformatica |
| Euro 32,00 | 10% | Euro 28,80 |
|
Prefazione
1) Algoritmi e loro implementazione in Java
2) Strutture dati elementari
3) Alberi
4) Ordinamento
5) Selezione
6) Alberi di ricerca
7) Tabelle hash
8) Code con priorità
9) Union-find
10) Grafi e visite di grafi
11) Minimo albero ricoprente
12) Cammini minimi
Prefazione
1 Algoritmi e loro implementazione in Java
1.1 Ciclo di sviluppo di codice algoritmico . . . . . . . . . . . . . . . 2
1.2 Fase progettuale . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
1.2.1 Analisi dei requisiti . . . . . . . . . . . . . . . . . . . . . 4
1.2.2 Valutazione della difficolta' intrinseca del problema . . . . 4
1.2.3 Progetto di un algoritmo risolutivo . . . . . . . . . . . . . 4
1.2.4 Analisi di correttezza . . . . . . . . . . . . . . . . . . . . 5
1.2.5 Analisi delle prestazioni in un modello di costo teorico.. 5
1.2.6 Progetto di algoritmi piu' efficienti . . . . . . . . . . . . . 9
1.3 Fase realizzativa . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
1.3.1 Implementazioneinunlinguaggiodiprogrammazione.. 10
1.3.2 Collaudoeanalisisperimentale . . . . . . . . . . . . . . 12
1.3.3 Metodologiedianalisisperimentale . . . . . . . . . . . . 15
1.3.4 Messaapuntoeingegnerizzazione . . . . . . . . . . . . . 19
1.4 Ingredientiperl’implementazioneinJava . . . . . . . . . . . . . 21
1.4.1 Stessainterfaccia,diverserealizzazioni . . . . . . . . . . 21
1.4.2 Tipigenericieboxing . . . . . . . . . . . . . . . . . . . 23
1.4.3 Testdiuguaglianza:ilmetodo equals . . . . . . . . . . 24
1.4.4 Ordinamentonaturale:ilmetodo compareTo . . . . . . 25
1.4.5 Gestionedeglierrori:eccezioni . . . . . . . . . . . . . . 27
1.4.6 Iteratori . . . . . . . . . . . . . . . . . . . . . . . . . . . 29
1.4.7 IlJavaCollectionsFramework . . . . . . . . . . . . . . . 30
1.5 Progettomotorediricerca . . . . . . . . . . . . . . . . . . . . . 31
1.6 Sommario . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34
1.7 Esercizi . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36
2 Strutturedatielementari
2.1 TipididatoeinterfacceJava . . . . . . . . . . . . . . . . . . . . 37
2.2 StrutturedatieclassiJava . . . . . . . . . . . . . . . . . . . . . . 38
2.3 Tecnicheperrappresentarecollezionidioggetti . . . . . . . . . . 43
2.3.1 Struttureindicizzate:array . . . . . . . . . . . . . . . . . 43
2.3.2 Strutturecollegate:recordepuntatori . . . . . . . . . . . 47
2.4 Tipodidatopila . . . . . . . . . . . . . . . . . . . . . . . . . . . 52
2.5 Tipodidatocoda . . . . . . . . . . . . . . . . . . . . . . . . . . 55
2.6 Progettomotorediricerca:lexiconeindicediretto . . . . . . . . 58
2.7 Analisisperimentale . . . . . . . . . . . . . . . . . . . . . . . . 63
2.8 Sommario . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 68
2.9 Esercizi . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 69
3 Alberi
3.1 Definizionipreliminarisuglialberi . . . . . . . . . . . . . . . . . 71
3.2 Tipodidatoalbero . . . . . . . . . . . . . . . . . . . . . . . . . 72
3.3 Tipodidatoalberobinario . . . . . . . . . . . . . . . . . . . . . 75
3.4 Rappresentazioniindicizzate . . . . . . . . . . . . . . . . . . . . 77
3.4.1 Vettorepadri . . . . . . . . . . . . . . . . . . . . . . . . 78
3.4.2 Vettoreposizionale . . . . . . . . . . . . . . . . . . . . . 81
3.5 Rappresentazionicollegate . . . . . . . . . . . . . . . . . . . . . 82
3.5.1 Puntatoriaifigli . . . . . . . . . . . . . . . . . . . . . . 83
3.5.2 Listafigli . . . . . . . . . . . . . . . . . . . . . . . . . . 86
3.5.3 Primofiglio-fratellosuccessivo . . . . . . . . . . . . . . 86
3.6 Visitedialberi . . . . . . . . . . . . . . . . . . . . . . . . . . . . 88
3.6.1 Visitainprofondit`a ..................... 89
3.6.2 Visitainampiezza . . . . . . . . . . . . . . . . . . . . . 92
3.7 Progettomotorediricerca:compressione . . . . . . . . . . . . . 94
3.7.1 IcodicidiHuffman . . . . . . . . . . . . . . . . . . . . . 94
3.7.2 GlialberidiHuffman . . . . . . . . . . . . . . . . . . . . 95
3.8 Analisisperimentale . . . . . . . . . . . . . . . . . . . . . . . . 100
3.9 Sommario . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 102
3.10 Esercizi . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 103
4 Ordinamento
4.1 Ordinareintempoquadratico . . . . . . . . . . . . . . . . . . . . 106
4.1.1 Ordinamentiincrementali . . . . . . . . . . . . . . . . . 106
4.1.2 Ordinamentoabolle . . . . . . . . . . . . . . . . . . . . 109
4.2 Mergesort . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 110
4.3 Heapsort . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 113
4.3.1 Strutturadatiheap . . . . . . . . . . . . . . . . . . . . . 113
4.3.2 Ordinare in loco mediante heap . . . . . . . . . . . . . . 117
4.4 Quicksort . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 118
4.5 Ordinareintempolineare . . . . . . . . . . . . . . . . . . . . . . 121
4.5.1 Integersort . . . . . . . . . . . . . . . . . . . . . . . . . 122
4.5.2 Radixsort . . . . . . . . . . . . . . . . . . . . . . . . . . 123
4.6 Progettomotorediricerca:indiceinverso . . . . . . . . . . . . . 126
4.7 Analisisperimentale . . . . . . . . . . . . . . . . . . . . . . . . 132
4.8 Sommario . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 136
4.9 Esercizi . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 137
5 Selezione
5.1 Selezioneperpiccolivaloridi k . . . . . . . . . . . . . . . . . . 141
5.1.1 Ricercadelsecondominimo . . . . . . . . . . . . . . . . 142
5.1.2 L’algoritmoHeapselect . . . . . . . . . . . . . . . . . . . 143
5.2 Calcolorandomizzatodelmediano . . . . . . . . . . . . . . . . . 144
5.3 Calcolodeterministicodelmediano . . . . . . . . . . . . . . . . 146
5.4 Progettomotorediricerca:ranking . . . . . . . . . . . . . . . . . 151
5.5 Analisisperimentale . . . . . . . . . . . . . . . . . . . . . . . . 157
5.6 Sommario . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 160
5.7 Esercizi . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 160
6 Alberi di ricerca
6.1 Alberibinaridiricerca . . . . . . . . . . . . . . . . . . . . . . . 167
6.2 AlberiAVL . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 177
6.2.1 Ribilanciamentotramiterotazioni . . . . . . . . . . . . . 178
6.2.2 Realizzazionedirotazionisempliciedoppie . . . . . . . . 181
6.2.3 Inserimentiecancellazionidichiavi . . . . . . . . . . . . 185
6.3 Alberi2-3 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 188
6.4 B-alberi . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 193
6.5 Alberi2-3-4ealberirosso-neri . . . . . . . . . . . . . . . . . . . 198
6.6 Analisisperimentale . . . . . . . . . . . . . . . . . . . . . . . . 205
6.7 Sommario . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 212
6.8 Esercizi . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 212
7 Tabelle hash
7.1 Tabelleadaccessodiretto . . . . . . . . . . . . . . . . . . . . . . 217
7.2 Tabellehash............................. 220
7.2.1 Hashingperfetto . . . . . . . . . . . . . . . . . . . . . . 221
7.2.2 Altretecnichedihashing . . . . . . . . . . . . . . . . . . 223
7.3 Listedicollisione . . . . . . . . . . . . . . . . . . . . . . . . . . 227
7.4 Indirizzamentoaperto . . . . . . . . . . . . . . . . . . . . . . . . 231
7.4.1 Funzionidiscansione . . . . . . . . . . . . . . . . . . . . 235
7.4.2 Generazionedinumeriprimi . . . . . . . . . . . . . . . . 239
7.4.3 Cancellazionedichiavi . . . . . . . . . . . . . . . . . . . 240
7.4.4 Analisidelcostodiscansione . . . . . . . . . . . . . . . 243
7.5 Analisisperimentale . . . . . . . . . . . . . . . . . . . . . . . . 244
7.6 Sommario . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 251
7.7 Esercizi . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 253
8 Code con priorita' 255
8.1 d-heap . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 255
8.2 Heapbinomiali . . . . . . . . . . . . . . . . . . . . . . . . . . . 268
8.3 Analisisperimentale . . . . . . . . . . . . . . . . . . . . . . . . 279
8.4 Sommario . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 286
8.5 Esercizi . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 287
9 Union-find
9.1 Approccielementarialproblemaunion-find . . . . . . . . . . . . 294
9.1.1 AlgoritmiditipoQuickFind . . . . . . . . . . . . . . . . 294
9.1.2 AlgoritmiditipoQuickUnion . . . . . . . . . . . . . . . 296
9.2 Bilanciamentonell’operazioneunion . . . . . . . . . . . . . . . . 298
9.2.1 BilanciamentoperalgoritmiditipoQuickFind . . . . . . 299
9.2.2 BilanciamentoperalgoritmiditipoQuickUnion . . . . . 301
9.3 Euristichedicompressionenell’operazionefind . . . . . . . . . . 306
9.4 Analisisperimentale . . . . . . . . . . . . . . . . . . . . . . . . 309
9.5 Sommario . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 315
9.6 Esercizi . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 316
10 Grafi e visite di grafi
10.1 Definizionipreliminarisuigrafi . . . . . . . . . . . . . . . . . . . 321
10.2 Tipodidatografo . . . . . . . . . . . . . . . . . . . . . . . . . . 323
10.3 Strutturedatiperrappresentaregrafi . . . . . . . . . . . . . . . . 327
10.3.1 Listadiarchi . . . . . . . . . . . . . . . . . . . . . . . . 327
10.3.2 Listediadiacenza . . . . . . . . . . . . . . . . . . . . . . 329
10.3.3 Matricediadiacenza . . . . . . . . . . . . . . . . . . . . 336
10.3.4 Matricediincidenza . . . . . . . . . . . . . . . . . . . . 337
10.4 Visitedigrafi . . . . . . . . . . . . . . . . . . . . . . . . . . . . 338
10.5 Visitainampiezza . . . . . . . . . . . . . . . . . . . . . . . . . . 344
10.6 Visitainprofondit`a ......................... 351
10.7 Progettomotorediricerca:crawling . . . . . . . . . . . . . . . . 359
10.8 Analisisperimentale . . . . . . . . . . . . . . . . . . . . . . . . 364
10.9 Sommario . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 367
10.10 Esercizi . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 368
11 Minimo albero ricoprente
11.1 Propriet`a deiminimialberiricoprenti . . . . . . . . . . . . . . . . 372
11.2 AlgoritmodiKruskal . . . . . . . . . . . . . . . . . . . . . . . . 374
11.2.1 Implementazionemedianteunion-find . . . . . . . . . . . 375
11.3 AlgoritmodiPrim . . . . . . . . . . . . . . . . . . . . . . . . . . 379
11.3.1 Implementazionemediantecodeconpriorit`a ....... 382
11.4 Progettomotorediricerca:clustering . . . . . . . . . . . . . . . 386
11.5 Sommario . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 391
11.6 Esercizi . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 392
12 Cammini minimi
12.1 Camminiminimiedistanzeinungrafo . . . . . . . . . . . . . . 395
12.2 Latecnicadelrilassamento . . . . . . . . . . . . . . . . . . . . . 398
12.3 AlgoritmodiBellman,FordeMoore . . . . . . . . . . . . . . . . 399
12.3.1 Implementazionemediantecoda . . . . . . . . . . . . . . 400
12.4 AlgoritmodiDijkstra . . . . . . . . . . . . . . . . . . . . . . . . 404
12.4.1 Implementazionemediantecodeconpriorit`a ....... 407
12.5 AlgoritmodiFloydeWarshall . . . . . . . . . . . . . . . . . . . 412
12.6 Progettomotorediricerca:crawling . . . . . . . . . . . . . . . . 414
12.7 Analisisperimentale . . . . . . . . . . . . . . . . . . . . . . . . 416
12.8 Sommario . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 418
12.9 Esercizi . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 419
Bibliografia 421
|
|
|
|
