Diario delle Lezioni A.A. 2009/10

1-2. 2/10/09:

Introduzione al corso.

• Breve storia della visualizzazione dei grafi.
• Differenza tra oggetto e sua rappresentazione.
• Nozioni preliminari di teoria dei grafi, teorema sulla somma dei gradi, regola della stretta di mano.
• Convenzioni, criteri estetici, precedenza tra criteri estetici, vincoli.
• Efficienza computazionale.

3-4. 6/10/09:

Rappresentazione di oggetti con struttura ad albero (1).

• Esempio di oggetti con struttura ad albero.
• H-tree ed equazione di ricorrenza per l'area.
• Algoritmo banale (visita in order) per il disegno downward su griglia.
• Algoritmo di Reingold e Tilford nel caso binario e k-ario e dimostrazione della linearità dell'algoritmo. * Algoritmo di Garg, Goodrich e Tamassia (introduzione).

5-6. 9/10/09:

Rappresentazione di oggetti con struttura ad albero (2).

• Algoritmo di Garg, Goodrich e Tamassia (conclusione).
• Disegno Radiale.
• Disegno HV e sue varianti nel caso binario e k-ario.

Rappresentazione di gerarchie (1).

• Introduzione

7-8. 13/10/09:

Rappresentazione di gerarchie (2).

• Tree maps; algoritmo Slice & Dice e sue varianti.
• Sun bursts.
• Cone trees e cam trees.
• Alberi botanici.

Rappresentazione di grafi in 2D (1).

• codifiche di rappresentazioni di grafi.
• st-grafi.
• Disegno ortogonale su griglia: rappresentazioni di visibilità.

9-10. 16/10/09:

Rappresentazione di grafi in 2D (2).

• Disegno ortogonale su griglia: algoritmo basato sulla rappresentazione di visibilità e dimostrazioni di correttezza, area e complessità.
• Disegno ortogonale su griglia: definizione e algoritmo di st-numerazione; dimostrazioni di correttezza e complessità dell'algoritmo e necessità della 2-connessione.
• Disegno ortogonale su griglia: algoritmo basato sulla st-numerazione e dimostrazioni di correttezza, area, numero di svolte e complessità.

11-12. 20/10/09:

Rappresentazione di grafi in 3D (1).

• Disegno ortogonale su griglia: panoramica della problematica e bibliografia correlata; scelta del miglior punto di vista.
• Disegno ortogonale: Fase di preprocessing, compresi i teoremi e le dimostrazioni (teorema di Eulero e di P. Hall);

13-14. 24/10/09:

Rappresentazione di grafi in 3D (2).

• Algoritmo con volume ottimo e 7 svolte per arco.
• Algoritmo con volume cubico e 3 svolte per arco.
• Disegno rettilineo: limitazione inferiore sul volume (Omega(n^3))

15-16. 27/10/09:

Rappresentazione di grafi in 3D (3).

• Disegno rettilineo: algoritmo generale basato sulla cubica gobba, algoritmo per grafi bipartiti e tripartiti, limitazione inferiore sul volume in funzione di n ed m.

Ottimizzazioni (1).

• Disegno 2D ortogonale, minimizzazione del numero di svolte: euristiche basate sulle configurazioni.

17-18. 3/11/09:

Ottimizzazioni (2).

• Disegno 2D ortogonale planare, compattamento dell'area: metodo basato sul minimo flusso (caso delle facce rettangolari e caso generale), teoremi sulla correttezza e sull'area.

Generalizzazioni (1).

• Generalizzazione al grado alto, disegno 2D ortogonale planare: algoritmo.

19-20. 6/11/09:

Generalizzazioni (2).

• Generalizzazione al grado alto, disegno 3D ortogonale planare: teorema sull'inesistenza di un disegno senza svolte; algoritmi che garantiscono volume O(n^3) ed una o due svolte per arco.
• Generalizzazione al grado alto, disegno 3D ortogonale planare: algoritmo che garantisce volume O(n^5/2) e tre svolte per arco.

