Appunti di Advanced algorithms and graph mining

Advanced Algorithms and GraphMining 2022-2023

Indice

• 1 Analisi degli algoritmi 1
• 1.1 Notazione O-Grande . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
• 1.2 Scoprire gli anagrammi . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
• 1.2.1 Soluzione 1: corrispondenze . . . . . . . . . . . . . . . . . . . . . 6
• 1.2.2 Soluzione 2: ordina e confronta . . . . . . . . . . . . . . . . . . . 6
• 1.2.3 Soluzione 3: forza bruta . . . . . . . . . . . . . . . . . . . . . . 7
• 1.2.4 Soluzione 4: conta e confronta . . . . . . . . . . . . . . . . . . . . 7
• 1.3 Sottoarray di somma massima . . . . . . . . . . . . . . . . . . . . . . . . 8
• 1.3.1 Soluzione 1: tutte le sottosequenze . . . . . . . . . . . . . . . . . 8
• 1.3.2 Soluzione 2: riutilizzando le sottosequenze . . . . . . . . . . . . . 9
• 1.3.3 Soluzione 3: sfruttando le proprietà . . . . . . . . . . . . . . . . . 9
• 1.4 Sottoarray di somma fissata . . . . . . . . . . . . . . . . . . . . . . . . . 10
• 1.5 Sottoinsieme di somma fissata . . . . . . . . . . . . . . . . . . . . . . . . 11
• 1.6 Performance delle strutture dati Python . . . . . . . . . . . . . . . . . . 12
• 1.6.1 Liste . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
• 1.6.2 Dizionari . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
• 2 Algoritmi di ricerca 17
• 2.1 Ricerca sequenziale . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
• 2.2 Ricerca binaria . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
• 2.3 Hashing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
• 2.3.1 Funzioni hash . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
• 2.3.2 Risoluzione delle collisioni . . . . . . . . . . . . . . . . . . . . . . 23
• 2.3.3 Map . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
• 2.3.4 Analisi dell’hashing . . . . . . . . . . . . . . . . . . . . . . . . . . 27
• 3 Algoritmi di ordinamento 29
• 3.1 Bubble Sort . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29
• 3.2 Selection Sort . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31
• 3.3 Insertion Sort . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32
• 3.4 Divide et Impera . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33
• 3.4.1 Merge Sort . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34
• 3.4.2 Quick Sort . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39
• 4 Strutture dati 42
• 4.1 Pila . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42
• 4.2 Coda . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45
• i Indice ii
• 5 Alberi 47
• 5.1 Visite di alberi . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52
• 5.2 Linked List . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53
• 5.2.1 Classe Node . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 54
• 5.2.2 Classe Linked List . . . . . . . . . . . . . . . . . . . . . . . . . . 54
• 6 Algoritmi greedy 57
• 6.1 Algoritmo del cassiere . . . . . . . . . . . . . . . . . . . . . . . . . . . . 58
• 6.2 Algoritmo di scheduling degli intervalli . . . . . . . . . . . . . . . . . . . 61
• 7 Programmazione dinamica 68
• 7.1 Numeri di Fibonacci . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 68
• 7.2 Algoritmo del cassiere . . . . . . . . . . . . . . . . . . . . . . . . . . . . 70
• 7.3 Distanza tra stringhe . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 72
• 8 Grafi 76
• 8.1 Breadth First Search . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 80
• 8.2 Depth First Search . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 84
• 8.3 Teoria dei grafi . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 87
• 8.4 Componenti fortemente connesse . . . . . . . . . . . . . . . . . . . . . . . 91
• 8.5 Distribuzione delle distanze . . . . . . . . . . . . . . . . . . . . . . . . . 96
• 8.5.1 Classical Sampling . . . . . . . . . . . . . . . . . . . . . . . . . . 99
• 8.5.2 Priority Sampling . . . . . . . . . . . . . . . . . . . . . . . . . . . 100
• 8.6 Sketches . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 103
• 8.6.1 Stima delle dimensioni . . . . . . . . . . . . . . . . . . . . . . . . 103
• 8.6.2 Stima della somiglianza . . . . . . . . . . . . . . . . . . . . . . . 107
• 8.6.3 Local Triangle Counting . . . . . . . . . . . . . . . . . . . . . . . 111
• 8.7 Diametro . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 112
• 8.8 Centralità . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 119
• 8.8.1 Closeness centrality . . . . . . . . . . . . . . . . . . . . . . . . . . 119
• 8.8.2 Betweenness centrality . . . . . . . . . . . . . . . . . . . . . . . . 120
• 9 Python 123
• 9.1 NumPy . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 125
• 9.2 Pandas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 126
• 9.3 NetworkX . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 127

