Appunti di

Algoritmi e Struture Dati

per il Corso di Laurea Specialistica in ECOSTI

Guido Fiorino

0 Presentazione

0.1 Programma del corso

• Un esempio introduttivo

• Cenni ai modelli di calcolo e alle metodologie di analisi

• Algoritmi di ordinamento Bucketsort e Radixsort

• Selezione e statistiche d’ordine

• Tecnica divide et impera

• Programmazione dinamica

• (Tecnica greedy)

• Grafi e loro visite

• (Minimo albero ricoprente)

• Cammini minimi

• Flusso

0.2 Materiale Didattico

Libro adottato:C. Demetrescu, I. Finocchi, G. Italiano, Algoritmi e strutture dati, McGraw-Hill, 2004.

Libri consigliati:T.H. Cormen, C.E. Leiserson, R.L. Rivest, Introduzione agli algoritmi, Jackson Libri, 1999.

R. Sedgewick, Algoritmi in C, Addison-Wesley Italia, 1993.

Dispense:A. Bertoni, M. Goldwurm, Progetto e analisi di algoritmi, scaricabile dal sitohttp://homes.dsi.unimi.it/ goldwurm/algo/

0.3 Esame

Uno scritto di 1h30min. in cui si chiedono algoritmi e dimostrazioni di teoremi visti nel corso, problemi incui si chiede di adattare quanto visto a lezione o dimostrazioni di teoremi non visti a lezione, esercizi chesiano applicazione di quanto visto a lezione.Un orale facoltativo che fara media con lo scritto.

2

1 Un esempio introduttivo

nel corso gli algoritmi NON verranno scritti in C o in JAVA o in qualche linguagglio di programmazione realema in pseudocodice; ci occupiamo di progettare algoritmi e di analizzarli matematicamente, cosa diversache condurre analisi sperimentali; L’analisi e preferibile perche ci da risposte su tutti i casi possibili, cioepermette di predire il comportamento di un algoritmo per ogni possibile dato di ingresso e permette discegliere tra 2 algoritmi anche senza averli implementati;

1.1 Numeri di Fibonacci

Come si espande una popolazione di conigli a partire da una singola coppia sotto le seguenti ipotesi sem-plificatrici: 1) una coppia di conigli genera una coppia di conigli all’anno; 2) i conigli nel primo anno nonsi riproducono; 3) i conigli sono immortali; in base a quanto detto possiamo graficamente rappresentare ilnumero conigli con un albero; e chiaro che nell’anno t abbiamo tutte le coppie di conigli presenti nell’annot − 1, infatti nessuno e morto; inoltre tutte le coppie presenti nell’anno t − 2 hanno figliato una coppia diconigli. Quindi se F (n) denota il numero di conigli nell’anno n dell’esperimento abbiamo che F (1) = 1,F (2) = 1, F (n) = F (n − 1) + F (n − 2) per n ≥ 3. Ne segue che F e una funzione definita per casi.E’ una funzione definita per ricorsione. Possiamo domandarci se esista una funzione analitica equivalente.proviamo a vedere se F (n) ha un andamento esponenziale, cioe se per caso F (n) = an, con a ∈ R. se F (n)ha andamento esponenziale allora sostituendo nella ricorrenza otteniamo

an = an−1 + an−2

Portando tutto a primo membro, raccogliendo a fattor comune an−2 otteniamo che deve essere a2−a−1 = 0.Risolvendo l’equazione otteniamo due soluzioni per a : a1 = 1+

√5

2 e a2 = 1−√

52 . Purtroppo anche se (1+

√5

2 )n

e (1−√

52 )n hanno il medesimo andamento di F (n) nessuna di loro due e F (n) come si vede ad esempio per

n = 2. Dov’e il problema? Il problema sta nel fatto che le due funzioni risolvono la ricorrenza ma nonrispettano il passo base di F (n). Siccome una qualunque combinazione lineare di funzioni che soddisfano laricorrenza di fibonacci, soddisfa anch’essa la ricorrenza cerchiamo di ricavare una funzione

G(n) = c1

(1 +

√5

2

)n

+ c2

(1−

√5

2

)n

combinazione lineare delle 2 trovate e che soddisfi anche il passo base, ovvero G(1) = 1, G(2) = 1. Imposti-amo il sistema cosi’ da scoprire quanto devono valere c1, c2

c1(1+√

52 )1 + c2(1−

√5

2 )1 = 1c1(1+

√5

2 )2 + c2(1−√

52 )2 = 1

Questo e un sistema in 2 equazioni e 2 incognite che risolto da

c1 =1√5, c2 = − 1√

5

3

Abbiamo quindi la nostra funzione G(n) = F (n), ovvero abbiamo scoperto l’andamento analitico di F (n):

F (n) =1√5

((1 +

√5

2

)n

−

(1−

√5

2

)n)

Questa soluzione immediatamente suggerisce un algoritmo molto facile. Il difetto di questa soluzione e chelavora con i reali ma un calcolatore non puo rappresentarli con una precisione illimitata. Questo produceerrore nei calcoli e quindi un errore nel computo di F (n).

1.2 Algoritmo ricorsivo

Piuttosto che usare la versione analitica di F (n), usiamo la sua definizione ricorsiva e scriviamo un algoritmoricorsivo per calcolare F (n) come quello in figura 1.4, pagina 6 (fibonacci2). Ma quanto tempo ci vuole adeseguire questo algoritmo in funzione del valore di ingresso? Prima di tutto stabiliamo cosa e per noi iltempo. Scegliere una grandezza come i secondi non va bene in quanto con il cambiare della tecnologia ilmedesimo codice eseguito su una macchina nuova impiega di meno. per noi il tempo impiegato sara inprima approssimazine il numero di righe di codice eseguite dove assumeremo che ciascuna riga possa essereeseguita sempre con il medesimo tempo e che questo sia costante. Valutiamo il numero di righe T (n) infunzione di n:

• se n = 1 o n = 2 allora T (n) = 1;

• se n ≥ 3, allora T (n) = T (n−1)+T (n−2)+2, ovvero il numero di righe eseguite e 2 piu il numero dirighe richiesto per eseguire la chiamata ricorsiva con parametro n− 1 piu il numero di righe richiestoper la chiamata ricorsiva con parametro n− 2.

Si osservi come la ricorrenza assomigli fortemente a quella della funzione F (n) di fibonacci. Valutiamo T (n):sicuramente vale che T (n) > T (n− 2) + T (n− 2) = 2T (n− 2). Srotolando la ricorsione otteniamo che

T (n) > 2T (n− 2) > 22T (n− 2 ∗ 2) > 23T (n− 2 ∗ 3) > ... > 2kT (n− 2 ∗ k) > ...

fino ad ottenere T(2) se n pari,

T (n) > 2T (n− 2) > 22T (n− 2 ∗ 2) > 23T (n− 2 ∗ 3) > ... > 2kT (n− 2 ∗ k) > ...

fino ad ottenere T(1) se n dispari. Ora, se n pari, quante iterazioni sono necessarie per raggiungere T(2)?Basta porre n−2∗k = 2 ed otteniamo k = n−2

2 , cioe k e il numero di iterazioni in funzione di n per arrivareal passo base. Sostituendo k otteniamo che T (n) > 2

n−22 . Questo ci dice che il numero di righe eseguito e

(almeno) esponenziale in funzione di n, con n pari. Per n dispari otteniamo T (n) > 2n−1

2 . Possiamo anchelimitare superiormente T (n):

T (n) < 2T (n− 1) + 2 < 22T (n− 2) + 2 ∗ 2 < 23T (n− 3) + 2 ∗ 3 < ... < 2kT (n− k) + 2 ∗ k < ...

4

Questa catena termina quando n− k = 2, ovvero dopo k = n− 2 iterazioni. Sostituendo otteniamo

T (n) < 2n−2 + 2 ∗ (n− 2)

possiamo concludere che il numero di istruzioni e esponenziale rispetto a n.

Il problema dell’algoritmo fibonacci2 e che ricalcola la soluzione al medesimo problema piu volte. Questolo si vede facilmente analizzando l’albero delle chiamate ricorsive: per calcolare F (8) si ricalcola piu volte ilvalore F (4).

Albero delle chiamate ricorsive di F(8)

1.3 algoritmo iterativo

L’algoritmo fibonacci3, figura 1.6 pagina 9 riutilizza le risposte a sottoproblemi gia risolti senza ricalcolare larisposta e questo fa risparmiare tempo. L’idea e di mantenere una lista i valori F (1), F (2), . . . e di accederviquando serve. calcoliamo il numero di righe di codice eseguite in funzione del valore n: le righe 1,2,5 vengonosempre eseguite; la riga 3 viene eseguita:

