ASD-Find Maximum SubArray & Topological Sort

Elaborato di Algoritmi e Strutture Dati

Gargiulo Alessandro - Mat. M63/417

5 gennaio 2014

Indice

1 Il problema del massimo sotto-array 1

1.1 Introduzione . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11.2 Soluzione Iterativa . . . . . . . . . . . . . . . . . . . . . . . . . . 1

1.2.1 Pseudocodice . . . . . . . . . . . . . . . . . . . . . . . . . 11.2.2 Correttezza dell'Algoritmo . . . . . . . . . . . . . . . . . 31.2.3 Complessità . . . . . . . . . . . . . . . . . . . . . . . . . . 3

1.3 Soluzione Iterativa Sempli�cata . . . . . . . . . . . . . . . . . . . 41.3.1 Pseudocodice . . . . . . . . . . . . . . . . . . . . . . . . . 41.3.2 Correttezza dell'Algoritmo . . . . . . . . . . . . . . . . . . 51.3.3 Complessità . . . . . . . . . . . . . . . . . . . . . . . . . . 6

1.4 Soluzione Ricorsiva . . . . . . . . . . . . . . . . . . . . . . . . . . 61.4.1 Pseudocodice Find-Max-Crossing-Subarray . . . . . . . . 71.4.2 Pseudocodice Find-Maximum-Subarray . . . . . . . . . . 81.4.3 Correttezza dell'Algoritmo . . . . . . . . . . . . . . . . . . 91.4.4 Complessità . . . . . . . . . . . . . . . . . . . . . . . . . . 10

1.4.4.1 Complessità con Albero di Ricorrenza . . . . . . 101.5 Realizzazione in C++ . . . . . . . . . . . . . . . . . . . . . . . . 11

1.5.1 Listato v1.0 . . . . . . . . . . . . . . . . . . . . . . . . . . 111.5.1.1 Simulazione . . . . . . . . . . . . . . . . . . . . . 12

1.5.2 Listato v2.0 . . . . . . . . . . . . . . . . . . . . . . . . . . 141.5.2.1 Simulazione . . . . . . . . . . . . . . . . . . . . . 14

1.5.3 Listato v3.0 - Ricorsione . . . . . . . . . . . . . . . . . . . 151.5.3.1 Simulazione . . . . . . . . . . . . . . . . . . . . . 18

1.5.4 Valutazione delle prestazioni . . . . . . . . . . . . . . . . 191.5.4.1 Prestazioni versione iterativa a doppio ciclo . . . 191.5.4.2 Prestazioni versione iterativa a singolo ciclo . . . 201.5.4.3 Prestazioni versione ricorsiva . . . . . . . . . . . 21

1.6 Conclusioni . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21

2 Topological sort 22

2.1 Introduzione . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 222.2 Depth-First-Search . . . . . . . . . . . . . . . . . . . . . . . . . 23

2.2.1 Pseudocodice . . . . . . . . . . . . . . . . . . . . . . . . . 242.2.2 Correttezza dell'algoritmo . . . . . . . . . . . . . . . . . . 24

I

INDICE

2.2.3 Complessità . . . . . . . . . . . . . . . . . . . . . . . . . . 252.3 Topological Sort . . . . . . . . . . . . . . . . . . . . . . . . . . . 26

2.3.1 Pseudocodice . . . . . . . . . . . . . . . . . . . . . . . . . 262.3.2 Funzionamento gra�co . . . . . . . . . . . . . . . . . . . . 262.3.3 Correttezza . . . . . . . . . . . . . . . . . . . . . . . . . . 27

2.3.3.1 Teorema del cammino bianco . . . . . . . . . . . 282.3.3.2 Teorema sui gra� aciclici . . . . . . . . . . . . . 282.3.3.3 Correttezza del topological sort . . . . . . . . . . 28

2.4 Realizzazione in C++ . . . . . . . . . . . . . . . . . . . . . . . . 292.4.1 Codice topological sort . . . . . . . . . . . . . . . . . . . . 292.4.2 Analisi delle prestazioni . . . . . . . . . . . . . . . . . . . 31

Elaborato in ASD: Algoritmi e Strutture Dati II

Capitolo 1

Il problema del massimo

sotto-array

1.1 Introduzione

Si vuole analizzare, risolvere e implementare il seguente problema :

�Sia dato un vettore A di n elementi, determinare il sottoarray

contiguo e non vuoto di A tale che la somma dei suoi elementi sia

massima�

Chiameremo tale sottoarray, massimo sottoarray.Gli n elementi presenti nel vettore A, sono interi positivi e negativi, in quanto

