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

Edit | Attach | Watch | Print version | History: r42 < r41 < r40 < r39 < r38 | Backlinks | Raw View | Raw edit | More topic actions
Topic revision: r42 - 2009-12-16 - TizianaCalamoneri






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