Capitolo 1: analisi degli algoritmi

Quando due programmi risolvono lo stesso problema, vorremmo essere in grado di riconoscere qual’è il migliore.

In particolare, un problema può essere risolto con molti algoritmi diversi. Inoltre ci sono molti modi di implementare lo stesso algoritmo, che si differenziano ad esempio dalle strutture dati usate o dal linguaggio di programmazione.

A questo proposito, osserviamo la seguente funzione mostrata. Questa funzione risolve il problema del calcolo della somma dei primi interi.

N
1 def sumOfN(n):
2 theSum = 0
3 for ini range(1, n+1):
4 theSum = theSum + i
5
6 return theSum
7
8 print(sumOfN(10))

Adesso osserviamo una versione alternativa della precedente funzione, meno leggibile e con un assegnamento evitabile.

1 def foo(tom):
2 fred = 0
3 for inbill range(1, tom+1):
4 barney = bill
5 fred = fred + barney
6
7 return fred
8
9 print(foo(10))

La funzione è meglio della funzione in termini di leggibilità. sumOfN foo

Invece, il processo di analisi degli algoritmi riguarda il confronto tra due algoritmi in termini di efficienza, ovvero paragonando la quantità di calcolo e di risorse computazionali che entrambi richiedono. In questi termini, le due versioni mostrate in precedenza sono molto simili, anche se una soluzione spreca una variabile in più.

A questo punto, è importante definire il significato di risorse computazionali. In particolare, ci sono due criteri che possono essere considerati:

• Spazio (o memoria) utilizzato dall’algoritmo. Questa quantità è tipicamente dipendente dall’input del problema. 1
• Capitolo 1. Analisi degli algoritmi 2
• Tempo richiesto dall’algoritmo. Confrontare due algoritmi significa controllare la quantità di tempo necessaria per completare il loro compito. Questa misura è chiamata “tempo di esecuzione” dell’algoritmo.

Un modo per misurare il tempo di esecuzione della funzione è quello di fare un sumOfN benchmark. Ovvero, per misurare il tempo richiesto dal programma utilizziamo il modulo nel quale viene fornita una funzione che ritorna il numero di cicli di time, time clock in secondi passati da un certo momento di riferimento. Chiamando questa funzione due volte (all’inizio ed alla fine) e calcolandone la differenza, possiamo sapere il numero di secondi esatti che sono stati usati per l’esecuzione del programma.

1 import time
2
3 def sumOfN(n):
4 start = time.time()
5
6 theSum = 0
7 for ini range(1, n+1):
8 theSum = theSum + i
9
10 end = time.time()
11
12 return theSum, end - start

Tale codice mostra il metodo originale con le relative chiamate alla funzione sumOfN Il metodo ritorna una tupla che contiene il risultato della somma ed il tempo di time. esecuzione (in secondi).

Osserviamo che, eseguendo tale metodo volte con lo stesso input (ovvero 5 = 10000), N otteniamo un tempo di esecuzione simile per ogni esecuzione (in media secondi). 0.0019

>>>for i in range(5):print("Sum is %d required %10.7f seconds"%sumOfN(10000))
Sum is 50005000 required 0.0018950 seconds
Sum is 50005000 required 0.0018620 seconds
Sum is 50005000 required 0.0019171 seconds
Sum is 50005000 required 0.0019162 seconds
Sum is 50005000 required 0.0019360 seconds

Se eseguiamo lo stesso metodo volte su un input volte più grande (ovvero 5 10 = N otteniamo un tempo di esecuzione simile per ogni esecuzione, ma con un costo 100000), volte maggiore rispetto al caso precedente. 10

>>>for i in range(5):print("Sum is %d required %10.7f seconds"%sumOfN(100000))
Sum is 5000050000 required 0.0199420 seconds
Sum is 5000050000 required 0.0180972 seconds
Sum is 5000050000 required 0.0194821 seconds
Sum is 5000050000 required 0.0178988 seconds
Sum is 5000050000 required 0.0188949 seconds

Capitolo 1. Analisi degli algoritmi 3