il problema con soli numeri positivi è banalmente risolto (il massimo sottoarraycoinciderebbe con l'intero array A).

1.2 Soluzione Iterativa

Una prima soluzione del problema è un algoritmo di tipo iterativo: una soluzionedi facile progettazione e interpretazione.

Dovendo trovare un sottoarray la cui somma degli elementi sia massima,possiamo pensare di partire dal primo elemento e calcolare la somma parziale trail singolo elemento e tutti i sottoarray di dimensione via via crescente. Terminatala scansione di tutti i sottoarray aventi come primo elemento, il primo elementodel vettore, andiamo ad esaminare tutti i sottoarray aventi come primo elemento,il secondo elemento del vettore di partenza.

Ciò che si è appena descritto ci suggerisce di utilizzare due iterazioni innes-tate per visitare tutti i possibili sottoarray.

1.2.1 Pseudocodice

1

CAPITOLO 1. IL PROBLEMA DEL MASSIMO SOTTO-ARRAY

Figure 1.1: Funzionamento gra�co : Ricerca del massimo sottoarray

1 FIND-MAXIMUM-SUB-ARRAY(A, low, high)2 maxsum = -infinito3 for i = low to high4 partialsum = 05 for j = i to high6 partialsum = partialsum + A[j]7 if partialsum > maxsum8 maxsum = partialsum9 lowmax = i

10 highmax = j11 return(maxsum, lowmax, highmax)

La funzione �nd-maximum-sub-array prende come parametri di ingresso:

1. Il vettore A nel quale ricercare il sottovettore

2. L'indice del primo valore dal quale iniziare la ricerca.

3. L'indice dell'ultimo valore entro il quale la ricerca termina.

I valori di ritorno della funzione sono anch'essi tre:

1. Il valore della somma degli elementi del massimo sottoarray.

2. L'indice estremo inferiore del sottoarray massimo.

3. L'indice estremo superiore del sottoarray massimo.

Dunque come si evince in �gura 1.1, l'algoritmo esplora tutti i possibili sot-tovettori del vettore di partenza a partire dall'indice low �no all'indice high.I valori del vettore in celle di colore bianco rappresentano valori non ancoraprocessati nell' i-j-esima iterazione, mentre quelli di colore grigio rappresentano

Elaborato in ASD: Algoritmi e Strutture Dati 2


possibili sottoarray dei quali valutarne la somma dei valori. Una variabile par-

tialsum tiene conto della somma parziale man mano che il sottoarray espandei propri estremi; se essa risulta essere maggiore della somma dei valori di unprecedente massimo sottoarray, allora il nuovo valore del massimo sottoarray èproprio la somma parziale e gli estremi del massimo sottoarray si aggiornano aquelli correnti (ossia la i-j-esima iterazione). Questo ci spinge a pensare ad unapossibile invariante di ciclo per dimostrare la correttezza dell'algoritmo.

1.2.2 Correttezza dell'Algoritmo

Trattasi di un algoritmo iterativo, quindi la correttezza si dimostra con il sem-plice principio di induzione. Nel dimostrare la correttezza abbiamo bisogno dide�nire un'invariante di ciclo, ossia una proprietà che viene conservata (e risultapertanto veri�cata) ad ogni iterazione.

�Sia A un vettore di n elementi dato in input alla procedura di ricerca delmassimo sottoarray. Ad ogni iterazione, il valoremaxsum risulta essere maggioreo uguale di partialsum.�

Dimostriamo dunque la correttezza con il principio di induzione.

• Passo Inizializzazione: Prima della prima iterazione del ciclo i = 0 ej = i = 0. Dunque partialsum risulta essere pari al primo elementodel vettore, che alla prima iterazione risulta essere banalmente il massimosottoarray (in quanto l'unico esaminato). maxsum è quindi inizializzatoal primo valore di partial sum, veri�cando così l'invariante di ciclo.

• Passo Conservazione: Dopo ogni i-j-esima iterazione partialsum viene ri-calcolato aggiungendo il valore corrente j-esimo del vettore A. A questopunto partialsum potrebbe essere superiore al valore di maxsum, ma lacondizione testata dall' if ci permette di riassegnare a maxsum il valore dipartialsum, ristabilendo l'invariante di ciclo.

• Passo Conclusione: L'ultima iterazione del doppio ciclo si veri�ca con i =high e j = high; ma avendo dimostrato il passo di conservazione sappiamoche maxsum contiene il valore corrente della somma degli elementi delmassimo sottoarray. Con l'ultima iterazione, l'unico sottoarray che puòavere una somma di valori maggiore di quella corrente è il sottoarraycontenente solo A[j], quindi partialsum = A[j]; ma ancora una volta lacondizione testata ci permette di ristabilire l'invariante di ciclo, cosicchéil valore di ritorno della funzione sia quello corretto.

1.2.3 Complessità

Tralasciando la complessita spaziale, analizziamo la complessità temporale delnostro algorimo in versione iterativa, salvo poi migliorarla con una versionericorsiva.

Supponiamo di avere un vettore con n elementi.



L'algoritmo consta di varie assegnazioni, tutte con complessità costante Θ (1)e di due cicli for innestati. Il ciclo più esterno esegue n iterazioni, dunque hauna complessità pari a Θ (n). Per ciascuna di queste iterazioni ne viene eseguitoun ciclo ulteriore di n− i iterazioni.

Dunque:

T (n) =

n∑i=0

n (n− i)

T (n) = n (n) + n (n− 1) + n (n− 2) + ... + n [n− (n− 1)]

T (n) = n (n) + n (n− 1) + n (n− 2) + ... + n

Il che ci porta a dedurre che T (n) ha una forma polinomiale del secondoordine che si presenta come

an2 + bn + c

Dato che la notazione asintotica nasconde il valore delle costanti diremo che

T (n) ∈ Θ(n2)

Si può migliorare la complessità dell'algoritmo facendo una semplice osser-vazione, pur non cambiando la natura iterativa. Tratteremo questo argomentonel prossimo paragrafo.

1.3 Soluzione Iterativa Sempli�cata

La sempli�cazione dell'algoritmo trattato nella precedente sezione, nascedall'osservazione che se una serie di numeri è tale da portare la somma parzialea zero oppure ad un numero negativo, allora il massimo sotto-array si troverào prima di questa serie di numeri (in tal caso gli indici estremi del massimosottoarray si saranno già aggiornati al loro corretto valore) o dopo di essi: sivaluteranno quindi tutti i sottoarray a partire dall'indice che ha reso negativala somma parziale).

1.3.1 Pseudocodice

Come già accennato in precedenza, dunque, la di�erenza tra i due algoritmi stanel valutare la condizione partialsum < 0.

1 FIND-MAXIMUM-SUB-ARRAY(A, low, high)2 maxsum = -infinito3 partialsum = 04 j = low



Figure 1.2: Funzionamento gra�co : ricerca del massimo sottoarray (versionesempli�cata)

5 for i = low to high6 partialsum = partialsum + A[j]7 if partialsum > maxsum8 maxsum = partialsum9 lowmax = j

10 highmax = i11 if partialsum < 012 partialsum = 013 j = i + 114 return(maxsum, lowmax, highmax)

In �gura 1.2 è mostrato il funzionamento dell'algoritmo in versione sempli-�cata.

Nella �gura 1.2 gli elementi in bianco rappresentano quelli non tenuti inconsiderazione nella i-esima iterazione, mentre quelli in grigio rappresentano ilsottoarray del quale si sta valutando se la somma degli elementi sia massima. Ilsottoarray dell'iterazione evidenziata in rosso, rappresenta il massimo sottoar-ray, da quel momento in poi gli indici lowmax e highmax non cambieranno piùin quanto non sarà più presente un sottoarray avente somma parziale superiore.


Senza spendere ulteriori considerazioni sulla correttezza dell'algoritmo (ma fo-calizzandoci su quello che era il nostro obiettivo : diminuire la complessità della



prima versione iterativa) citiamo quella che potrebbe essere una invariante diciclo per la versione sempli�cata.

�Ad ogni i-esima iterazione lowmax e highmax sono gli indici estremi delsottoarray avente somma di elementi pari a maxsum. Inoltre maxsum per ogniiterazione risulta essere maggiore o al più uguale di partialsum.�

E' possibile dimostrare l'invarianza di ciclo con un discorso simile a quellotrattato nel precedente paragrafo. In più bisogna giusti�care la riga di codicej = i + 1: ma questa è vera in quanto scaturisce dall'osservazione fatta inprecedenza, che risulta esser vera.

1.3.3 Complessità

La di�erenza sostanziale per quanto riguarda le due versioni sin ora trattate è chela prima utilizza due cicli innestati, mentre la seconda sfrutta un'interessanteosservazione sul massimo sottoarray per utilizzare una sola iterazione. Con-siderando che tutte le operazioni svolte all'interno dell ciclo sono assegnazionied al più delle somme, sono eseguite in tempo costante ( quindi Θ (1)).

Tutte le operazioni interne al ciclo sono eseguite high − low volte, ossia nvolte (con n pari al numero di elementi nell'array).

Giungiamo quindi a conclusione che la complessità della nuova versionedell'algoritmo è lineare ed in particolare :

T (n) ∈ Θ(n)

1.4 Soluzione Ricorsiva

Un'ulteriore versione del nostro algoritmo di ricerca del massimo sottoarray sipuò avere applicando il metodo di �divide et impera�. Questa soluzione prevededi suddividere il problema in più sottoproblemi a patto che la di�coltà diquest'ultimi sia inferiore a quella di partenza, risolvere i sottoproblemi e com-binare opportunamente i risultati per arrivare ad una soluzione del problema dipartenza.

Nel particolare, dati gli indici �low, high, mid� rispettivamente l'indice es-tremo più basso, l'indice estremo più alto e la mediana degli indici di un vettoreA, si prevede di suddividere la ricerca tra tutti i sottovettori in tre sottoproblemi:

1. La ricerca del massimo sottoarray all'interno nel sottoarray �di sinistra�,ossia A [low...mid].

2. La ricerca del massimo sottoarray all'interno del sottoarray �di destra�,ossia in A [mid + 1...high].

3. La ricerca del massimo sottoarray nel vettore che passa per mid, ossia tratutti i sottoarray con indici estremi i e j tali che low ≤ i < mid < j ≤ high.



Ciascuno dei tre sottoproblemi ha una dimensione decisamente inferiore a quelladel problema di partenza (in quanto il vettore originario viene partizionato indue parti), dunque è possibile applicare il metodo �divide et impera� per lasoluzione ricorsiva del problema.

Qualsiasi sottoarray che passa per la mediana è formato da due sottoarraynella forma A [low...mid]e A [mid + 1...high], quindi basta trovare i massimisottoarray nella forma A [i...mid]e A [mid + 1...j] e poi combinarli. Utilizziamoa questo scopo una funzione di supporto Find-Max-Crossing-Subarray.

1.4.1 Pseudocodice Find-Max-Crossing-Subarray

Questa procedura non fa altro che cercare il sottoarray con somma di elementimassima, tra tutti quelli che passano per il valore di mediana mid.

I parametri di ingresso della funzione sono:

1. A : vettore su cui ricercare il massimo sottoarray passante per la mediana.

2. low : indice estremo inferiore del vettore A.

3. high : indice estremo superiore del vettore A.

4. mid : indice della mediana del vettore A.

1 Find-Max-Crossing-Subarray(A, low, high, mid)2 leftsum = -infinito3 righttsum = -infinito4 sum = 05 for i = mid to low6 sum = sum + A[i]7 if(sum > leftsum)8 leftsum = sum9 leftindex = i

10 sum = 011 for j = mid+1 to high12 sum = sum + A[j]13 if(sum > rightsum)14 rightsum = sum15 rightindex = j16 return (leftindex, rightindex, leftsum + rightsum)

L'algoritmo appena illustrato procede nel cercare il valore massimo dellasomma degli elementi a sinistra di mid, memorizzandone l'indice estremo in-feriore, poi trova la somma massima a destra e restituisce in�ne gli indici delmassimo sottoarray ed il valore della somma degli elementi dello stesso.

Questa procedura serve solo da supporto per quella che stiamo per discutere.Prima di discutere la procedura che si servirà di Find-Max-Crossing-

Subarray, spendiamo qualche parola sulla complessità della stessa.La procedura è composta da due cicli:



• Il primo e�ettua mid− low + 1 iterazioni.

• Il secondo e�ettua high−mid− 1 iterazioni.

Per ciascuno dei due cicli vengono e�ettuate operazioni a complessità costanteΘ (1), dunque:

(mid− low + 1) ∗Θ(1) + (high−mid− 1) ∗Θ (1) + Θ(1)

Θ (mid− low + 1) + Θ(high−mid− 1) + Θ (1)

Θ(mid− low + 1 + high−mid− 1) + Θ(1)

Θ (high− low) + Θ (1)

T (n) ∈ Θ (n)

1.4.2 Pseudocodice Find-Maximum-Subarray

In principio avevamo suddiviso il problema principale della ricerca del massimosottoarray in tre sottoproblemi.

Nella procedura seguente risolveremo ciasciuno di questi problemi utiliz-zando ricorsivamente la stessa funzione ed in più utilizzando la procedura disupporto trattata nel paragrafo precedente.

La procedura di ricerca del massimo sottoarray consta di tre parametri diingresso:

1. A : Vettore all'interno del quale cercare il massimo sottoarray.

2. low : Indice estremo inferiore dell'array.

3. high : Indice estremo superiore dell'array.

1 Find-Maximum-Subarray(A, low, high)2 if low = high3 return (low, high, A[low])4 else5 mid = floor(low + high / 2)6 (maxleft, lowleft, highleft) =7 Find-Maximum-Subarray(A, low, mid)8 (maxright, lowright, highright) =9 Find-Maximum-Subarray(A, mid + 1, high)

10 (maxcross, lowcross, highcross) =



11 Find-Max-Crossing-Subarray(A, low, high, mid)12 if(maxleft > maxright AND maxleft > maxcross)13 return (maxleft, lowleft, highleft)14 else if(maxright > maxleft AND maxright > maxcross)15 return (maxright, lowright, highright)16 else17 return (maxcross, lowcross, highcross)

Analizziamo la procedura di ricerca del massimo sottoarray:La condizione di uscita dalla ricorsione è che alla funzione stessa sia passato

un vettore di un solo elemento (caso low = high); in questo caso il massimosottoarray è quello con indici coincidenti low e high, e con valore massimo disomma, il valore stesso dell'elemento.

Se gli indici estremi non coincidono, viene calcolato l'indice mediana e sichiama ricorsivamente la funzione sulla parte sinistra, destra e sui sottovettoricontenenti l'indice stesso.

A questo punto ci troviamo con tre valori interi, corrispondenti alle sommedei massimi sottoarray a sinistra, destra ed a cavallo tra i due.

Tra questi tre basta trovare quello più grande e restituire gli indici associatial vettore che ha generato quella somma.


L'algoritmo analizzato in questo caso è un algoritmo di tipo ricorsivo: non èquindi possibile utilizzare il principio di induzione con il metodo di invariantedi ciclo. Dobbiamo servirci del principio di induzione completo:

• Si dimostra la correttezza nel passo base con n = 1.

• Si suppongono le chiamate ricorsive corrette e quindi n− 1 chiamate cor-rette. Sulla base di questa si dimostra la correttezza per n chiamate.

Dimostriamo quindi tramite il principio di induzione completa, la correttezzadell'algoritmo, supponendo per semplicità corretta la chiamata alla funzioneFind-Max-Crossing-Subarray.

• Per n = 1, gli indici low e high, coincidono e la funzione ritorna A [low]cheè anche il massimo sottovettore in un vettore di un singolo valore.

• Supponendo corrette le chiamate su n− 1 elementi, la ricorsione opera sun2 elementi, ossia su un insieme contenuto in n − 1 per cui le chiamatericorsive sono corrette e ritornano il valore corretto della somma deglielementi del sottoarray sinistro, destro e a cavallo tra i due. A questo puntoè necessario trovare il valore massimo tra i tre, ma l'algoritmo tramitele tre comparazioni opera proprio trovando il valore maggiore. Dunqueviene restituito il valore maggiore e relativamente gli indici corretti delsottoarray.

Dunque deduciamo che la funzione operi correttamente.



1.4.4 Complessità

Per analizzare la complessità di un algoritmo ricorsivo, andiamo ad analizzare lacomplessità di ciasciuna operazione: una di queste fa uso proprio della funzionedella quale si sta calcolando la complessità.

Ci si imbatte quindi in una equazione alle ricorrenze.L'algoritmo prevede sostanzialmente dei confronti (con complessità

costante), due chiamate ricorsive ed una chiamata alla funzione Find-Max-Crossing-Subarray ( complessità Θ (n) ).

Le chiamate ricorsive sono e�ettuate sul sottoarray destro e sinistro, di di-mensioni ciascuna pari ad n

2 . L'equazione alle ricorrenze per n > 1 è quindi:

T (n) = 2 ∗ T(n

2

)+ Θ (n)

Esso risulta essere in forma del teorema dell'esperto(T (n) = a ∗ T

(nb

)+ f (n)

)con a ≥ 1 e b > 1

