-
28 settembre 2017 - Lezione 1
Presentazione del corso. Introduzione. Il concetto di algoritmo.
-
29 settembre 2017 - Lezione 2
Algoritmi e programmi. Sintesi e analisi di algoritmi.
Alcuni semplici esempi.
-
2 ottobre 2017 - Lezione 3
Esempio: differenti algoritmi per calcolo dei numeri di Fibonacci
(mediante formula di Binet, algoritmo ricorsivo, algoritmo iterativo).
Discussione sui tempi di calcolo e sulla quantità di memoria
utilizzati dagli algoritmi presentati.
-
5 ottobre 2017 - Lezione 4
Calcolo dei numeri di Fibonacci utilizzando le potenze di matrici.
Confronto tra i vari algoritmi presentati per i numeri di Fibonacci.
La macchina RAM: introduzione.
Materiale di riferimento per le lezioni 1-4:
[DFI, capitolo 1], [BG, capitolo 1]
-
6 ottobre 2017 - Lezione 5
La macchina RAM e il suo linguaggio. Esempi.
-
9 ottobre 2017 - Lezione 6
La macchina RAM e il suo linguaggio: ulteriori esempi.
Criterio di costo uniforme e logaritmico.
Richiami sulle principali notazioni asintotiche.
Analisi di algoritmi: caso peggiore e caso medio.
Materiale di riferimento per le lezioni 5 e 6:
Per la macchina RAM e i criteri di costo si veda
[BG, paragrafo 3.1] e [DFI,
paragrafo 2.1].
Per le notazioni asintotiche si veda [DFI,
paragrafo 2.2]. Il capitolo 2 di [BG] è
un utile riferimento per molte delle nozioni matematiche utilizzate nel corso.
-
12 ottobre 2017 - Lezione 7
Costo di algoritmi e complessità di problemi:
delimitazioni inferiori e superiori.
Tempo polinomiale rispetto a tempo esponenziale.
Ricerca sequenziale. Ricerca dicotomica (o binaria) ricorsiva.
Evoluzione dello stack.
Ricerca dicotomica iterativa.
Ricerca in un array: pseudocodice.
Materiale di riferimento per la lezione 7:
[DFI,
paragrafi 2.3 e 2.4], [BG, paragrafi 1.2 e 1.3]
-
13 ottobre 2017 - Lezione 8
Il problema dell'ordinamento: introduzione.
Ordinamento interno ed esterno.
Alcune tecniche di ordinamento elementari:
per selezione (Selection sort),
per inserimento (Insertion sort),
"a bolle" (Bubble sort).
Ordinamenti elementari: pseudocodice.
Materiale di riferimento relativo alle tecniche elementari di ordinamento:
[DFI, introduzione del capitolo 4 e paragrafo 4.2]
Alcuni esercizi relativi
alle tecniche elementari di ordinamento.
-
19 ottobre 2017 - Lezione 9
Merge di due array ordinati. Calcolo del numero di confronti.
Ordinamento per fusione (mergesort).
Numero di confronti, tempo di calcolo, spazio utilizzato, altezza
dello stack.
Merge e mergesort: pseudocodice.
Materiale di riferimento:
[DFI, paragrafo 4.4]
-
23 ottobre 2017 - Lezione 10
L'algoritmo di ordinamento quicksort. Calcolo del numero di confronti
nel caso peggiore, migliore e in media.
Materiale di riferimento relativo a quicksort:
[DFI, paragrafo 4.5].
-
26 ottobre 2017 - Lezione 11
Quicksort: stima dello spazio utilizzato e dell'altezza dello stack.
Modifica dell'algoritmo per ridurre l'altezza dello stack.
Tecnica divide-et-impera. Schema generale. Esempio: calcolo del minimo
e del massimo in un array. Calcolo del numero di confronti.
Quicksort: pseudocodice.
Materiale di riferimento relativo all'uso dello stack in quicksort:
Una discussione sull'uso dello
spazio utilizzato e sulla sua riduzione (con alcune differenze rispetto
a quella presentata a lezione) si trova in
[BG, paragrafo 8.5.3].
Materiale di riferimento relativo alla tecnica divide-et-impera:
[DFI, paragrafo 10.1], si consiglia di consultare
anche [BG, capitolo 10]
-
27 ottobre 2017 - Lezione 12
Tecnica divide-et-impera. Esempio: calcolo del prodotto di matrici
quadrate con il metodo di Strassen.
Equazioni divide-et-impera: il teorema fondamentale delle ricorrenze.
Materiale di riferimento relativo al teorema fondamentale
delle ricorrenze:
A lezione il risultato è stato presentato nella forma
semplificata data in [BG, paragrafo 6.4].
Una versione più generale è data in
[DFI, paragrafo 2.5.3].
Per vari esempi di soluzione di equazioni di ricorrenza ottenute
nell'analisi di algoritmi ricorsivi si consiglia
[DFI, paragrafo 2.5].
Alcuni esercizi relativi
alla tecnica divide-et-impera.
-
30 ottobre 2017 - Lezione 13
Tipi di dati. Tecniche per la rappresentazione di collezioni di dati: strutture
indicizzate e strutture collegate. Liste concatenate e loro
manipolazione (ricerca in liste non ordinate; ricerca, inserimento e
cancellazione in liste ordinate).
Implementazione di liste mediante array e mediante puntatori.
-
2 novembre 2017 - Lezione 14
Pile: operazioni fondamentali. Implementazione di pile mediante array.
Implementazione di pile mediante liste concatenate.
Code: operazioni fondamentali. Implementazione di code mediante array
(cenni). Implementazione di code mediante liste.
Strutture ad albero: introduzione e nomenclatura.
Rappresentazioni indicizzate e collegate di strutture ad albero.
Visite di alberi: schema di visita generica, visita in ampiezza, visita
in profondità.
Materiale di riferimento per le lezioni 13 e 14:
Una presentazione generale degli argomenti si trova in [DFI, capitolo 3]. I dettagli relativi alle
operazioni sulle liste concatenate e all'implementazione di pile e
code mediante liste si possono trovare in [PF,
capitolo 13 (capitolo 11 o 12 nelle edizioni precedenti)] e in
[BG, capitolo 4].
-
3 novembre 2017 - Lezione 15
Alberi binari. Definizione ricorsiva. Visite in ordine anticipato,
simmetrico, posticipato.
Rappresentazione di alberi generici mediante alberi binari.
Rappresentazione di alberi binari mediante nodi con riferimenti ai
figli sinistro e destro.
Esempi. Alberi binari di ricerca: introduzione.
-
6 novembre 2017 - Lezione 16
Alberi binari di ricerca. Ricerca, inserimento e cancellazione in
alberi binari di ricerca.
Alberi binari di ricerca: pseudocodice.
-
9 novembre 2017 - Lezione 17
Alberi di ricerca: profondità minima e massima di un albero
contenente n chiavi. Tempo per ricerca, inserimento e cancellazione in
alberi di ricerca.
Alberi perfettamente bilanciati. Alberi bilanciati (AVL). Profondità
minima e massima. Alberi di Fibonacci.
Ricerca e inserimento in alberi AVL.
Confronto tra array ordinati, alberi di ricerca, alberi AVL.
Alberi 2-3 (introduzione).
Materiale di riferimento relativo agli alberi:
[DFI, paragrafo 3.3, capitolo 6 (in particolare
paragrafi 6.2, 6.4, 6.5)].
Alcuni esercizi relativi
agli alberi binari.
-
10 novembre 2017 - Lezione 18
Alberi 2-3: ricerca, inserimento e cancellazione.
Dizionari in memoria secondaria. B-alberi: definizione ed esempi.
Ricerca di un elemento in un B-albero.
-
13 novembre 2017 - Lezione 19
B-alberi: analisi dell'operazione di ricerca (stima del numero di confronti,
stima del numero di accessi a memoria secondaria).
Inserimento e cancellazione in B-alberi.
La struttura dati heap. Rimozione del massimo da uno heap e
risistemazione dello heap. Costruzione top-down di uno heap
a partire da un albero binario.
-
16 novembre 2017 - Lezione 20
Costruzione bottom-up di uno heap.
L'algoritmo di ordinamento heapsort. Calcolo del numero di confronti.
Rappresentazione implicita di un albero binario "quasi completo"
mediante vettore posizionale. L'algoritmo heapsort per l'ordinamento
in loco di un vettore.
Heapsort: pseudocodice.
Materiale di riferimento relativo a heapsort:
[DFI, paragrafo 4.3].
Alcuni esercizi relativi agli
alberi 2-3, B-alberi, heapsort.
-
16 novembre 2017 - Lezione 21
Riepilogo e confronto tra gli algoritmi di ordinamento basati su
confronti tra chiavi (numero di confronti nel caso peggiore, utilizzo della
memoria per eventuali strutture ausiliarie o ricorsione).
Limitazione inferiore al numero di confronti effettuati nel caso peggiore
da ogni algoritmo di ordinamento basato su confronti tra chiavi.
Metodi di ordinamento non basati su confronti tra chiavi
(introduzione): integersort.
Materiale di riferimento relativo alla limitazione inferiore al numero di
confronti:
[DFI, paragrafo 4.1].
-
20 novembre 2017 - Lezione 22
Metodi di ordinamento non basati su confronti diretti tra chiavi.
Bucketsort. Radixsort.
Ordinamenti non basati su confronti: pseudocodice.
Materiale di riferimento relativo agli algoritmi di ordinamento non
basati su confronti tra chiavi:
[DFI, paragrafi 4.6 e 4.7].
Alcuni esercizi relativi agli
algoritmi di ordinamento.
-
23 novembre 2017 - Lezione 23
Cenni all'analisi ammortizzata di algoritmi.
Union-find. Algoritmi di tipo QuickFind a di tipo QuickUnion.
QuickFind con bilanciamento nell'operazione union. QuickUnion con
bilanciamento in altezza nell'operazione union. QuickUnion con
bilanciamento in altezza nell'operazione union e compressione di
cammino nell'operazione find.
Materiale di riferimento:
Introduzione all'analisi ammortizzata di algoritmi:
[DFI, prima parte del paragrafo 2.7].
Union-find: [DFI, capitolo 9].
Alcuni esercizi relativi agli
algoritmi union-find.
-
24 novembre 2017 - Lezione 24
Grafi. Introduzione e definizioni fondamentali.
-
27 novembre 2017 - Lezione 25
Rappresentazione di grafi: lista di archi, liste di adiacenza, liste
di incidenza, matrice di adiacenza, matrice di incidenza.
Attraversamento di grafi: visita in ampiezza e visita in
profondità ricorsiva. Stima del tempo utilizzato per le visite
in base alla rappresentazione del grafo utilizzata.
Visite a grafi: pseudocodice.
Materiale di riferimento relativo ai grafi (lezioni 24 e 25):
[DFI, paragrafi 12.1, 12.2, 12.3].
-
30 novembre 2017 - Lezione 26
L'algoritmo di Kruskal per determinare il minimo albero ricoprente.
Correttezza dell'algoritmo di Kruskal. Implementazione mediante
union-find. Complessità in tempo. L'algoritmo di Prim.
Materiale di riferimento relativo al minimo albero ricoprente:
[DFI, introduzione del capitolo 13, paragrafi 13.1,
13.2 (tutto), 13.3 (prima parte)].
Alcuni esercizi relativi ai grafi.
-
1 dicembre 2017 - Lezione 27
Problemi di ottimizzazione e tecnica greedy.
Materiale di riferimento relativo alla tecnica greedy:
[DFI, paragrafo 10.3].
Alcuni esercizi relativi alla
tecnica greedy.
-
4 dicembre 2017 - Lezione 28
Programmazione dinamica. Esempi: calcolo del
sottovettore di somma massima, cammini di valore minimo su matrici.
Materiale di riferimento relativo alla programmazione dinamica:
[DFI, paragrafo 10.2].
-
11 dicembre 2017 - Lezione 29
Programmazione dinamica. Esempio: distanza tra stringhe.
Cammini minini nei grafi: introduzione.
Materiale di riferimento relativo alla distanza tra stringhe:
[DFI, paragrafo 11.2].
Alcuni esercizi relativi alla
programmazione dinamica.
-
14 dicembre 2017 - Lezione 30
Cammini minini nei grafi. Cammini minimi tra tutte le coppie di
vertici: l'algoritmo di Floyd e Warshall.
Cammini minimi da un vertice a tutti gli altri: l'algoritmo di
Dijkstra.
Cammino minimo tra due vertici.
Cammini minimi: pseudocodice.
Materiale di riferimento relativo ai cammini minimi:
[DFI, capitolo 14].
Alcuni esercizi relativi ai cammini
minimi.
-
14 dicembre 2017 - Lezione 31
Tabelle hash. Funzioni hash e loro scelta. Il problema delle
collisioni. Risoluzione delle collisioni mediante liste di collisione.
Materiale di riferimento relativo alle tabelle hash:
[DFI, capitolo 7].
-
18 dicembre 2017 - Lezione 32
Tabelle hash. Risoluzione delle collisioni mediante indirizzamento
aperto. Costo delle operazioni di ricerca e inserimento in tabelle
hash. Re-hashing: analisi ammortizzata dell'inserimento.
Materiale di riferimento (oltre a quello indicato per la lezione
precedente):
Un'analisi ammortizzata dell'inserimento con re-hashing è
presentata in [BG, ultima parte del paragrafo 9.3].
Alcuni esercizi relativi alle
tabelle hash.
-
11 gennaio 2018 - Lezione 33
Problemi di decisione, ricerca e ottimizzazione.
Classi di complessità in tempo e spazio: P, PSPACE, EXPTIME e
loro relazioni.
-
12 gennaio 2018 - Lezione 34
Il problema SODD di soddisfacibilità di formule booleane in forma
normale congiuntiva.
Algoritmi nondeterministici. Soluzione di SODD in tempo polinomiale
mediante un algoritmo nondeterministico. La classe NP.
Il concetto di riducibilità polinomiale.
Esempio: riduzione da SODD al problema CLIQUE.
Materiale di riferimento relativo alle classi di complessità:
[DFI, Paragrafi 16.1, 16.2, 16.3].
Alcuni esercizi relativi ai
problemi difficili.
-
15 gennaio 2018 - Lezione 35
Riducibilità polinomiale. Problemi NP-hard. Problemi
NP-completi. Il teorema di Cook (enunciato). Alcuni esempi di problemi
NP-completi.
-
18 gennaio 2018 - Prova di fine
corso