Differenze

Queste sono le differenze tra la revisione selezionata e la versione attuale della pagina.

--- matematica:asd:asd_20:progetto_17 [13/05/2021 alle 15:24 (4 anni fa)] – Roberto Grossi
+++ matematica:asd:asd_20:progetto_17 [21/05/2021 alle 11:41 (4 anni fa)] (versione attuale) – Roberto Grossi
@@ Linea 9: / Linea 9: @@
 Il progetto si compone di varie fasi:
   - Scaricare e studiare il formato dei dati utilizzati da IMDB nel [[http://www.imdb.com/interfaces|sito ufficiale]]. In particolare, ai fini del progetto sono necessari soltanto i seguenti file testuali, recuperabili al [[https://datasets.imdbws.com/|link]]:
-    - [[https://datasets.imdbws.com/name.basics.tsv.gz|name.basics.tsv.gz]]       lista di attori, attrici, ecc.
+    - [[https://datasets.imdbws.com/name.basics.tsv.gz|name.basics.tsv.gz]]:       lista di attori, attrici, ecc.
-    - [[https://datasets.imdbws.com/title.basics.tsv.gz|title.basics.tsv.gz]]      lista di film
+    - [[https://datasets.imdbws.com/title.basics.tsv.gz|title.basics.tsv.gz]]:      lista di film
-    - [[https://datasets.imdbws.com/title.principals.tsv.gz|title.principals.tsv.gz]]  chi ha lavorato in quali film
+    - [[https://datasets.imdbws.com/title.principals.tsv.gz|title.principals.tsv.gz]]:  chi ha lavorato in quali film
-  - Costruire il suddetto grafo //G=(V,E)// utilizzando tali file. Utilizzare le liste di adiacenza per memorizzare il grafo (ed evitare problemi di eccessiva occupazione di memoria).
+  - Costruire una rete sociale rappresentata tramite il suddetto grafo //G=(V,E)// utilizzando tali file. Utilizzare le liste di adiacenza per memorizzare il grafo (ed evitare problemi di eccessiva occupazione di memoria).
+  - Studiare la nozione di **centralità dei nodi nei grafi**, da applicare alle reti sociali, seguendo il materiale di [[http://matteo.rionda.to/centrtutorial/|questo tutorial online]] e il contenuto di [[https://vigna.di.unimi.it/ftp/papers/AxiomsForCentrality.pdf|questo paper]].
+  - Progettare e implementare degli algoritmi per la centralità, selezionandoli da quanto studiato sopra. Evitare gli algoritmi puramente numerici, essendo quest'ultimi studiati in insegnamenti dedicati, preferendo gli algoritmi che usano la struttura combinatoria del grafo descritto sopra.
-Utilizza i dati dei trasporti locali della città di Parigi e chiede di realizzare un "city route planner", che permette di stabilire il percorso tra due fermate fornite come interrogazione. I passi concettuali sono i seguenti:
-  - utilizzare i dati per la città di Parigi [dettagli di seguito];
+//Nota sul formato dei file.// I file che terminano in *.tsv (tab separated values), sono utilizzati come formato semplice di scambio: ogni riga testuale rappresenta un "record" i cui campi sono separati da una spaziatura tabulata ('\t' in C/C++). . Occorre quindi leggere una linea alla volta di ciascun file e separare i campi. Per esempio, possiamo reindirizzare l'input da tastiera in modo che il comando di lettura ''cin'' legga da file invece che da tastiera, usando il comando:
-  - scegliere un giorno della settimana;
-  - prendere i mezzi di trasporto disponibili quel giorno per muoversi in città;
-  - interrogare i dati con input: due qualunque fermate A e B, un orario P di partenza da A, un tempo limite T massimo di percorrenza;
-  - stimare l'orario di arrivo in B partendo da A al tempo P, purché sia rispettato il tempo limite P+T
-  - elencare i mezzi per arrivare in orario (come stimato nel punto 5)
-I dati per Parigi possono essere scaricati accedendo alle pagine di Microsoft Teams per il corso, nella sezione "files", c'è il folder denominato "Progetto_ASD_2019_2020".
+<code>freopen("file.tsv", "r", stdin);</code>
-La descrizione dei campi utilizzati in tali dati si trova nel seguente articolo, a partire dalla pagina 10: [[https://www.nature.com/articles/sdata201889|Kujala, R., Weckström, C., Darst, R. et al. A collection of public transport network data sets for 25 cities. Sci Data 5, 180089 (2018).]]
+A questo punto possiamo leggere ogni riga di ''file.tsv'' come stringa C++ ed estrarne i campi separati dal delimitatore '\t'. Iterando più volte sulla riga, possiamo ottenere tutti i campi.
-I dati forniti sono presi da un data set reale e non sono tutti strettamente necessari allo svolgimento del progetto. Occorre quindi procedere per gradi (che poi sono anche i criteri di valutazione del progetto):
-  * definire chiaramente l’obiettivo
-  * capire quali sono i dati rilevanti per raggiungere l’obiettivo
-  * costruire un opportuno grafo basandosi su tali dati
-  * proporre e implementare una soluzione per il problema algoritmico su grafi che naturalmente emerge
-Si noti che il progetto va svolto modellando il problema come un problema su grafi (orientati o meno) in cui i nodi e gli archi sono etichettati.
-//Nota.// Nella soluzione proposta è sempre possibile camminare tra due fermate, come alternativa agli altri mezzi, alla [[https://en.wikipedia.org/wiki/Preferred_walking_speed|velocità di 5km all'ora]].
-//Nota sul formato dei file.// I file che terminano in *.csv (textual comma separated values), sono utilizzati come formato semplice di scambio: ogni riga testuale rappresenta un "record" i cui campi sono separati da un punto e virgola nel nostro caso. Occorre quindi leggere una linea alla volta di ciascun file e separare i campi. Per esempio, possiamo reindirizzare l'input da tastiera in modo che il comando di lettura ''cin'' legga da file invece che da tastiera, usando il comando:
-<code>freopen("file.csv", "r", stdin);</code>
-A questo punto possiamo leggere ogni riga di ''file.csv'' come stringa C++ ed estrarne i campi separati dal delimitatore ';'. Iterando più volte sulla riga, possiamo ottenere tutti i campi.
 <code>
@@ Linea 49: / Linea 27: @@
 string s;
 cin >> s;
-string delimitatore = “;”;
+string delimitatore = “\t”;
 string campo = s.substr(0, s.find(delimitatore));
 </code>
+Per decomprimere i file *.tsv.gz lanciare il comando <code>gunzip *.tsv.gz</code> Per scorrere un file *.tsv usare il comando "less" ("more" oppure "cat") seguito dal nome del file *.tsv, poiché alcuni editor potrebbero non essere in grado di aprire tali file.
+Per vedere le prime N linee di un file *.tsv (o le ultime N righe) lanciare il comando "head -N" (oppure "tail -N") seguito dal nome del file *.tsv, dove N è appunto il numero di righe che si vuole esaminare. Per vedere i singoli caratteri, i tab, ecc., lanciare il comando "od -c" seguito dal nome del file *.tsv.