====== Progetto di ASD 2014/2015 ======

Il progetto si basa su file presi dal mondo reale e prevede di effettuare un'analisi sperimentale dei dati su un insieme S di alcune pagine prese da wikipedia e "ripulite" dalla formattazione (ringraziamenti a Marco Cornolti e Francesco Piccinno per aver messo a disposizione tali dati):
  * qui c'è un piccolo campione per fare le prove {{:matematica:asd:asd_14:wiki-small.zip|}};
  * qui c'è un campione di circa 21mila pagine per un totale di circa 100 milioni di caratteri {{:matematica:asd:asd_14:wikipedia_20k.zip|}}: più pagine si riescono a trattare, meglio è.

Lo scopo è costruire un grafo G=(V,E) a partire dall'insieme S, dove V rappresenta le parole distinte che si trovano nelle varie pagine in S e un arco (u,v) di E rappresenta il fatto che le due parole u e v appaiono consecutivamente (in alternativa, sufficientemente vicine) in una di tali pagine. 

Sono lasciate allo studente delle scelte:
  * se ignorare le "stop word" come articoli, preposizioni, ecc.;
  * se vedere G come grafo orientato o meno;
  * se vedere G come grafo pesato o meno.

Nell'ultimo caso, è possibile associare dei pesi agli archi, per esempio, usando la mutua informazione [[http://en.wikipedia.org/wiki/Pointwise_mutual_information]] [[http://dl.acm.org/citation.cfm?id=89095]]. Ma anche altre misure possono essere usate (o magari inventate allo scopo).

Utilizzando la struttura di tale grafo G, possibilmente annotato con ulteriori informazioni se necessario, il progetto richiede allo studente di concepire e implementare algoritmi per 
  * identificare parole importanti, intese non solo come singole parole, ma anche come gruppi di parole;
  * data una "nuova" pagina non appartenente a S, stabilirne l'importanza utilizzando le parole importanti identificate nel punto precedente.
 
Nello svolgimento del progetto, può essere utile vedere ogni pagina come un cammino (pesato o meno) in G e considerare i nodi di G che corrispondono alle parole importanti. Potrebbero esserci problemi di allocazione di memoria per G quando si elaborano un numero elevato di pagine: in tal caso, conviene fare più passate di lettura per costruire G un pezzo alla volta. Inoltre, conviene sempre memorizzare G utilizzando le liste di adiacenza, dove quest'ultime sono in realtà un array di array di varia lunghezza: se d(u) indica il grado di un nodo u, conviene fare una prima passata per scoprire il valore di d(u) e allocare un array di d(u) elementi per ogni nodo u, e una seconda passata per riempire tali array con le corrispondenti liste dei vicini. Quindi il termine "lista" va inteso in senso lato per occupare meno memoria. 

Durante lo svolgimento del progetto, possono essere utili un paio di strumenti:
  * ''od -c'' vedi [[http://linux.about.com/library/cmd/blcmdl1_od.htm]]
  * ''mmap'' vedi [[matematica:asd:asd_14:mmap]] e [[http://man7.org/linux/man-pages/man2/mmap.2.html]]