DiarioLezioni < Algoreti

Tags: view all tags

---+Diario delle lezioni A.A. 2007-2008

I riferimenti bibliografici fanno uso delle abbreviazioni mostrate nel paragrafo "Libri di testo e materiale didattico" della pagina Web del corso.

---++++ <font color=green> Venerdì 21 dicembre 2007</font>

Svolgimento di esercizi di preparazione all'esame.

---++++ <font color=green>Martedì 18 dicembre 2007</font>

Svolgimento di esercizi di preparazione all'esame.

---++++ <font color=green>Venerdì 14 dicembre 2007</font>

Didattica sospesa per 18-mo Incontro con le Aziende.

---++++ <font color=green>Martedì 11 dicembre 2007</font>

L'approccio preflow-push al calcolo del massimo flusso: implementazione O(m n^2) [AMO93 paragrafo 7.6]

---++++ <font color=green>Venerdì 7 dicembre 2007</font>

Shortest augmenting path: implementazione O(m n^2) con etichette di distanza [AMO93 paragrafo 7.4]

---++++ <font color=green>Martedì 4 dicembre 2007</font>

Shortest augmenting path: implementazione O(m^2 n) con distanze esatte. Etichette di distanza. [AMO93 paragrafi 7.2 e 7.4]

---++++ <font color=green>Venerdì 30 novembre 2007</font>

Lezione annullata causa sciopero generale dei trasporti.

---++++ <font color=green>Martedì 27 novembre 2007</font>

Correzione esercizi della prima prova intermedia.

---++++ <font color=green>Venerdì 23 novembre 2007</font>

Algoritmo di Edmonds e Karp. Algoritmo di capacity scaling. [DFI04 paragrafo 14.5, AMO93 paragrafo 7.3]

---++++ <font color=green>Martedì 20 novembre 2007</font>

Possibile non convergenza dell'algoritmo di labeling in presenza di pesi irrazionali. Teorema di decomposizione del flusso in cammini. [Zwick95, DFI04 paragrafo 14.5]

---++++ <font color=green>Martedì 13 novembre 2007:</font><font color= green ><b> svolgimento della prima prova intermedia</b></font>

---++++ <font color=green>Venerdì 9 novembre 2007</font>

Tempo di esecuzione dell'algoritmo di labeling. Esercizi sul massimo flusso in preparazione della prova intermedia: esercizio 3 dall'esonero del 19 aprile 2007, esercizio 1 dall'esonero del 12 giugno 2007, esercizio 1 dall'esame del 17 settembre 2007 (punti 1, 2, 3, 6) [AMO93, paragrafo 6.5]

---++++ <font color=green>Martedì 6 novembre 2007</font>

Tagli s-t: capacità, capacità residua e flusso attraverso un taglio. Limitazione superiore al valore del flusso con la capacità di un qualunque taglio. Algoritmo basato su cammini aumentanti: correttezza e teorema di massimo flusso minimo taglio. Corrispondenza tra cammini aumentanti e cammini nella rete originaria.  Cenni all'integralità del flusso. [AMO93, paragrafi 6.3, 6.4, 6.5]

---++++ <font color=green>Martedì 30 ottobre 2007</font>

Introduzione al problema del <b><font color=990000>massimo flusso</font></b>. Definizione formale, assunzioni, capacità residua e rete residua. Un esempio di applicazione: scheduling su macchine parallele uniformi [AMO93, paragrafi 6.1, 6.2, 6.3]

---++++ <font color=green>Venerdì 26 ottobre 2007</font>

Esercizi su cammini minimi in preparazione della prova intermedia.

---++++ <font color=green>Martedì 23 ottobre 2007</font>

Tecnica della ripesatura: l'algoritmo di Johnson. Svolgimento di esercizi in classe [CLRS01, paragrafo 25.4] 

---++++ <font color=green>Venerdì 19 ottobre 2007</font>

Distance vector protocol: cambiamenti dei costi dei link. L'algoritmo di Floyd-Warshall [DVP, KR03, DFI04 cap. 13] 

---++++ <font color=green>Martedì 16 ottobre 2007</font>

Distance vector protocol: inizializzazione, dimostrazione di correttezza [DVP, KR03] 

---++++ <font color=green>Venerdì 5 ottobre 2007</font>

Algoritmo di Dijkstra. Calcolo dei cammini minimi a sorgente singola in grafi diretti aciclici [DFI04 cap. 13] 

---++++ <font color=green>Martedì 2 ottobre 2007</font>

Algoritmo di Bellman-Ford. Esercizi [DFI04 cap. 13] 

---++++ <font color=green>Venerdì 28 settembre 2007</font>

Condizioni di Bellman. L'operazione di rilassamento. Teorema di correttezza delle stime [DFI04 cap. 13, appunti presi a lezione] 

---++++ <font color=green>Martedì 25 settembre 2007</font>

Introduzione al corso. Panoramica sugli argomenti che verranno affrontati. Introduzione al problema dei <b><font color=990000>cammini minimi</font></b> e discussione di proprietà basilari  [Kleinberg-Reti, Intro, DFI04 cap. 13]