Introduzione agli Algoritmi a.a. 2008-2009 (canale P-Z)

Si presuppongono una conoscenza di base di analisi matematica (studio di funzioni ed equazioni numeriche) ed una buona conoscenza di un linguaggio di programmazione come C, Java o C++. Non ci sono propedeuticità. Tuttavia è consigliabile aver superato, o almeno frequentato, il corso di Fondamenti di Programmazione.

Strutture dati fondamentali (pile, code, code con priorità). Principali algoritmi di ordinamento e ricerca. Alberi binari di ricerca e tabelle hash: rappresentazione in memoria e algoritmi per la ricerca, la cancellazione e l'inserimento di un elemento. Metodi per l'analisi asintotica delle risorse di calcolo utilizzate da algoritmi iterativi e ricorsivi.

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(logn). 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.

• C. Demetrescu, I. Finocchi, G.F. Italiano, Algoritmi e Strutture Dati, Mc Graw Hill, seconda edizione, 2008.
• T.H. Cormen, C.E. Leiserson, R.L. Rivest e C. Stein, Introduction to Algorithms, second edition, MIT Press e Mc Graw Hill, 2001.