Differenze

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

--- matematica:asd:asd_22:progetto_21 [27/05/2023 alle 21:26 (2 anni fa)] – Roberto Grossi
+++ matematica:asd:asd_22:progetto_21 [17/07/2023 alle 11:44 (2 anni fa)] (versione attuale) – Roberto Grossi
@@ Linea 9: / Linea 9: @@
 ==== Prima parte ====
-Questa parte richiede un po' di analisi dei dati per poter poi costruire il grafo G. I dati di interesse per il progetto sono in tre file testuali, inputs.csv, outputs.csv e transactions.csv, che possono essere scaricati dal seguente [[https://unipiit.sharepoint.com/:f:/s/a__td_53655/EpZSfavnOkxKpjl4340DKacB__kBZ9p0LZ1--7JmN3-hWw?e=zKGpcr|LINK]] (sono tre file da 183Mb, 100Mb e 30Mb).
+Questa parte richiede un po' di analisi dei dati per poter poi costruire il grafo G. I dati di interesse per il progetto sono in tre file testuali, inputs.csv, outputs.csv e transactions.csv, che possono essere scaricati dal seguente [[https://unipiit.sharepoint.com/:f:/s/a__td_53655/EpZSfavnOkxKpjl4340DKacB__kBZ9p0LZ1--7JmN3-hWw?e=zKGpcr|LINK]] (sono tre file da 183Mb, 100Mb e 30Mb).  (Per fare una prova, si può usare un piccolo esempio {{ :matematica:asd:asd_22:small.zip |small.zip}})
 Vediamoli in dettaglio, utilizzando il comando ''wc'' (word count) in Linux, dove ciascuno dei tre file corrisponde a una riga: nella prima colonna è riportato il numero di linee del file, nella terza il numero totale di caratteri (la seconda colonna non interessa nel nostro caso).
@@ Linea 189: / Linea 190: @@
   * In tale grafo, prendere una delle componenti connesse più grandi, ignorando la direzione degli archi. Tale componente connessa gigante diventa il nostro grafo G.
-Si osservi che in principio G è aciclico, ma le transazioni all'interno di un blocco sono simultanee. Tra di loro si possono creare dei piccoli cicli in cui una transazione paga e la ricevente le fornisce "il resto": un po' come quando si paga con una banconota con resto e il vero valore trasferito è la differenza degli amount delle due transazioni (ricordiamo, stesso blocco) che sono collegate tra loro da due archi (qui c'è un esempio estremo di tali coppie di  [[https://www.blockchain.com/explorer/transactions/btc/43d41a287996d4df74d147308ae3d6ea7960af0b0b0ab967c836f39be96bef22|transazioni]] che per pagare circa 26 dollari viene inviato l'equivalente di 766 191 271 dollari in Bitcoin per ricevere come resto la differenza di 766 191 245 dollari in Bitcoin). Volendo si possono ignorare tale transazioni ai fini del progetto.
+Si osservi che in principio G è aciclico, ma le transazioni all'interno di un blocco sono simultanee. Tra di loro si possono creare dei piccoli cicli in cui una transazione paga e la ricevente le fornisce "il resto": un po' come quando si paga con una banconota con resto e il vero valore trasferito è la differenza degli amount delle due transazioni (ricordiamo, stesso blocco) che sono collegate tra loro da due archi (c'è un [[https://www.blockchain.com/explorer/transactions/btc/43d41a287996d4df74d147308ae3d6ea7960af0b0b0ab967c836f39be96bef22|esempio estremo]] di tali coppie di transazioni dove, per pagare circa 26 dollari, viene inviato l'equivalente di 766 191 271 dollari in Bitcoin per ricevere come resto la differenza di 766 191 245 dollari in Bitcoin).
 ==== Terza parte ====
-Una volta costruito il grafo ripulito, G risulta essere una sola componente connessa gigante quando la direzione degli archi è ignorata.
+Una volta costruito il grafo G come una sola componente connessa gigante, quando la direzione degli archi è ignorata, la terza parte richiede di svolgere i seguenti compiti:
-La terza parte richiede di svolgere i seguenti compiti:
+  * Rimuovere da G le coppie di archi (x,y) con amount = a1 e (y,x) con amount = a2, dove a1 > a2, rimuovere (y,x) e lasciare (x,y) con amount = a1 - a2. Verificare se G sia ancora ciclico o meno.
-  * Modellare la nozione di flusso di moneta, che viene trasferita attraverso le varie transazioni, come un cammino orientato in G in cui si incontrano gli amount nei nodi.
+  * Modellare la nozione di flusso di moneta, che viene trasferita attraverso le varie transazioni, come un cammino orientato in G in cui si incontrano gli amount negli archi.
   * Progettare un algoritmo che, partendo da una transazione presa come nodo u di partenza, individua tutti i flussi di denaro che si propagano in G a partire da u e che superano una certa soglia di valore.
-Per favorire la programmazione e il debug, verrà fornito un piccolo grafo di esempio al seguente LINK:
+Per favorire la programmazione e il debug, viene fornito un piccolo grafo di esempio {{ :matematica:asd:asd_22:small.zip |small.zip}}
-NOTA del docente: preparazione di un piccolo esempio in corso!
-**Ringraziamenti.** Il dott. Damiano Di Francesco Maesa ha cortesemente fornito i file ripuliti, inputs.csv, outputs.csv e transactions.csv, e chiarimenti sul loro contenuto.
+**Ringraziamenti.** Il dott. Damiano Di Francesco Maesa ha cortesemente fornito i file ripuliti, inputs.csv, outputs.csv e transactions.csv, e chiarimenti sul loro contenuto. I tutor Federico Lazzeri e Alberto L'Episcopo hanno fornito parte del codice e un piccolo esempio per fare il test.