• 1 volta se n = 1, 2,

• n− 1 volte negli altri casi;

il passo 4 viene eseguito:

• 0 volte nei casi n = 1, 2,

• n− 2 volte altrimenti.

riassumendo: la linea 3 viene eseguita:

• n-1 volte per n ≥ 2,

• 1 volta se n = 1;

la linea 4 viene eseguita:

• n− 2 volte se n ≥ 2,

• 0 altrimenti.

Il numero di linee di codice eseguite, ovvero il tempo di esecuzione in funzione di n e:

T (n) =

4 se n ≤ 1;3 + (n− 2) + (n− 1) = 2n se n ≥ 2

anche l’occupazione di memoria e un fattore rilevante. L’algoritmo richiede spazio proporzionale a n.l’algoritmo puo essere modificato in fibonacci4 (figura 1.8, pagina 12) per utilizzare spazio costante. Ilprezzo che si paga e una maggiore lentezza.

5

1.4 Notazione asintotica

L’analisi fatta sinora soffre del fatto che contiamo le linee di codice, e quindi il medesimo programma scrittosu linee di codice differenti da valori differenti pur avendo la medesima velocita; aumentare la velocita di uncomputer da tempi differenti, ma l’analisi non cambia dato che sempre lo stesso numero di righe di codicee eseguito. si puo astrarre da questi dettagli mediante la notazione asintotica cioe trascurando le costantimoltiplicative delle funzioni e vedendo come “viaggia” la complessita per n → ∞; date due funzioni f(n)g(n) da N a N, diremo che f(n) e “O di g(n)” e scriveremo f(n) ∈ O(g(n)) o con abuso di notazione anchef(n) = O(g(n)) se esistono n0 e c > 0 tali che f(n) <= cg(n) per n ≥ n0, cioe f(n) da un certo punto inpoi si comporta come g(n) a meno di una costante.

1.5 Un algoritmo basato su potenze ricorsive

Sia A =(

1 11 0

). Allora

Lemma 1.1 An−1 =(

F (n) F (n− 1)F (n− 1) F (n− 2)

), n ≥ 2.

Cosı possiamo definire l’algoritmo iterativo fibonacci5 (figura 1.10, pagina 14) basato sulla moltiplicazionedi matrici. si vede immediatamente che il tempo di esecuzione e O(n), quindi uguale a finonacci3 e fi-bonacci4, ma qui la notazione asintotica nasconde le costanti. fibonacci5 usa spazio di memoria costante.fibonacci5 puo essere ulteriormente migliorato facendo la moltiplicazione di matrici mediante quadrati suc-cessivi, basandosi sul fatto che An = An/2∗An/2, se n pari. otteniamo cosı fibonacci6 (figura 1.11, pagina 15)il cui tempo di esecuzione e in pratica il tempo speso per la chiamata alla funzione. Studiamo il tempoimpiegato da potenzamatrice in funzione di n: se n = 1 il tempo e una costante, T (1) = K ∈ N. Se n > 1,allora T (n) = T (n

2 ) + K1. svolgendo i conti abbiamo che T (n2 ) = T ( n

22 ) + K1, che sostituito in T (n) daT (n) = T ( n

22 ) + 2K1. Procedendo cosı alla i-esima sostituzione abbiamo che T (n) = T ( n2i ) + iK1. Ora,

n2i = 1, quando i = lg n, quindi dopo i sostituzioni abbiamo T (n) = T (1) + (lg n)K1 ∈ O(lg n). il tempo diesecuzione della chiamata ricorsiva per fare la potenza n-esima e logaritmico nel valore di n.

6

2 Modelli di Calcolo

Per poter studiare gli algoritmi abbiamo bisogno di un modello di calcolo. Quello che si usa di solito e lamacchina a registri, dove oltre ad un dispositivo di input ed uno di output si ha a disposizione un numeroarbitrario di registri ciascuno dei quali puo contenere numeri interi o reali di grandezza arbitaria. Queste sonoassunzioni non realistiche ma semplificano l’analisi. Infatti non e vero che ciascuna singola operazione abbiail medesimo tempo e sia indipendente dalla grandezza dei dati. quando comunque tale criterio sia adottatosi parla di misura di costo uniforme. Il criterio di costo logaritmico tiene conto della dimensione deidati ed il tempo di ogni singola operazione e misurato rispetto alla dimensione dei dati coinvolti. Siccomeogni intero n ∈ N e rappresentabile in base b con dlgb be cifre, si parla di costo logaritmico. Ad esempio,dato n quanto costa calcolare 2n, con il seguente algoritmo?

x<-2for i=1 to n do x<-x*2

Secondo il criterio di costo uniforme tempo O(n) in quanto la moltiplicazione costa 1 ed il for e iterato nvolte. Ma per il costo logaritmico l’analisi e diversa: all’iterazione i-esima x vale 2i. Il tempo speso permoltiplicare x per 2 e lg 2i dato che la moltiplicazione per due e uno shift verso sx, mentre l’incremento dii costa lg i. Quindi il tempo e

n∑i=1

i + lg i,

ovvero compreso tra n(n+1)2 e n(n + 1), cioe Θ(n2).

2.1 La notazione asintotica

La notazione asintotica consente di semplificare l’analisi nel senso che possiamo trascurare le costanti ed itermini di ordine inferiore. Considereremo funzioni da N in R+. Data una funzione f(n) definiamo

O(f(n)) = g(n)|∃c > 0,∃n0 >= 0 tale che g(n) ≤ c · f(n),∀n ≥ n0Ω(f(n)) = g(n)|∃c > 0,∃n0 >= 0 tale che g(n) ≥ c · f(n),∀n ≥ n0Θ(f(n)) = g(n)|∃c1 > 0,∃c2 > 0,∃n0 >= 0 tale che c1 · f(n) ≤ g(n) ≤ c2 · f(n),∀n ≥ n0

Il fatto che g ∈ O(f) ci dice che g cresce al max come f e da questa e dominata (modulo la costantemoltiplicativa); il fatto che g ∈ Ω(f) ci dice che g cresce almeno come f e da questa ne e limitata inferiormente(modulo la costante moltiplicativa);

2.2 Metodi di analisi

Un algoritmo e un metodo che forniti dei dati di ingresso produce dei risultati in uscita. Per produrretali risultati e necessario impiegare delle risorse. Le risorse piu importanti sono il tempo di esecuzione e lamemoria necessaria per svolgere i calcoli. Analizzare un algoritmo che risolve un certo problema significa

7

determinare in funzione di ogni possibile dato di ingresso il numero di passi che compie l’algoritmo o laquantita di memoria usata dall’algoritmo per produrre l’output. Si tratta quindi di scoprire delle funzionidall’insieme dei dati di ingresso ai naturali. Tali funzioni possono essere semplici ed intuitive quando l’insiemedei possibili dati di ingresso e l’insieme dei naturali come nel caso degli algoritmi che risolvono il problemadi fibonacci, ma possono essere complicate quando l’insieme dei possibili dati sono sequenze di interi, comenel caso degli algoritmi di ordinamento. Funzioni di questo tipo sarebbero di difficile interpretazione circal’uso di risorse computazionali da parte degli algoritmi. Quello che si preferisce fare e definire delle funzionidi complessita che esprimano l’uso di risorse in funzione della quantita di informazione fornita in input.

2.2.1 Quantita di Informazione di una Istanza

Per valutare la quantita di informazione fornita in input di definisce prima di tutto la nozione di dimensionedi una istanza, la quale a seconda del problema in esame potra essere il numero di cifre di cui e costituitoun intero, il numero di componenti di un vettore. Nella sua accezione piu stringente per dimensione diuna istanza dobbiamo intendere il numero di simboli che occorrono per scrivere i dati di input. Quindi, aquesto punto valuteremo i tempi di esecuzione di un algoritmo come funzione dalla dimensione delle istanze(cioe da interi) a reali positivi. Ora qui sorge un problema che puo essere visto anche analizzando l’esempiodi fibonacci: istanze diverse, che danno luogo a tempi di esecuzione diversi hanno la medesima dimensionedi istanza, si prenda ad esempio l’istanza n = 120 e n = 999 entrambe di dimensione tre. Come possiamodefinire il tempo o lo spazio di calcolo? Piuttosto che riprendere fibonacci in cui il tempo di esecuzionee in maniera naturale espresso da interi ad interi in quanto l’input e un singolo numero intero, usiamo ilproblema della ricerca di un elemento in una lista.