9-15/11/09:

Settimana di interruzione della didattica

21-22. 17/11/09:

Generalizzazioni (3).

• Generalizzazione a grafi semplicemente connessi, disegno 2D ortogonale: algoritmo di Biedl e Kant con teoremi per area e numero di svolte.
• Generalizzazione a grafi semplicemente connessi, disegno 2D ortogonale: metodo dell'aumentazione.
• Generalizzazione a grafi non planari, disegno 2D ortogonale: planarizzazione.

Visualizzazione di strutture molecolari (1).

• Algoritmo generale basato sulla minimizzazione delle forze di interazione.
• Algoritmo di Tutte.

23-24. 20/11/09:

Visualizzazione di strutture molecolari (2).

• Divagazione sul problema del dispiegamento dei sensori mobili (1)
• Generalizzazioni degli algoritmi basati sulla minimizzazione delle forze di interazione: di Sugiyama e Misue, di Davidson e Harel.
• Tecnica del simulated annealing, di Harel e Koren.
• Gestione dei vincoli tramite metodi basati sulle forze.

25-26. 24/11/09:

Disegno ortogonale interattivo (1).

• Mantenere la mappa mentale.
• La problematica del disegno interattivo e i 4 possibili scenari.
• Algoritmo per lo scenario "Relative Coordinates".
• Teoremi per lo studio dell'area e del numero di svolte dell'algoritmo per lo scenario "Relative Coordinates".
• Algoritmo per lo scenario "No change".
• Teoremi per lo studio dell'area e del numero di svolte dell'algoritmo per lo scenario "No change".
• Confronto tra scenario "Relative Coordinates" e scenario "No Change".

27-28. 27/11/09:

Disegno ortogonale interattivo (2).

• Network evolution.

Visualizzazione di oggetti in 3D (1).

• Triangolazione: determinazione dei punti e dei triangoli.
• Triangolazione di Delunay e diagramma di Voronoi.
• Modelli di illuminazione: modelli locali e globali; modello di Lambert, luce ambientale, modello di Phong, attenuazione della luce.

29-30. 1/12/09:

Visualizzazione di oggetti in 3D (2).

• Divagazione sul problema del dispiegamento dei sensori mobili (2)
• Modelli di ombreggiatura: flat shading, ombreggiatura di Gouraud, ombreggiatura di Phong.
• Proiezione di ombre.
• Sorgenti puntiformi vs. sorgenti estese; ombre e penombre.

Visualizzazione di topologie di interconnessione (1).

• Il modello di Thompson per il layout; vincoli dettati dalla tecnologia VLSI; cenni al layout 3D.

Somministrazione del questionario di valutazione del corso.

31-32. 4/12/09:

Visualizzazione di topologie di interconnessione (2).

• Diversi layout di una stessa topologia di interconnessione (butterfly): Layout 'slanted'; Layout via layered cross product;
• Raffronto delle due rappresentazioni e cenni all'ottimizzazione dell'area.

Visualizzazione di carte geografiche (1).

• Premessa: panoramica su: problemi NP-completi, riduzioni polinomiali; 3-SAT, 2-SAT.

8/12/09:

Festa dell'Immacolata

33. 9/12/09:

Seminario: Diagrammi di Voronoi, Distanza di Laguerre e Dispiegamento di Sensori Mobili

34-35. 11/12/09:

Visualizzazione di carte geografiche (1).

• Il problema della etichettatura degli oggetti.
• Panoramica della complessita' di problemi di etichettatura di oggetti: etichettatura di punti e di linee.
• Alcuni algoritmi di etichettatura: etichettatura di punti, di linee, di carte geografiche.

36-37. 15/12/09:

Visualizzazione di oggetti molto grandi (infiniti).

