Implementare una libreria che offre un algoritmo di ordinamento Merge-BinaryInsertion Sort. Con BinaryInsertion Sort ci riferiamo a una versione dell'algoritmo Insertion Sort in cui la posizione, all'interno della sezione ordinata del vettore, in cui inserire l'elemento corrente è determinata tramite ricerca binaria. Il Merge-BinaryInsertion Sort è un algoritmo ibrido che combina Merge Sort e BinaryInsertion Sort. L'idea è di approfittare del fatto che il BinaryInsertion Sort può essere più veloce del Merge Sort quando la sottolista da ordinare è piccola. Ciò suggerisce di considerare una modifica del Merge Sort in cui le sottoliste di lunghezza k o inferiore sono ordinate usando il BinaryInsertion Sort e sono poi combinate usando il meccanismo tradizionale di fusione del Merge Sort. Il valore del parametro k dovrà essere studiato e discusso nella relazione. Ad esempio, k=0 implica che Merge-BinaryInsertion Sort si comporta esattamente come il Merge Sort classico, mentre k>>0 aumenta l'utilizzo del BinaryInsertion Sort.
Il codice che implementa Merge-BinaryInsertion Sort deve essere generico. Inoltre, la libreria deve permettere di specificare (cioè deve accettare in input) il criterio secondo cui ordinare i dati.
Implementare gli unit-test per la libreria secondo le indicazioni suggerite nel documento Unit Testing.
Il file records.csv che potete trovare (compresso) all'indirizzo
https://mega.nz/file/dskTnYYR#lYsIorxm7t30pEJghBUXt7JGPyqanvHgGgOpLfbTIGo
contiene 20 milioni di record da ordinare. Ogni record è descritto su una riga e contiene i seguenti campi:
- id: (tipo intero) identificatore univoco del record;
- field1: (tipo stringa) contiene parole estratte dalla divina commedia, potete assumere che i valori non contengano spazi o virgole;
- field2: (tipo intero);
- field3: (tipo floating point);
Il formato è un CSV standard: i campi sono separati da virgole; i record sono
separati da \n.
Usando l'algoritmo implementato, si ordinino i record (non è sufficiente ordinare i
singoli campi) contenuti nel file records.csv in ordine non decrescente secondo i valori contenuti nei tre campi "field" (cioè, per ogni valore di k, è necessario ripetere l'ordinamento tre volte, una volta per ciascun campo).
Si misurino i tempi di risposta variando il valore di k e si produca una breve relazione in cui si riportano i risultati ottenuti insieme a un loro commento. Dimostrare nella relazione come il valore di k dovrebbe essere scelto nella pratica. Nel caso l'ordinamento si protragga per più di 10 minuti potete interrompere l'esecuzione e riportare un fallimento dell'operazione. I risultati sono quelli che vi sareste aspettati? Se sì, perché? Se no, fate delle ipotesi circa il motivo per cui l'algoritmo non funziona come vi aspettate, verificatele e riportate quanto scoperto nella relazione.
Si ricorda che che il file records.csv NON DEVE ESSERE OGGETTO DI COMMIT SU GIT!
Si consideri il problema di determinare la distanza di edit tra due stringhe (Edit distance): date due stringhe s1 e s2, non necessariamente della stessa lunghezza, determinare il minimo numero di operazioni necessarie per trasformare la stringa s2 in s1. Si assuma che le operazioni disponibili siano: cancellazione e inserimento. Esempi:
- "casa" e "cassa" hanno edit distance pari a 1 (1 cancellazione);
- "casa" e "cara" hanno edit distance pari a 2 (1 cancellazione + 1 inserimento);
- “vinaio” e “vino” hanno edit distance=2 (2 inserimenti);
- "tassa" e "passato" hanno edit distance pari a 4 (3 cancellazioni + 1 inserimento);
- "pioppo" e "pioppo" hanno edit distance pari a 0.
- Si implementi una versione ricorsiva della funzione edit_distance la cui struttura riproponga quella della seguente definizione (indichiamo con
$|s|$ la lunghezza di$s$ e con$\mathrm{rest}(s)$ la sottostringa di$s$ ottenuta ignorando il primo carattere di$s$ ):
- se
$|s1|$ = 0, allora$\mathrm{edit_distance}(s1,s2) = |s2|$ ; - se
$|s2|$ = 0, allora$\mathrm{edit_distance}(s1,s2) = |s1|$ ; - altrimenti, siano:
- $d_{\mathrm{no-op}} = \begin{cases} \mathrm{edit_distance}(\mathrm{rest}(s1),\mathrm{rest}(s2)) & \mathrm{se\ } s1[0]=s2[0] \ \infty & \mathrm{altrimenti} \end{cases}$
$d_{\mathrm{canc}} = 1+ \mathrm{edit_distance}(s1,\mathrm{rest}(s2))$ $d_{\mathrm{ins}} = 1+ \mathrm{edit_distance}(\mathrm{rest}(s1),s2)$
Si ha:
- Si implementi una seconda versione edit_distance_dyn della funzione, adottando una strategia di programmazione dinamica. Tale versione deve essere anch'essa ricorsiva e la sua struttura deve essere simile a quella della versione richiesta al punto precedente.
Nota: Le definizioni sopra riportate non corrispondono al modo usuale di definire la distanza di edit. Sono però del tutto sufficienti per risolvere l'esercizio e, come detto, sono quelle su cui dovrà essere basato il codice prodotto.
Implementare gli unit-test degli algoritmi secondo le indicazioni suggerite nel documento Unit Testing.
All'indirizzo
https://mega.nz/file/I8dB0DqA#NcE81UGubU1PXx2bS2gQYO5Z7v8LqtjzI1UMVOL4NmM
potete trovare i file dictionary.txt e correctme.txt (in una cartella compressa).
Il file dictionary.txt contiene l'elenco (di una parte significativa) delle parole italiane. Le parole sono scritte di seguito, ciascuna su una riga.
Il file correctme.txt contiene una citazione di John Lennon. La citazione presenta alcuni errori di battitura.
Si implementi un'applicazione che usa la funzione edit_distance_dyn per determinare, per ogni parola w in correctme.txt, la lista di parole in dictionary.txt con edit distance minima da w. Si sperimenti il funzionamento dell'applicazione e si riporti in una breve relazione (circa una pagina) i risultati degli esperimenti.
Si ricorda che i file dictionary.txt e correctme.txt NON DEVONO ESSERE OGGETTO DI COMMIT SU GIT!
Si implementi la struttura dati Union-Find Set (con le euristiche di unione per rango e compressione del cammino). La struttura dati deve permettere di inserire oggetti di tipo generico e non prevedere un insieme iniziale finito di elementi.
Una descrizione della Union-Find Set è riportata sul testo Cormen et al., Introduzione agli algoritmi e strutture dati, McGraw-Hill, nel capitolo Strutture dati per insiemi disgiunti, paragrafo Foreste di insiemi disgiunti.
Implementare gli unit-test degli algoritmi secondo le indicazioni suggerite nel documento Unit Testing.
Si implementi una libreria che realizza la struttura dati Grafo in modo che sia ottimale per dati sparsi (IMPORTANTE: le scelte implementative che farete dovranno essere giustificate in relazione alle nozioni presentate durante le lezioni in aula). La struttura deve consentire di rappresentare sia grafi diretti che grafi non diretti (suggerimento: un grafo non diretto può essere rappresentato usando un'implementazione per grafi diretti modificata per garantire che, per ogni arco (a,b), etichettato w, presente nel grafo, sia presente nel grafo anche l'arco (b,a), etichettato w. Ovviamente, il grafo dovrà mantenere l'informazione che specifica se esso è un grafo diretto o non diretto.).
L'implementazione deve essere generica sia per quanto riguarda il tipo dei nodi, sia per quanto riguarda le etichette degli archi.
La struttura dati implementata dovrà offrire (almeno) le seguenti operazioni (accanto ad ogni operazione è specificata la complessità richiesta; n può indicare il numero di nodi o il numero di archi, a seconda del contesto):
- Creazione di un grafo vuoto – O(1)
- Aggiunta di un nodo – O(1)
- Aggiunta di un arco – O(1)
- Verifica se il grafo è diretto – O(1)
- Verifica se il grafo contiene un dato nodo – O(1)
- Verifica se il grafo contiene un dato arco – O(1) (*)
- Cancellazione di un nodo – O(n)
- Cancellazione di un arco – O(1) (*)
- Determinazione del numero di nodi – O(1)
- Determinazione del numero di archi – O(n)
- Recupero dei nodi del grafo – O(n)
- Recupero degli archi del grafo – O(n)
- Recupero nodi adiacenti di un dato nodo – O(1) (*)
- Recupero etichetta associata a una coppia di nodi – O(1) (*)
(*) quando il grafo è veramente sparso, assumendo che l'operazione venga effettuata su un nodo la cui lista di adiacenza ha una lunghezza in O(1).
Implementare gli unit-test degli algoritmi secondo le indicazioni suggerite nel documento Unit Testing.
Si implementi l'algoritmo di Kruskal per la determinazione della minima foresta ricoprente di un grafo.
L'implementazione dell'algoritmo di Kruskal dovrà utilizzare la struttura dati Union-Find Set implementata nell'esercizio precedente.
N.B. Nel caso in cui il grafo sia costituito da una sola componente connessa, l'algoritmo restituirà un albero; nel caso in cui, invece, vi siano più componenti connesse, l'algoritmo restituirà una foresta costituita dai minimi alberi ricoprenti di ciascuna componente connessa.
La struttura dati Grafo e l'algoritmo di Kruskal dovranno essere utilizzati con i dati contenuti nel file italian_dist_graph.csv.
Il file italian_dist_graph.csv che potete trovare all'indirizzo
https://mega.nz/file/g9VgWBzR#lODhFBDXZGFoMiBZidw8mQEhAYNaZZXkaMGsGfakqiU
contiene le distanze in metri tra varie località italiane e una frazione delle località a loro più vicine. Il formato è un CSV standard: i campi sono separati da virgole; i record sono separati dal carattere di fine riga (\n).
Ogni record contiene i seguenti dati:
- località 1: (tipo stringa) nome della località "sorgente". La stringa può contenere spazi, non può contenere virgole;
- località 2: (tipo stringa) nome della località "destinazione". La stringa può contenere spazi, non può contenere virgole;
- distanza: (tipo float) distanza in metri tra le due località.
Note :
- potete interpretare le informazioni presenti nelle righe del file come archi non diretti (pertanto, si suggerisce di inserire nel grafo sia l'arco di andata che quello di ritorno a fronte di ogni riga letta).
- il file è stato creato a partire da un dataset poco accurato. I dati riportati contengono inesattezze e imprecisioni.
Si ricorda il file italian_dist_graph.csv NON DEVE ESSERE OGGETTO DI COMMIT SU GIT!
Controlli
Un'implementazione corretta dell'algoritmo di Kruskal, eseguita sui dati contenuti nel file italian_dist_graph.csv, dovrebbe determinare una minima foresta ricoprente con 18.640 nodi, 18.637 archi (non orientati) e di peso complessivo di circa 89.939,913 Km.