|
Prossima revisione
|
Revisione precedente
|
matematica:asd:asd_13:progetto_13 [09/06/2014 alle 15:22 (10 anni fa)]
Roberto Grossi creata |
matematica:asd:asd_13:progetto_13 [13/08/2014 alle 15:00 (10 anni fa)] (versione attuale)
Roberto Grossi |
| Questo progetto viene valutato in trentesimi e sostituisce l'esame scritto del corso o il seminario, e non necessita la presentazione del mini-progetto. Può essere scelto il seguente tema oppure un argomento da concordare con il docente. | Questo progetto viene valutato in trentesimi e sostituisce l'esame scritto del corso o il seminario, e non necessita la presentazione del mini-progetto. Può essere scelto il seguente tema oppure un argomento da concordare con il docente. |
| |
| Progetto in C/C++ (o altro linguaggio da concordare con il docente) per estrarre clique massimali da un grafo (orientato o meno). Dato un grafo G=(V,E), una clique è un sottoinsieme Q di vertici in V, connessi a due a due, cioè per ogni x e y in V esiste un arco (x,y) in E. Una clique Q è massimale se non esiste altra clique Q' massimale che contiene Q (ricordare che entrambe Q e Q' sono sottoinsiemi di vertici in V). | Progetto in C/C++ (o altro linguaggio da concordare con il docente) per estrarre **clique massimali** da un grafo (orientato o meno). Dato un grafo G=(V,E), una clique è un sottoinsieme Q di vertici in V, connessi a due a due, cioè per ogni x e y in V esiste un arco (x,y) in E. Una clique Q è massimale se non esiste altra clique Q' massimale che contiene Q (ricordare che entrambe Q e Q' sono sottoinsiemi di vertici in V). |
| |
| | Il progetto è ispirato al [[http://www.cs.uiuc.edu/homes/hanj/cs512/bk2chaps/chapter_9.pdf|graph mining]] e richiede di prendere un grafo G e un intero k, e di restituire tutte le clique massimali Q che sono contenute in G e che sono composte da almeno k vertici, cioè vale |Q| >= k. Per risolvere il problema possono essere utili delle tecniche di enumerazione nei grafi (tutorial da consultare, non va letto tutto: |
| | {{:matematica:asd:asd_13:uno1.pdf|parte1}}, |
| | {{:matematica:asd:asd_13:uno2.pdf|parte2}}, |
| | {{:matematica:asd:asd_13:uno3.pdf|parte3}}. |
| | Conviene provare ad attaccare il problema con i propri mezzi prima di addentrarsi nella bibliografia e nelle pubblicazioni reperibili in rete. |
| |
| | Per i dati, ci sono oltre [[http://amici.dsi.unifi.it/lasagne/?page_id=19|150 grafi disponibili (real-life network)]] su cui sperimentare il proprio codice: scegliere l'opzione network e quindi una tipologia di grafo nel menù a tendina, per poterlo scaricare. Il formato di ciascun file contiene le seguenti informazioni: la prima linea contiene il numero N di vertici del grafo e le N linee seguenti contengono ciascuna una coppia di interi I e D_I separati da uno spazio, a indicare che il vertice I ha grado D_I, dove I = 0, 1, 2, ..., N-1. Infine, le rimanenti linee contengono ciascuna una coppia di interi I e J separati da uno spazio, dove J è maggiore di I, a indicare che l'arco non orientato (I,J) appartiene al grafo. Notare che, per risparmiare spazio, per il vertice I sono riportati soltanto i vertici adiacenti J maggiori di I (ignorare i self-loop del tipo I I). |
