|
|
CONSIGLIATO DA LIBRINFORMATICA
Introduzione agli algoritmi e strutture dati - seconda edizione
|
| Editore | Mc Graw Hill |
| Autore | Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein |
| Titolo originale | Introduction to Algorithms, Second Edition |
| Editore originale | MIT Press |
| Pagine | 984 |
| Volumi | 1 |
| Livello | Intermedio-Avanzato |
| Lingua | Italiano |
| Data pubblicazione | 05 - 2005 |
| ISBN | 8838662517 |
|
|
| Prezzo di copertina |
| Euro 55,00 |
|
Indice
Prefazione xi
Presentazione dell’edizione italiana xv
I Fondamenti
Introduzione 3
1 Ruolo degli algoritmi nell’elaborazione dei dati 5
1.1 Algoritmi 5
1.2 Algoritmi come tecnologia 9
2 Per incominciare 13
2.1 Insertion sort 13
2.2 Analisi degli algoritmi 18
2.3 Progettare gli algoritmi 24
3 Crescita delle funzioni 35
3.1 Notazione asintotica 35
3.2 Notazioni standard e funzioni comuni 43
4 Ricorrenze 52
4.1 Il metodo di sostituzione 53
4.2 Il metodo dell’albero di ricorsione 56
4.3 Il metodo dell’esperto 61
4.4 Dimostrazione del teorema dell’esperto 63
5 Analisi probabilistica e algoritmi randomizzati 76
5.1 Il problema delle assunzioni 76
5.2 Variabili casuali indicatrici 79
5.3 Algoritmi randomizzati 82
5.4 Approfondimento dell’analisi probabilistica 88
II Ordinamento e statistiche d’ordine
Introduzione 103
6 Heapsort 106
6.1 Heap 106
6.2 Conservare la propriet`a dell’heap 108
6.3 Costruire un heap 110
6.4 L’algoritmo heapsort 113
6.5 Code di priorit`a 114
vi Indice
7 Quicksort 121
7.1 Descrizione di quicksort 121
7.2 Prestazioni di quicksort 124
7.3 Una versione randomizzata di quicksort 128
7.4 Analisi di quicksort 129
8 Ordinamento in tempo lineare 138
8.1 Limiti inferiori per l’ordinamento 138
8.2 Counting sort 140
8.3 Radix sort 143
8.4 Bucket sort 145
9 Mediane e statistiche d’ordine 153
9.1 Minimo e massimo 153
9.2 Selezione in tempo atteso lineare 155
9.3 Selezione in tempo lineare nel caso peggiore 158
III Strutture dati
Introduzione 165
10 Strutture dati elementari 168
10.1 Stack e code 168
10.2 Liste concatenate 171
10.3 Implementare puntatori e oggetti 175
10.4 Rappresentazione di alberi radicati 179
11 Hashing 186
11.1 Tavole a indirizzamento diretto 186
11.2 Tavole hash 188
11.3 Funzioni hash 193
11.4 Indirizzamento aperto 200
11.5 Hashing perfetto 207
12 Alberi binari di ricerca 214
12.1 Che cos’`e un albero binario di ricerca? 214
12.2 Interrogazione di un albero binario di ricerca 216
12.3 Inserimento e cancellazione 220
12.4 Alberi binari di ricerca costruiti in modo casuale 223
13 Alberi rosso-neri 231
13.1 Propriet`a degli alberi rosso-neri 231
13.2 Rotazioni 234
13.3 Inserimento 236
13.4 Cancellazione 243
14 Aumentare le strutture dati 255
14.1 Statistiche d’ordine dinamiche 255
14.2 Come aumentare una struttura dati 260
14.3 Alberi di intervalli 263
Indice vii
IV Tecniche avanzate di progettazione e di analisi
Introduzione 271
15 Programmazione dinamica 273
15.1 Programmazione delle catene di montaggio 274
15.2 Moltiplicare una sequenza di matrici 280
15.3 Elementi della programmazione dinamica 287
15.4 La pi`u lunga sottosequenza comune (LCS) 297
15.5 Alberi binari di ricerca ottimi 302
16 Algoritmi golosi 315
16.1 Problema della selezione di attivit`a 316
16.2 Elementi della strategia golosa 323
16.3 I codici di Huffman 328
16.4 Fondamenti teorici dei metodi golosi 335
16.5 Un problema di programmazione dei lavori 340
17 Analisi ammortizzata 346
17.1 Il metodo dell’aggregazione 347
17.2 Il metodo degli accantonamenti 350
17.3 Il metodo del potenziale 352
17.4 Tavole dinamiche 356
V Strutture dati avanzate
Introduzione 369
18 B-alberi 372
18.1 Definizione dei B-alberi 375
18.2 Operazioni fondamentali con i B-alberi 378
18.3 Cancellare una chiave da un B-albero 384
19 Heap binomiali 390
19.1 Alberi binomiali ed heap binomiali 391
19.2 Operazioni con gli heap binomiali 395
20 Heap di Fibonacci 408
20.1 Struttura degli heap di Fibonacci 409
20.2 Operazioni con heap riunibili 411
20.3 Diminuire il valore di una chiave e cancellare un nodo 419
20.4 Limitare il grado massimo 422
21 Strutture dati per insiemi disgiunti 427
21.1 Operazioni con gli insiemi disgiunti 427
21.2 Rappresentazione di insiemi disgiunti tramite liste concatenate 430
21.3 Foreste di insiemi disgiunti 433
21.4 Unione per rango con compressione del cammino 436
viii Indice
VI Algoritmi per grafi
Introduzione 449
22 Algoritmi elementari per grafi 451
22.1 Rappresentazione dei grafi 451
22.2 Visita in ampiezza 454
22.3 Visita in profondit`a 462
22.4 Ordinamento topologico 470
22.5 Componenti fortemente connesse 472
23 Alberi di connessione minimi 480
23.1 Creare un albero di connessione minimo 481
23.2 Gli algoritmi di Kruskal e Prim 485
24 Cammini minimi da sorgente unica 496
24.1 Definizioni e propriet`a dei cammini mimini 496
24.2 L’algoritmo di Bellman-Ford 503
24.3 Cammini minimi da sorgente unica nei grafi orientati aciclici 506
24.4 Algoritmo di Dijkstra 509
24.5 Vincoli sulle differenze e cammini minimi 514
24.6 Dimostrazione delle propriet`a dei cammini minimi 519
25 Cammini minimi fra tutte le coppie 530
25.1 Introduzione 530
25.2 Cammini minimi e moltiplicazione di matrici 532
25.3 Algoritmo di Floyd-Warshall 537
25.4 Algoritmo di Johnson per i grafi sparsi 543
26 Flusso massimo 550
26.1 Reti di flusso 551
26.2 Il metodo di Ford-Fulkerson 557
26.3 Abbinamento massimo nei grafi bipartiti 568
26.4 Algoritmi push-relabel 572
26.5 Algoritmo relabel-to-front 582
VII Argomenti scelti
Introduzione 601
27 Reti di ordinamento 604
27.1 Reti di confronto 604
27.2 Il principio zero-uno 608
27.3 Una rete di ordinamento bitonico 611
27.4 Una rete di fusione 614
27.5 Una rete di ordinamento 616
28 Operazioni con le matrici 621
28.1 Propriet`a delle matrici 621
28.2 Algoritmo di Strassen per il prodotto di matrici 629
28.3 Risoluzione dei sistemi di equazioni lineari 635
28.4 Inversione di matrici 646
28.5 Matrici simmetriche e definite positive e minimi quadrati 651
Indice ix
29 Programmazione lineare 660
29.1 Introduzione 660
29.2 Le forme standard e slack 666
29.3 Formulare i problemi come programmi lineari 673
29.4 L’algoritmo del simplesso 678
29.5 Dualit`a 690
29.6 La soluzione di base iniziale ammissibile 695
30 Polinomi e FFT 705
30.1 Rappresentazione dei polinomi 707
30.2 DFT e FFT 712
30.3 Implementazioni efficienti della FFT 719
31 Algoritmi di teoria dei numeri 728
31.1 Concetti elementari di teoria dei numeri 729
31.2 Massimo comun divisore 734
31.3 Aritmetica modulare 739
31.4 Risolvere le equazioni lineari modulari 744
31.5 Il teorema cinese del resto 747
31.6 Potenze di un elemento 751
31.7 Crittografia a chiave pubblica RSA 754
31.8 Test di primalit`a 760
31.9 Scomposizione di un numero intero in fattori primi 768
32 String matching 776
32.1 Introduzione 776
32.2 L’algoritmo ingenuo di string matching 778
32.3 Algoritmo di Rabin-Karp 780
32.4 String matching con automi a stati finiti 784
32.5 Algoritmo di Knuth-Morris-Pratt 789
33 Geometria computazionale 797
33.1 Propriet`a dei segmenti di retta 797
33.2 Verificare se qualche coppia di segmenti si interseca 803
33.3 Trovare l’involucro convesso 809
33.4 Trovare la coppia di punti pi`u vicini 817
34 NP-Completezza 825
34.1 Introduzione 825
34.2 Tempo polinomiale 830
34.3 Verifica in tempo polinomiale 836
34.4 NP-completezza e riducibilit`a 840
34.5 Dimostrazioni della NP-completezza 849
34.6 Problemi NP-completi 856
35 Algoritmi di approssimazione 873
35.1 Il problema della copertura di vertici 875
35.2 Il problema del commesso viaggiatore 877
35.3 Il problema della copertura di insiemi 883
35.4 Randomizzazione e programmazione lineare 887
35.5 Il problema della somma di sottoinsieme 891
x Indice
VIII Appendici: prerequisiti matematici
Introduzione 903
A Sommatorie 904
A.1 Formule e propriet`a delle sommatorie 904
A.2 Limitare le sommatorie 907
B Insiemi e altro 914
B.1 Insiemi 914
B.2 Relazioni 918
B.3 Funzioni 920
B.4 Grafi 922
B.5 Alberi 926
C Calcolo combinatorio e delle probabilit`a 934
C.1 Calcolo combinatorio 934
C.2 Probabilit`a 939
C.3 Variabili casuali discrete 944
C.4 Distribuzioni geometriche e binomiali 949
C.5 Le code della distribuzione binomiale 954
Bibliografia
Indice analitico
|
|
|
|
