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).
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).
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