| KEYWORD |
Algoritmi per la visualizzazione automatica di grafi
Parole chiave CIRCUITO, GRAFO, RENDERING, VISUALIZZAZIONE
Riferimenti STEFANO GRIVET TALOCIA
Gruppi di ricerca EMC Group (Electromagnetic Compatibility)
Descrizione Un grafo è un insieme di elementi (nodi o vertici) che possono essere collegati fra loro da linee (lati). Il campo di applicazione della teoria dei grafi e' estremamente vasto e differenziato: un grafo fornisce gli strumenti ideali per descrivere la topologia dei circuiti elettrici e elettronici, delle reti di telecomunicazioni, delle reti di trasporto (stradale, ferroviaria), e persino delle reti di interazioni sociali fra individui o gruppi.
Per definire un grafo e' sufficiente specificare l'insieme dei nodi e, per ogni lato, a quale coppia di nodi esso e' connesso. In svariate applicazioni risulta pero' utile una visualizzazione o rendering del grafo, che consiste nello specificare anche le coordinate di ogni nodo e il percorso di ogni lato, inteso come curva nel piano o nello spazio. Solo queste informazioni permettono di disegnare il grafo, rendendone evidente la struttura "ad occhio". In alcune applicazioni (ad esempio, reti di trasporto stradale o ferroviario), le coordinate dei nodi sono date (le stazioni da raggiungere), mentre possono costituire parametri di progetto i percorsi dei lati e quali lati siano necessari (ad esempio, per garantire di raggiungere ogni stazione). In altre applicazioni, invece, il grafo e' noto solo mediante una definizione astratta, e mancano completamente le informazioni necessarie alla sua visualizzazione. Ad esempio, durante il progetto di un sistema elettronico complesso costituito da un gran numero di componenti che devono essere posizionati su un circuito stampato e successivamente collegati fra loro, sono necessari opportuni algoritmi (place and route) che in modo del tutto automatico permettano di definire la posizione dei vari componenti ed il percorso dei relativi collegamenti, in modo da ottimizzare opportuni parametri (ad esempio, l'area complessivamente occupata o la lunghezza complessiva dei collegamenti). Per tali applicazioni, il concetto di "visualizzazione" coincide con il progetto CAD del layout del circuito.
Questa tesi si propone di studiare gli algoritmi esistenti di visualizzazione automatica di grafi, e di sviluppare un software in ambiente Matlab che realizzi i principali. Particolare attenzione sara' dedicata ai grafi planari (che possono essere disegnati su un piano senza che i percorsi si incrocino), visto l'elevato interesse applicativo (in particolare, nella teoria dei circuiti). Il lavoro di tesi prevede anche la modifica di algoritmi esistenti per includere, mediante opportune formulazioni matematiche, i vincoli che permettono di ottenere visualizzazioni chiare ed equilibrate dal punto di vista estetico. Tali vincoli dipendono dalle applicazioni specifiche per cui viene determinata la visualizzazione. Le applicazioni che saranno considerate dipenderanno dal candidato/a e dai suoi interessi.
Conoscenze richieste Predisposizione per la formalizzazione matematica di problemi e algoritmi. Programmazione in ambiente Matlab. Utile conoscenza di linguaggio C/C++ per utilizzare librerie software
Scadenza validita proposta 07/10/2021
PROPONI LA TUA CANDIDATURA