Dunque bisogna confrontare Θ (n) con nlogb a ed essendo Θ (n) dello stessoordine di grandezza di nlog2 2 = n la soluzione risulta essere nella forma

T (n) ∈ Θ(nlogb a lg (n)

)T (n) ∈ Θ (n lg (n))

1.4.4.1 Complessità con Albero di Ricorrenza

Per trovare la stessa soluzione (o veri�care quella trovata) è possibile costruirel'albero di ricorrenza.

Esso va ad esplorare la complessità di ogni singola chiamata ricorsiva allafunzione stessa.

Il nodo della radice �esplode� nella complessità n più due rami che corrispon-dono alle due chiamate ricorsive sulla metà degli elementi.

A loro volta ciascuno di questi nodi esplodono in altre due chiamate difunzione sulla metà degli elementi di partenza. L'albero che ne viene fuori èquello in �gura 1.3

Sommando la complessità per ogni livello, otteniamo proprio n.L'ultimo livello è quello costituito da tutte le chiamate a funzioni con low =

high, ed il numero di queste chiamate è proprio pari alla cardinalità del vettorein input (ossia n).

Dunque la complessità è la somma delle complessità ad ogni livello, quindih ∗ n con h pari all'altezza dell'albero. Per un albero binario l'altezza risultaessere h = lg n + 1 dunque:

T (n) ∈ Θ (n ∗ (lg n + 1))

T (n) ∈ Θ (n lg n)

Troviamo dunque coerenza con il risultato ottenuto per via analitica.



Figure 1.3: Albero di Ricorrenza

1.5 Realizzazione in C++

Di seguito riporteremo il listato dell'algoritmo di ricerca del massimo sottoarrayimplementato in C++.

La funzione principale che richiama queste funzioni, non fa altro che inizial-izzare staticamente un vettore di 6000 interi: di questi, viene chiesto all'utentequanti ne vuole utilizzare.

Supponiamo di chiamare x il valore inserito da utente; il vettore verrà inizial-izzato con x valori casuali nel range

{−x

2 ; +x2

}. Successivamente sono applicati

una serie di codici per apprezzare con una maggiore precisione il tempo di es-ecuzione della funzione stessa, ma rimandiamo il lettore ai paragra� successiviper la completa spiegazione.

1.5.1 Listato v1.0

Si noti che mentre in pseudocodice è possibile indicare una tripla di valori diritorno della funzione, in C e C++ ciò non è possibile. Si è quindi scelto diutilizzare la soluzione del passaggio di parametri per riferimento.

Viceversa il valore della somma degli elementi del massimo sottoarray è ilvalore di ritorno della funzione.

1 #include "functions.h"2

3 int find_maximum_sub_array4 (const int A[], const int low, const int high,5 int &low_max, int &high_max){6 int partial_sum = 0;



7 int max_sum = -2147483648;8 int i, j;9 for(i = low; i <= high; i++){

10 partial_sum = 0;11 for(j = i; j <= high; j++){12 partial_sum += A[j];13 if(partial_sum > max_sum){14 max_sum = partial_sum;15 low_max = i;16 high_max = j;17 }18 }19 }20 return max_sum;21 }

Le variabili locali utili alla funzione sono quattro:

1. partial_sum : variabile di tipo intero che conterrà iterazione per iterazioneil valore della somma parziale di ogni sottoarray.

2. max_sum : variabile di tipo intero inizializzata al minimo valore esprim-ibile su 32 bit (con segno), conterrà il valore della somma degli elementidel massimo sottoarray.

3. i : indice del ciclo più esterno.

4. j : indice del ciclo più interno.

Ogni iterazione esterna ha lo scopo di azzerare il valore della somma parziale(da ricalcolare per ogni sottovettore) e di stabilire un indice minimo di partenzaper un sottoarray.

Con l'iterazione interna invece si esplorano tutti i sottovettori aventi comeindice minimo quello dell'i-esima iterazione. Per ogni j-esima iterazione si ag-giorna il contenuto della somma parziale e si provvede ad aggiornare quello dellasomma massima se e solo se quest'ultimo è inferiore alla somma parziale.

1.5.1.1 Simulazione

Per testare il funzionamento corretto della nostra subroutine mostriamo il risul-tato di due simulazioni :

1. Vettore di interi casuale : per mostrare la correttezza per una genericadistribuzione di dati in input.

2. Vettore di interi scelti : per testare il corretto funzionamento di tutte lenostre versioni dell'algoritmo con la stessa distribuzione di dati in input.



La prima simulazione mostra il seguente risultato :

A[0]: -2A[1]: 1A[2]: -4A[3]: -5A[4]: -3A[5]: -2A[6]: 1A[7]: 2A[8]: 4A[9]: -5Execution Time = 0.001 millisecMaximum Sub-Array Have Sum : 7Index Values Of Maximum Sub-Array Are 6 And 8Max Sub-Array Is1 ; 2 ; 4 ;

Utilizziamo nella seconda simulazione un esempio riportato su libro di testo1,come esempio di confronto tra tutti gli algoritmi discussi.

A[0]: 13A[1]: -3A[2]: -25A[3]: 20A[4]: -3A[5]: -16A[6]: -23A[7]: 18A[8]: 20A[9]: -7A[10]: 12A[11]: -5A[12]: -22A[13]: 15A[14]: -4A[15]: 7Execution Time = 0.001 millisecMaximum Sub-Array Have Sum : 43Index Values Of Maximum Sub-Array Are 7 And 10Max Sub-Array Is18 ; 20 ; -7 ; 12 ;

1Fig 4.3 di �Introduzione agli algoritmi e strutture dati�, terza edizione, McGraw-Hill[T.Cormen, C. Leiserson, R.Rivest, C.Stein]



1.5.2 Listato v2.0

Di seguito viene riportata la versione sempli�cata ad una iterazione.

1 #include "functions.h"2

3 int find_maximum_sub_array4 (const int A[], const int low, const int high,5 int &low_max, int &high_max){6 int partial_sum = 0;7 int max_sum = -2147483648;8 int i, j;9 j = low;

10 for(i = low; i <= high; i++){11 partial_sum += A[i];12 if(partial_sum > max_sum){13 max_sum = partial_sum;14 low_max = j;15 high_max = i;16 }17 if(partial_sum <= 0){18 partial_sum = 0;19 j = i + 1;20 }21 }22 return max_sum;23 }

Il trattamento di partial_sum e max_sum rimane il medesimo; in aggiuntaviene valutata la condizione di valore negativo della somma parziale: in tal casol'indice estremo basso j viene aggiornato al prossimo valore di i.

1.5.2.1 Simulazione

Testiamo il funzionamento della seconda versione dell'algoritmo, utilizzando unadistribuzione di dati in input casuale.

A[0]: -3A[1]: 3A[2]: -5A[3]: -2A[4]: -3A[5]: 1A[6]: 0A[7]: -2A[8]: -4A[9]: -4Execution Time = 0 millisecMaximum Sub-Array Have Sum : 3



Index Values Of Maximum Sub-Array Are 1 And 1Max Sub-Array Is3 ;