• Esempi di oggetti molto grandi: mappa del web, relazioni di dipendenza tra moduli software, ecc.
• Tecnica della clusterizzazione.
• Un algoritmo per la rappresentazione di grafi clusterizzati.
• Tecnica della navigazione.
• Discussione delle problematiche collegate a queste due tecniche e loro raffronto.
• Occhio di pesce.
• Altre tecniche.

Diario delle Lezioni A.A. 2008/09

1-2. 3/3/09:

Introduzione al corso.

• Breve storia della visualizzazione dei grafi.
• Differenza tra oggetto e sua rappresentazione.
• Nozioni preliminari di teoria dei grafi, teorema sulla somma dei gradi, regola della stretta di mano.
• Convenzioni, criteri estetici, precedenza tra criteri estetici, vincoli.
• Efficienza computazionale.

3-4. 5/3/09:

Rappresentazione di oggetti con struttura ad albero (1).

• Esempio di oggetti con struttura ad albero.
• H-tree ed equazione di ricorrenza per l'area.
• Algoritmo banale (visita in order) per il disegno downward su griglia.
• Algoritmo di Reingold e Tilford nel caso binario e k-ario e dimostrazione della linearità dell'algoritmo.

5-6. 10/3/09:

Rappresentazione di oggetti con struttura ad albero (2).

• Algoritmo di Garg, Goodrich e Tamassia.
• Disegno Radiale.

7-8. 12/3/09:

Rappresentazione di oggetti con struttura ad albero (3).

• Disegno HV e sue varianti nel caso binario e k-ario.

Rappresentazione di gerarchie.

• Tree maps; algoritmo Slice & Dice e sue varianti.
• Sun bursts.
• Cone trees e cam trees.
• Alberi botanici.

9-10. 17/3/09:

Rappresentazione di grafi in 2D (1).

• codifiche di rappresentazioni di grafi.
• st-grafi.
• Disegno ortogonale su griglia: rappresentazioni di visibilità; algoritmo basato sulla rappresentazione di visibilità e dimostrazioni di correttezza, area e complessità.

11-12. 19/3/09:

Rappresentazione di grafi in 2D (2).

• Disegno ortogonale su griglia: definizione e algoritmo di st-numerazione; dimostrazioni di correttezza e complessità dell'algoritmo e necessità della 2-connessione.
• Disegno ortogonale su griglia: algoritmo basato sulla st-numerazione e dimostrazioni di correttezza, area, numero di svolte e complessità.

13-14. 24/3/09:

• Seminario del Prof. Madhu Sudan: (Computational) Complexity in everyday life.

15-16. 26/3/09:

Rappresentazione di grafi in 3D (1).

• Disegno ortogonale su griglia: panoramica della problematica e bibliografia correlata; scelta del miglior punto di vista.
• Disegno ortogonale: Fase di preprocessing, compresi i teoremi e le dimostrazioni (teorema di Eulero e di P. Hall);
• Algoritmo con volume ottimo e 7 svolte per arco (prima parte).

17-18. 31/3/09:

Rappresentazione di grafi in 3D (2).

• Algoritmo con volume ottimo e 7 svolte per arco (seconda parte).
• Algoritmo con volume cubico e 3 svolte per arco.
• Disegno rettilineo: limitazione inferiore sul volume (Omega(n^3)), algoritmo generale basato sulla cubica gobba, algoritmo per grafi bipartiti e tripartiti, limitazione inferiore sul volume in funzione di n ed m.

19-20. 2/4/09:

Generalizzazioni.

• Generalizzazione al grado alto, disegno 2D ortogonale planare: algoritmo.
• Generalizzazione al grado alto, disegno 3D ortogonale planare: teorema sull'inesistenza di un disegno senza svolte; algoritmi che garantiscono volume O(n^3) ed una o due svolte per arco.
• Generalizzazione al grado alto, disegno 3D ortogonale planare: algoritmo che garantisce volume O(n^5/2) e tre svolte per arco.
• Generalizzazione a grafi semplicemente connessi, disegno 2D ortogonale: algoritmo di Biedl e Kant con teoremi per area e numero di svolte.
• Generalizzazione a grafi semplicemente connessi, disegno 2D ortogonale: metodo dell'aumentazione.
• Generalizzazione a grafi non planari, disegno 2D ortogonale: planarizzazione.