Quindi, il costo di questa implementazione è lineare (ovvero, il tempo di esecuzione può essere mostrato su una retta all’aumentare dell’input).

Adesso consideriamo il seguente codice, che mostra un modo diverso di risolvere il problema della somma. Questa funzione, sfrutta l’equazione per calcolare (N )(N +1)NP =ii=1 2 senza iterazioni la somma dei primi numeri interi. N

1 def sumOfN(n):
2 return (n * (n+1)) / 2
3
4 print(sumOfN(10))

Osserviamo cosa accade se eseguiamo gli stessi test su questo nuovo metodo, utilizzando diversi valori di (ovvero ed 5 10000, 100000, 1000000, 10000000 100000000). N

Sum is 50005000 required 0.00000095 seconds
Sum is 5000050000 required 0.00000191 seconds
Sum is 500000500000 required 0.00000095 seconds
Sum is 50000005000000 required 0.00000095 seconds
Sum is 5000000050000000 required 0.00000119 seconds

Al riguardo, possiamo fare due osservazioni significative:

• I tempi risultanti sono molto minori rispetto a quelli ottenuti con il precedente algoritmo.
• I tempi risultanti non dipendono dal valore di . Invece, nella soluzione iterativa N i tempi crescono con . N

1.1 Notazione O-Grande

Per caratterizzare l’efficienza di un algoritmo in termini del tempo di esecuzione (indipendentemente dall’implementazione, dal linguaggio o dal computer utilizzato) è importante quantificare il numero di operazioni o di passi che l’algoritmo richiede.

In questo contesto, il tempo di esecuzione di un algoritmo corrisponde al numero di passi che l’algoritmo esegue, dove ogni passo ha un costo di tempo unitario. Possiamo denotare questa funzione come dove il parametro corrisponde alla grandezza (n), T n dell’input (o taglia del problema) e possiamo leggerlo come “T è il tempo che serve (n) per risolvere un problema di taglia n”.

Ad esempio, i passi algoritmici nella funzione sono definiti dal numero di istruzioni di assegnamento eseguite. Tale numero è dato dal numero di volte che eseguiamo l’operazione theSum theSum a partire da theSum= + = 0. i

Perciò ovvero il problema richiede istruzioni di assegnamento. (n) = 1 + 1 +T n, n

Tuttavia, il numero esatto di operazioni non è importante. Invece, ciò che risulta rilevante è l’ordine di grandezza, che dipende dalle operazioni più costose dell’algoritmo.

Infatti, quando cresce, la parte più costosa dell’algoritmo ha un peso molto maggiore rispetto alle altre. In altre parole, quando cresce, la parte dominante di (n) n T tende a sovrastare gli altri termini. Questa parte dominante è ciò che ci interessa per confrontare algoritmi.

Capitolo 1. Analisi degli algoritmi 4

