eBook Gratis

Tra gli argomenti trattati:

• Array, liste concatenate, stringhe, alberi e le altre principali strutture dati
• Approfondimenti sugli ADT e sulla programmazione orientata agli oggetti
• Estensiva trattazione di algoritmi relativi a ordinamento, selezione, ADT coda con priorita', ADT tabella di simboli
• Implementazioni complete relative a: code binomiali, ordinamento digitale a piu' vie, alberi di ricerca binari randomizzati, alberi splay, skip list, trie a piu' vie e altro ancora
• oltre 1000 nuovi esercizi per aiutare gli studenti ad apprendere meglio le proprieta' degli algoritmi

Fondamenti

Capitolo 1. Introduzione
1.1 Algoritmi
1.2 Un esempio: il problema della connettivita'
1.3 Algoritmi union-find
1.4 Prospettive
1.5 Sommario degli argomenti

Capitolo 2. Principi di progettazione degli algoritmi
2.1 Implementazioni e analisi empiriche
2.2 Analisi degli algoritmi
2.3 Velocita' di crescita delle funzioni
2.4 Notazione O grande
2.5 Ricorrenze fondamentali
2.6 Esempi di analisi di algoritmi
2.7 Tempo garantito, tempo stimato e limitazioni

Strutture dati

Capitolo 3. Strutture dati elementari
3.1 Costrutti di base
3.2 Array
3.3 Liste concatenate
3.4 Elaborazione elementare di liste
3.5 Allocazione di memoria per liste
3.6 Stringhe
3.7 Strutture dati composte

Capitolo 4. Tipi di dati astratti
4.1 Collezioni di oggetti
4.2 Tipo di dato astratto stack
4.3 Esempi di client dell'ADT stack
4.4 Implementazione dell'ADT stack
4.5 Implementazioni generiche
4.6 Creazione di nuovi ADT
4.7 Code FIFO e code generalizzate
4.8 Elementi duplicati ed elementi indice
4.9 ADT di prima categoria
4.10 Esempio di ADT basato su applicazioni
4.11 Prospettive

Capitolo 5. Ricorsione e alberi
5.1 Algoritmi ricorsivi
5.2 Divide et impera
5.3 Programmazione dinamica
5.4 Alberi
5-5 Proprieta' matematiche degli alberi binari
5-6 Attraversamento di alberi
5.7 Algoritmi ricorsivi su alberi binari
5.8 Attraversamento di grafi
5.9 Prospettive

Ordinamento

Capitolo 6. Metodi di ordinamento elementari
6.1 Regole del gioco
6.1 Implementazioni generiche di algoritmi di ordinamento
6.3 Ordinamento per selezione
6.4 Ordinamento per inserzione
6.5 Bubble sort
6.6 Prestazioni degli ordinamenti elementari
6.7 Visualizzazione di algoritmi
6.8 Shellsort
6.9 Ordinamento di liste concatenate
6.10 Indicizzazione con chiavi

Capitolo 7. Quicksort
7.1 L'algoritmo di base
7.2 Descrizione delle prestazioni del Quicksort
7.3 Dimensione dello stack
7.4 File parziali di piccole dimensioni
7.5 Partizionamento col metodo della mediana fra tre elementi
7.6 Chiavi duplicate
7-7 Stringhe e vettori
7.8 Selezione

Capitolo 8. Merging e Mergesort
8.1 Merging a due vie
8.2 Merging astratto sul posto
8.3 Mergesort top-down
8.4 Miglioramenti dell'algoritmo di base
8.5 Mergesort bottom-up
8.6 Descrizione delle prestazioni del Mergesort
8.7 Implementazione del Mergesort su liste concatenate
8.8 Rivisitazione della ricorsione

Capitolo 9. Code con priorita' e Heapsort
9.1 Implementazioni elementari
9.2 La struttura dati heap
9.3 Algoritmi su heap
9.4 Heapsort
9.5 ADT coda con priorita'
9.6 Code con priorita' per array di programmi client
9.7 Code binomiali

Capitolo 10. Ordinamento digitale
10.1 Bit, byte e parole
10.2 Quicksort binario
10.3 Ordinamento digitale MSD
10.4 Quicksort digitale a tre vie
10.5 Ordinamento digitale LSD
10.6 Descrizione delle prestazioni degli ordinamenti digitali
10.7 Ordinamenti sublineari

Capitolo 11. Metodi speciali di ordinamento
11.1 Mergesort odd-even di Batcher
11.2 Reti di ordinamento
11.3 Ordinamento sul posto
11.4 Ordinamento esterno
11.5 Implementazioni del sort-merge
11.6 Sort-merge parallelo

Ricerca

Capitolo 12. Tabelle di simboli e alberi binari di ricerca
12.1 Tipo di dato astratto tabella di simboli
12.2 Ricerca indicizzata da chiave
12.3 Ricerca sequenziale
12.4 Ricerca binaria
12.5 Implementazione di indici con tabelle di simboli
12.6 Alberi binari di ricerca (BST)
12.7 Prestazioni dei BST
12.8 Inserimento alla radice in un BST
12.9 Implementazione tramite BST di altre funzioni

Capitolo 13. Alberi bilanciati
13.1 BST randomizzati
13.2 Splay BST
13.3 Alberi 2-3-4 top-down
13.4 Alberi red-black
13.5 Skip list
13.6 Studio delle prestazioni

Capitolo 14. Hashing
14.1 Funzioni di hash
14.2 Concatenazioni separate
14.3 Scansione lineare
14.4 Hashing doppio
14.5 Tabelle hash dinamiche
14.6 Prospettive

Capitolo 15. Ricerca digitale
15.1 Alberi di ricerca digitale
15.2 Trie
15.3 Trie patricia
15.4 Trie a piu' vie e TST
15.5 Algoritmi per indici di stringhe di testo

Capitolo 16. Ricerca esterna
16.1 Regole del gioco
16.2 Accesso sequenziale indicizzato
16.3 B alberi
16.4 Hashing estendibile
16.5 Prospettive

Appendice

Indice