21-22. 7/4/09:

Ottimizzazioni.

• Disegno 2D ortogonale, minimizzazione del numero di svolte: euristiche basate sulle configurazioni.
• Disegno 2D ortogonale planare, compattamento dell'area: metodo basato sul minimo flusso (caso delle facce rettangolari e caso generale), teoremi sulla correttezza e sull'area.

Vacanze di Pasqua e interruzione della didattica

23-24. 28/4/09:

Visualizzazione di strutture molecolari (1).

• Algoritmo generale basato sulla minimizzazione delle forze di interazione.
• Divagazione sul problema del dispiegamento dei sensori mobili
• Algoritmo di Tutte.
• Generalizzazioni degli algoritmi basati sulla minimizzazione delle forze di interazione: di Sugiyama e Misue, di Davidson e Harel.

25-26. 30/4/09:

Visualizzazione di strutture molecolari (2).

• Tecnica del simulated annealing, di Harel e Koren.
• Gestione dei vincoli tramite metodi basati sulle forze.

Disegno ortogonale interattivo (1).

• Mantenere la mappa mentale.
• La problematica del disegno interattivo e i 4 possibili scenari.
• Algoritmo per lo scenario "Relative Coordinates".
• Teoremi per lo studio dell'area e del numero di svolte dell'algoritmo per lo scenario "Relative Coordinates".

27-28. 5/5/09:

Disegno ortogonale interattivo (2).

• Algoritmo per lo scenario "No change".
• Teoremi per lo studio dell'area e del numero di svolte dell'algoritmo per lo scenario "No change".
• Network evolution.

Visualizzazione di oggetti in 3D (1).

• Triangolazione: determinazione dei punti e dei triangoli.

29-30. 7/5/09:

Visualizzazione di oggetti in 3D (2).

• Triangolazione di Delunay e diagramma di Voronoi.
• Modelli di illuminazione: modelli locali e globali; modello di Lambert, luce ambientale, modello di Phong, attenuazione della luce.
• Modelli di ombreggiatura: flat shading, ombreggiatura di Gouraud, ombreggiatura di Phong.
• Proiezione di ombre.
• Sorgenti puntiformi vs. sorgenti estese; ombre e penombre.

31-32. 12/5/09:

Visualizzazione di carte geografiche (1).

• Premessa: problemi NP-completi, riduzioni polinomiali; un algoritmo per 2-SAT.
• Il problema della etichettatura degli oggetti.
• Panoramica della complessita' di problemi di etichettatura di oggetti: etichettatura di punti e di linee.

33-34. 14/5/09:

Visualizzazione di carte geografiche (2).

• Alcuni algoritmi di etichettatura: etichettatura di punti, di linee, di carte geografiche.
• Il problema della determinazione delle intersezioni di segmenti: definizione del problema, algoritmo e sua correttezza.

35-36. 19/5/09:

Visualizzazione di topologie di interconnessione.

• Il modello di Thompson per il layout; vincoli dettati dalla tecnologia VLSI; cenni al layout 3D.
• Diversi layout di una stessa topologia di interconnessione (butterfly): Layout 'slanted'; Layout via layered cross product;
• Raffronto delle due rappresentazioni e cenni all'ottimizzazione dell'area.

37. 21/5/09:

• Somministrazione del questionario di valutazione del corso.

38-39. 21/5/09:

Visualizzazione di oggetti molto grandi (infiniti).

• Esempi di oggetti molto grandi: mappa del web, relazioni di dipendenza tra moduli software, ecc.
• Tecnica della clusterizzazione.
• Un algoritmo per la rappresentazione di grafi clusterizzati.
• Tecnica della navigazione.
• Discussione delle problematiche collegate a queste due tecniche e loro raffronto.
• Occhio di pesce.
• Altre tecniche.