2.2.2 Ricerca Sequenziale

Prendiamo l’algoritmo di ricerca sequenziale (figura 2.2, pagina 30) e valutiamo il numero di confronti chee l’operazione piu frequente. Vogliamo predire il tempo di esecuzione in funzione della quantita di datipresente nella lista, piuttosto che in funzione dell’istanza, cioe dei dati che compaiono nella lista.

Denotiamo con tempo la funzione che associa ad ogni possibile istanza I il tempo di esecuzione dell’algoritmosu I. Ci sono 3 tipi di analisi:

• caso peggiore: fissata la dimensione dell’istanza, quante operazioni al massimo compiamo?

Tworst(n) = max|I|=n

(tempo(I))

• caso migliore: fissata la dimensione dell’istanza, quante operazioni compiamo nel caso piu favorevole?

Tbest(n) = min|I|=n

(tempo(I))

• caso medio:Tavg(n) =

∑|I|=n

Prob(I) · tempo(I)

8

Facile l’analisi di caso peggiore e migliore, facciamo l’analisi di caso medio: assumiamo che l’elemento xpossa trovarsi in una qualsiasi posizione con la medesima probabilita, quindi

Prob(pos(x) = i) =1n

Quindi

Tavg(n) =n∑

i=1

Prob(pos(x) = i) ∗ i =n∑

i=1

1n∗ i =

n + 12

se x ∈ Lista. Se x 6∈ Lista allora il numero di confronti atteso e n.

Possiamo compiere un’altra analisi di caso medio, assumendo come una distribuzione delle istanze tale cheogni permutazione sia equiprobabile. Ci sono n! possibili permutazioni di n oggetti. Fissata la posizione idi x ci sono (n− 1)! possibili permutazioni aventi x nel posto i, quindi possiamo scrivere:

Tavg(n) =∑n!

π=11n! ∗ (n.ro confronti sulla permutazione π)

per ciascuna delle permutazioni il nro di confronti e una quantita compresa tra 1 e n; riscriviamo la som-matoria raccogliendo i termini rispetto al nro di confronti:

Tavg(n) =∑n

i=1(n−1)!

n! ∗ i

= 1n

∑ni=1 i = n+1

2

2.2.3 Ricerca Binaria

Prendiamo lo pseudocodice per la ricerca binaria in Figura 2.4, pagina 34.

Consideriamo un array di estremi [a, b], dove b− a + 1 = n.

• Caso migliore: x e in posizione a+b2 ;

• Caso peggiore: x viene trovato quando a = b. Dato che dopo un confronto l’array in cui si effettua laricerca ha dimensione n

2 , poi n22 e dopo i confronti n

2i , affinche sia n2i = 1 deve essere i = log2 n. Quindi

Tworst(n) = O(log n).

• caso medio: assumiamo che x ∈ Lista e che possa occupare con la medesima probabilita qualsiasiposizione, allora

Tavg(n) =n∑

pos=1

1n∗ (n.ro confronti per x in posizione pos).

Per valutare questa quantita facciamo una sorta di ragionamento al contrario: quante posizioni con-sentono di trovare x con 1 confronto? una, la posizione centrale. E con 2 confronti? 2, le posizioni1/4 ·n e 3/4 ·n. E con 3 confronti? 4, le posizioni 1/8 ·n, 3/8 ·n, 5/8 ·n, 7/8 ·n. Possiamo andare avanti

9

cosı fino a che i = lg2 n. La costruzione ci dice che per trovare x con i confronti, x puo occupare 2i−1

posizioni diverse. Quindi la sommatoria puo essere riscritta come

Tavg(n) =lg2 n∑i=1

1n∗ i ∗ n.ro posizioni che richiedono i confronti

=1n

lg2 n∑i=1

i · 2i−1 = lg2 n− 1 +1n

.

Si osservi come il tempo medio non si discosti dal tempo peggiore, questo e spiegabile con il fatto che metadegli elementi si comporta come il caso peggiore.

10

3 Statistiche d’Ordine

Il problema da risolvere e il seguente: dati n elementi ed un intero k ∈ 1, . . . , n, trovare il k-esimo elementoquando la sequenza e ordinata (k-esimo piu piccolo o piu grande a seconda dell’ordinamento). La ricercadel mediano avviene quando k = bn

2 c. Due algoritmi sono interessanti:

• uno randomizzato, basato su partition di quicksort;

• uno deterministico.

Partiamo da un problema differente: selezione per piccoli valori di k. La ricerca del minimo puo esserefatta con n− 1 confronti, questo bound e ottimale in quanto se lo facessimo con meno non confronteremmoqualche elemento che puo essere il minimo. Vogliamo generalizzare l’idea alla ricerca del secondo minimoed in generale alla ricerca del k-esimo minimo, con k = O( n

lg n). Esaminiamo il semplice algoritmo per laricerca del secondo minimo, in Figura 5.2, pagina 117. Vale quanto segue

Lemma 3.1 L’algoritmo secondominimo esegue 2n − 3 confronti nel caso peggiore e n + O(lg n) nel casomedio.

D imostrazione:

• Il caso peggiore si verifica quando facciamo 2 confronti per ciascuna delle n − 2 iterazioni, e questoavviene quando il vettore e ordinato in maniera decrescente.

• Per l’analisi di caso medio supponiamo che ogni permutazione del vettore A sia equiprobabile. Ogniiterazione esegue almeno il primo confronto, ma il secondo e eseguito solo se A[i] e il minimo o ilsecondo minimo nei primi i valori di A. Ognuno dei primi i valori puo essere uno dei 2 piu piccoli conprobabilita 2

i . Quindi mediamente il secondo confronto e fatto

n∑i=3

2i

= 2 lg n + O(1)

Sommando gli n confronti fatti alla riga 5 otteniamo n + O(lg n).

Si osservi che 2i viene fuori dalla seguente semplice osservazione: il minimo puo trovarsi in una tra le i

possibili posizioni, il secondo minimo puo trovarsi in una delle restanti i − 1 possibili posizioni quindi lepossibili posizioni in cui trovare primo e secondo minimo sono i(i− 1).

Ora, qual e la probabilita che il minimo o il secondo minimo si trovino in i ? Sono tutti i casi della forma(i, j) e (j, i), con j ∈ 1, . . . , i − 1, cioe 2(i − 1) casi favorevoli sui i(i − 1) casi totali, da cui 2

i . A questopunto, possiamo fare di meglio nel caso peggiore e selezionare il secondo minimo piu efficientemente? Si,l’idea e quella di suddividere gli n elementi in coppie e vedere chi e il minimo in ciascuna coppia. Tali minimivengono di nuovo confrontati a coppie tra di loro e cosı via. Colui che resta e il minimo. Dov’e il secondo

11

minimo? E’ in quelle coppie in cui compare il minimo. Rifacciamo una ricerca di minimo tra gli elementiche occorrono in tali coppie. Questa idea puo essere generalizzata al caso in cui k = O( n

lg n). Volendo ilk-esimo massimo procediamo come segue: rendiamo heap il vettore, e questo e fatto in tempo O(n). Aquesto punto cancelliamo il massimo k volte e dopo ogni cancellazione ripristiniamo la proprieta di heap, equesto e fatto in tempo O(lg n). Cosı complessivamente il tempo e O(n + k lg n). L’algoritmo e il seguente:

Algoritmo Heapselect(array A, intero K)-> elem1. heapify(A)2. for i = 1 to k-1 do3. scambia(a[1],A[N])4. fixheap(A,N-1)5. return A[1]

Si osservi che qualora fosse k = O( nlg n) il tempo e O(n). Ma se applichiamo tale algoritmo alla ricerca del

mediano, ovvero k = dn2 e il tempo e O(n lg n), come un ordinamento.

3.1 Calcolo Randomizzato del Mediano

L’idea fondamentale e la seguente: partizioniamo l’array in 3 regioni,A1, contenente gli elementi piu piccoli del perno,A2 con gli elementi uguali al perno,A3 con gli elementi maggiori del perno. Se gli estremi di A2 includono la posizione che stiamo cercandoabbiamo finito, altrimenti procediamo ricorsivamente su A1 oppure A3 a seconda di quella che occupa laposizione che stiamo cercando.

Si tratta di modificare partition di quicksort (Figura 5.7, pagina 121). La modifica e dettata da ordinidi efficienza e semplicita dell’analisi probabilistica.

Il caso peggiore si verifica (come con quicksort) quando le partizioni sono sbilanciate. In tal caso l’equazionedi ricorrenza e

T (n) = O(n) + T (n− 1)

che ha come soluzione T (n) = O(n2).

