ProgrammaDelCorso < Algoritmi

Tags: view all tags
---+++ <font color=990000 size="+2"> <b>Programma del Corso</b></font>

Si tenga presente che, anche se un argomento non e' trattato sulle dispense ne' sulle tesine, questo NON e' un buon motivo per non studiarlo. Inoltre, si consiglia di affiancare comunque i testi consigliati alle dispense e ai lucidi. 

N.B. Le parti di testo blu sono argomenti facoltativi

---+++ <font color=red>1. Definizioni preliminari </font>

   * Breve storia della visualizzazione di oggetti nei secoli
   * Modellizzazione teorica degli oggetti da rappresentare; differenza tra oggetto e sua rappresentazione
   * Definizioni di base di teroria dei grafi
   * Convenzioni (polyline, ortogonale, rettilinea, planare, upward, tridimensionale); criteri estetici (numero di incroci, area, numero di svolte, lunghezza degli archi, simmetrie, risoluzione angolare); precedenze tra i criteri estetici; vincoli (richiesta di posizionare un vertice al centro o sul contorno della rappresentazione, richiesta di raggruppare -clustering- vertici secondo alcuni criteri, richiesta di mantenere una certa forma).

 <font color=red>Materiale didattico di riferimento: </font>

   * E. Kruja, J. Marks, A. Blair, R. Waters: "A Short note on the history of Graph Drawing"; Proc. Graph Drawing (GD01), LNCS 2265, pp. 272-286, 2001.
   * C. Chen: Information Visualization beyond the horizon &#65533; 2nd Edition, Springer 2004, pp. 8-10.
   * G. Di Battista, P. Eades, R. Tamassia, I.G. Tollis: Graph Drawing Algorithms for the visualization of graphs, Prentice Hall, 1999, pp. 1-18.
   * M. Kaufmann, D. Wagner; Drawing Graphs: Methods and Models, Springer, 2001, pp. 1-22.


---+++ <font color=green>2. Visualizzazione di oggetti con struttura ad albero </font>

   * Esempio di oggetti con struttura ad albero: mappa di un file system, indice di una base di dati, alberi genealogici.
   * Terminologia per gli alberi.
   * Visualizzazione ortogonale ottima come H-tree
   * Un algoritmo di disegno upward planare basato sul livellamento dell'albero, con nodi a coordinate intere
   * Un algoritmo di disegno upward planare piu' efficiente
   * Un algoritmo di disegno radiale
   * Un algoritmo di disegno HV
   * Visualizzazione di gerarchie: tree maps, sun bursts, cone trees, alberi botanici

