Studenti della laurea triennale

Si ricorda che tutti gli studenti iscritti alla laurea triennale devono OBBLIGATORIAMENTE presentare un progetto. Un progetto puo' essere fatto singolarmente o in coppia. Prima di cominciare un progetto, e' necessario contattare Tiziana Calamoneri scrivendo a calamo@diNOSPAM.uniroma1.it (bisogna cancellare la stringa NOSPAM dall'indirizzo). Unitamente al progetto va consegnata anche una relazione esplicativa del progetto, le cui istruzioni di compilazione sono dettagliate nel seguito.

Attenzione: per implementare gli algoritmi richiesti nel progetto è necessario consultare l'articolo originale: nelle dispense i dettagli implementativi sono omessi!

Possibili progetti A.A. 2008/09 elenco aggiornato al 1/4/09

• Alberi: Algoritmo di Reingold e Tilford; gerarchie: algoritmo per treemaps di Shneiderman & Wattenberg basato sull'idea del quicksort
• Alberi: Algoritmo H-tree (per alberi completi e non); gerarchie: algoritmo Slice & Dice (peso=num. dei nodi nel sottoalbero)
• Alberi: disegno HV; grafi: disegno ortogonale su griglia 2D basato sulla st-numerazione

*Progetti assegnati durante l'A.A. 2007/08*

• Alberi: Algoritmo di Reingold e Tilford; grafi: algoritmo di Tutte (ed, eventualmente, sue generalizzazioni)
• Alberi: disegno HV; grafi: disegno ortogonale su griglia 2D basato sulla st-numerazione
• Alberi: disegno H-tree; grafi: disegno ortogonale su griglia 2D per grafi di grado alto

Modalita' di presentazione dei progetti Piu' o meno 20 giorni prima della data dell'orale, e' in calendario appelli una data per presentare i progetti: l'appuntamento e' nel mio studio, in modo che possiate mostrare l'esecuzione di entrambi i programmi (per alberi e per grafi). Lo stesso giorno va presentata anche la relazione (cartacea). Il progetto, quindi, NON va inviato per e-mail. Il giorno della presentazione dei progetti, entrambi i programmi devono girare sul vostro portatile, se ne avete uno, oppure su un computer in laboratorio che avrete opportunamente sistemato in precedenza. La relazione abbinata al progetto deve contenere:

• nome e cognome dell'autore del progetto.
• indicazioni sugli algoritmi implementati ed eventuali varianti utilizzate.
• screen shots di almeno 3 run di ciascun algoritmo, in cui ogni albero in input abbia almeno 30 nodi e ogni grafo in input almeno 20. A fianco ad ogni screen shot si deve mettere un disegno (anche fatto manualmente) dell'albero o del grafo in input.
• una breve trattazione delle strutture dati utilizzate.
• un resoconto della complessità computazionale, tenendo conto delle strutture dati usate.

Studenti della laurea magistrale

Gli studenti iscritti alla laurea magistrale devono OBBLIGATORIAMENTE presentare un progetto o una tesina, a scelta. Alcuni possibili argomenti di tesine sono riportati nel seguito. Non sono esclusi argomenti non riportati qui che potrebbero interessare, previa comunicazione al docente. Per dare la propria disponibilita', ed evitare di fare in molti lo stesso lavoro, prima di cominciare, contattare Tiziana Calamoneri scrivendo a calamo@diNOSPAM.uniroma1.it (bisogna cancellare la stringa NOSPAM dall'indirizzo).

Possibili tesine elenco aggiornato all'11/3/08

• visualizzazione di gerarchie secondo tecniche non viste a lezione
• algoritmo di Garg, Goodrich e Tamassia per il disegno di alberi (con tutti i dettagli)
• algoritmi di Papakostas e Tollis per il disegno ortogonale su griglia di grafi basato sulla pairing technique
• algoritmi per il best view point approssimato (dis. ortogonale 3d)
• algoritmo di Fossmeier e Kaufmann ('96) per l'estensione al grado alto basato sulla rappresentazione di visibilità
• algoritmo di Tamassia ('87) per minimizzare il numero di svolte utilizzando il minimo flusso
• algoritmo di Harel e Koren ('02) per usare il metodo delle forze su grafi con nodi non puntiformi

Tesine scritte dagli studenti

Tesine scritte dagli studenti dell'A.A. 05/06:

• Tree Maps.1.doc
• Miglior punto di vista.doc
• algoritmo di flipping.pdf
• Simulated Annealing.doc
• Calcolo punti in ombra.pdf
• carte geografiche.pdf
• minimo flusso.pdf
• HyperbolicTrees.doc
• Sunburst.pdf

Tesine scritte dagli studenti dell'A.A. 04/05:

• Approfondimenti sui modelli di illuminazione
• Compattamento Area caso ortogonale
• Soluzione per i Sistemi lineari
• Dettagli della dimostrazione di Tamassia e Tollis
• Etichettatura Carte geografiche
• Preservare la mappa mentale
• Visualizzazione di Grandi Grafi
• Grafi Clusterizzati
• Modelli di illuminazione
• Disegno di Alberi Dinamici

Tesine scritte dagli studenti dell'A.A. 03/04:

SULLA PARTE 3a DEL PROGRAMMA:

• Disegno Ortogonale 3D: Preliminaries
• Disegno Ortogonale 3D: alg. di disegno compatto
• DisegnoOrtogonale 3D: algoritmo 3bends
• disegno 3D rettilineo
• Approfondimento:Pairing Technique di Papakostas e Tollis

SULLA PARTE 3b DEL PROGRAMMA:

• Disegno Ortogonale 3D con grado alto
• Approfondimento: Metodi Del Flusso:

SULLA PARTE 4 DEL PROGRAMMA:

• Approfondimento: Diagrammi di Voronoi
• Approfondimento: Triangolazione di Delunay

SULLA PARTE 6 DEL PROGRAMMA:

* Approfondimento: Algoritmo polinomiale per 2SAT

SULLA PARTE 7 DEL PROGRAMMA:

• Layout di topologie di interconnessione

SULLA PARTE 8 DEL PROGRAMMA:

• Approfondimento: Fish Eye e Navigazione