Quindi, il funzionamento con il nostro esempio base.

A[0]: 13A[1]: -3A[2]: -25A[3]: 20A[4]: -3A[5]: -16A[6]: -23A[7]: 18A[8]: 20A[9]: -7A[10]: 12A[11]: -5A[12]: -22A[13]: 15A[14]: -4A[15]: 7Execution Time = 0 millisecMaximum Sub-Array Have Sum : 43Index Values Of Maximum Sub-Array Are 7 And 10Max Sub-Array Is18 ; 20 ; -7 ; 12 ;

Da notare il tempo di esecuzione dei due algoritmi. La stima misurata è di0 millisecondi in quanto l'algoritmo risulta così veloce che non se ne riesce adapprezzare una stima di misura al millesimo secondo.

1.5.3 Listato v3.0 - Ricorsione

La versione ricorsiva dell'algoritmo, come visto anche in pseudocodice, utilizzauna funzione di appoggio per la ricerca di sottoarray massimi a cavallo trail sottoarray destro e quello sinistro. La suddetta funzione di supporto è laseguente:

1 #include "functions.h"2 #include <math.h>3

4 int find_max_crossing_subarray5 (const int A[], const int low, const int mid, const int high,6 int &low_max, int &high_max){7 int i, j;8 int partial_sum;9 int right_sum;



10 int left_sum;11 //LEFT-SIDE-FIND-MAX-SUB-ARRAY12 partial_sum = 0;13 left_sum = -65535;14 for(i = mid; i >= low; i--){15 partial_sum += A[i];16 if(partial_sum > left_sum){17 left_sum = partial_sum;18 low_max = i;19 }20 }21 //RIGHT-SIDE-FIND-MAX-SUB-ARRAY22 partial_sum = 0;23 right_sum = -65535;24 for(j = mid+1; j <= high; j++){25 partial_sum += A[j];26 if(partial_sum > right_sum){27 right_sum = partial_sum;28 high_max = j;29 }30 }31 return left_sum + right_sum;32 }

All'interno della funzione troviamo variabili utili allo scope della funzione,tra cui:

• right_sum : memorizza la somma di elementi dei sottoarray di destra.

• left_sum : memorizza la somma di elementi dei sottoarray di sinistra

• partial_sum : memorizza il valore parziale della somma per valutare sequest'ultima è massima.

La funzione si suddivide in due fasi, una per la ricerca del massimo sottovettoredi sinistra (rispetto all'elemento mid) e l'altra per la ricerca a destra. Si notiinfatti che gli indici del ciclo �di sinistra� sono decrescenti, in quanto a noiinteressa trovare un sottoarray che contenga mid e che sia massimo: logicaquindi la scelta di partire ad esaminare il vettore da mid per poi decrescere.Dualmente nel secondo ciclo si parte dall'elemento subito dopo mid (per nonincludere nella somma due volte il valore di mid), per poi crescere verso la �nedel vettore.

Anche qui c'è da notare che tra i parametri di ingresso risultano due variabilipassate per riferimento: esse rappresentano i valori degli indici del massimosottoarray, che precedentemente avevamo segnalato come valori di ritorno.

Entriamo dunque nel vivo della funzione di calcolo del massimo sottoarray,il cui codice segue.



1 #include "functions.h"2 #include <math.h>3

4 int find_maximum_subarray5 (const int A[], const int low, const int high,6 int &low_max, int &high_max){7 int mid;8 int left_low, left_high;9 int right_low, right_high;

10 int cross_low, cross_high;11 signed int left_max_sum, right_max_sum, cross_max_sum;12 if(low == high){13 low_max = low;14 high_max = high;15 return A[low];16 }17 else{18 mid = floor((double)((low + high)/2));19 //LEFT SIDE20 left_max_sum =21 find_maximum_subarray(A, low, mid, left_low, left_high);22 //RIGHT SIDE23 right_max_sum =24 find_maximum_subarray(A, mid+1, high, right_low, right_high

);25 //CROSS26 cross_max_sum =27 find_max_crossing_subarray28 (A, low, mid, high, cross_low, cross_high);29 //FIND MAX VALUE30 if(left_max_sum >= right_max_sum && left_max_sum >=

cross_max_sum){31 low_max = left_low;32 high_max = left_high;33 return left_max_sum;34 }else if(right_max_sum >= left_max_sum &&35 right_max_sum >= cross_max_sum){36 low_max = right_low;37 high_max = right_high;38 return right_max_sum;39 }else{40 low_max = cross_low;41 high_max = cross_high;42 return cross_max_sum;43 }44 }45 }



L'algoritmo è il medesimo di quello visto in pseudocodice.Nell'implementazione abbiamo bisogno di dichiarare variabili che conter-ranno i valori massimi di somma, e gli indici dei sottoarray di destra, sinistra eda cavallo tra i due. Gli indici estremi inferiori saranno memorizzati in left_low,

right_low e cross_low, quelli alti in left_high, right_high, cross_high, mentrele somme in left_max_sum, right_max_sum e cross_max_sum.

L'unica nota da aggiungere è l'inserimento della libreria <math.h> perl'utilizzo della funzione �oor per il calcolo della mediana.

1.5.3.1 Simulazione

Anche in questo caso testiamo il funzionamento della nostra funzione in C/C++La prima simulazione sarà e�ettuata su una distribuzione di dati in input

casuale e darà come risultato:

A[0]: -1A[1]: -1A[2]: 0A[3]: 0A[4]: 2A[5]: -1A[6]: -4A[7]: 4A[8]: 3A[9]: -2Execution Time = 0 millisecMaximum Sub-Array Have Sum : 7Index Values Of Maximum Sub-Array Are 7 And 8Max Sub-Array Is4 ; 3 ;

Mentre la seconda sulla nota distribuzione di dati in input, già utilizzata inprecedenza.

A[0]: 13A[1]: -3A[2]: -25A[3]: 20A[4]: -3A[5]: -16A[6]: -23A[7]: 18A[8]: 20A[9]: -7A[10]: 12A[11]: -5A[12]: -22



A[13]: 15A[14]: -4A[15]: 7Execution Time = 0 millisecMaximum Sub-Array Have Sum : 43Index Values Of Maximum Sub-Array Are 7 And 10Max Sub-Array Is18 ; 20 ; -7 ; 12 ;

Il quale è il medesimo risultato ottenuto con gli altri due codici precedenti.Con questo si chiude la trattazione sul funzionamento del nostro algoritmo;

adesso andremo a valutarne le prestazioni.

1.5.4 Valutazione delle prestazioni

Cercheremo in questo paragrafo di dimostrare i risultati ottenuti analiticamente,sulla complessità degli algoritmi di ricerca del massimo sottoarray.

Prima di mostrare la procedura di analisi dei tempi dei programmi scritti inC/C++ ricordiamo la de�nizione della notazione asintotica Θ (g (n))

f (n) ∈ Θ (g (n)) ≡ {f (n) : ∃c1, c2, n0 > 0|c1 ∗ g (n) < f (n) < c2 ∗ g (n) ,∀n ≥ n0}

Ossia, dire che una funzione è Θ (g (n)) signi�ca dire che è possibile trovaredue costanti positive che moltiplicate per g (n) fanno da limite sia superiore cheinferiore alla funzione che è Θ (n), a partire da un certo n0.

