-
2 ottobre 2019 - Lezione 1
Presentazione del corso. Introduzione. Il concetto di algoritmo.
-
7 ottobre 2019 - Lezione 2
Algoritmi e programmi. Sintesi e analisi di algoritmi.
Alcuni semplici esempi.
-
9 ottobre 2019 - Lezione 3
Esempio: calcolo di potenze di interi. Un algoritmo iterativo. Un algoritmo
ricorsivo. Correttezza degli algoritmi presentati.
Stima del tempo e dello spazio di calcolo
-
11 ottobre 2019 - Lezione 4
Richiami sulle principali notazioni asintotiche.
Esempio: calcolo delle potenze di interi. Un algoritmo iterativo migliore.
Stima del tempo e dello spazio di calcolo.
Confronto tra i vari algoritmi per il calcolo delle potenze di interi presentanti.
Materiale di riferimento per le lezioni 1-4:
I contenuti di queste lezioni sono presentati nel capitolo 1 di [DFI] mediante un esempio differente
(calcolo dei numeri di Fibonacci, anziché calcolo delle potenze di interi).
Si veda inoltre [BG, capitolo 1] e, per le notazioni asintotiche, [DFI, paragrafo 2.2].
-
14 ottobre 2019 - Lezione 5
Operazioni elementari e modelli di calcolo: cenni al modello RAM.
Criterio di costo uniforme e logaritmico.
Costo di algoritmi e complessità di problemi:
delimitazioni inferiori e superiori.
Materiale di riferimento su modelli di calcolo, criteri di costo,
complessità di algoritmi e di problemi:
[DFI,
paragrafi 2.1, 2.3, 2.4.1], [BG, paragrafi 1.2 e 1.3].
Il capitolo 2 di [BG] è
un utile riferimento per molte delle nozioni matematiche utilizzate nel corso.
Per una presentazione approfondita della Macchina RAM e dei criteri di costo si veda
[BG, paragrafo 3.1].
-
16 ottobre 2019 - Lezione 6
Tempo polinomiale rispetto a tempo esponenziale.
Ricerca sequenziale. Ricerca dicotomica (o binaria) ricorsiva.
Evoluzione dello stack.
Stima del numero di confronti, tempo, spazio.
Ricerca dicotomica iterativa.
Ricerca in un array: pseudocodice.
Materiale di riferimento su ricerca sequenziale e ricerca binaria:
[DFI,
paragrafo 2.4].
-
18 ottobre 2019 - Lezione 7
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).
Materiale di riferimento relativo alle tecniche elementari di ordinamento:
Note e pseudocodice.
[DFI, introduzione del capitolo 4 e paragrafo 4.2]
Alcuni esercizi relativi
alle tecniche elementari di ordinamento.
-
21 ottobre 2019 - Lezione 8
Fusione (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.
Materiale di riferimento:
Note e pseudocodice.
[DFI, paragrafo 4.4]
-
23 ottobre 2019 - Lezione 9
Tecnica divide-et-impera. Schema generale. Esempio: minimo
e del massimo in un array; calcolo del numero di confronti.
Prodotto di matrici secondo la definizione; stima del numero di confronti.
Materiale di riferimento relativo alla tecnica divide-et-impera:
[DFI, paragrafo 10.1], si consiglia di consultare
anche [BG, capitolo 10]
Alcuni esercizi relativi
alla tecnica divide-et-impera.
-
28 ottobre 2019 - Lezione 10
Equazioni divide-et-impera: il teorema fondamentale delle ricorrenze (Master Theorem).
Tecnica divide-et-impera. Esempio: calcolo del prodotto di matrici
quadrate con il metodo di Strassen.
L'algoritmo di ordinamento quicksort (inizio): struttura generale; costruzione della
partizione.
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].
-
30 ottobre 2019 - Lezione 11
L'algoritmo di ordinamento quicksort. Calcolo del numero di confronti
nel caso peggiore, migliore e in media. Stima dello spazio utilizzato e dell'altezza dello stack.
Modifica dell'algoritmo per ridurre l'altezza dello stack.
Materiale di riferimento relativo a quicksort:
Note e pseudocodice.
[DFI, paragrafo 4.5]
-
4 novembre 2019 - Lezione 12
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 e inserimento in liste ordinate).
Liste lineari: pseudocodice.
-
6 novembre 2019 - Lezione 13
Cancellazione da liste ordinate.
Implementazione di liste mediante array e mediante puntatori.
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.
Alberi binari: introduzione e nomenclatura.
Visita generica ad alberi binari.
Materiale di riferimento su liste, pile e conde:
Una presentazione generale degli argomenti si trova in [DFI, capitolo 3 (fino al paragrafo 3.2)]. 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].
-
8 novembre 2019 - Lezione 14
Alberi binari: visite in ampiezza e in profondità.
Visite in profondità in ordine anticipato,
simmetrico, posticipato. Esempi.
Esempi. Alberi binari di ricerca: introduzione.
Ricerca ricorsiva ed iterativa in un albero binario di ricerca.
-
11 novembre 2019 - Lezione 15
Inserimento e cancellazione in alberi binari di ricerca.
Alberi binari 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 o AVL (inizio).
Alberi binari di ricerca: pseudocodice.
Materiale di riferimento su alberi binari di ricerca:
[DFI, paragrafo 6.1]
-
13 novembre 2019 - Lezione 16
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 con radice. Rappresentazioni indicizzate e collegate.
Visite in ampiezza, visite in profondità.
Materiale di riferimento su alberi AVL e alberi generali:
Per gli alberi AVL si veda [DFI, paragrafo 6.2] e
questo simulatore.
Per gli alberi con radice, le loro rappresentazioni e le
visite si veda [DFI, paragrafo 3.3].
-
15 novembre 2019 - Lezione 17
Alberi 2-3. Ricerca, inserimento e cancellazione in alberi 2-3.
Dizionari in memoria secondaria. B-alberi: definizione ed esempi.
Ricerca di un elemento in un B-albero (con stima del numero di confronti,
e del numero di accessi a memoria secondaria).
Cenni alle operazioni di inserimento e cancellazione in B-alberi.
Materiale di riferimento relativo agli alberi 2-3 e ai B-alberi:
[DFI, paragrafi 6.4 e 6.5].
Alcuni esercizi relativi
relativi ad alberi binari e alberi di ricerca.
-
18 novembre 2019 - Lezione 18
La struttura dati heap. Rimozione del massimo da uno heap e
risistemazione dello heap. Costruzione top-down e bottom-up di uno heap
a partire da un albero binario.
L'algoritmo di ordinamento heapsort. Calcolo del numero di confronti.
Rappresentazione implicita di un albero binario "quasi completo"
mediante vettore posizionale.
Materiale di riferimento relativo a heapsort:
Note e pseudocodice.
[DFI, paragrafo 4.3]
-
20 novembre 2019 - Lezione 19
Implementazione in loco di heapsort.
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.
Altre operazioni sugli heap (inserimento, cancellazione, modifica
di chiave). Code con priorità e loro implementazione mediante heap.
Materiale di riferimento relativo al riepilogo sugli algoritmi di ordinamento e
alla limitazione inferiore per il numero di confronti:
Note.
[DFI, paragrafo 4.1].
Materiale di riferimento relativo alle operazioni sugli heap e alle
code con priorità:
Note.
Si veda anche la prima parte del capitolo 8 di [DFI].
-
22 novembre 2019 - Lezione 20
Metodi di ordinamento non basati su confronti tra chiavi: integersort,
bucketsort, radixsort.
Materiale di riferimento relativo agli algoritmi di ordinamento non basati su confronti tra chiavi:
[DFI, paragrafi 4.6 e 4.7],
Pseudocodice.
Esercizi relativi
relativi ad algoritmi di ordinamento, heap e ulteriori esercizi relativi ad alberi.
-
25 novembre 2019 - Lezione 21
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 relativo a Union-Find:
[DFI, capitolo 9].
Alcuni esercizi relativi a union-find.
-
27 novembre 2019 - Lezione 22
Cenni all'analisi ammortizzata di algoritmi.
Grafi. Introduzione e definizioni fondamentali.
Materiale di riferimento relativo all'analisi ammortizzata di algoritmi:
[DFI,
prima parte del paragrafo 2.7]
-
29 novembre 2019 - Lezione 23
Alberi: relazione tra numero di vertici e numero di archi
Rappresentazioni di grafi: lista di archi, liste di adiacenza, liste
di incidenza, matrice di adiacenza, matrice di incidenza.
Stima dello spazio utilizzato da ciascuna rappresentazione.
Visita di grafi in ampiezza.
Stima del tempo utilizzato per la visita in ampiezza
in base alla rappresentazione del grafo utilizzata.
Materiale di riferimento relativo ai grafi (lezioni 22 e 23):
[DFI, paragrafi 12.1, 12.2, 12.3].
Pseudocodice relativo alle visite di grafi.
-
2 dicembre 2019 - Lezione 24
Visita di grafi in profondità.
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 2019 - Lezione 25
L'algoritmo di Kruskal per determinare il minimo albero ricoprente.
Correttezza dell'algoritmo di Kruskal. Implementazione mediante
union-find. Complessità in tempo.
-
6 dicembre 2019 - Lezione 26
L'algoritmo di Prim per determinare il minimo albero ricoprente.
Implementazione mediante code con priorità. Complessità in tempo.
Materiale di riferimento relativo al minimo albero ricoprente:
Note.
Si veda anche
[DFI, introduzione del capitolo 13, paragrafi 13.1,
13.2 (tutto), 13.3 (prima parte)].
Alcuni esercizi relativi ai grafi.
-
9 dicembre 2019 - Lezione 27
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 2019 - Lezione 28
Programmazione dinamica. Esempio: calcolo della distanza tra due stringhe.
Materiale di riferimento relativo alla distanza tra stringhe:
[DFI, paragrafo 11.2]
Alcuni esercizi relativi alla
programmazione dinamica.
-
13 dicembre 2019 - Lezione 29
Problemi di cammini minimi nei grafi: introduzione.
Cammini minimi tra tutte le coppie di vertici: l'algoritmo di Floyd e Warshall.
-
16 dicembre 2019 - Lezione 30
Cammini minimi da un vertice a tutti gli altri: l'algoritmo di Dijkstra.
Implementazione dell'algoritmi di Dijkstra mediante code con priorità.
Cammino minimo tra due vertici
Materiale di riferimento relativo ai cammini minimi:
[DFI, capitolo 14].
Pseudocodice degli algoritmi di Floyd e Warshall e di Dijkstra.
Alcuni esercizi relativi ai cammini
minimi.
-
18 dicembre 2019 - Lezione 31
Tabelle hash: introduzione. Funzioni hash e loro scelta. Il problema delle
collisioni.
-
20 dicembre 2019 - Lezione 32
Tabelle hash. Risoluzione delle collisioni mediante liste di collisione.
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 relativo alle tabelle hash:
[DFI, capitolo 7].
Note sul re-hashing.
Alcuni esercizi relativi alle
tabelle hash.
-
8 gennaio 2020 - Lezione 33
Introduzione alla complessità computazionale.
Problemi di decisione, ricerca e ottimizzazione.
Classi di complessità in tempo e spazio: P, PSPACE, EXPTIME e
loro relazioni.
-
10 gennaio 2020 - Lezione 34
I problemi PARTIZIONE e CLIQUE.
Il problema SODD di soddisfacibilità di formule booleane in forma
normale congiuntiva.
Algoritmi nondeterministici. Soluzione di SODD, PARTIZIONE e CLIQUE in tempo polinomiale
mediante algoritmi nondeterministici. La classe NP.
Materiale di riferimento relativo alle classi di complessità:
[DFI, Paragrafi 16.1, 16.2, 16.3].
Algoritmi nondeterministici: pseudocodice.
Alcuni esercizi relativi ai
problemi difficili.
-
13 gennaio 2020 - Lezione 35
Il concetto di riducibilità polinomiale.
Proprietà delle riduzioni polinomiali.
Esempio: riduzione da SODD al problema CLIQUE.
Riducibilità polinomiale. Problemi NP-hard. Problemi
NP-completi. Il teorema di Cook (enunciato). Alcuni esempi di problemi
NP-completi.
-
15 gennaio 2020 - Lezione 36
Esercizi vari.