PARTE SESTA: Algoritmi su Grafi
-
16/11/04:
-
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. 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:
86,
87,
88,
89,
90.
91,
92,
93,
94,
95.
-
17/11/04:
-
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.
-
18/11/04:
-
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.
-
23/11/04:
-
Algoritmo di Kruskal. Correttezza dell'algoritmo di Kruskal.
Analisi della complessità dell'algoritmo di
Kruskal. Esecuzione dettagliata dell'algoritmo di Kruskal.
-
Approfondimento: Differenze tra ACM e MAR.
-
Dispense:
100,
101,
102.
-
24/11/04:
-
Algoritmo di Prim per il calcolo del minimo albero ricoprente.
Correttezza dell'algoritmo di Prim.
Analisi della complessità dell'algoritmo di
Prim.
-
Approfondimento: Generazione di tutti i MAR di un grafo completo di 5 nodi.
-
Dispense:
103,
104,
105,
106.
-
25/11/04:
-
Approfondimento: Il massimo albero ricoprente di un grafo. Modifica dell'algoritmo di Prim e sua esecuzione.
-
1/12/04:
-
Riepilogo: risoluzione esercizi, chiarimento dubbi.
-
2/12/04:
-
Riepilogo: risoluzione esercizi, chiarimento dubbi.