Per la valutazione dei tempi di esecuzione utilizzeremo la libreria sys/-time.h, che utilizza la variabile clocks_per_sec, ossia quanti colpi di clockci sono in un secondo. In sostanza andremo a misurare di quanti colpi di clocknecessita la nostra funzione, per poi dividerli per il numero di clock contenutiin un secondo. Siccome le frequenze di clock dei processori moderni sono moltoelevate, eseguire una sola volta l'algoritmo darebbe risultati prossimi allo zero(o addirittura zero). Quindi per una misurazione più precisa e�ettueremo millevolte l'operazione di ricerca del massimo sottoarray, così da apprezzare un tempodi esecuzione maggiore di zero, salvo poi dividere il risultato per mille ed ot-tenere così il tempo di esecuzione di una sola chiamata di funzione.

Per gra�care l'andamento temporale al crescere della cardinalità del vettoredi ingresso, l'operazione appena descritta verrà e�ettuata per distribuzioni didati in ingresso di dimensione via via crescendo: in particolare partiremo da unvettore di 100 elementi, per arrivare (di dieci in dieci) a 3000 elementi.

1.5.4.1 Prestazioni versione iterativa a doppio ciclo

In �gura 1.4 mostriamo il gra�co dell'andamento temporale della prima versionedel nostro algoritmo. Ricordiamo che la complessità trovata era T (n) ∈ Θ

(n2)

In questo caso le costanti trovate sono:



Figure 1.4: Gra�co andamento temporale algoritmo v1.0

Figure 1.5: Gra�co andamento temporale algoritmo v2.0

c1 =1

250

c2 =1

1000

1.5.4.2 Prestazioni versione iterativa a singolo ciclo

In �gura 1.5 il gra�co dell'andamento temporale della seconda versione del nos-tro algoritmo. Ricordiamo che la complessità trovata era T (n) ∈ Θ (n)

Le costanti trovate sono:

c1 =1

200

c2 =1

90



Figure 1.6: Gra�co andamento temporale algoritmo ricorsivo

1.5.4.3 Prestazioni versione ricorsiva

In �gura 1.6 il gra�co dell'andamento temporale della terza ed ultima ver-sione del nostro algoritmo. Ricordiamo che la complessità trovata era T (n) ∈Θ (n lg n)

Le costanti trovate sono:

c1 =1

300

c2 =1

40

1.6 Conclusioni

Con l'analisi delle prestazioni degli algoritmi si chiude la trattazione del prob-lema di ricerca del massimo sottoarray.

Tra le soluzioni implementate, la prima risulta ovviamente la più lenta, inquanto al crescere della cardinalità del vettore in input, i tempi crescono con ilquadrato.

Inoltre stesso in fase di simulazione si è riscontrato un tempo di esecuzionetotale del programma (da 100 a 3000 valori) improponibile per un semplicealgoritmo; diverso è il caso degli altri due che hanno necessitato decisamente dimeno tempo per l'esecuzione.


Capitolo 2

Topological sort

2.1 Introduzione

Prima di formalizzare il problema dell'ordinamento topologico, è bene dare al-cune de�nizioni utili a comprenderlo a fondo. Le de�nizioni provengono dallateoria dei gra�.

Un grafo non orientato G = (V,E)è de�nito da un insieme �nito V (G) ={v1, v2, ..., vn}di elementi detti nodi o vertici e da un insieme E (G) ={e1, e2, ..., em} ⊆ V xV di coppie non ordinate di nodi dette archi o spigoli.

Se ad ogni arco, associamo una direzione (uscente da un vertice ed entrantein un altro), otteniamo un grafo orientato.

Un grafo orientato, può de�nirsi aciclico se non presenta cicli diretti, ossiase partendo da un nodo qualsiasi non è possibile tornare ad esso percorrendonel giusto verso gli archi.

De�niamo dunque l'ordinamento topologico, che è il cuore del nostro prob-lema.

De�nisco ordinamento topologico, un ordinamento lineare di tutti i verticidi un grafo aciclico orientato. Si dice che i nodi di un grafo sono ordinatitopologicamente se essi sono disposti in modo tale che ogni nodo viene prima ditutti i nodi collegati ai suoi archi uscenti. L'ordinamento topologico non è unordinamento totale, poiché la soluzione può non essere unica.

L'algoritmo su cui si basa quello dell'ordinamento topologico, è la visita inprofondità (DFS) di un grafo orientato. Basandoci sulla DFS, l'ordinamentotopologico risulta piuttosto semplice, in quanto non è altro che una stampa diuno stack, all'interno del quale sono memorizzati man mano i nodi visitati dallaDFS.

22

CAPITOLO 2. TOPOLOGICAL SORT

Figure 2.1: Ordine di scoperta nodi in DFS

2.2 Depth-First-Search

La visita in profondità Depth-First-Search (DFS) di un grafo consiste nellaesplorazione sistematica di tutti i vertici andando in ogni istante il più possibilein profondità. Gli archi vengono esplorati a partire dall'ultimo vertice scopertov che abbia ancora archi non esplorati uscenti e quando questi sono �niti sitorna indietro per esplorare gli altri archi uscenti dal vertice dal quale v erastato scoperto.

Il procedimento continua �no a quando non vengono scoperti tutti i verticiraggiungibili dal vertice sorgente originario. Se al termine rimane qualche verticenon scoperto, uno di questi diventa una nuova sorgente e si ripete la ricerca apartire da esso.

E' possibile visualizzare uno dei possibili ordini di scoperta dei nodi (connodo sorgente '1') in �gura 2.1

Per creare un sistema di �tracciamento� dello stato di visita, ad ogni nodoviene associato un colore:

• Ogni vertice è inizialmente bianco.

• E' grigio quando viene scoperto.

• Viene reso nero quando la visita è �nita, cioè quando la sua lista di adia-cenza è stata completamente esaminata.

Oltre al colore, si associano ad ogni vertice due informazioni temporali:

1. Tempo di inizio visita: quando un nodo è reso grigio per la prima volta.

2. Tempo di �ne visita: quando è reso nero.



Il tempo è un intero compreso fra 1 e due volte il numero di vertici, poiché ognivertice può essere scoperto una sola volta e la sua visita può �nire una solavolta.

2.2.1 Pseudocodice

Di seguito speci�chiamo in pseudocodice il funzionamento della DFS

1 DFS(G)2 Per ogni u in V[G]3 u.color = WHITE4 u.parent = NIL5 time = 06 Per ogni v in V[G]7 if v.color = WHITE8 DFS-Visit(v)9

10 DFS-Visit(u)11 u.color = GREY12 u.starttime = time = time + 113 Per ogni v in Adj(u)14 if v.color = white15 v.parent = u16 DFS-Visit(v)17 u.color = black18 u.endtime = time = time + 1

L'algoritmo DFS comincia con l'inizializzazione di tutti i nodi. Nel partico-lare tutti i nodi sono inizialmente bianchi e con predecessore nullo.

Si noti l'utilizzo di un �contatore� del tempo, inizializzato a zero.Come da de�nizione di DFS, si comincia la visita da un qualsiasi nodo che

non sia ancora stato esplorato (quindi di colore bianco) per poi andare più inprofondità possibile richiamando ricorsivamente la DFS-Visit.