Ordine di grandezza. La funzione descrive la parte dominante di ovvero la parte (n), T che ha un incremento più rapido al crescere di L’ordine di grandezza è spesso chiamato e viene scritto come fornendo un’approssimazione al numero (n)), O(f di passi della computazione. La funzione fornisce una semplice rappresentazione (n) f della parte dominante di (n). T

Nel precedente esempio abbiamo osservato che Quando diventa grande, (n) = 1 +T n. n la costante non è più importante in quanto dominata dal termine più significativo 1 n. Per cui diciamo che il tempo è O(n).

Se abbiamo un numero di passi pari a Quando è piccolo, 2(n) = 5n + 27n + 1005. T n la costante sembra dominare. Tuttavia, quando diventa grande, il termine 21005 n n diventa il più importante. Dunque la funzione ha ordine di grandezza ,2(n) (n) = T f n ovvero 2 ). O(n

Spesso, il comportamento dell’algoritmo dipende dal valore esatto dei dati e non solo da quanti sono. In questo caso, ci sono diverse misure che potremmo considerare:

• Caso peggiore, quanto tempo viene richiesto nel caso in cui gli dati siano n quelli per cui l’algoritmo si comporta peggio.
• Caso medio, quanto è il tempo medio di esecuzione considerando tutti i possibili insiemi di dati. n

Gli ordini di grandezza più comuni sono mostrati nella seguente tabella. Per capire quali funzioni dominino una sull’altra, dobbiamo analizzare il loro comportamento quando è grande. n

La seguente figura mostra il grafico delle funzioni descritte in tabella. Quando è piccolo la gerarchia non è ben definita, mentre quando cresce è chiaro quale funzione n domina sull’altra.

Capitolo 1. Analisi degli algoritmi 5

ES: Consideriamo il seguente frammento di codice. Sebbene questo programma non faccia niente, possiamo analizzarne le performance.

1 a = 5
2 b = 6
3 c = 10
4 for ini range(n):
5 for inj range(n):
6 x = i * i
7 y = j * j
8 z = i * j
9 for ink range(n):
10 w = a * k + 45
11 v = b * b
12 d = 33

Possiamo facilmente vedere che il numero di assegnamenti è per i primi 2 ) O(n mi due cicli (di cui uno annidato) ed per il terzo ciclo. Dal momento O(n) che ovvero la parte dominante è il costo del- 2 2 2) + = ), ), O(n O(n) O(n O(n l’algoritmo sarà quando cresce. 2 ) O(n n

La seguente figura mostra alcune funzioni comuni di O-grande e come si confrontano con la funzione discussa. Notiamo che all’inizio è più (n) (n) T T grande della funzione cubica. Tuttavia, quando cresce, la funzione cubica n sovrasta (n). T Figura 1.1: Confronto di con funzioni O-grande comuni. T (n)

1.2 Scoprire gli anagrammi

Una stringa è l’anagramma dell’altra se è costituita dai caratteri ordinati in modo diverso rispetto ai caratteri presenti nella stringa originale (per esempio “heart” e “earth” sono anagrammi).

Capitolo 1. Analisi degli algoritmi 6

Per semplicità, assumiamo che le due stringhe in input abbiano la stessa lunghezza e che siano fatte di simboli appartenenti alle 26 lettere, con caratteri alfabetici minuscoli.

Vogliamo scrivere una funzione booleana che, date due stringhe, ritorni se una True stringa è l’anagramma dell’altra.

1.2.1 Soluzione 1: corrispondenze

Una possibile soluzione è quella di controllare se ogni carattere compare con la stessa molteplicità in entrambe le stringhe. Idealmente, se nella prima stringa occorrono due “a”, allora anche nella seconda stringa devono occorrere esattamente due “a”.

1 def anagramSolution1(s1, s2):
2 alist = list(s2)
3
4 pos1 = 0
5 TruestillOK =
6
7 while andpos1 < len(s1) stillOK:
8 pos2 = 0
9 Falsefound =
10 while and notpos2 < len(alist) found:
11 if s1[pos1] == alist[pos2]:
12 Truefound =
13 else:
14 pos2 = pos2 + 1
15
16 if found:
17 Nonealist[pos2] =
18 else:
19 FalsestillOK =
20
21 pos1 = pos1 + 1
22
23 return stillOK
24
25 print(anagramSolution1('abcd', 'dcba'))

Ognuno degli caratteri in causa una iterazione sugli caratteri nella lista di s1 s2. n n Dunque questa soluzione ha complessità temporale 2 ). O(n

1.2.2 Soluzione 2: ordina e confronta

Le stringhe ed sono anagrammi solo se consistono degli stessi caratteri, indipendentemente dall’ordine con cui essi compaiono. Dunque, affinché due stringhe siano s1 s2 anagrammi è necessario che, ordinandole, si ottengano due stringhe uguali.

1 def anagramSolution2(s1, s2):
2 alist1 = list(s1)
3 alist2 = list(s2)
4
5 alist1.sort()
6 alist2.sort()
7
8 pos = 0
9 Truematches =
10

Capitolo 1. Analisi degli algoritmi 7

11 while andpos < len(s1) matches:
12 if alist1[pos] == alist2[pos]:
13 pos = pos + 1
14 else:
15 Falsematches =
16
17 return matches
18
19 print(anagramSolution2('abcd', 'dcba'))

A prima vista potremmo essere tentati di dire che il tempo di esecuzione sia poi- O(n), ché è presente una sola iterazione su caratteri dopo l’ordinamento. Tuttavia, le due n chiamate al metodo di Python hanno un costo oppure Dunque, sort 2 ) log O(n O(n n). il costo dell’ordinamento domina rispetto al costo del confronto. Quindi, l’ordine di grandezza di questo algoritmo è determinato dal costo del processo di ordinamento.

1.2.3 Soluzione 3: forza bruta

Forza bruta. L’algoritmo di tende ad esplorare tutte le pos