Facciamo l’analisi probabilistica: preso il perno x e considerata la partizione degli elementi in due insiemiS1 e S2 tali che S1 contiene tutti gli elementi ≤ x e S2 tutti gli elementi ≥ x, il mediano sta sicuramentenell’insieme piu grande, la cui dimensione e ≥ n

2 . Quindi, a meno di non restituire il mediano nel passoricorsivo dell’algoritmo eliminiamo |A2|+min(|A3|, |A1|) elementi. Si dimostra che il caso della selezione delmediano, cioe k = dn

2 e, e il peggiore, infatti per valori diversi di k la probabilita di eseguire il passo ricorsivosulla partizione piu piccola aumenta. Quando k 6= dn

2 e si puo ottenere una partizione di dimensione piugrande di k ma minore di dn

2 e su cui si effettua la ricorsione, cosa che mai accade se k = dn2 e. Ad ogni passo

eliminiamo un numero di elementi compreso tra 1 e n2 , tale numero e equiprobabile se il vettore ha tutti

elementi diversi e equiprobabile e la scelta tra tutti i possibili x. Se ogni partizione e equiprobabile allora lachiamata ricorsiva avviene in maniera equiprobabile su array che hanno dimensione compresa tra n

2 e n− 1

12

e la probabilita di incorrere su un array di dimensione i ∈ n2 , . . . , n− 1 e

1n− 1− n

2 + 1=

2n

Se l’array ha dimensione n viene partizionato in 3 con n− 1 confronti usando un array di supporto oppurecon 2(n− 1) confronti operando in loco. Quindi il numero di confronti atteso e

C(n) = O(n) + 2n

∑n−1i=n

2C(i), n ≥ 1

C(0) = 0

da cui si dimostra per sostituzione che vale

C(n) ≤ tn, t ∈ N

Base: C(0) = 0 ≤ t · 0;

Induzione:

C(n) = (n− 1) +2n

n−1∑i=n

2

C(i) ≤ per hp induttiva

≤ (n− 1) +2n

n−1∑i=n

2

t · i

≤ (n− 1) +2n· t

n−1∑i=n

2

i

C(n) ≤ (n− 1) +2n· t(

n−1∑i=1

i−

n2−1∑

i=1

i)

≤ (n− 1) +2n· t((n− 1)n

2− (n/2− 1)n/2

2)

≤ (n− 1) + t(3/4n− 1/2)≤ n(3/4t + 1)− 1/2t− 1≤ n(3/4t + 1)≤ tn, per t ≥ 4.

3.2 Calcolo Deterministico del Mediano

L’algoritmo che presentiamo e deterministico nel senso che l’elemento x su cui fare la partizione e sceltoin modo deterministico mediante chiamata ricorsiva. In questo modo si garantisce che il partizionamentobasato su x divide l’array in due parti tali che il mediano puo essere cercato (ricorsivamente) su una frazionedell’array grande al piu la meta. L’idea e di selezionare x in modo che non disti troppo dal mediano cosı dagarantire che ogni chiamata sia, ad esempio, su un array grande al piu 3

4 di quello di input. L’idea si basasul calcolo del mediano dei mediani:

13

1. L’insieme degli elementi e frazionato in tanti gruppi da 5. Si ottengono dn5 e gruppi in cui l’ultimo puo

contenere eventualmente meno di 5 elementi. Abbiamo cosı S1, . . . , Sdn5e gruppi;

2. di ogni gruppo calcoliamo il mediano; facile e veloce perche ci sono solo 5 elementi in ogni gruppo.Chiamiamo tali mediani m1, . . . ,mdn

5e;

3. per chiamata ricorsiva trova il mediano M dei mediani m1, . . . ,mdn5e;

4. usa l’algoritmo quickselect dove l’elemento di partizionamento x vale M .

L’algoritmo e il seguente (Figura 5.10, pagina 125).

Algoritmo select(array A, intero k)->elem1. if (|A|<=10) then2. ordina A3. return k-esimo elemento

4. partiziona A in dn/5e sottoinsiemi di (max) 5 elementi5. for i= 1 to dn/5e do mi mediano di Si

6. M=select(mi|i ∈ [1, dn/5e], dn/10e)7. partiziona A prodotto rispetto a M calcolando:8. A1 = y ∈ A|y < M9. A2 = y ∈ A|y = M10. A3 = y ∈ A|y > M11.if (k ≤ |A1|) then return select (A1, k)12.else if (k > |A1|+ |A2|)13. then return select (A3, k − |A1| − |A2|)14.else return M

E’ facile dimostrare che 6 confronti sono sufficienti per trovare il mediano tra 5 elementi, quindi tutti imediani mi possono essere trovati in 6dn

5 e passi. Il calcolo del mediano dei mediani e fatto per chiamataricorsiva e quindi richiede tempo T (dn

5 e). Il vero problema e sapere su quale dimensione dell’array e fattala chiamata ricorsiva, cioe la dimensione che il partizionamento produce. Nel seguente lemma contiamo glielementi esclusi:

Lemma 3.2 La chiamata ricorsiva al passo 4 e effettuata su al piu 710n + 3 elementi.

D imostrazione: Ad ogni passo dopo aver partizionato scartiamo gli elementi uguali a M piu quelli o piugrandi o piu piccoli. Supponiamo di scartare quelli piu grandi, quanti elementi scartiamo in tutto? Dato cheM e mediano degli mi almeno meta di questi e scartata, e quindi almeno d1

2dn5 ee = d n

10e dato che gli mi sonodn

5 e. Ora, ciascun mi e mediano del proprio gruppo Si di 5 elementi quindi e garantito dalla definizione dimediano che almeno altri due elementi di Si siano maggiori di mi e quindi siano scartati. Cosı quei gruppi Si

tali che mi ≥ M hanno almeno 3 elementi ≥ M che quindi vengono scartati. I gruppi Si con 5 elementi taliche mi ≥ M sono, per quanto osservato sopra, d n

10 − 1e (-1 e dovuto al fatto che l’ultimo gruppo potrebbe

14

non avere 5 elementi). Cosı e garantito che vengano scartati almeno 3n10 − 3 elementi. Con un ragionamento

assolutamente analogo possiamo dimostrare che il medesimo numero di elementi e scartato se la chiamataricorsiva scarta quelli piu piccoli. Se ne deduce che la chiamata ricorsiva e fatta su 7n

10 + 3 elementi.

Theorem 3.3 Nel caso peggiore select esegue O(n) confronti.

D imostrazone: ci vuole tempo 6dn5 e < 6(n

5 +1) per il calcolo degli mi; il mediano dei mediani M e calcolatoper chiamata ricorsiva su dn

5 e elementi, quindi il tempo e T (dn5 e). Per partizionare l’array di n elementi

ci vuole tempo (n − 1). La chiamata ricorsiva per ottenere la soluzione e fatta su 7n10 + 3 elementi, quindi

impiega tempo T ( 710n + 3). Complessivamente i confronti, ovvero il tempo, sono

T (n) ≤ 115

n + T (dn5e) + T (

710

n + 3) + 5

A questo punto per sostituzione si puo dimostrare che T (n) ≤ Kn− 4K.

15

4 Ordinamento

4.1 Bucketsort

Consideriamo di voler ordinare n numeri dell’intervallo [1, . . . , n], e che i numeri possano ripetersi. Allorabasta usare un vettore ausiliario di n componenti in cui contiamo le frequenze e poi riscrivere il vettore deidati sulla base delle frequenze di ciascun intero (vedi algoritmo integersort, figura 4.20, pagina 103).