Non appena inizia la visita in profondità di un nodo si pone il colore a grigioe si marca il tempo di inizio visita, per poi andare a valutare i nodi adiacenti alnodo in questione: se uno di questi è colorato di bianco, si imposta la dipendenzadi predecessore e si inizia una nuova visita sul nodo adiacente bianco.

Terminati i nodi adiacenti bianchi, il nodo può essere marcato di nero e sene può registrare il tempo di �ne visita.

2.2.2 Correttezza dell'algoritmo

Lo scopo della visita in profondità è quello di andare a scoprire man manotutti i nodi presenti all'interno del grafo, andando ogni volta più in profonditàpossibile. In prima battuta bisogna dimostrare la correttezza della DFS-Visited in seguito quella della DFS.



DFS-Visit è un algoritmo ricorsivo e per tanto ne dimostriamo la correttezzatramite principio di induzione completa; la visita può dirsi terminata quandotutti i nodi connessi all'origine sono colorati di nero.

• Passo Base. Per n = 1, il nodo viene scoperto e colorato di grigio, men-tre la lista di adiacenza Adj è vuota. Dunque non si entra nel ciclo enon si richiama ricorsivamente la funzione. Successivamente il nodo vienecolorato di nero, ma essendo l'unico nodo, ciò fa terminare la visita diprofondità.

• Passo Induttivo. Supponendo che la chiamata ricorsiva operi corretta-mente, essa viene e�ettuata su tutti i nodi contenuti nella lista di adi-acenza. Ma al più un nodo può essere connesso a tutti gli n − 1 nodirestanti del grafo, ossia un numero inferiore ad n. Qualora vi fossero al-tri nodi connessi all'origine tramite un cammino semplice, essi sarebberopresenti nella lista di adiacenza di un nodo intermedio, che chiamerebbecorrettamente la funzione; se non fossero connessi tramite un camminosemplice, non rientrerebbero nella de�nizione di visita in profondità. Peripotesi induttiva l'algoritmo opera correttamente.

Dimostrare la correttezza della DFS è quindi banale, in quanto l'algoritmo nonfa altro che richiamare la visita in profondità su ogni nodo del grafo.

• Se avessimo n nodi indipendenti e quindi non connessi, cadremmo nel casodi n chiamate base alla visita in profondità.

