Tags:
create new tag
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.

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]

Edit | Attach | Watch | Print version | History: r18 < r17 < r16 < r15 < r14 | Backlinks | Raw View | Raw edit | More topic actions
Topic revision: r18 - 2008-09-11 - IreneFinocchi






 
Questo sito usa cookies, usandolo ne accettate la presenza. (CookiePolicy)
This site is powered by the TWiki collaboration platform Powered by PerlCopyright © 2008-2018 by the contributing authors. All material on this collaboration platform is the property of the contributing authors.
Ideas, requests, problems regarding TWiki? Send feedback