Tale algoritmo impiega un tempo lineare rispetto al numero di elementi. La dimostrazione e immediata: lalinea 3 consiste nel contare le frequenze ed il tempo e O(n). Dato che la somma dei valori in Y e n, comp-lessivamente il ciclo while viene eseguito n volte(basta osservare che l’operazione di decremento deve essereeffuttuata esattamente n volte. Quindi si ottiene complessivamente O(n). L’algoritmo e immediatamenteadattabile al caso in cui l’intervallo degli interi sia [1, . . . , k]. In tal caso il tempo sara O(n+k), che resta unaquantita lineare se k e dell’ordine di n. Ma se k fosse molto grande, ad esempio nc, con c > 1, l’algoritmoavrebbe complessita O(nc), che se c ≥ 2 significa avere prestazioni peggiori degli algoritmi di ordinamentostandard. Vedremo la soluzione piu avanti.

Se non bisogna ordinare numeri ma record di dati rispetto ad un dato numerico, es. anno di nascita, mesedi nascita, possiamo modificare l’algoritmo integersort in bucketsort come segue:

algoritmo bucketsort(array X, intero k)1. sia n la dimensione di X2. sia Y una array di k liste inizialmente vuote3. for i=1 to n do4. appendi X[i] alla lista Y[X[i].key]5. poni il risultato della concatenazione

delle k liste Y[1],...,Y[k] in X

piuttosto che usare dei contatori usiamo delle liste, dove in ogni lista vengono messi quei record aventila medesima chiave di ordinamento. Dopo aver costruito le liste basta concatenarle con un tempo che eO(n + k).

Si osservi che gli algoritmi descritti NON operano in loco, ovvero hanno bisogno di memoria aggiuntiva oltrea quella dei dati, una caratteristica che non hanno gli algoritmi basati su confronti.

Una caratteristica di bucketsort utile da osservare e la sua stabilita: 2 elementi x[i], x[j] con la medesimachiave e tali che i < j, si troveranno in 2 nuove posizioni x[i′], x[j′], tali che i′ < j′.

4.2 Radixsort

Se k e un numero grande, molto piu grande di n, possiamo considerare le cifre che compongono i numerie applicare bucketsort a ciscuna cifra dei numeri, partendo dalla cifra meno significativa. Radixsort puoessere espresso come segue :

16

algoritmo radixsort (array A, intero nrocifre)1. d=0;2. while (d < nrocifre)3. usa bucketsort per ordinare gli elementi

di A rispetto alla cifra di posto d;4. d++

Se il valore massimo che una chiave puo assumere e k, allora blgb kc + 1 e al piu la quantita di cifre di cuisono composti i numeri da ordinare, dove b rappresenta la base in cui sono espressi i numeri da ordinare;ad esempio, se i numeri da ordinare sono espressi in base 10, il valore massimo che compare nel vettoreda ordinare e 9999, sappiamo che tutti i numeri sono composti da al piu 4 cifre. Quindi lgb k passate dibucketsort sono sufficienti, dove ciascuna passata occupa tempo O(n).

Considerare ciascuna cifra non ci consente di sfruttare bene bucketsort, che comunque impiega tempo almenon, anche se k piccolo. Allora la cosa migliore da fare e scegliere un k pari a n per ciascuna passata dibucketsort, ovvero non scegliere k = 10 (se i numeri fossero rappresentati in base 10, cioe con le cifre0,1,2,. . . ,9) per 1 passata di bucketsort, ma k uguale a n, tanto il tempo resta sempre O(n), ma possiamorisparmiare passate. Questo significa dire che piuttosto che prendere una cifra ne prendiamo lg10 n = |n|.Cosı se k = nc, ovvero |k| = c lg10 n, invocando bucketsort considerando lg10 n cifre faremo c invocazioni, edil tempo restera O(n).

17

5 Tecniche Algoritmiche

Sono tre le principali tecniche per la progettazione di algoritmi. La tecnica divide et impera, che consistenel dividere l’istanza del problema da risolvere in sottoistanze le quali vengono risolte ricorsivamente e le cuisoluzioni sono ricombinate per ottenere la soluzione dell’istanza. E’ una tecnica top-down nel senso che siparte dall’istanza generale e si divide in istanze piu piccole. La programmazione dinamica, che si basasulla filosofia bottom-up. Si procede dai sottoproblemi piu piccoli verso quelli piu grandi. E’ una tecnica utilequando le sottoistanze non sono una indipendente dall’altra ed una stessa sottoistanza dell’istanza originariapuo comparire piu volte. Le soluzioni delle sottoistanze sono memorizzate in una tabella cosı qualora lamedesima sottoistanza dovesse essere reincontrata sara sufficiente esaminare l’elemento della tabella che necontiene la soluzione. La tecnica greedy, che costruisce la soluzione applicando di volta in volta la sceltalocalmente piu promettente. Molti problemi di ottimizzazione ammettono algoritmi greedy ottimali.

5.1 Tecnica Divide et Impera

Lo sforzo del progettista consiste nell’individuare sia come dividere il problema sia (ma soprattutto) comericombinare le soluzioni parziali. Prendiamo l’esempio della moltiplicazione di interi di grandezza arbitraria,la moltiplicazione di numeri che non stanno in una cella di memoria non puo essere considerata a tempocostante.

Presi 2 numeri di n cifre X = xn−1 . . . x0 e Y = yn−1 . . . y0 entrambi di n cifre, la moltiplicazione prendetempo O(n2), dove la moltiplicazione di 2 cifre prende tempo costante. Supponiamo per semplicita che nsia potenza di 2 e suddividiamo ciascun numero in 2 gruppi di n

2 cifre:

X = X110n2 + X0

Y = Y110n2 + Y0

ovvero, X0 = xn2−1 . . . x0, X1 = xn . . . xn

2, Y0 = yn

2−1 . . . y0, Y1 = yn . . . yn

2. Cosı

XY = (X110n2 + X0)(Y110

n2 + Y0)

= (X1Y110n) + X1Y010n2 + X0Y110

n2 + X0Y0

= 10n(X1Y1) + 10n2 (X1Y0 + X0Y1) + (X0Y0)

Si osservi come le moltiplicazioni tra parentesi siano quelle del doppio prodotto (X1 + X0)(Y0 + Y1) =X1Y1 + X0Y1 + X1Y0 + X0Y0, da cui

(X1 + X0)(Y0 + Y1)−X1Y1 −X0Y0 = X0Y1 + X1Y0

Tutto questo ci dice che con i 3 prodotti (X1 + X0)(Y0 + Y1), X1Y1 e X0Y0 possiamo calcolare XY come

10n(X1Y1) + 10n2 ((X1 + X0)(Y0 + Y1)−X1Y1 −X0Y0) + (X0Y0)

dove questi 3 prodotti sono tra numeri aventi al piu n2 + 1 cifre.

18

Per semplicita nell’analisi seguente consideriamo i numeri su cui si fanno le moltiplicazioni di n2 cifre in

quanto l’analisi e asintotica. L’espressione data sopra dice che il tempo per moltiplicare 2 numeri di n cifreequivale al tempo per fare 3 moltiplicazioni tra numeri di n

2 cifre piu il tempo di fare somme e shift (lemoltiplicazioni per 10) di numeri a n cifre, quindi il tempo e:

T (n) = 3T (n2 ) + K2(n), n > 1

T (1) = K1 ∈ N

Srotolando la ricorrenza otteniamo

T (n) = 3kT (1) + K2n + K2n

2+ · · ·+ K2

n

2k

con k = lg2 n, da cui

T (n) = 3lg2 nK1 + K2n

lg2 n∑i=0

12i

= O(nlg2 3)

5.2 La Programmazione Dinamica

La tecnica algoritmica Programmazione dinamica, prende nome dal fatto che si basa su una tabella(mono o pluridimensionale) la quale memorizza le soluzioni dei sottoproblemi del problema originario e taletabella viene compilata o meglio programmata dinamicamente, a run-time. E’ una tecnica bottom up inquanto la tabella e compilata partendo dai sottoproblemi piu semplici, cioe dai casi base e passando poia sottoproblemi piu difficili combinando in maniera opportuna le soluzioni dei problemi piu semplici perottenere quelle dei problemi piu difficili. In opposizione, la tecnica top-down affronta l’istanza del problemagenerale e la divide man mano in sottoistanze piu piccole. La tecnica di programmazione dinamica procedecome segue:

1. si identificano i sottoproblemi del problema originario e si utilizza una tabella per memorizzare lesoluzioni dei sottoproblemi;

2. si definiscono i valori iniziali della tabella relativi ai problemi piu semplici;

3. si avanza nella tabella calcolando il valore della soluzione di un sottoproblema (cioe un entry dellatabella) in funzione dei valori delle soluzioni dei sottoproblemi gia risolti;

4. si restituisce la soluzione del problema originario.

5.2.1 Associativita del prodotto tra matrici

Di seguito ci occupiamo della moltiplicazione di matrici. E’ noto che M1M2 = M puo essere fatto se ilnumero di colonne di M1 e uguale al numero di righe di M2 e la matrice M ha il numero di righe diM1 ed il numero di colonne di M2. Il prodotto di matrici e associativo ma non commutativo. Di seguito

19

considereremo unitario il tempo per fare una moltiplicazione ed una somma. Date le n matrici M1M2 . . .Mn

dove la matrice i-esima ha dimensione li × li+1 qual e il modo di associarle cosı da minimizzare il numerodi operazioni di moltiplicazione? Il modo di associare le matrici influenza il modo in cui operiamo. Adesempio, siano M1(10, 20), M2(20, 30), M3(30, 2). E’ facile verificare che il numero di moltiplicazioni variadi molto a seconda che si faccia M1(M2M3) o (M1M2)M3. Torniamo al problema con n matrici. Indichiamocon P (i, j) il sottoproblema che consiste nel moltiplicare le matrici Mi . . .Mj . Quindi il problema originarioe P (1, n). Abbiamo che

1. I sottoproblemi che dobbiamo risolvere sono i P (i, j) con i ≤ j; il costo ottimo lo memorizziamo inuna matrice C bidimensionale, che risulta una triangolare superiore, nell’entry (i, j);

2. i sottoproblemi del tipo P (i, i), i = 1, . . . , n, sono banali perche ci sono 0 moltiplicazioni, quindiC[i, i] = 0;

3. la soluzione al problema M1M2 . . .Mn sta in C[1, n];

Dobbiamo specificare come calcoliamo il valore di C[i, j] associato al problema Mi . . .Mj in funzione deisottoproblemi piu piccoli gia risolti cioe gia sapendo come associare prodotti di un numero di matrici inferioria j − i + 1, in particolare sapendo come associare in modo ottimo prodotti di sequenze di matrici del tipoMi . . .Mr e Mr . . .Mj . Per fare questo dobbiamo tentare tutti i possibili valori di r e vedere quale di questiproduce il minimo di

C[i, r] + C[r + 1, j] + lilr+1lj

cioe porremoC[i, j] = min

i≤r≤j−1C[i, r] + C[r + 1, j] + lilr+1lj

Si tratta quindi di compilare in maniera sistematica gli entry della matrice, partendo dai problemi con unamatrice (casi base), passando con quei problemi con due matrici, poi a quelli con 3 etc. Questo significacompilare la matrice muovendosi per diagonali a partire da quella principale e poi salendo via via su quelleparallele. Quello che si ottiene e l’algoritmo di pagina 252 riportato qui di seguito.

Algoritmo OrdineMatrici(l1,l2,...,ln+1)

1. matrice C di n x n interi2. for i= 1 to n do C[i,i]=0;3. for d= 1 to (n-1) do4. for i= 1 to (n-d) do5. j=d+i;

6. C[i,j]=C[i,i]+C[i+1,j]+lili+1lj

7. for r=i+1 to (j-1) do

8. C[i,j]=minC[i,j],C[i,r]+C[r+1,j]+lilr+1lj9. return C[1,n]

20

Theorem 5.1 L’algoritmo ordinematrici richiede tempo O(n3), dove n e il numero di matrici.

D imostrazione: nella diagonale d, 1 ≤ d ≤ n−2 ci sono n−d elementi e per ciascuno di essi, che rappresentaun problema di moltiplicazione di d + 1 matrici, ci sono d− 1 possibilita (i possibili valori di r sono d− 1).Otteniamo quindi la seguente serie di sommatorie:

T (n) =n−1∑d=1

n−d∑i=1

d+i−1∑r=i

1

=n−1∑d=1

n−d∑i=1

d

=n−1∑d=1

d(n− d + 1)

=n−1∑d=1

dn−n−1∑d=1

d +n−1∑d=1

1

= n(n− 1)n

2− (n− 1)n

2+ n

= O(n3)

Si osservi come sia notevolmente piu lento un algoritmo di tipo divide et impera in cui presa l’istanzaMi . . .Mj per ogni r = 1, . . . , j − 1 faccia una chiamata ricorsiva su Mi . . .Mr e Mr+1 . . .Mj per trovarela partizione ottima e poi decide quale r e il migliore per partizionare Mi . . .Mj . Molti sottoproblemi diMi . . .Mr e Mr+1 . . .Mj verrebebro risolti piu volte! Si osservi che se dato Mi . . .Mj la partizione ottima e

(Mi . . .Mr)(Mr+1 . . .Mj)

allora anche le due partizioni devono essere parentesizzate ottimamente, altrimenti non potrebbe esserlo(Mi . . .Mr)(Mr+1 . . .Mj). Questo significa che il problema dell’associativita del prodotto di matrici verificail principio della sottostruttura ottima: se la soluzione ad un problema e ottima allora anche le soluzioni aisottoproblemi sono ottime.

5.3 Knapsack

Il problema dello zaino e il seguente: si ha a disposizione uno zaino di capacita C nel quale si voglionomettere degli oggetti, ciascun tipo di oggetto ha un peso ed un valore. Il problema e di massimizzare ilvalore posto nello zaino senza superare il peso C che lo zaino in tutto puo trasportare. Di ogni tipo dioggetto sono disponibili un numero illimitato di copie.

21

Per scrivere un algoritmo che risolve il problema osserviamo che se per ciascun tipo di oggetto i conosco ilvalore della soluzione ottima del problema dello zaino quando la capacita e C − peso(i) (C − peso(i) ≥ 0)allora posso calcolare il valore della soluzione ottima del problema dello zaino con capacita C vedendo perogni oggetto i qual e quello che aggiunto allo zaino ne massimizza il valore. Piu formalmente potremmo direche date le soluzioni ottime ott(1), . . . , ott(n) ai problemi con zaini di capacita C − peso(1), . . . , C − peso(n)aggiungiamo allo zaino quell’oggetto j tale che ott(j) + valore(j) = maxi=1,...,n(ott(i) + valore(i)). Unaprima soluzione a questa idea potrebbe essere la seguente:

zaino(intero capacita, array peso, array valore)-> intero1. if capacita <= 0 return 02. else

3. max <- 0;4. for(i <- 0; i<n; i++)5. 6. if ( capacita-peso[i] >= 0 )

ris=zaino(capacita-peso(i),peso, valore)+valore[i];

7. if (ris > max ) max=ris

8. 9. return max10.

Questo algoritmo ricalcola piu volte la soluzione al medesimo problema. Cosı il tempo e esponenziale rispettoal valore di capacita e al numero di oggetti. Una analisi delle chiamate ricorsive dell’algoritmo evidenziacome il medesimo sottoproblema possa essere risolto piu volte. Per ridurre il numero di chiamate dobbiamomemorizzare il valore delle soluzioni ottime mano a mano che le troviamo cosı da evitare delle chiamateinutili. Siccome i problemi differiscono tra loro per il diverso valore di capacita introduciamo un vettore diC + 1 celle, una cella per ogni possibile valore che la capacita dello zaino puo assumere nei sottoproblemidel problema originario.

zaino2(intero capacita, array peso, array valore,array soluzioneottima)->intero

if (soluzioneottima[capacita] <> -1 )

return soluzioneottima[capacita]else

max=0for(i <- 1; i <= nroOgg ; i++)

22

if (capacita-peso[i]>=0)

ris=zaino2(capacita-peso[i],peso,valore,soluzioneottima)+valore[i]

if (ris > max) max=ris

soluzioneottima[capacita]=maxreturn max

Possiamo apportare un’altra modifica all’algoritmo procedendo bottom-up, cioe cercare di compilare il vet-tore delle capacita dalle capacita piu piccole alle capacita piu grandi. Se abbiamo il problema dello zainocon capacita C e gia abbiamo le soluzioni per tutte le capacita piu piccole di C non c’e bisogno di farechiamate ricorsive per risolvere i sottoproblemi per zaini di capacita C−peso(i), per i = 1, . . . , n, basta fareun ciclo su i che va da 1 a n perche il valore ottimo per il problema C − peso(i) gia l’abbiamo. Il passo basedel problema e ovviamente per lo zaino di capacita uguale a zero, il cui ottimo e zero.

zaino3(capacita, array peso, array valore, array soluzioneottima)

for c <- 1 to capacita do

max <- 0for i <- 1 to n do

if ( c-peso(i)>=0)if (max < soluzioneottima[c-peso[i]]+valore[i])

max <- soluzioneottima[c-peso[i]]+valore[i]soluzioneottima[c]=max;

Differente e l’idea se abbiamo uno zaino di capacita C ed n tipi di oggetti 1, . . . , n, ciascuno con un pesop(1), . . . , p(n) ed un valore v(1), . . . , v(n), ma di ogni oggetto abbiamo solo una copia, quindi nella soluzioneottima ciascun oggetto o compare, o non compare. Se l’oggetto 1 compare nella soluzione ottima, allorala soluzione senza l’oggetto 1 e ottima per il problema con uno zaino di capacita C − p(1) e n − 1 tipi dioggetti, 2, . . . , n, ciascuno con un peso p(2), . . . , p(n) ed un valore v(2), . . . , v(n); se l’oggetto 1 non comparenella soluzione ottima allora la soluzione e uguale alla soluzione ottima per il problema con uno zaino dicapacita C e n − 1 tipi di oggetti 2, . . . , n, ciascuno con un peso p(2), . . . , p(n) ed un valore v(2), . . . , v(n).Se il primo oggetto appartiene alla soluzione ottima, allora la soluzione senza tale oggetto e soluzione ottimadel problema senza tale oggetto con uno zaino che ha capacita diminuita del peso dell’oggetto; se l’oggettonon appartiene alla soluzione ottima, allora basta risolvere il problema in cui l’oggetto non e presente.

23

Una prima soluzione che non usa la programmazione dinamica e la seguente:

zaino4(intero capacita,array peso,array valore,intero lastobj)-> interoif (capacita <= 0 || lastobj<0) return 0else

ris1=zaino4(capacita, peso, valore, lastobj-1)ris2=zaino4(capacita-peso[lastobj],peso,valore,lastobj-1)

+valore[lastobj]if ris1 > ris2 return ris1else return ris2

Questa soluzione soffre comunque del fatto che il medesimo problema puo essere sottoproblema di piuproblemi e quindi risolto piu volte, come indica una facile analisi delle chiamate ricorsive. Cio che distingueun problema dai suoi sottoproblemi sono gli oggetti presenti e la capacita dello zaino. Possiamo quindiutilizzare una matrice che ha tante colonne quanti sono gli oggetti nell’istanza del problema e tante righequanto e il valore della capacita dello zaino e nella posizione di indice (j, i) l’ottimo del sottoproblema la cuiistanza ha i primi i oggetti dell’istanza del problema originario ed uno zaino di capacita j.

zaino5(intero capacita, array peso, array valore,intero lastobj, matrice soluzioneottima)-> intero

if (capacita <= 0 || lastobj<0) return 0else

if (soluzioneottima[capacita,lastobj-1]==-1)ris1=zaino5(capacita, peso, valore,

lastobj-1, soluzioneottima)else ris1=soluzioneottima[capacita,lastobj-1]if (soluzioneottima[capacita-peso[lastobj],lastobj-1]==-1)

ris2=zaino4(capacita-peso[lastobj], peso, valore,lastobj-1, soluzioneottima)+valore[lastobj]

else ris2=soluzioneottima[capacita-peso[lastobj],lastobj-1]+valore[lastobj]

if (ris1 > ris2) soluzioneottima[capacita,lastobj]=ris1else soluzioneottima[capacita,lastobj]=ris2return soluzioneottima[capacita,lastobj];

24

5.4 Longest Common Subsequence (LCS)

Data una sequenza di elementi una sua sottosequenza e ottenuta privando la sequenza di un numero qualsiasidi elementi. Ad esempio le parole sono sequenze di lettere e una sottosequenza di “MAGGIO” e “MGG”.Formalmente, date due sequenze X = 〈x1, . . . , xn〉 e Z = 〈z1, . . . , zk〉 diremo che Z e sottosequenza di Xse esiste una sequenza di indici di X 〈i1, . . . ik〉 strettamente crescente e tale che per ogni j = 1, . . . , k,Xij = Zj . Date due sequenze X e Y , Z e sottosequenza comune di X e Y se Z e sottosequenza sia di X chesi Y . Nel problema di trovare la sottosequenza piu lunga ci vengono date due sequenze X = 〈x1, . . . , xm〉 eY = 〈y1, . . . , yn〉 e dobbiamo trovare la sottosequenza comune piu lunga. Vediamo come possiamo risolvereil problema usando la programmazione dinamica. Innanzitutto e immediato vedere che un algoritmo a forzabruta che enumeri tutte le sottosequenze di X e vede se sono anche sottosequenze di Y e impraticabile inquanto dato X = 〈x1, . . . , xm〉 le sue sottosequenze sono tutti i sottoinsiemi di X cioe 2m. Comunque laprogrammazione dinamica e applicabile se vale il principio della sottostruttura ottima. Dimostriamo taleproprieta nel seguente teorema:

Theorem 5.2 Siano X = 〈x1, . . . , xm〉 e Y = 〈y1, . . . , yn〉 due sequenze e Z = 〈z1, . . . , zk〉 una LCS di X eY . Allora vale quanto segue:

1. se xm = yn allora deve essere zk = xm = yn e 〈z1, . . . , zk−1〉 e LCS di 〈x1, . . . , xm−1〉 e 〈y1, . . . , yn−1〉;

2. se xm 6= yn allora se zk 6= xm allora Z e LCS di 〈x1, . . . , xm−1〉 e Y ;

3. se xm 6= yn allora se zk 6= yn allora Z e LCS di X e 〈y1, . . . , yn−1〉.

D imostrazione:

1. per hp e xm = yn, allora se per assurdo fosse zk 6= xm ( e quindi zk 6= yn), allora Z potrebbe essereallungata aggiungendo xm e troveremmo una nuova sottosequenza comune tra X e Y piu lunga di Z,contro l’hp del teorema che dice che Z e LCS. Quindi deve essere zk = xm(= yn). A questo punto〈z1, . . . , zk−1〉 e LCS di 〈x1, . . . , xm−1〉 e 〈y1, . . . , yn−1〉 perche se esistesse un LCS W di lunghezzamaggiore di k − 1, allora attaccando a W l’elemento xm(= yn) otterremmo un LCS di lunghezzamaggiore di k per X e Y , contro l’hp del th che dice che Z, di lunghezza k, e LCS di X e Y ;

2. per hp e xm 6= yn e zk 6= xm, allora i k elementi comuni a X e Y si trovano in 〈x1, . . . , xm−1〉 eY = 〈y1, . . . , yn〉. D’altronde non puo esistere in 〈x1, . . . , xm−1〉 e Y = 〈y1, . . . , yn〉 una sottosequenzaW con piu di k elementi, altrimenti essa sarebbe anche sottosequenza di X e Y e Z di k elementi nonsarebbe LCS di X e Y . Cosı Z e una LCS di 〈x1, . . . , xm−1〉 e Y .

3. simmetrico al punto precedente.

25

Il teorema precedente ci dice come analizzare i sottoproblemi per ottenere la soluzione al problema dato:

1. se xm = yn allora cerchiamo un LCS di 〈x1, . . . , xm−1〉 e 〈y1, . . . , yn−1〉 e una volta trovata l’allunghiamocon xm;

2. se xm 6= yn cerchiamo un LCS di 〈x1, . . . , xm−1〉 e Y , e un LCS di X e 〈y1, . . . , yn−1〉, e prendiamo asoluzione migliore la quale e anche quella per X e Y .

E’ facile rendersi conto che molti sottoproblemi si sovrappongono. Ovviamente se una delle due sequenze halunghezza 0 allora la LCS ha lunghezza 0. Questo e il caso base. Possiamo introdurre una matrice C[m×n]tale che C[i, j] e il valore della LCS nel caso 〈x1, . . . , xi〉 e 〈y1, . . . , yj〉. Per quanto detto vale che

1. C[0, t] = 0, per t = 0, . . . , n;

2. C[t, 0] = 0, per t = 0, . . . ,m;

3. se i, j > 0, C[i, j] =

C[i− 1, j − 1] + 1, se xi = yj

maxC[i, j − 1], C[i− 1, j], altrimenti

Quindi un primo algoritmo risolutivo computa la matrice procedendo ricorsivamente top-down. Possiamorisparmiare le chiamate ricorsive e procedere nella compilazione della matrice secondo uno schema bottomup tenendo conto che la prima riga e la prima colonna valgono zero. Un’ulteriore analisi dei valori da porrenelle celle C[i, j], se i, j > 0 mostra che possiamo ottenere la risposta facendo uso di una matrice di sole duerighe.

Nel seguente algoritmo X ha m + 1 componenti,Y ha n + 1 componenti, C e la matrice calcolata e in C[m,n]si trova LCS(X,Y).

Algoritmo LCS(array X, array Y, intero m, intero n, matrice C)1. for i= 1 to m do c[i,0]=0;2. for i= 0 to n do c[0,j]=0;3. for i= 1 to m do4. for j= 1 to n do5. if (x[i]=y[j]) then c[i,j]=c[i-1,j-1]+16. else if (c[i-1,j]>=c[i,j-])7. then c[i,j]=c[i-1,j]8. else c[i,j]=c[i,j-1]

Nel seguente algoritmo la matrice C ha due righe, quella di indice 0 e quella di indice 1. Le colonne sono n.

Algoritmo LCS2(array X, array Y, intero m, intero n, matrice C)1. for j= 0 to n do c[0,j]=0;3. for i= 1 to m do

26

c[i%2,0]=04. for j= 1 to n do5. if (x[i]=y[j]) then c[i%2,j]=c[(i-1)%2,j-1]+16. else if (c[(i-1) % 2,j]>=c[i%2,j-])7. then c[i%2,j]=c[(i-1)%2,j]8. else c[i%2,j]=c[i%2,j-1]

Invece di una matrice possiamo usare un vettore e 2 variabili...

27

6 Grafi

Un grafo G e una coppia (V,E) dove V e un insieme non vuoto di oggetti e E ⊆ V 2. Se per ogni (x, y) ∈ Evale (y, x) ∈ E si parla di grafo non orientato, altrimenti il grafo si considera orientato. Dato (x, y) ∈ Ediremo che (x, y) incide sui vertici x e y. Per grafi non orientati si dice che x e y sono adiacenti. Uncammino in un grafo G da un vertice x ad un vertice y e una sequenza di vertici (v0, v1, . . . , vu) dove v0 = x,vu = y e (vi−1, vi) ∈ E. In tal caso il cammino passa per i vertici v0, . . . , vu e gli archi (vi−1, vi). Il camminoe semplice se i vertici sono distinti. Un cammino che inizia e finisce nello stesso nodo e un ciclo. Il ciclo esemplice se i nodi intermedi del cammino sono tutti distinti tra loro. Un grafo non orientato e connessose esiste un cammino tra ogni coppia di nodi del grafo. Un grafo orientato e fortemente connesso se esisteun cammino orientato tra ogni coppia di vertici del grafo.

6.1 Rappresentare i grafi

• Lista di archi: gli archi del grafo vengono elencati in un vettore o in un lista. Ogni componentedel vettore o della lista rappresenta un arco, contiene quindi i (puntatori ai) nodi estremi dell’arco.Talune manipolazioni o algoritmi richiedono la scansione dell’intera lista, compromettendo talvoltal’efficienza.

• Lista di adiacenza: una delle strutture dati piu utilizzata per i grafi. Per ogni nodo vi e una lista cheelenca i nodi a lui adiacenti. Si osservi che in tale rappresentazione gli archi sono implicitamentecodificati. Efficiente per visite di grafi.

• Liste di incidenza: si elencano gli archi in una struttura, come nel primo caso, ed inoltre per ogninodo v si mantiene una lista che elenca gli archi incidenti su v.

• matrice di adiacenza: matrice M di dimensione |V |x|V |, indicizzata dai nodi del grafo, tale cheM [x, y] = 1 se (x, y) ∈ E, M [x, y] = 0 altrimenti. Permette la verifica dell’esistenza di un arcotra coppie di nodi in tempo costante, ma stabilire chi sono i vicini di un nodo comporta un tempoproporzionale a |V |. Rappresentazione utile per calcoli algebrici. Infatti dato che codifica cammini dilunghezza 1 tra i nodi, per trovare nodi a distanza 2 basta moltiplicare la matrice per se stessa, e cosi’via per trovare nodi connessi tra loro con cammini di lunghezza 3, 4 etc.

• matrice di incidenza: matrice M di dimensione |V |x|E|, dove le righe sono indicizzate dai nodi, lecolonne dagli archi. M [i, j] = 1 se l’arco indicizzato da j incide sul nodo indicizzato da i. Per grafiorientati si possono usare +1 e −1 per distinguere nodo sorgenete e nodo destinazione dell’arco inquestione.

6.2 Visite di Grafi

Visitare un grafo significa seguirne sistematicamente gli archi in modo da visitarne i nodi. Sia G = (V,E)un grafo. Le seguenti sono carattristiche comuni per tutte le visite dei grafi:

28

• Le visite costruiscono un albero, che indicheremo con T , dei nodi visitati. I nodi di T sono unsottoinsieme di V .

• vi e un insieme di nodi F ⊆ nei nodi di T che viene detto frangia di T. Tale frangia sono in praticale foglie di T .

• Gli algoritmi di visita si distinguono per la politica che adottano nel considerare i nodi inseriti/estrattidalla frangia (l’ordine di visita dei nodi).

6.2.1 Visita generica

Quando visitiamo un grafo dobiamo prestare attenzione a non cadere in cicli infiniti a causa del fatto chevisitiamo piu volte lo stesso nodo. Il problema viene evitato introducendo un bit di marcatura. Riportiamol’algoritmo di pagina 275.

Algoritmo Visita Generica(grafo G, vertice s)-> albero1. Rendi tutti i nodi non marcati;2. Sia T l’albero formato dal solo nodo s;3. Sia F l’insieme vuoto;4. marca il vertice s e aggiungi s a F5. while (F non e’ vuoto ) do6. estrai da F un qualsiasi vertice u;7. visita il vertice u;8. for each ( arco (u,v) di G ) do9. if (v non e’ marcato) then10. marca v e aggiungilo a F;11. rendi u padre di v in T;12. else <eventuali operazioni dipendenti

dallo specifico tipo di visita>13. return T

Prima di tutto l’algoritmo termina perche la prima volta che un nodo viene inserito in F viene marcatoe solo i nodi non marcati venmgono inseriti in F. Il tempo di marcatura complessivamente e lineare nelnumero di nodi del grafo, considerando che una singola marcatura costi tempo costante; Per ogni nodoestratto dalla frangia F occorre generare tutti i suoi vicini. L’efficienza di questa operazione dipende dallarappresentazione scelta. Si osservi come :

• nel caso di rappresentazione con liste di adiacenza o incidenza il tempo dipenda complessivamente dalnumero di archi del grafo;

• nel caso di rappresenzazione mediante lista di archi, per ogni nodo del grafo gli archi del grafo venganoscanditi tutti;

29

• nel caso di rappresentazione mediante matrice di adiacenza, per ogni nodo la riga nella matrice cor-rispondente debba essere scandita interamente.

6.2.2 Visita in ampiezza

Consideriamo un grafo G = (V,E) non orientato. Visitare in ampiezza un grafo G a partire da un nodosorgente s significa adattare la visita generica in modo tale che la frangia F in cui vengono messi/estratti inodi sia gestita come una struttura dati coda. L’albero di visita T che si ottiene (detto BFS da breadth-firstsearch) ha la proprieta che ogni suo nodo e il piu vicino possibile alla radice. Riportiamo l’algoritmo apagina 280

Algoritmo VisitaBFS(grafo G, vertice s)-> albero1. Rendi tutti i nodi non marcati;2. Sia T l’albero formato dal solo nodo s;3. Sia F l’insieme vuoto;4. marca il vertice s5. aggiungi s in coda a F6. while (F non e’ vuoto ) do7. estrai da F il primo vertice u;8. visita il vertice u;9. for each ( arco (u,v) di G ) do10. if (v non e’ marcato) then11. marca v12 aggiungilo in coda a F;12. rendi u padre di v in T;13. return T

6.2.3 Visita in profondita

Consideriamo un grafo G = (V,E) non orientato. Visitare in profondita un grafo G a partire da un nodosorgente s significa adattare la visita generica in modo tale che la frangia F in cui vengono messi/estrattii nodi sia gestita come una struttura dati pila (stack). L’albero di visita T che si ottiene e detto DFS dadepth-first search. La visita in profondita e un adattamento della visita in preordine di alberi binari. Quibisogna tener conto del fatto che ci possono essere cicli tra nodi e che un nodo puo avere piu successori.Vediamo due versioni: una ricorsiva ed una iterativa. Riportiamo l’algoritmo a pagina 283.

Algoritmo VisitaDFSRicorsiva(grafo G, vertice v, albero T)1. Marca e visita il vertice v;2. Per ogni arco (v,w) in G esegui:3. if (w non e marcato) then4. aggiungi l’arco (v,w) a T

30

5. VisitaDFSRicorsiva(grafo G, vertice w, albero T)

Algoritmo visitaDFS(grafo G, vertice s)6. Sia T l’albero vuoto;7. VisitaDFSRicorsiva(grafo G, vertice v, albero T);13. return T

Di seguito diamo la versione iterativa:

Algoritmo VisitaDFS(grafo G, vertice s)-> albero1. Rendi tutti i nodi non marcati;2. Sia T l’albero formato dal solo nodo s;3. Sia F l’insieme vuoto;4. marca il vertice s5. aggiungi s in coda a F6. while (F non e’ vuoto ) do7. estrai da F il primo vertice u;8. visita il vertice u;9. for each ( arco (u,v) di G ) do10. if (v non e’ marcato) then11. marca v12 aggiungilo in testa a F;12. rendi u padre di v in T;13. return T

31