Diario delle Lezioni A.A. 2007/08

1-2. 26/2/08:

Introduzione al corso.

• Breve storia della visualizzazione dei grafi.
• Differenza tra oggetto e sua rappresentazione.
• Nozioni preliminari di teoria dei grafi, teorema sulla somma dei gradi, regola della stretta di mano.
• Convenzioni, criteri estetici, precedenza tra criteri estetici, vincoli.
• Efficienza computazionale.

3-4. 29/2/08:

Rappresentazione di oggetti con struttura ad albero (1).

• Esempio di oggetti con struttura ad albero.
• H-tree ed equazione di ricorrenza per l'area.
• Algoritmo banale (visita in order) per il disegno downward su griglia.
• Algoritmo di Reingold e Tilford nel caso binario e k-ario e dimostrazione della linearità dell'algoritmo.

5-6. 4/3/08:

Rappresentazione di oggetti con struttura ad albero (2).

• Algoritmo di Garg, Goodrich e Tamassia.
• Disegno Radiale.
• Disegno HV e sue varianti nel caso binario e k-ario.

7-8. 7/3/08:

Rappresentazione di gerarchie.

• Tree maps; algoritmo Slice & Dice e sue varianti.
• Sun bursts.
• Cone trees e cam trees.
• Alberi botanici.

Rappresentazione di grafi in 2D (1).

• codifiche di rappresentazioni di grafi.
• st-grafi.

9-10. 11/3/08:

Rappresentazione di grafi in 2D (2).

• Disegno ortogonale su griglia: rappresentazioni di visibilità; algoritmo basato sulla rappresentazione di visibilità e dimostrazioni di correttezza, area e complessità.
• Disegno ortogonale su griglia: definizione e algoritmo di st-numerazione; dimostrazioni di correttezza e complessità dell'algoritmo e necessità della 2-connessione.

11-12. 14/3/08:

Rappresentazione di grafi in 2D (3).

• Disegno ortogonale su griglia: algoritmo basato sulla st-numerazione e dimostrazioni di correttezza, area, numero di svolte e complessità.

Rappresentazione di grafi in 3D (1).

• Disegno ortogonale su griglia: panoramica della problematica e bibliografia correlata; scelta del miglior punto di vista.

13-14. 18/3/08:

Rappresentazione di grafi in 3D (2).