<font color=green>Materiale didattico di riferimento:</font>
   * G. Di Battista, P. Eades, R. Tamassia, I.G. Tollis: Graph Drawing Algorithms for the visualization of graphs, Prentice Hall, 1999, pp. 41-60.
   * Leiserson: Area-efficient graph layouts (for VLSI), Proc. 21th IEEE Symp. On Found. Of Compu. Sci (FOCS'80), pp. 270-281, 1980.
   * M. Kaufmann, D. Wagner; Drawing Graphs: Methods and Models, Springer, 2001, pp. 46-52.
   * A. Garg, M.T. Goodrich, R. Tamassia: "Planar Upward Tree Drawings with Optimal Area", Internat. J. Comput. Geom. Appl., 6, 333-356, 1996, pp. 2-6.
   * C. Chen: Information Visualization beyond the horizon &#65533; 2nd Edition, Springer 2004, pp 89-95, e pp.190-193; 
   * B.B. Bederson, B. Shneiderman and M. Wattenberg. Ordered and Quantum Trremaps: Making Effective Use of 2D Space to Display Hierarchies. ACM Trans. Graph. 21(4), 833-854, 2002, pp. 833-837; 
   * G.G. Robertson, J.D. Mackinlay and S.K. Card. Cone Trees: animated 3D visualizations of hierarchical information. ACM ??? , 189-194, 1991, pp 189-191.


---+++ <font color=yellow>3a. Visualizzazione di grafi: alcuni casi particolari </font>

   * Disegno ortogonale 2D: Codifiche di grafi; st-numerazione; Un algoritmo basato sulla st-numerazione; Un algoritmo basato sulla rappresentazione di visibilita'. Algoritmo di st-numerazione.
   * Disegno ortogonale 3D: Punto di vista; Alcune premesse di teoria dei grafi (caratterizzazione dei cicli euleriani e teorema di P. Hall, dim. del teorema di Eulero e dim. del teorema di P. Hall); Due algoritmi di disegno 3D ortogonale.
   * Disegno rettilineo 3D: Un algoritmo di disegno rettilineo e limitazione inferiore sul volume per grafi generali; algoritmo e limitazione inferiore per grafi 2-, 3- <font color=blue>e 4</font>-partiti. Teorema sulla limitazione inferiore del volume come funzione del numero di archi del grafo.
   * Disegno ortogonale interattivo: mantenere la mappa mentale; gli scenari del disegno interattivo; un algoritmo per dis. ortogonale su griglia 2d nello scenario relative-coordinates e uno nello scenario no-change; confronto tra i due scenari.
   * Visualizzazione di grafi in evoluzione (network evolution).

<font color=yellow>Materiale didattico di riferimento:</font>
   * M. Kaufmann, D. Wagner; Drawing Graphs: Methods and Models, Springer, 2001, pp. 121-141, esclusa sez. 6.2, 172, 176-180, 190-192, 228-240. PER APPROFONDIRE: pagg. 182-189.
   * G. Di Battista, R. Tamassia: Algorithms for Plane Representations of acyclic digraphs, Theoretical Computer Science 61, pp 175-198, 1988. solo sezioni 1, 2 e, della sezione 3, solo i teoremi 3.4, 3.5 e figura 12.
   * Nishizeki, T., Chiba, N.: "Planar graphs: theory and algorithms", North-Holland, Amsterdam, 1988, pp.34-40.
   * T. Biedl, G.Kant: "A better heuristic for orthogonal graph drawings", Proc. 2nd European Symp. on Algorithms (ESA'94), LNCS 855, pp.24-35.
   * P. Eades, A. Symvonis, S. Whitesides: Two Algorithms for Three Dimensional Orthogonal Graph Drawing;, Proc. Graph Drawing (GD&#65533;96) LNCS 1190, pp. 139-154, 1996 tutto. 
   * un qualunque testo di teoria dei grafi per la caratterizzazione dei circuiti euleruani e il teorema di P. Hall.
   * Cohen, Eades, Lin, Ruskey: 'Three-Dimensional Graph Drawing", Proc. Graph Drawing '94, LNCS 894, pp. 1-11, 1994. Solo sezioni 1 e 2, esclusa dimostrazione del teorema 1
   * G. Di Battista, P. Eades, R. Tamassia, I.G. Tollis: Graph Drawing; Algorithms for the visualization of graphs, Prentice Hall, 1999, pp. 99-102, 130-132, 137-138, 218-235.
   * C. Chen: Information Visualization beyond the horizon, Springer, 2004, pp. 278-282.
   * T. Calamoneri, A. Sterbini: 3D straigh-line drawing of 4-colorable graphs, Information Proc. Letters 63, pp. 97-102, 1997 tutto.

---+++ <font color=violet>3b. Generalizzazione della visualizzazione di grafi: il caso particolare del disegno ortogonale</font>

   * Esempi di estensione al caso di grado alto (2D ortogonale planare, 2D ortogonale non planare e 3D ortogonale); 
   * Esempi di estensione da grafi biconnessi a semplicemente connessi;
   * Esempi di estensione da grafi planari a non planari.

<font color=violet>Materiale didattico di riferimento:</font>

   * G. Di Battista, P. Eades, R. Tamassia, I.G. Tollis: Graph Drawing; Algorithms for the visualization of graphs, Prentice Hall, 1999, pp.168-169, 215-216, 253-262.
   * M. Kaufmann, D. Wagner; Drawing Graphs: Methods and Models, Springer, 2001, pp. 29-33.
   * T.Biedl, T.Shermer, S.Whitesides, S.Wismath: "Orthogonal 3-D Graph Drawing", Proc. Graph Drawing (GD'97), LNCS 1353, pp. 76-86, 1997.
   * T. Biedl, G.Kant: "A better heuristic for orthogonal graph drawings", Proc. 2nd European Symp. on Algorithms (ESA'94), LNCS 855, pp.24-35 (già citato in precedenza).

---+++ <font color=orange>3c. Ottimizzazione della visualizzazione di grafi: il caso particolare del disegno ortogonale</font>

   * Minimizzazione del numero di svolte: euristiche; 
   * Compattamento dell'area: metodo del flusso.

<font color=orange>Materiale didattico di riferimento:</font>

   * G. Di Battista, P. Eades, R. Tamassia, I.G. Tollis: Graph Drawing; Algorithms for the visualization of graphs, Prentice Hall, 1999, pp. 143-154, 157-161.
   * PER APPROFONDIRE: pp. 164-168.
   * M. Kaufmann, D. Wagner; Drawing Graphs: Methods and Models, Springer, 2001, pp. 167-169 (escluso alg. delle 4M).
   * PER APPROFONDIRE: pp.147-167.

---+++ <font color=purple>4. Visualizzazione di strutture molecolari</font>

   * Algoritmi basati sulla ricerca del punto di minimo delle forze di interazione: algoritmo di Garg e algoritmo di Tutte
   * Generalizzazione di Sugiyama e Misue, generalizzazione di Davidson e Harel e la tecnica del simulated annealing, generalizzazione di Harel e Koren
   * Vincoli.

<font color=purple>Materiale didattico di riferimento:</font>

   * G. Di Battista, P. Eades, R. Tamassia, I.G. Tollis: Graph Drawing &endash; Algorithms for the visualization of graphs, Prentice Hall, 1999, pp. 303-324, escluso par. 10.3.
   * C. Chen: Information Visualization beyond the horizon &#65533; 2nd Edition, Springer 2004, pp 77-80
   * PER APPROFONDIRE: Kaufmann pp. 71-86
   * PER APPROFONDIRE: D. Harel, Y. Koren. Drawing graphs with non uniform vertices. Proc. Working Conference on Advanced Visual Interfaces (AVI'02), 157--166. ACM Press, 2002.
 
---+++ <font color=red>5. Visualizzazione di superfici in 3 dimensioni</font>

   * Il problema della triangolazione: come calcolare i punti della triangolazione; come calcolare la triangolazione, dato l'insieme dei punti; triangolaione di De Lunay e diagramma di Voronoi;
   * Modelli di illuminazione: Modelli di illuminazione locali:modello di Lambert, luce ambientale, modello di Phong, attenuazione
   * Ombreggiature: flat shading, ombreggiatura di Gourard, ombreggiatura di Phong
   * Ombre proiettate e sorgenti estese

<font color=red>Materiale didattico di riferimento:</font>

   * D. Marini, M. Bertolo, A. Rizzi. Comunicazione Visiva Digitale &#65533; Fondamenti di eidomatica. Addison-Wesley, 2001, pp. 87-92, 254-259, 262-266.
   * G. Attardi, A. Bernasconi. Fondamenti di Computer Graphics, 1997. paragrafi 9.1, 9.2 e 9.4; http://medialab.di.unipi.it/web/IUM/Fondamenti/cap9.htm 

---+++ <font color=pink>6. Visualizzazione di topologie di interconnessione</font>

   * 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

<font color=pink>Materiale didattico di riferimento:</font>

   * F. T. Leighton: Introducton to Parallel Algorithms and Architectures: Arrays, Trees, Hypercubes. Morgan Kaufmann ed. 1992, pp. 440-442.
   * D.S. Wise: "Compact Layouts of Banyan/FFT Networks", VLSI Systems and Computations, pp.186-195, 1981, solo disegno e osservazioni su di esso.
   * G. Even, S. Even: "Embedding Interconnection Networks in Grids via the Layered Cross Product", Networks 36(2), pp. 91-95, 2000, esclusa sez. 3.3.


---+++ <font color=magenta>7. Visualizzazione di carte geografiche</font>

   * <font color=blue>Premessa: problemi NP-completi, riduzioni polinomiali; un algoritmo per 2-SAT</font>
   * 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
   * <font color=blue>Il problema della determinazione delle intersezioni di segmenti: algoritmo e sua correttezza</font>

<font color=magenta>Materiale didattico di riferimento:</font>
   * Cormen, Leiserson, Rivest; Introduzione agli algoritmi, Jackson Libri 1995, pp.864-877, 883-885 esclusa dim. Th. Di Cook.
   * C.H. Papadimitriou: Computational complexity, Addison-Wesley Publ. Co. 1994, pp 183-187.
   * M. Kaufmann, D. Wagner; Drawing Graphs: Methods and Models, Springer, 2001, pp. 247-273, esclusi par. 10.3.5, 10.3.6, 10.6.
   * M. de Berg, M. van Kreveld, M. Overmars, O. Schwarzkopf: Computational Geometry; Algorithms and Applications. Springer-Verlag, Heidelberg, 1997, pagg. 19-29.

---+++ <font color=green>8. Visualizzazione di oggetti molto grandi (infiniti)</font>

   * 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

<font color=green>Materiale didattico di riferimento: </font>

   * P. Eades, Q.-W. Feng: Multilevel Visualization of Clustered Graphs. Proc. Graph Drawing '96, LNCS 1190, pp. 101-112, 1996 escluso approccio gerarchico all'interno della sez. 3.1.
   * C. Chen: Information Visualization beyond the horizon &#65533; 2nd Edition, Springer 2004, pp 30-32.
   * PER APPROFONDIRE: M. Kaufmann, D. Wagner; Drawing Graphs: Methods and Models, Springer, 2001, pp. 193-227.