PARTE SESTA: Algoritmi su Grafi
-
18/11/03:
-
Il problema dell'albero dei cammini minimi a sorgente singola in
un grafo pesato con pesi non negativi. Definizioni. Tecnica del rilassamento.
-
Algoritmo di Dijkstra.
-
Approfondimento: Esecuzione dell'algoritmo
di Dijkstra.
-
Dispense: 86,
87,
88,
89,
90.
-
19/11/03:
-
Algoritmo di Dijkstra. Dimostrazione di correttezza ed analisi della complessità. Esempi.
-
Approfondimento: Esecuzione dell'algoritmo
di Dijkstra con grafo fissato e sorgente variabile. Modifica dell'algoritmo
di Dijkstra per la determinazione del cammino minimo tra un nodo sorgente ed un nodo destinazione.
-
Dispense:
91,
92,
93,
94,
95.
-
20/11/03:
-
Il problema del minimo albero ricoprente di un grafo pesato con
pesi positivi. Definizioni. Teorema dell'appartenenza ad un minimo
albero ricoprente di un arco leggero di un taglio.
-
Approfondimento: Generazione di tutti i tagli di un grafo. Determinazione dell'arco leggero di un taglio.
-
Dispense:
96,
97,
98,
99.
-
25/11/03:
-
Problema della gestione di una collezione di insiemi disgiunti.
Operazioni MAKE-SET(x), FIND-SET(x), UNION(x,y).
Risoluzione attraverso l'uso di liste concatenate.
Analisi della complessità.
-
Dispense:
99-2,
99-3,
99-4,
99-5.
-
26/11/03:
-
Algoritmo di Kruskal. Correttezza dell'algoritmo di Kruskal.
Analisi della complessità dell'algoritmo di
Kruskal. Esecuzione dettagliata dell'algoritmo di Kruskal.
-
Approfondimento: Ingegnerizzazione dell'algoritmo di Kruskal.
-
Dispense:
100,
101,
102.
-
27/11/03:
-
Algoritmo di Prim per il calcolo del minimo albero ricoprente.
Correttezza dell'algoritmo di Prim.
Analisi della complessità dell'algoritmo di
Prim.
-
Approfondimento: Esecuzione dell'algoritmo di Prim.
-
Dispense:
103,
104,
105,
106.
-
2/12/03:
-
Riepilogo: risoluzione esercizi, chiarimento dubbi.
-
3/12/03:
-
Riepilogo: risoluzione esercizi, chiarimento dubbi.
-
4/12/03:
-
Riepilogo: risoluzione esercizi, chiarimento dubbi.