• Disegno ortogonale: Fase di preprocessing, compresi i teoremi e le dimostrazioni (teorema di Eulero e di P. Hall, algoritmo con volume ottimo e 7 svolte per arco.

Vacanze di Pasqua

15-16. 28/3/08:

Rappresentazione di grafi in 3D (3).

• Disegno ortogonale: Algoritmo con volume O(n^3) e 3 svolte per arco.
• Disegno rettilineo: limitazione inferiore sul volume (Omega(n^3)), algoritmo generale basato sulla cubica gobba, algoritmo per grafi bipartiti e tripartiti, limitazione inferiore sul volume in funzione di n ed m.

17-18. 1/4/08:

Generalizzazioni (1).

• Generalizzazione al grado alto, disegno 2D ortogonale planare: algoritmo.
• Generalizzazione al grado alto, disegno 3D ortogonale planare: teorema sull'inesistenza di un disegno senza svolte; algoritmi che garantiscono volume O(n^3) ed una o due svolte per arco.
• Generalizzazione al grado alto, disegno 3D ortogonale planare (segue): algoritmo che garantisce volume O(n^5/2) e tre svolte per arco.

19-20. 4/4/08:

Generalizzazioni (2).

• Generalizzazione a grafi semplicemente connessi, disegno 2D ortogonale: algoritmo di Biedl e Kant con teoremi per area e numero di svolte.
• Generalizzazione a grafi semplicemente connessi, disegno 2D ortogonale: metodo dell'aumentazione.
• Generalizzazione a grafi non planari, disegno 2D ortogonale: olanarizzazione.

Ottimizzazioni (1).

• Disegno 2D ortogonale, minimizzazione del numero di svolte: euristiche basate sulle configurazioni.

21-22. 8/4/08:

Ottimizzazioni (2).

• Disegno 2D ortogonale planare, compattamento dell'area: metodo basato sul minimo flusso (caso delle facce rettangolari e caso generale), teoremi sulla correttezza e sull'area.

Visualizzazione di strutture molecolari (1).

• Algoritmo generale basato sulla minimizzazione delle forze di interazione.
• Algoritmo di Tutte.

23-24. 11/4/08:

Visualizzazione di strutture molecolari (2).

• Generalizzazioni degli algoritmi basati sulla minimizzazione delle forze di interazione: di Sugiyama e Misue, di Davidson e Harel, tecnica del simulated annealing, di Harel e Koren.
• Gestione dei vincoli tramite metodi basati sulle forze.

25-26. 15/4/08:

Disegno ortogonale interattivo (1).

• Mantenere la mappa mentale.
• La problematica del disegno interattivo e i 4 possibili scenari.
• Algoritmo per lo scenario "Relative Coordinates".

27-28. 18/4/08:

Disegno ortogonale interattivo (2).

• Teoremi per lo studio dell'area e del numero di svolte dell'algoritmo per lo scenario "Relative Coordinates".
• Algoritmo per lo scenario "No change".
• Teoremi per lo studio dell'area e del numero di svolte dell'algoritmo per lo scenario "No change".
• Network evolution.

Interruzione della Didattica

29-30. 6/5/08:

Visualizzazione di oggetti in 3D.

• Triangolazione: determinazione dei punti e dei triangoli; triangolazione di Delunay e diagramma di Voronoi.
• Modelli di illuminazione: modelli locali e globali; modello di Lambert, luce ambientale, modello di Phong, attenuazione della luce.
• Modelli di ombreggiatura: flat shading, ombreggiatura di Gouraud, ombreggiatura di Phong.
• Proiezione di ombre.
• Sorgenti puntiformi vs. sorgenti estese; ombre e penombre.

31-32. 9/5/08:

Visualizzazione di carte geografiche (1).

• Premessa: problemi NP-completi, riduzioni polinomiali; un algoritmo per 2-SAT.
• Il problema della etichettatura degli oggetti.
• Panoramica della complessita' di problemi di etichettatura di oggetti: etichettatura di punti e di linee.

33-34. 13/5/08:

Visualizzazione di carte geografiche (2).

• Alcuni algoritmi di etichettatura: etichettatura di punti, di linee, di carte geografiche.
• Il problema della determinazione delle intersezioni di segmenti: definizione del problema.

35-36. 16/5/08:

Visualizzazione di carte geografiche (3).

• Il problema della determinazione delle intersezioni di segmenti: algoritmo e sua correttezza.

Visualizzazione di topologie di interconnessione (1).

• Il modello di Thompson per il layout; vincoli dettati dalla tecnologia VLSI; cenni al layout 3D.
• Diversi layout di una stessa topologia di interconnessione (butterfly): Layout 'slanted'.

37-38-39. 20/5/08:

Visualizzazione di topologie di interconnessione (2).

• Diversi layout di una stessa topologia di interconnessione (butterfly): Layout via layered cross product; Raffronto delle due rappresentazioni e cenni all'ottimizzazione dell'area.

Visualizzazione di oggetti molto grandi (infiniti) (previsione).

• Esempi di oggetti molto grandi: mappa del web, relazioni di dipendenza tra moduli software, ecc.
• Tecnica della clusterizzazione.
• Un algoritmo per la rappresentazione di grafi clusterizzati.
• Tecnica della navigazione.
• Discussione delle problematiche collegate a queste due tecniche e loro raffronto.
• Occhio di pesce.
• Altre tecniche.

-- TizianaCalamoneri