Tags:
create new tag
view all tags
---+++ <font color=990000 size="+2"> <b>Programma del Corso A.A. 2005/06 (provvisorio)</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, soprattutto, alle tesine, che vengono TUTTE messe in rete, siano esse di buona qualita' oppure no. N.B. Le parti di testo colorato 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 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 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 Sapce 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. ---++ AGGIORNATO FIN QUI ++ ---+++ <font color=yellow>3a. Visualizzazione di grafi: alcuni casi particolari </font> * Disegno ortogonale 2D: Codifiche di grafi; Un algoritmo basato sulla st-numerazione; Un algoritmo basato sulla rappresentazione di visibilita'. * Disegno 3D: Due algoritmi di disegno 3D ortogonale; Un algoritmo di disegno rettilineo ed alcune limitazioni inferiori. * Disegno ortogonale interattivo: alcuni scenari e algoritmi <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-230. * PER APPROFONDIRE: pagg. 182-189, * 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. * 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. * 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 * T. Calamoneri, A. Sterbini: 3D straigh-line drawing of 4-colorable graphs, Information Proc. Letters 63, pp. 97-102, 1997. ---+++ <font color=violet>3b. Ottimizzazione e generalizzazione della visualizzazione di grafi: il caso particolare del disegno ortogonale</font> * Generalizzazione: Esempi di estensione al caso di grado alto (2D ortogonale planare e 3D); <font color=violet>Esempi di estensione da grafi biconnessi a semplicemente connessi</font>, da planari a non planari * <font color=violet> Ottimizzazione: Minimizzazione del numero di svolte; Compattamento dell'area</font> <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. 143-145, 151-162, 215-216, 253-262. * PER APPROFONDIRE: pp. 164-168. * M. Kaufmann, D. Wagner; Drawing Graphs: Methods and Models, Springer, 2001, pp. 29-33, 141-143, 167-169 (escluso alg. delle 4M). * PER APPROFONDIRE: pp.147-167. * 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=red>4. Visualizzazione di superfici in 3 dimensioni</font> * Il problema della triangolazione: come calcolare i punti della triangolazione; come eliminare alcuni punti della triangolazione; come calcolare la triangolazione, dato l'insieme dei punti; diagrammi di Voronoi * Modelli di illuminazione: Il modello di Lambert; luce ambientale; il modello di Phong; attenuazione della luce <font color=red>Materiale didattico di riferimento:</font> * D. Marini, M. Bertolo, A. Rizzi. Comunicazione Visiva Digitale Fondamenti di eidomatica. Addison-Wesley, 2001, pp. 88-92, 254-262. ---+++ <font color=blue>5. Visualizzazione di strutture molecolari</font> * Algoritmi basati sulla ricerca del punto di minimo delle forze di interazione: algoritmo di Garg e algoritmo di Tutte * Generalizzazioni e vincoli; la tecnica del simulated annealing <font color=blue>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. * PER APPROFONDIRE: Kaufmann pp. 71-86 ---+++ <font color=magenta>6. Visualizzazione di carte geografiche</font> * Premessa: problemi NP-completi, riduzioni polinomiali; un algoritmo per 2-SAT * Il problema della etichettatura degli oggetti * Panoramica della complessita' del problema dell'etichettatura * Alcuni algoritmi di etichettatura <font color=magenta>Materiale didattico di riferimento:</font> * Cormen, Leiserson, Rivest; Introduzione agli algoritmi, Jackson Libri 1995, pp.863 ss. * M. Kaufmann, D. Wagner; Drawing Graphs: Methods and Models, Springer, 2001, pp. 247-273, esclusi par. 10.3.5, 10.3.6, 10.6. ---+++ <font color=pink>7. Visualizzazione di topologie di interconnessione</font> * Il modello di Thompson per il layout; vincoli dettati dalla tecnologia VLSI * 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=blue>8. Visualizzazione di oggetti molto grandi (infiniti)</font> * Esempi di oggetti molto grandi: mappa del web, relazioni di dipendenza tra moduli software * 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 <font color=blue>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. * PER APPROFONDIRE: M. Kaufmann, D. Wagner; Drawing Graphs: Methods and Models, Springer, 2001, pp. 193-227. -- Users.TizianaCalamoneri - 26 Sep 2005
E
dit
|
A
ttach
|
Watch
|
P
rint version
|
H
istory
: r2
<
r1
|
B
acklinks
|
V
iew topic
|
Ra
w
edit
|
M
ore topic actions
Topic revision: r2 - 2006-03-23
-
TizianaCalamoneri
Log In
or
Register
Algoritmi_vis Web ...
Algoritmi_vis Web
Algoritmi_vis Web Home
Users
Groups
Index
Search
Changes
Notifications
Statistics
Preferences
User Reference ...
User Reference
ATasteOfTWiki
TextFormattingRules
TWikiVariables
FormattedSearch
TWikiDocGraphics
TWikiSkinBrowser
InstalledPlugins
ChangeEmailAddress
ChangePassword
ResetPassword
Prenotazioni esami
Laurea Triennale ...
Laurea Triennale
Algebra
Algoritmi
Introduzione agli algoritmi
Algoritmi 1
Algoritmi 2
Algoritmi per la
visualizzazione
Architetture
Prog. sist. digitali
Architetture 2
Basi di Dati
Basi di Dati 1 Inf.
Basi di Dati 1 T.I.
Basi di Dati (I modulo, A-L)
Basi di Dati (I modulo, M-Z)
Basi di Dati 2
Calcolo
Calcolo differenziale
Calcolo integrale
Calcolo delle Probabilitą
Metodi mat. per l'inf. (ex. Logica)
canale AD
canale PZ
Programmazione
Fond. di Programmazione
Metodologie di Programmazione
Prog. di sistemi multicore
Programmazione 2
AD
EO
PZ
Esercitazioni Prog. 2
Lab. Prog. AD
Lab. Prog. EO
Lab. Prog. 2
Prog. a Oggetti
Reti
Arch. di internet
Lab. di prog. di rete
Programmazione Web
Reti di elaboratori
Sistemi operativi
Sistemi Operativi (12 CFU)
Anni precedenti
Sistemi operativi 1
Sistemi operativi 2
Lab. SO 1
Lab. SO 2
Altri corsi
Automi, Calcolabilitą
e Complessitą
Apprendimento Automatico
Economia Aziendale
Elaborazione Immagini
Fisica 2
Grafica 3D
Informatica Giuridica
Laboratorio di Sistemi Interattivi
Linguaggi di Programmazione 3° anno Matematica
Linguaggi e Compilatori
Sistemi Informativi
Tecniche di Sicurezza dei Sistemi
ACSAI ...
ACSAI
Computer Architectures 1
Programming
Laurea Magistrale ...
Laurea Magistrale
Percorsi di studio
Corsi
Algoritmi Avanzati
Algoritmica
Algoritmi e Strutture Dati
Algoritmi per le reti
Architetture degli elaboratori 3
Architetture avanzate e parallele
Autonomous Networking
Big Data Computing
Business Intelligence
Calcolo Intensivo
Complessitą
Computer Systems and Programming
Concurrent Systems
Crittografia
Elaborazione del Linguaggio Naturale
Estrazione inf. dal web
Fisica 3
Gamification Lab
Information Systems
Ingegneria degli Algoritmi
Interazione Multi Modale
Metodi Formali per il Software
Methods in Computer Science Education: Analysis
Methods in Computer Science Education: Design
Prestazioni dei Sistemi di Rete
Prog. avanzata
Internet of Things
Sistemi Centrali
Reti Wireless
Sistemi Biometrici
Sistemi Distribuiti
Sistemi Informativi Geografici
Sistemi operativi 3
Tecniche di Sicurezza basate sui Linguaggi
Teoria della
Dimostrazione
Verifica del software
Visione artificiale
Attivitą complementari
Biologia Computazionale
Design and development of embedded systems for the Internet of Things
Lego Lab
Logic Programming
Pietre miliari della scienza
Prog. di processori multicore
Sistemi per l'interazione locale e remota
Laboratorio di Cyber-Security
Verifica e Validazione di Software Embedded
Altri Webs ...
Altri Webs
Dottorandi
Commissioni
Comm. Didattica
Comm. Didattica_r
Comm. Dottorato
Comm. Erasmus
Comm. Finanziamenti
Comm. Scientifica
Comm Scientifica_r
Corsi esterni
Sistemi Operativi (Matematica)
Perl e Bioperl
ECDL
Fondamenti 1
(NETTUNO)
Tecniche della Programmazione 1° modulo
(NETTUNO)
Seminars in Artificial Intelligence and Robotics: Natural Language Processing
Informatica generale
Primo canale
Secondo canale
II canale A.A. 10-11
Informatica
Informatica per Statistica
Laboratorio di Strumentazione Elettronica e Informatica
Progetti
Nemo
Quis
Remus
TWiki ...
TWiki
Tutto su TWiki
Users
Main
Sandbox
Home
Site map
AA web
AAP web
ACSAI web
AA2021 web
Programming web
AA2021 web
AN web
ASD web
Algebra web
AL web
AA1112 web
AA1213 web
AA1920 web
AA2021 web
MZ web
AA1112 web
AA1213 web
AA1112 web
AA1314 web
AA1415 web
AA1516 web
AA1617 web
AA1819 web
Old web
Algo_par_dis web
Algoreti web
More...
Algoritmi_vis Web
Create New Topic
Index
Search
Changes
Notifications
RSS Feed
Statistics
Preferences
View
Raw View
Print version
Find backlinks
History
More topic actions
Edit
Raw edit
Attach file or image
Edit topic preference settings
Set new parent
More topic actions
Account
Log In
Register User
Questo sito usa cookies, usandolo ne accettate la presenza. (
CookiePolicy
)
Torna al
Dipartimento di Informatica
E
dit
A
ttach
Copyright © 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