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.

Venerdì 21 dicembre 2007

Svolgimento di esercizi di preparazione all'esame.

Martedì 18 dicembre 2007

Svolgimento di esercizi di preparazione all'esame.

Venerdì 14 dicembre 2007

Didattica sospesa per 18-mo Incontro con le Aziende.

Martedì 11 dicembre 2007

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

Venerdì 7 dicembre 2007

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

Martedì 4 dicembre 2007

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

Venerdì 30 novembre 2007

Lezione annullata causa sciopero generale dei trasporti.

Martedì 27 novembre 2007

Correzione esercizi della prima prova intermedia.

Venerdì 23 novembre 2007

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

Martedì 20 novembre 2007

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

Martedì 13 novembre 2007: svolgimento della prima prova intermedia

Venerdì 9 novembre 2007

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]

Martedì 6 novembre 2007

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]

Martedì 30 ottobre 2007

Introduzione al problema del massimo flusso. 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]

Venerdì 26 ottobre 2007

Esercizi su cammini minimi in preparazione della prova intermedia.

Martedì 23 ottobre 2007

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

Venerdì 19 ottobre 2007

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

Martedì 16 ottobre 2007

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

Venerdì 5 ottobre 2007

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

Martedì 2 ottobre 2007

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

Venerdì 28 settembre 2007

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

Martedì 25 settembre 2007

Introduzione al corso. Panoramica sugli argomenti che verranno affrontati. Introduzione al problema dei cammini minimi e discussione di proprietà basilari [Kleinberg-Reti, Intro, DFI04 cap. 13]