Programma del corso di Algoritmi I (Informatica, A.A. 2008-2009)
Se non diversamente specificato, i riferimenti bibliografici sono relativi al libro di testo "Algoritmi e strutture dati", 2/ed. Demetrescu, Finocchi, Italiano, McGraw-Hill, 2008.
a) Introduzione
- Progettazione ed analisi di algoritmi
- verifica di correttezza
- analisi del tempo di esecuzione
- analisi dell'occupazione di memoria
- Un esempio "giocattolo": il calcolo dei numeri di Fibonacci
- Un secondo esempio: ricerca di duplicati.
Rif. Capitolo 1: tutto. Paragrafi 1.1, 1.2 e 1.3 del libro [DFFI07].
b) Metodologie di analisi
- Ordine di grandezza delle funzioni, la notazione asintotica O, Omega, Theta
- Algebra della notazione asintotica; analisi delle costanti additive e moltiplicative
- Delimitazioni inferiori e superiori alla complessitā di un problema rispetto ad una data risorsa di calcolo
- Analisi nel caso peggiore e migliore
- Analisi di algoritmi ricorsivi:
- equazioni di ricorrenza, albero della ricorsione
- risoluzione di ricorrenze tramite analisi dell'albero della ricorsione
- metodo dell'iterazione
- metodo della sostituzione
- il teorema fondamentale delle ricorrenze (teorema master): enunciato ed esempi.
Rif. Capitolo 2: paragrafi 2.2, 2.3, 2.4 (tranne caso medio), 2.5. Appendice: paragrafi 17.1, 17.2, 17.3, 17.4
c) Algoritmi di ricerca e di ordinamento
- Ricerca sequenziale e binaria: analisi nel caso peggiore e migliore.
- Delimitazione inferiore al tempo di esecuzione di algoritmi di ordinamento basati su confronti: alberi di decisione
- Algoritmi di ordinamento quadratici (con analisi nel caso peggiore): insertionSort, selectionSort, bubbleSort
- Un algoritmo di ordinamento ottimo basato sulla tecnica del divide et impera (con analisi nel caso peggiore): mergeSort
- Un algoritmo di ordinamento ottimo basato sull'uso di strutture dati efficienti (con analisi nel caso peggiore): heapSort
- la struttura dati heap
- cancellazione del minimo e costruzione di un heap in tempo lineare
- rappresentazione posizionale di alberi binari
- ordinamento in loco
- Un algoritmo efficiente nel caso medio: quickSort (analisi nel caso peggiore, intuizione caso medio)
- Il concetto di stabilitā nell'ordinamento.
- Ordinamento in tempo lineare: algoritmi intergerSort e bucketSort
Rif. Capitolo 2: paragrafo 2.4 (tranne caso medio). Capitolo 4: tutto tranne paragrafo 4.7. Appendice: paragrafi 17.3 e 17.4. Paragrafi 7.1, 7.2 e 7.4.1 del libro [CLRS01].
d) Dizionari
- Implementazioni banali: array ordinati e liste collegate
- Alberi binari di ricerca:
- operazioni search, insert, delete
- ricerca del massimo, del minimo, del predecessore e del successore
- Bilanciamento in altezza: alberi AVL
- calcolo del fattore di bilanciamento
- limitazione superiore all'altezza di un albero AVL
- rotazioni semplici e doppie
- mantenimento del bilanciamento durante inserimenti e cancellazioni
Rif. Capitolo 3: paragrafo 3.1. Capitolo 6: paragrafi 6.1 e 6.2.
e) Alberi e grafi
- Alberi
- rappresentazioni indicizzate
- rappresentazioni collegate
- visite
- I grafi come tipi di dati astratti
- Definizioni e proprietā fondamentali
- Rappresentazioni in memoria
- matrice di adiacenza
- liste di adiacenza
- matrice di incidenza
- lista di archi
- Algoritmo di visita generica di un grafo
- albero di copertura generato da una visita
- analisi del tempo di esecuzione in funzione della rappresentazione usata
- Algoritmi di visita in ampiezza e in profonditā (sia per grafi orientati che non)
- implementazione ricorsiva della visita in profonditā
- implementazioni iterative di entrambe le visite basate su code e pile
- proprietā degli alberi di copertura ottenuti dalle visite
- partizione degli archi indotta dalle visite
- Calcolo delle componenti connesse in grafi non orientati
Rif. Capitolo 3: paragrafo 3.3. Capitolo 12: tutto tranne paragrafo 12.5. Appendice: paragrafo 17.5.1