• Se i nodi sono connessi, la chiamata alla DFS-Visit è e�ettuata solo peri nodi bianchi, e dato che è una chiamata corretta (colora di nero tutti inodi connessi all'origine), scopriremo tutti i nodi del grafo.

2.2.3 Complessità

Per un analisi più precisa della complessità della visita in profondità (che poivedremo coincidere con la complessità dell'ordinamento topologico), ricorriamoall'analisi ammortizzata. Se volessimo ricorrere alle equazioni con ricorrenze citroveremmo di fronte a una soluzione poco accurata, invece con un analisi at-tenta del codice ci rendiamo conto di conoscere già esattamente quante iterazionil'algoritmo e�ettuerà, ossia siamo in grado di fare un analisi ammortizzata.

Per quanto riguarda la DFS-Visit, siamo in grado di dire che avvengono(nel ciclo for) 'E' confronti, dove E è il numero di archi presenti nel grafo G.Utilizzando però l'analisi ammortizzata ci accorgiamo che questo è un limitesuperiore (ossia la complessità è un O (E)): infatti è vero che avvengono Econfronti, ma la funzione ricorsiva viene richiamata solo se il nodo è marcatobianco.

Dato che la prima cosa che la DFS-Visit fa è marcare il nodo di grigio, essaviene richiamata in un numero di volte che è al più E. Diremo quindi che lacomplessità è Θ (E).



La DFS invece è un semplice algoritmo iterativo, che richiama la DFS-Visitper ogni suo vertice. In realtà abbiamo detto anche precedentemente, che la chia-mata alla DFS-Visit viene fatta per ogni nodo solo se E = {Ø} (caso peggioreper la DFS). Dunque anche in questo caso, anziché a�ermare che l'iterazionedella DFS chiama O (V ) volte la DFS-Visit (dove V è l'insieme dei vertici),diremo che la chiama Θ (V ).

La complessità della DFS risulta dunque

T (n) ∈ Θ (V + E)

2.3 Topological Sort

L'ordinamento topologico è un ordinamento de�nito su i vertici di un grafoorientato aciclico (directed acyclic graph DAG).

Si può pensare all'ordinamento topologico come ad un modo per ordinarei vertici di un DAG lungo una linea orizzontale in modo che tutti gli archiorientati vadano da sinistra verso destra: questo ci da l'idea che i DAG sonoutilizzabili per modellare successioni di eventi temporali.

Abbiamo introdotto la visita in profondità (DFS) con marcatura temporalein quanto secondo l'ordinamento topologico:

• Un vertice v il cui tempo di �ne visita e' successivo ad un vertice u, dovra'precederlo nell'ordinamento �nale.

2.3.1 Pseudocodice

Sfruttando dunque l'algoritmo DFS, il topological sort risulta banale: basteràinserire in una coda i nodi, man mano che diventano neri, per poi leggerli dallatesta (per cui il primo che diventa nero, è il primo ad esser letto).

1 Topological-Sort(G)2 Chiama DFS(G) per calcolare tutti i tempi di fine visita3 Data Q coda di vertici4 Per ogni v in V(G)5 Q.Enqueue(v) ogni volta che termino la visita su un nodo (

quando diventa nero)6 return Q

Sostanzialmente il funzionamento del topological-sort sta tutto nellavisita in profondità di un grafo. Infatti per quanto riguarda la complessità diquesto algoritmo, dato che l'accodamento ha una complessità Θ (1), diremo chel'algoritmo ha una complessità pari a quella della DFS, ossia Θ (V + E).

2.3.2 Funzionamento gra�co

La �gura 2.2 mostra i tempi di inizio e �ne visita DFS, dato un grafo orientatoaciclico, di ogni nodo.



Figure 2.2: Tempi di inizio e �ne visita DFS

Figure 2.3: Ordinamento topologico

L'ordinamento topologico invece da luogo al gra�co in �gura 2.3.

La �gura 2.3 non presenta archi all'indietro, ed è dunque un ordinamentotopologico corretto.

Nella �gura 2.2 sono stati evidenziati anche i tempi di inizio e �ne visitadella DFS. Ordinare topologicamente equivale semplicemente ad ordinare i nodia seconda del loro tempo di �ne visita (dal più grande al più piccolo).

2.3.3 Correttezza

Per quanto riguarda la veri�ca della correttezza di questo tipo di algoritmi,dobbiamo prendere in prestito i teoremi sulla teoria del gra�.

topological-sort produce un ordinamento topologico di ungrafo orientato aciclico G.

E' su�ciente dimostrare che per ogni coppia di nodi (u, v) ∈ V , se esiste unarco (u, v) allora il tempo di �ne visita in v è minore di quello in u.



Prima di dimostrare questo, de�niamo i tipi di archi in base al colore deinodi e de�niamo d[u] = TempoInizioV isita, f [u] = TempoFineV isita

• se v è bianco. L'arco è un arco d'albero

• se v è grigio. L'arco è un arco di ritorno

• se v è nero. L'arco è un arco in avanti o un arco di attraversamento

• se inoltre d[u] < d[v] allora è un arco in avanti

• se d[u] > d[v] allora è un arco di attraversamento

2.3.3.1 Teorema del cammino bianco

In una foresta DFS, un nodo v è discendente di u, se e solo se al tempo d[u](in cui la visita scopre u), il vertice v e raggiungibile da u con un camminocontenente esclusivamente nodi bianchi.

2.3.3.2 Teorema sui gra� aciclici

Un grafo orientato è aciclico se e solo se l'algoritmo DFS su G non trova alcunarco di ritorno.

Supponiamo che G contenga un ciclo c. Sia v il primo vertice scoperto inc, e (u, v) l'arco che lo precede in c. Allora, al tempo d[v], c'è un percorsobianco da v a u. Per il teorema del cammino bianco, sappiamo che u diventa undiscendente di v nella foresta DF. Perciò (u, v) deve essere un arco di ritorno.

Supponiamo che DFS incontri un arco di ritorno (u, v). Allora il vertice vè un antenato di u nella foresta DF. Quindi esiste certamente un percorso cheva da v a u nel grafo G. Tale percorso, concatenato con l'arco di ritorno (u, v),forma un ciclo, quindi il grafo G non è aciclico. Ne concludiamo che se DFSnon trova archi di ritorno, il grafo è aciclico.

2.3.3.3 Correttezza del topological sort

Dunque, constatata l'assenza di archi di ritorno in un grafo aciclico possiamodire che per ogni coppia (u, v) ∈ V , l'arco (u, v) può essere:

• L'arco di un albero. Quindi v è bianco e diventa discendente di u; neconsegue che f [v] < f [u]

• Un arco in avanti o di attraversamento. In tal caso v è nero e ne consegueche f [v] < f [u] poiché v è già diventato nero prima di aver concluso lavisita di u.



2.4 Realizzazione in C++

2.4.1 Codice topological sort

Come già abbondantemente accennato, il topological sort utilizza prevalente-mente DFS per eseguire l'ordinamento. Dunque riporteremo qui di seguito ilcodice della DFS e della DFS-Visit con una variante per realizzare l'ordinamentotopologico: sostanzialmente ogni volta che termina la visita su di un nodo,esso va inserito all'interno di un vettore, che poi verrà letto in ordine contrario(in quanto i tempi di �ne visita sono in ordine decrescente) così da simularegrossolanamente il funzionamento di una coda.

1 #include "dfs.h"2 #include <iostream>3 using std::cout;4 using std::endl;5

6 extern int time_visit;7 extern int index;8

9 void DFS(char G[], node_set V, const int riemp,10 const AdjMatrix Adj, node_set inorder){11 int i;12 for(i = 0; i < riemp; i++){13 V[i].id = i;14 V[i].label = G[i];15 V[i].color = ’w’;16 V[i].parent = ’0’;17 V[i].time_start = 0;18 V[i].time_end = 0;19 }20 time_visit = 0;21 index = 0;22 for(i = 0; i < riemp; i++){23 if(V[i].color == ’w’){24 DFS_Visit(V[i], V, Adj, riemp, inorder

);25 }26 }27 index--;28 }29

30 void DFS_Visit(node &u, node_set V, const AdjMatrix Adj,31 const int riemp, node_set inorder){32 int i;33 u.color = ’g’;34 u.time_start = ++time_visit;35 for(i = 0; i < riemp; i++){36 if(Adj[u.id][i] == 1){



37 if(V[i].color == ’w’){38 V[i].parent = ’u’;39 DFS_Visit(V[i], V, Adj,

riemp, inorder);40 }41 }42 }43 u.color = ’b’;44 u.time_end = ++time_visit;45 inorder[index].label = u.label;46 inorder[index].time_end = u.time_end;47 index++;48 }

E' necessario anche riportare parte dell'header �le, in quanto è necessariovisualizzare la struttura di un nodo di un grafo.

Ogni nodo presenta un numero identi�cativo (utile per individuarlo nellamatrice di adiacenza), un'etichetta per il riconoscimento da parte dell'utente,un colore, un predecessore, un tempo di inizio visita e �ne visita.

1 struct node{2 int id;3 char label;4 char color; //w = WHITE, g = GRAY, b = BLACK5 char parent;6 int time_start;7 int time_end;8 };9

10 typedef node node_set[DIM];

L'algoritmo della DFS è stato realizzato tramite matrici di adiacenza, dovela i-j esima locazione contiene un 1 se il nodo individuato dalla riga i ha un arcoverso il nodo individuato dalla colonna j.

L'algoritmo è quello già visualizzato in pseudocodice. Commentiamo peròalcune piccole aggiunte dovute all'implementazione.

Sono presenti due variabili extern, ossia due variabili dichiarate globali inaltri �le a cui è possibile accedere (in lettura e scrittura) in questo �le. Sebbenel'utilizzo di variabili globali (ed ancor più di tipo extern) è sconsigliato nellaprogrammazione, le utilizzeremo in quanto il progetto è di piccole dimensioni etrattasi di una simulazione a scopo solo didattico.

Una prima variabile conteggia gli istanti di tempo, la seconda conta quantielementi sono inseriti di volta in volta nell vettore �nale da cui leggere l'ordinedei nodi.

A questo punto per ogni nodo bianco viene richiamata la DFS-Visit.Essa colora il nodo che sta visitando ed esplora la matrice di adiacenza

partendo dalla riga relativa al nodo da visitare, per valutare eventuali nodi



adiacenti. Se uno di questi nodi adiacenti è bianco, la procedura opera ricor-sivamente. In seguito viene aumentato il tempo e segnato nel nodo che haterminato la visita; l'etichetta del nodo viene poi aggiunta alla lista ordinatatopologicamente.

Basterà stampare in ordine inverso questa lista per ottenere un correttoordinamento topologico.

L'output di questo algoritmo scritto in C++, a seguito di un input in �gura2.2 è mostrato in �gura 2.4.

Nell'output del programma troviamo anche segnati i tempi di inizio e �nevisita, perfettamente coincidenti con l'analisi �gra�ca� e�ettuata in precedenza.

2.4.2 Analisi delle prestazioni

Precedentemente avevamo a�ermato che la complessità del topological sort fosseΘ (V + E). Andiamo a simulare il nostro algoritmo registrandone i tempi diesecuzione.

La simulazione consta nell'ordinamento topologico di 256 gra� diversi(rispettivamente aventi da 1 a 255 nodi).

La matrice di adiacenza viene generata automaticamente con una procedurarandomizzata.

In seguito l'ordinamento è eseguito mille volte, salvo poi dividere il tempodi esecuzione per mille.

Gra�cando i risultati otteniamo il risultato in �gura 2.5.

A sinistra è possibile visualizzare l'andamento temporale al crescere di vertcie transizioni.

A destra è possibile vedere l'esplicazione della notazione tetha. Si noti che2901 < n0 < 4148

Le costanti utilizzate sono:

c1 =1

40

c2 =1

50



Figure 2.4: Output topological sort



Figure 2.5: Andamento temporale dell'ordinamento topologico


ASD-Find Maximum SubArray & Topological Sort

Documents

Transcript of ASD-Find Maximum SubArray & Topological Sort