Analisi asintotica della complessità di calcolo
Discussione delle problematiche relative alla valutazione dell'efficienza di programmi/algoritmi:
indipendenza dalle caratteristiche della macchina; tempo di calcolo in funzione della dimensione
dell'input; analisi nei casi migliore, peggiore e medio.
Ordini asintotici O(f(n)), Ω(f(n)) e Θ(f(n)) e loro proprietà.
Analisi asintotica della complessità di algoritmi ricorsivi.
Equazioni di ricorrenza: risoluzione tramite iterazione; albero di ricorsione.
Teorema fondamentale delle ricorrenze (solo enunciato).
Algoritmi di ordinamento
Algoritmo di ordinamento
merge-sort: descrizione e analisi della complessità.
Algoritmo di ordinamento
quick-sort: descrizione, analisi della complessità nei
casi migliore e peggiore, cenni sulla complessità nel caso medio.
Delimitazione inferiore sul numero di confronti per algoritmi di ordinamento basati
su confronti: albero delle decisioni.
Counting-sort: descrizione ed analisi.
L'algoritmo di ordinamento
heap-sort: analisi della complessità.
Strutture dati basate su alberi
Definizioni e proprietà di
alberi: ordine, altezza e numero di nodi. Alberi ordinati e non.
Alberi binari. Rappresentazione di un albero
m-ario tramite un albero binario.
Rappresentazione in memoria di alberi: strutture linkate e vettore dei padri.
Visite di alberi.
Struttura dati
heap. Descrizione delle operazioni di inserimento, estrazione
del massimo, modifica e cancellazione. Analisi della complessità.
Implementazione di una
coda con priorità tramite heap: confronto con
implementazioni tramite liste e vettori.
Alberi binari di ricerca. Operazioni di ricerca, inserimento e rimozione: analisi
della complessità e implementazione.
Alberi binari di ricerca bilanciati:
alberi AVL. Dimostrazione che un albero
AVL ha altezza O(log
n). Operazioni di rotazione. Procedura di ribilanciamento
a seguito di un inserimento: descrizione e dimostrazione di correttezza.
Procedura di ribilanciamento a seguito di una rimozione: descrizione e
dimostrazione di correttezza.
Implementazione di
Dizionari tramite strutture dati basate su alberi: confronto
con implementazioni tramite vettori e liste, ordinati e non.
Tabelle Hash
Universo delle chiavi e funzioni hash. Il problema delle collisioni. Hashing con liste di trabocco
(o liste di collisione). Cenni sulla complessità nel caso ideale. Hashing interno
(o indirizzamento aperto): sequenze di scansione, scansione lineare (fenomeni di agglomerazione)
e hashing doppio. Operazione di eliminazione. Cenni sulla complessità nel caso ideale.
Implementazione di Dizionari tramite tabelle hash: confronto con
implementazioni tramite alberi.
Grafi
Definizioni di base: grafi diretti e non diretti, adiacenza, grado, cammini e cicli.
Connessione: componenti connesse. Visite di grafi: visita in profondità e visita in ampiezza.
Uso delle visite per determinare le componenti connesse di grafi non diretti. Alberi di visita.
Rappresentazioni di grafi: liste di adiacenza e matrici di adiacenza.
Uso della visita in ampiezza per trovare i cammini minimi.