Appunti per il Modulo di Algoritmi e Struture Dati Guido ... · nel corso gli algoritmi verranno...
102
Appunti per il Modulo di Algoritmi e Struture Dati Guido Fiorino Ultima Versione: 22 marzo 2011
Transcript of Appunti per il Modulo di Algoritmi e Struture Dati Guido ... · nel corso gli algoritmi verranno...
Appunti per il Modulo di
Algoritmi e Struture Dati
Guido Fiorino
Ultima Versione: 22 marzo 2011
0 Presentazione
0.1 Programma del corso
• Un esempio introduttivo
• Cenni ai modelli di calcolo e alle metodologie di analisi
• Complessita degli algoritmi di ordinamento
• Complessita degli algoritmi di selezione e statistiche d’ordine
• (polinomi e trasfomata di Fourier)
• Tecnica divide et impera
• Programmazione dinamica
• Tecnica greedy
• (Branch and Bound)
• 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.
2
0.4 Altro
• Ricevimento: contattarmi via email;
• questi appunti: http://web-nuovo.dimequant.unimib.it/~guidofiorino/
3
1 Un esempio introduttivo
• nel corso gli algoritmi verranno principalmente scritti in pseudocodice. La codifica in un reale linguag-gio di programmazione, C o JAVA, sara quindi in subordine e servira solo per concretezza.
• Ci occupiamo di progettare algoritmi e di analizzarli matematicamente, cosa diversa dal condurreanalisi sperimentali;
• L’analisi e preferibile perche ci da risposte su tutti i casi possibili, cioe permette di predire il com-portamento di un algoritmo per ogni possibile dato di ingresso e permette di scegliere tra 2 algoritmianche senza averli implementati.
• Piuttosto che discutere astrattamente il significato delle affermazioni precedenti, per amore di concre-tezza consideriamo un problema molto semplice.
1.1 Numeri di Fibonacci
• Come si espande una popolazione di conigli a partire da una singola coppia sotto le seguenti ipotesisemplificatrici: 1) una coppia di conigli genera una coppia di conigli all’anno; 2) i conigli nel primoanno non si riproducono; 3) i conigli sono immortali;
• in base a quanto detto possiamo graficamente rappresentare il numero conigli con un albero; e chiaroche nell’anno t abbiamo tutte le coppie di conigli presenti nell’anno t − 1, infatti nessuno e morto;inoltre tutte le coppie presenti nell’anno t − 2 hanno figliato una coppia di conigli. 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 funzionedefinita 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+√
52 )n e (1−
√5
2 )n hanno il medesimo andamento di F (n) nessuna di loro due eF (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).
4
• Siccome una qualunque combinazione lineare di funzioni che soddisfano la ricorrenza di fibonacci,soddisfa anch’essa la ricorrenza cerchiamo di ricavare una funzione
G(n) = c1
(1 +√
52
)n+ c2
(1−√
52
)ncombinazione lineare delle 2 trovate e che soddisfi anche il passo base, ovvero G(1) = 1, G(2) = 1.Impostiamo il sistema cosi’ da scoprire quanto devono valere c1, c2
c1(1+
√5
2 )1 + c2(1−√
52 )1 = 1
c1(1+√
52 )2 + c2(1−
√5
2 )2 = 1
Questo e un sistema in 2 equazioni e 2 incognite che risolto da
c1 =1√5, c2 = − 1√
5
Abbiamo quindi la nostra funzione G(n) = F (n), ovvero abbiamo scoperto l’andamento analitico di F (n):
F (n) =1√5
((1 +√
52
)n−
(1−√
52
)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).
Esercizio. provare per credere: scrivete un programma C per l’algoritmo, scegliete le variabili di tipodouble o long double.
1.2 Algoritmo ricorsivo
• Piuttosto che usare la versione analitica di F (n), usiamo la sua definizione ricorsiva e scriviamo unalgoritmo ricorsivo per calcolare F (n) come quello in figura 1.4, pagina 6 (fibonacci2).
• Ma quanto tempo ci vuole ad eseguire questo algoritmo in funzione del valore di ingresso?
• Prima di tutto stabiliamo cosa e per noi il tempo. Scegliere una grandezza come i secondi non va benein quanto con il cambiare della tecnologia il medesimo codice eseguito su una macchina nuova impiegadi meno.
• per noi il tempo impiegato sara in prima approssimazine il numero di righe di codice eseguite doveassumeremo che ciascuna riga possa essere eseguita sempre con il medesimo tempo e che questo siacostante.
5
• Valutiamo il numero di righe T (n) in funzione 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 ilnumero di righe richiesto per eseguire la chiamata ricorsiva con parametro n− 1 piu il numero dirighe richiesto per 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 ricorsioneotteniamo 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 raggiungereT(2)? Basta porre n − 2 ∗ k = 2 ed otteniamo k = n−2
2 , cioe k e il numero di iterazioni in funzionedi n per arrivare al 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 otteniamoT (n) > 2
n−12 .
• Possiamo anche limitare superiormente T (n):
T (n) < 2T (n− 1) + 2 < 22T (n− 2) + 2 ∗ 2 < 23T (n− 3) + 2 ∗ 3 < ... < 2kT (n− k) + 2 ∗ k < ...
Questa catena termina quando n− k = 2, ovvero dopo k = n− 2 iterazioni, oppure quando n− k = 1.Nel primo caso, sostituendo n− 2 al posto di k 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.Questo lo si vede facilmente analizzando l’albero delle chiamate ricorsive: per calcolare F (8) si ricalcolapiu volte il valore F (4).
Albero delle chiamate ricorsive di F(8), pagina 7, Fig 1.5
6
1.3 algoritmo iterativo
• L’algoritmo fibonacci3, figura 1.6 pagina 9 riutilizza le risposte a sottoproblemi gia risolti senza rical-colare la risposta e questo fa risparmiare tempo. L’idea e di mantenere una lista i valori F (1), F (2), . . .e di accedervi quando serve.
• calcoliamo il numero di righe di codice eseguite in funzione del valore n: le righe 1,2,5 vengono sempreeseguite;
• 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.Il prezzo che si paga e una maggiore lentezza.
1.4 Notazione asintotica
• L’analisi fatta sinora soffre del fatto che contiamo le linee di codice, e quindi il medesimo programmascritto su linee di codice differenti da valori differenti pur avendo la medesima velocita;
• aumentare la velocita di un computer da tempi differenti, ma l’analisi non cambia dato che sempre lostesso numero di righe di codice e eseguito.
7
• si puo astrarre da questi dettagli mediante la notazione asintotica cioe trascurando le costanti molti-plicative 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 anche f(n) = O(g(n)) se esistono n0 e c > 0 tali che f(n) <= cg(n) pern ≥ n0, cioe f(n) da un certo punto in poi 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 moltiplica-zione di matrici.
• si vede immediatamente che il tempo di esecuzione e O(n), quindi uguale a finonacci3 e fibonacci4,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 quadratisuccessivi, 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 spesoper la chiamata alla funzione.
• Studiamo il tempo impiegato 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 (n2 ) +K1.
• svolgendo i conti abbiamo che T (n2 ) = T ( n22 ) + K1, che sostituito in T (n) da T (n) = T ( n
22 ) + 2K1.Procedendo cosı alla i-esima sostituzione abbiamo che T (n) = T ( n
2i ) + 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 di esecuzione della chiamata ricorsiva per fare la potenza n-esima e logaritmico nel valore din.
1.6 Il metodo dei quadrati ripetuti
L’algoritmo basato su potenze ricorsive usa un metodo noto come quadrati ripetuti. Vale la pena dievidenziarla dato che propone un modo veloce di elevare a potenza un numero o una matrice.
Dovendo fare ab, piuttosto che iterare a ∗ a ∗ a ∗ · · · ∗ a si calcola il valore di c = ab2 e quindi il risultato e
8
ab = c ∗ c oppure ab = c ∗ c ∗ a
a seconda che b sia pari o dispari. Ovviamente, per calcolare c = ab2 possiamo calcolare d = a
b4 e quindi
c = d ∗ d oppure c = d ∗ d ∗ a a seconda che b2 sia pari o dispari, idem per d. Ovviamente la base di questo
procedimento e che elevare a zero un numero da come risultato 1.
Questo modo di procedere e in stile divide et impera, tipico ad esempio di MergeSort. Oltre all’ovviaversione ricorsiva ne possiamo progettare una iterativa basata sul seguente ragionamento fatto al contrariocioe partendo da zero piuttosto che da b. Consideriamo di avere calcolato la sequenza
a0, a1, a2, a4, a8, . . . , ax (1)
Domanda: quanto deve essere lunga la sequenza e come mettere assieme i valori della sequenza per ottenereab? La risposta sta nella rappresentazione di b in base 2. Sappiamo che ogni numero della base 10 puo essereespresso in base 2 cioe tramite una sequenza di bit
1bn−1 . . . b0
che inizia per 1 e tali cheb = b0 ∗ 20 + b1 ∗ 21 + b2 ∗ 22 · · ·+ 1 ∗ 2n
Cosı
ab = ab0∗20+b1∗21+b2∗22···+1∗2n = ab0∗20 ∗ ab1∗21 ∗ ab2∗22 ∗ · · · ∗ a1∗2n
Nota che se un certo bit bi vale zero, allora il fattore vale 1, altrimenti il fattore vale a2i.
L’espressione appena data ci dice quali elementi della sequenza (1) devono essere moltiplicati tra di loro equanto la sequenza deve essere lunga. Quindi l’algoritmo si basa sull’espansione binaria dell’esponente. InFigura 1 e dato lo pseudolinguaggio.
Algoritmo potenza(intero base,intero esp)->interoris=1pow=base;while (esp > 0) doif (esp % 2 == 1) then ris=ris*powpow=pow*powesp=esp/2
return ris
Figura 1: potenza basata su quadrati ripetuti
9
Il tempo di esecuzione di questo algoritmo e ovviamente analogo a quello in versione ricorsiva, basta osservareche la variabile esp viene divisa per due ad ogni iterazione, analogamente a quanto avviene per l’algoritmoprecedente.
Esercizio Scrivere l’algoritmo per fare la potenza di una matrice.
1.7 L’algortimo di Euclide per il MCD
Si tratta di trovare il piu grande divisore d tra due numeri a, b ∈ N. Supponiamo a ≥ b. L’algoritmo diEuclide si basa sulle seguenti osservazioni. Qualsiasi numero d divida sia a che b, in simboli d|a e d|b, deveanche dividere a− b. Infatti,
se d|a allora a = q ∗ d, con q ∈ Nse d|b allora b = q′ ∗ d, con q′ ∈ N
cosı a− b = q ∗ d− q′ ∗ d = (q − q′) ∗ d, quindi d divide a− b.Vale anche che se d|a− b e d|b allora d|a. Infatti
se d|a− b allora a− b = q ∗ d, con q ∈ Nse d|b allora b = q′ ∗ d, con q′ ∈ N
cosı (a− b) + b = q ∗ d+ q′ ∗ d = d ∗ (q + q′), quindi d divide a.
In base a quanto provato sopra
se a ≥ b mcd(a,b)=mcd(a-b,b)se a− b ≥ b mcd(a-b,b)=mcd(a-2b,b)se a− 2b ≥ b mcd(a-2b,b)=mcd(a-3b,b). . . . . .
Per quanto possiamo andare avanti cosı? Per k volte, dove k e tale che
0 ≤ a− kb < b (2)
Quindi nell’espressione (2) k altro non e che il quoziente della divisione ab e a−kb e il resto di tale divisione.
Abbiamo chemcd(a, b) = mcd(a− kb, b)
Adesso basta continuare con lo stesso metodo, cioe dividere b per a − kb e prendere il resto. Si va avantifin quando non si ottiene resto zero. Infatti per ogni n > 0 vale mcd(n, 0) = n. La Figura 2 presental’algoritmo: Circa il fatto che prima o poi si trovi un resto pari a zero non ci sono dubbi. Si osservi infattiche la sequenza dei resti ottenuti dalle divisioni e strettamente decrescente (il resto e sempre strettamenteinferiore del divisore). Il tempo dell’algortimo e strettamente dipendente dal numero di volte che vengonoripetute le istruzioni nel ciclo. Facciamo vedere che nella sequenza dei resti r1, r2, . . . , ru che vengono calcolati
10
Algoritmo Euclide(intero a,intero b)->interodo
r=a%ba=b;b=r
while (r <> 0)return a
Figura 2: Algoritmo di Euclide
durante l’iterazione vale che ri+2 < ri/2 cioe e garantito un dimezzamento ogni due resti. La dimostrazioneha due casi:(i) ri+1 ≤ ri/2, allora dato che ri+2 < ri+1 l’affermazione segue banalmente. (ii) se non vale il punto (i)allora necessariamente ri+1 e compreso nell’intervallo [ ri2 + 1, ri − 1]. In base a come procede l’algoritmo,la quantita ri+2 e il resto della divisione tra ri e ri+1. Il quoziente della divisione e 1, il resto, cioe ri+2 eri − 1 ∗ ri+1. Dato che il range di ri+1 e [ ri2 + 1, ri − 1] segue che il range di ri+2 e [1, ri2 − 1], in ogni casostrettamente inferiore alla meta di ri.
In base al risultato appena ottenuto il numero di iterazioni e ovviamente governato da una legge giaincontrata, infatti:
r2 < r02 = b
2
r4 < r22 = b
22
r6 < r42 = b
23
r8 < r62 = b
24
. . . . . . . . .
ru < b
2u2
Per avere il valore di u per cui ru = 0, basta sapere per quale u vale che
b
2u2
= 1, che risolta da 2 lg b = u
Quindi il numero di iterazioni e proporzionale al logaritmo in base 2 del valore di b.
Infine vale la pena osservare che ogni qual volta vale il punto (ii) i resti soddisfano la definizione dei numeridi Fibonacci, infatti
ri+2 = ri − ri+1 implica ri+2 + ri+1 = ri
Quindi se a e b sono due numeri di Fibonacci consecutivi la sequenza di resti ottenuta sempre soddisfa ilpunto (ii). Quindi il numero di iterazioni dell’algoritmo e quello massimo.
Esercizio Un algoritmo alternativo per il mcd(a, b) e quello che prevede, partendo da b di provare tutti ipossibili divisori nel range [b, 1]. Implementate questo algoritmo e quello di Euclide ed eseguiteli su numeridi Fibonacci abbastanza grandi e vedrete la differenza nei tempi!
11
Per ora abbiamo considerato come tempo semplicemente il numero di righe che vengono eseguite. In pra-tica e come affermare che i comandi contenuti negli algoritmi sono eseguiti sempre in tempo costante,indipendentemente dal valore assunto dalle variabili.
Questo pero potrebbe anche essere un’assunzione troppo forte. Pensiamo alla nostra esperienza: e vero cheper calcolare 99×99 ci mettiamo tanto quanto per calcolare 9999×9999? E ancora, e vero che per calcolare99 + 99 ci mettiamo tanto quanto 99999 + 99999? La risposta e no, per sommare e moltiplicare ci vuoletanto piu tempo quanto piu grandi, cioe piu lunghi, sono i numeri su cui lavoriamo.
Esercizio Assumendo che per sommare due numeri da una cifra ci mettiamo sempre lo stesso tempo (cioeil tempo e costante), quanto tempo occorre per sommare i due numeri anan−1 . . . a0 bnbn−1 . . . b0 con il notoalgoritmo della somma?
Esercizio Assumendo che per moltiplicare due numeri da una cifra ci mettiamo sempre lo stesso tempo,quanto tempo occorre per moltiplicare i due numeri anan−1 . . . a0 bnbn−1 . . . b0 con il noto algoritmo dellamoltiplicazione?
Nel prossimo paragrafo affrontiamo i problemi che abbiamo aperto in questa introduzione e che come vedremoderivano dal fatto di non aver ancora ben formalizzato matematicamente le varie nozioni per ora introdotte.
12
2 Modelli di Calcolo e Metodologie di Analisi
2.1 Un quadro generale
Analizzare gli algoritmi significa stabilire come le loro richieste di risorse computazionali aumenta all’au-mentare della dimensione dei dati di input.
La pratica insegna che le buone performances dei programmi dipendono anche dalla scelta delle strutturedati. Puo infatti accadere che a fronte dello stesso metodo, differenti scelte di strutture dati portino adifferenti tempi di esecuzione.
Per quanto riguarda i problemi, spesso accade che essi abbiano natura discreta, cioe coinvolgano la ricercadi una/la soluzione all’interno di un insieme finito di prossibilita combinatoriali (spazio di ricerca).
Ovviamente dato un problema il primo interesse e quello di trovare un algoritmo. Ma immediatamente doponasce quello della efficienza computazionale, in particolare efficienza rispetto al tempo di esecuzione, cheinformalmente possiamo associare a “essere veloci”. Anche l’uso della memoria (spazio computazionale) eun altro aspetto dell’efficienza. Fissiamo le idee sull’efficienza rispetto al tempo di esecuzione.
Una definizione concreta di efficienza non puo ridursi all’affermazione: “ un algoritmo e efficiente se lasua implementazione va velocemente su dati di input reali”. Tale definizione e troppo vaga ed impreci-sa. Puo accadere che pessimi algoritmi possano essere veloci quando eseguiti su piccoli casi test e/o suprocessori potenti. D’altronde buoni metodi risolutivi potrebbero sembrare pessimi a causa di una cattivaimplementazione (es. scelta sbagliata delle strutture dati).
Inoltre, cos’e un input reale?
Infine, la definizione non tiene conto della scalabilita di un algoritmo, cioe di come le performance di unalgoritmo si comportano all’aumentare della dimensione dei dati di input. Puo accadere che due algoritmidiversi possano avere la medesima velocita quando eseguiti su input di una certa dimensione, ma essere l’unomolto piu lento dell’altro quando gli input hanno dimensione 10 volte superiore.
Abbiamo quindi bisogno di una nozione di efficienza indipendente dalla piattaforma, indipendente dall’i-stanza e che permetta di descrivere come varia la richiesta di risorse computazionali al variare della quantita(dimensione, lunghezza) dei dati da elaborare.
In pratica, abbiamo bisogno di una visione matematica.
La “dimensione dei dati da elaborare” (dimensione dell’istanza di input) e per definizione il numero disimboli di cui sono composti i dati da elaborare. Il consumo di risorse (tempo, spazio, ...) da parte di unalgoritmo oggetto di analisi sara espresso matematicamente mediante una funzione, chiamiamola T , nelladimensione dei dati di input, quindi T ha come dominio i numeri naturali (N).
Consideriamo x ∈ N. E’ ovvio che il numero di possibili input diversi di lunghezza x e un numero finito(esempio, se gli input possono essere inseriti usando solo le 26 lettere minuscole dell’alfabeto inglese, allorai possibili input di dimensione 4 sono 264). La funzione T associa ad ogni possibile valore di x un valore cherappresenta il consumo di tempo.
Dato che fissato x sono molte le istanze di dimensione x, come definiamo T?
13
Un modo e analizzare l’algoritmo oggetto di studio secondo il caso peggiore (worst case analysis): per ognipossibile valore di x si considerano tutte le istanze di dimensione x ed il tempo associato all’algoritmo,cioe il valore di T (x) e il tempo piu alto impiegato. Quindi, l’obiettivo e quello di determinare comevaria la funzione T al variare di x. Sebbene sembri troppo penalizzante, catturare l’efficienza pratica diun algoritmo basandosi sul caso peggiore fornisce un limite superiore alle risorse necessarie ad eseguirel’algoritmo qualunque sia l’input di una data dimensione.
Sorge adesso la questione: quale andamento deve avere T perche l’algoritmo oggetto di studio sia consideratoefficiente? L’esperienza mostra che tipici problemi di interesse pratico hanno una natura combinatoriale elo spazio in cui cercare la/una soluzione cresce esponenzialmente rispetto ai dati di input. Buona partedei problemi possiede un ovvio algoritmo che prevede di analizzare per enumerazione l’intero spazio dellesoluzioni. Tale algoritmo pero ha tempo esponenziale rispetto alla dimensione dei dati di ingresso.
Come esempio si pensi all’ordinamento di n dati: ci sono n! modi di organizzare i dati, ma solo uno necostituisce l’ordinamento crescente. D’altrone sappiamo che esistono algoritmi che permettono di ordinarefacendo n2 o anche solo n log n confronti e scambi. Tra l’altro questi risultati possono essere determinati senzabisogno di implementrare gli algoritmi, ma solo mediante ragionamenti matematici sul metodo. L’analisi diun algoritmo indica anche come possa concretamente essere implementato. Siamo quindi al punto che moltiproblemi hanno ovvi algoritmi basati sull’analisi dello spazio di ricerca, il quale cresce esponenzialmente nelladimensione dei dati. Tali algoritmi sono in pratica inutilizzabili. Quindi il primo punto e che la definizionedi efficienza deve implicare tempi decisamente inferiori rispetto a quelli necessari agli algoritmi a forza bruta.
Dato che crescita esponenziale significa che ad un aumento unitario della dimensione dei dati di input corri-sponde un aumento moltiplicativo del tempo di esecuzione, un comportamento desiderabile e che all’aumentodi un fattore costante k della dimensione dei dati di input corrisponda un aumento delle risorse richiste pariad un fattore k′. Questo e tipico di un andamento polinomiale:
T (x) = xd, d ∈ N fissatoT (x0) = xd0T (2x0) = (2x0)d = 2dxd0, dove 2d e il fattore.
Si considera efficiente un consumo di risorse con andamento polinomiale (rispetto alla dimensione dei dati,d’ora in poi lo considero implicito).
Se per un attimo focalizziamo la nostra attenzione sul tempo di calcolo, si osserva una imperfezione nellanostra definizione: parliamo di tempo di calcolo, ma abbiamo gia detto che non samo necessariamenteinteressati ad una implementazione, ma ad uno studio matematico. Questo significa che tempo (tempo diesecuzione) deve essere definito meglio.
Qui non intendiamo il numero di secondi, ma piuttosto il numero di passi di esecuzione elemetari cioecomandi che siano assimilabili a quelli in grado di svolgere una CPU reale: assegnamenti, confronti, in-crementi e decrementi sono operazioni elementari. Sotto particolari condizioni che specificheremo megliotra poco anche le operazioni aritmetiche sono elementari. In verita purche si descriva l’algoritmo con unopseudolinguaggio non troppo sofisticato, passo di esecuzione puo essere assimilato all’esecuzione di una ri-ga dell’algoritmo. Perche possiamo evitare di essere molto precisi circa il concetto di passo di esecuzioneelementare? La risposta risiede nel fatto che nella sostanza l’andamento della funzione T non viene molto
14
influenzato dalle diverse nozioni, il suo comportamento asintotico non cambia: se rispetto ad un fissatopseudolinguaggio il consumo di tempo ha andamento polinomiale esso lo avra anche con un differente pseu-dolinguaggio, purche ogni istruzione del primo sia traducibile con un numero polinomiale di istruzioni delsecondo (la moltiplicazione di polinomi e un polinomio!).
Anche per questa ragione le funzioni che descrivono i tempi di esecuzione non sono definite in manieraesatta, ma piuttosto si descrive l’andamento della funzione dando il suo ordine di crescita per mezzo dellanotazione O.
Non ha molta utilita contare esattamente il numero di passi di un algoritmo, infatti le funzioni x2 e x2 + 2xal crescere di x si comportano alla stessa maniera e quindi due algoritmi diversi i cui tempi di esecuzionesiano descritti dalle due funzioni date sono considerati avere la stessa velocita.
La morale e quindi che nel descrivere il consumo di risorse le costanti ed i fattori moltiplicativi noninteressano.
In breve:
Per poter studiare gli algoritmi abbiamo bisogno di un modello di calcolo.
Quello che si usa di solito e la macchina a registri, dove oltre ad un dispositivo di input ed uno di output siha a disposizione un numero arbitrario di registri ciascuno dei quali puo contenere numeri interi o reali digrandezza arbitaria.
Queste sono assunzioni non realistiche ma semplificano l’analisi.
Infatti non e vero che ciascuna singola operazione abbia il medesimo tempo e sia indipendente dalla grandezzadei dati. Quando si adotta tale criterio si parla di misura di costo uniforme.
Il criterio di costo logaritmico tiene conto della dimensione dei dati ed il tempo di ogni singola operazionee misurato rispetto alla dimensione dei dati coinvolti. Siccome ogni intero n ∈ N e rappresentabile in baseb con blgb bc+ 1 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 per moltiplicare x per 2 e lg 2i dato che la moltiplicazioneper due e uno shift verso sx, mentre l’incremento di i 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).
Esercizio Valutare l’algortimo di Figura 1 secondo il criterio di costo logaritmico.
15
2.2 La notazione asintotica
• La notazione asintotica consente di semplificare l’analisi nel senso che possiamo trascurare le costantied i termini 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 (modulola costante moltiplicativa);
2.3 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 la memoria necessaria per svolgere i calcoli.
• Analizzare un algoritmo che risolve un certo problema significa determinare in funzione di ogni possibiledato di ingresso il numero di passi che compie l’algoritmo o la quantita di memoria usata dall’algoritmoper produrre l’output.
• Si tratta quindi di scoprire delle funzioni dall’insieme dei dati di ingresso ai naturali.
• Tali funzioni possono essere semplici ed intuitive quando l’insieme dei possibili dati di ingresso el’insieme dei naturali come nel caso degli algoritmi che risolvono il problema di fibonacci, ma possonoessere complicate quando l’insieme dei possibili dati sono sequenze di interi, come nel caso deglialgoritmi di ordinamento.
• Funzioni di questo tipo sarebbero di difficile interpretazione circa l’uso di risorse computazionali daparte degli algoritmi.
• Quello che si preferisce fare e definire delle funzioni di complessita che esprimano l’uso di risorse infunzione della quantita di informazione fornita in input.
2.4 Quantita di Informazione di una Istanza
• Per valutare la quantita di informazione fornita in input di definisce prima di tutto la nozione didimensione di una istanza, la quale a seconda del problema in esame potra essere il numero di cifredi cui e costituito un intero, il numero di componenti di un vettore.
16
• Nella sua accezione piu stringente per dimensione di una istanza dobbiamo intendere il numerodi simboli che occorrono per scrivere i dati di input. Quindi, a questo punto valuteremo i tempi diesecuzione di un algoritmo come funzione nella dimensione delle istanze (cioe da interi) a interi.
• Ora qui sorge un problema che puo essere visto anche analizzando l’esempio di fibonacci: istanzediverse, che danno luogo a tempi di esecuzione diversi hanno la medesima dimensione di istanza, siprenda ad esempio l’istanza n = 120 e n = 999 entrambe di dimensione tre. Come possiamo definireil tempo o lo spazio di calcolo?
17
3 Valutiamo la complessita di alcuni algoritmi visti in precedenza inbase alla dimesione dell’istanza
Abbiamo visto che l’algoritmo fibonacci2 ha un tempo di esecuzione tale che T (n) > 2n−1
2 , dove n ∈ N el’argomento per cui si vuole calcolare il valore F (n).
La lunghezza l di n e l = log n, da cui n = 10l, se usiamo la base 10 per scrivere i dati di input.
Esprimento T in funzione di l e non di n otteniamo che
T (l) > 210l−1
2
Questa analisi gia ci dice che l’algoritmo ha un tempo super-esponenziale nella dimensione dell’istanza diinput.
L’unico piccolo difetto che possiamo trovare e di tipo formale: la variabile l e reale e non intera, quindila funzione T e funzione reale di variabile reale. Per esprimere T come funzione intera di variabile interadobbiamo arrotondare all’intero superiore log n. A questo punto sono numerosi gli input n che coincidonocon dlogne, ciascuno dei quali ha un tempo di esecuzione diverso. Procediamo facendo l’analisi di casopeggiore per il tempo di esecuzione:
Tw(l) = maxT (n)|10l−1 ≤ n ≤ 10l − 1 = T (10l − 1) > 210l−1
2
Analogamente possiamo procedere nell’analisi dell’algoritmo iterativo fibonacci3, la cui complessita intempo avevamo stabilito essere T (n) = 2n, dove n e sempre il valore dell’argomento di F . Dal momento chevale la relazione l = log n, in prima approssimazione segue che
T (l) = 2 ∗ 10l
Se vogliamo esprimere il consumo di risorse mediante una funzione intera di variabile intera allora seguendoil procedimento fatto sopra possiamo condurre l’analisi di caso peggiore e ottenere
Tw(l) = maxT (n)|10l−1 ≤ n ≤ 10l − 1 = T (10l − 1) = 2 ∗ (10l − 1)
cioe esponenziale in l.
Infine l’algoritmo fibonacci5, basato su potenze ricorsive ha una funzione di complessita di tipo logaritmico:T (n) = lg n. A questo punto segue che esprimendo T in funzione della lunghezza l di n abbiamo
T (l) = lg 10l = k ∗ l, k ∈ N
Quindi il consumo di risorse da parte dell’ultimo algoritmo e di tipo lineare nella lunghezza dell’input.
18
• Analizziamo il problema della ricerca di un elemento in una lista.
3.1 Ricerca Sequenziale
• Prendiamo l’algoritmo di ricerca sequenziale (figura 2.2, pagina 30) e valutiamo il numero di confrontiche e l’operazione piu frequente.
Algoritmo RicercaSequenziale(vettore di interi L, intero x)-> 0,11. sia dim il nro di elementi di L;2. for i=1 to dim do3. if (L[i] == x) return 1;4. return 0;
Figura 3: Algoritmo di Ricerca Sequenziale
• Vogliamo predire il tempo di esecuzione in funzione della quantita di dati presente nellalista, piuttosto che in funzione dell’istanza, cioe dei dati che compaiono nella lista e dell’elemento xda ricercare.
• Denotiamo con tempo la funzione che associa ad ogni possibile istanza I il tempo di esecuzionedell’algoritmo su 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 favo-revole?
Tbest(n) = min|I|=n
(tempo(I))
– caso medio:Tavg(n) =
∑|I|=n
Prob(I) · tempo(I)
3.2 ANALISI DI CASO MEDIO
• Facile l’analisi di caso peggiore e migliore, facciamo l’analisi di caso medio: assumiamo che l’elementox possa trovarsi in una qualsiasi posizione con la medesima probabilita, quindi
Prob(pos(x) = i) =1n
19
Quindi
Tavg(n) =n∑i=1
Prob(pos(x) = i) ∗ i =n∑i=1
1n∗ i =
n+ 12
se x ∈ L. Se x 6∈ L allora il numero di confronti atteso e n.
• Possiamo compiere un’altra analisi di caso medio, assumendo come una distribuzione delle istanze taleche ogni permutazione sia equiprobabile.
• Ci sono n! possibili permutazioni di n oggetti. Fissata la posizione i di x ci sono (n − 1)! possibilipermutazioni aventi x nel posto i, quindi possiamo scrivere:
Tavg(n) =∑n!
π=11n! ∗ (n.ro confronti sulla permutazione π)
dove∑n!
π=1 e da leggersi come somma su tutte le possibili permutazioni;
• per ciascuna delle permutazioni il nro di confronti e una quantita compresa tra 1 e n; riscriviamo lasommatoria raccogliendo i termini rispetto al nro di confronti:
Tavg(n) =∑n
i=1(n−1)!n! ∗ i
= 1n
∑ni=1 i = n+1
2
Nota: il risultato e il tempo atteso sotto l’ipotesi che x appartenga a L.
3.3 Ricerca Binaria
Prendiamo lo pseudocodice per la ricerca binaria in Figura 2.4, pagina 34.
Algoritmo ricercaBinaria(vettore di interi L, intero x)->0,11. a=12. b=lunghezza di L3. while (L[(a+b)/2]<>x) do4. m=(a+b)/25. if (L[i]>x) then b=m-16. else a=m+17. if (a>b) then return 08. return 1
Figura 4: Algoritmo di ricerca binaria
Consideriamo un array di estremi [a, b], dove b− a + 1 = n.
20
• Caso migliore: x e in posizione a+b2 ;
• Caso peggiore: x viene trovato quando a = b. Dato che dopo un confrontol’array in cui si effettua la ricerca ha dimensione n
2 , poi n22 e dopo i confronti n
2i ,affinche sia n
2i = 1 deve essere i = log2 n. Quindi Tworst(n) = O(log n).
• caso medio: assumiamo che x ∈ L e che possa occupare con la medesimaprobabilita una qualsiasi delle n posizioni, allora
Tavg(n) =n∑
pos=1
1
n∗ (n.ro confronti per x in posizione pos).
Per valutare questa quantita facciamo una sorta di ragionamento al contrario:quante posizioni consentono di trovare x con 1 confronto? una, la posizionecentrale. E con 2 confronti? 2, le posizioni 1/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.
21
Albero delle posizioni
Nro Confronti posizioni
1 n/2
2 n/4 n/8
3 n/8 3/8n 5/8n 7/8n
Possiamo andare avanti cosı fino a che i = lg2 n. La costruzione ci dice cheper trovare x con i confronti, x puo occupare 2i−1 posizioni diverse. Nellasommatoria vi e esattamente un termine per cui il numero di confronti vale1, vi sono esattamente due termini per cui il numero di confronti vale 2, visono esattamente quattro termini per cui il numero di confronti vale 3, vi sonoesattamente otto termini per cui il numero di confronti vale 4, etc.
Quindi la sommatoria puo essere riscritta come
Tavg(n) =
lg2 n∑i=1
1
n∗ i ∗ n.ro posizioni che richiedono i confronti
=1
n
lg2 n∑i=1
i · 2i−1 = lg2 n− 1 +1
n.
22
Si osservi come il tempo medio non si discosti dal tempo peggiore, questo espiegabile con il fatto che meta degli elementi si comporta come il caso peggiore.
23
4 Statistiche d’Ordine
Il problema da risolvere e il seguente: dati n elementi ed un intero k ∈ 1, . . . , n,trovare il k-esimo elemento quando la sequenza e ordinata (k-esimo piu piccolo opiu grande a seconda dell’ordinamento). La ricerca del mediano avviene quandok = bn2c. Due algoritmi sono interessanti:
• uno randomizzato, basato su partition di quicksort;
Partiamo da un problema differente: selezione per piccoli valori di k. La ricerca delminimo puo essere fatta con n−1 confronti, questo bound e ottimale in quanto se lofacessimo con meno non confronteremmo qualche elemento che puo essere il minimo.
Vogliamo generalizzare l’idea alla ricerca del secondo minimo ed in generale allaricerca del k-esimo minimo, con k = O( n
lg n).
Esaminiamo il semplice algoritmo per la ricerca del secondo minimo, Figura 5.2,pagina 117.
Vale quanto segue
Lemma 4.1 L’algoritmo secondominimo esegue 2n− 3 confronti nel caso peggioree n + O(lg n) nel caso medio.
D imostrazione: Il caso peggiore si verifica quando facciamo 2 confronti per ciascu-na delle n − 2 iterazioni, e questo avviene quando il vettore e ordinato in manieradecrescente.
Per l’analisi di caso medio supponiamo che ogni permutazione del vettore A siaequiprobabile.
• Ogni iterazione esegue almeno il primo confronto, ma il secondo e eseguito solose A[i] e il minimo o il secondo minimo nei primi i valori di A.
24
• Ognuno dei primi i valori puo essere uno dei 2 piu piccoli con probabilita 2i .
• Quindi mediamente il secondo confronto e fatto
n∑i=3
2
i= 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 unadelle restanti i − 1 possibili posizioni quindi le possibili posizioni in cui trovareprimo e secondo minimo sono i(i− 1).
Ora, qual e la probabilita che il minimo o il secondo minimo si trovino in i ? Sonotutti i casi della forma (i, j) e (j, i), con j ∈ 1, . . . , i−1, cioe 2(i−1) casi favorevolisui i(i− 1) casi totali, da cui 2
i .
A questo punto, possiamo fare di meglio nel caso peggiore e selezionare il secondominimo piu efficientemente? In particolare, possiamo progettare un algoritmo il cuicaso peggiore sia uguale a quello di caso medio appena visto?
Si, l’idea e quella di suddividere gli n elementi in coppie e vedere chi e il minimoin ciascuna coppia. Tali minimi vengono di nuovo confrontati a coppie tra di loro ecosı via. Colui che resta e il minimo.
Ecco un esempio su
44 55 12 42 94 18 06 67
Dov’e il secondo minimo? E’ in quelle coppie in cui compare il minimo. Rifac-ciamo una ricerca di minimo tra gli elementi che occorrono in tali coppie. Nota cheil numero di elementi e lg n. E’ chiaro quindi che abbiamo in mano un metodo perricercare il secondo minimo con n + O(lg n) confronti nel caso peggiore invece checon 2n.
Concludiamo che abbiamo un metodo il cui caso peggiore e uguale a quello del casomedio dell’algoritmo dato sopra. La struttura e nota come albero delle selezioni
25
L’albero delle selezioni altro non e che uno heap di cui ricordiamo la definizione:la sequenza di elementi a1, . . . , an ha la proprieta di heap, o piu brevemente e unoheap, se soddisfa le seguenti proprieta:
1. ai ≤ a2i, se esiste l’elemento a2i, cioe 2i ≤ n;
2. ai ≤ a2i+1, se esiste l’elemento a2i+1, cioe 2i + 1 ≤ n;
L’idea della ricerca del secondo minimo puo essere generalizzata al caso in cui sivoglia il k-esimo minimo, con k = O( n
lg n). L’idea applica l’algoritmo heapsort chemerita una drata che forniamo qui di seguito.
4.1 HeapSort
Probabilmente HeapSort non occuperebbe il posto che occupa tra gli algoritmi diordinamento se J. Williams non avesse trovato un modo di rappresentare l’alberodi selezione mediante una struttura dati di n elementi. Tale struttura dati e notacome heap, la cui definizione e stata fornita poco sopra. Si osservi che in base allecondizioni date, gli elementi oltre la meta della sequenza, cioe an/2+1, . . . , an nondevono soddisfare alcun vincolo rispetto agli altri elementi, quindi gia rispettano laproprieta di heap. Inotre, si osservi anche la similitudine tra proprieta di heap ealbero delle selezioni.
Adesso dobbiamo risolvere il seguente problema:
data una sequenza qualsiasi di elementi a1, . . . , an come la trasformiamo in unoheap?
La prima osservazione e che gli elementi della seconda meta sono gia uno heap. Sesappiamo trasformare in uno heap una sequenza data ai, . . . , an in cui ai+1, . . . , ane uno heap, allora siamo a posto, perche bastera applicare tale algoritmo n
2 volte apartire dall’elemento di posto an
2.
Questo algoritmo e facilmente descritto per ricorsione come segue:
26
si confronta ai con a2i e a2i+1. Se ai e il minimo dei 3 allora ai, . . . , an e unoheap e non c’e nulla che deve essere fatto. In caso contrario si scambia ai conil piu piccolo tra a2i e a2i+1, cosı che adesso ai rispetta la proprieta di heap.Pero a seconda del posto dove e avvenuto lo scambio, l’elemento di posto a2i
o quello di posto a2i+1 potrebbe non rispettare la proprieta di heap, e quindioccorre procedere ricorsivamente a partire dalla posizione in cui e stato fattolo scambio. In pratica l’elemento inizialmente in posizione ai deve essere messoal posto giusto in modo che non violi la proprieta di heap, quindi va fattoprogressivamente sprofondare all’interno della sequenza fino a che non occupiun posto corretto.
L’algoritmo che abbiamo descritto va sotto il nome di setacciamento. Qui di se-guito ne diamo una versione ricorsiva in cui a1, . . . , an e la sequenza, s e l’indicedell’elemento da aggiungere allo heap il quale parte dall’elemento di posto s + 1.
setaccio(a1, . . . , an,s)
SE 2s ≤ n e a2s e piu piccolo di asALLORA min = 2s altrimenti min = s;
SE 2s + 1 ≤ n e a2s+1 e piu piccolo di aminALLORA min = 2s + 1SE min 6= s
ALLORA scambia amin con as;
setaccio(a1, . . . , an,min)
• Al termine della chiamata a setaccio la sequenza as, . . . , an e uno heap se lasequenza as+1, . . . , an prima della chiamata era uno heap. In Figura 5 ne diamouna possibile implementazione in linguaggio C.
• A questo punto possiamo usare la procedura setaccio per ottenere uno heap.Come? Basta iterare la chiamata a setaccio in modo da allungare progressi-vamente la sequenza di elementi che soddisfano la proprieta di heap.
• Ovviamente partiamo dall’elemento di mezzo, dato che la seconda parte gia
27
/* n indice dell’ultimo elemento del vettore *//* ricorda che i vettori partono all’indice 0 */void setaccio(int a[],int s,int n)int min,temp;if (2*s+1<=n && a[2*s+1]<=a[s]) min=2*s+1;else min=s;if (2*s+2<=n && a[2*s+2]<=a[min]) min=2*s+2;if (s != min)
temp=a[s];a[s]=a[min];a[min]=temp;setaccio(a,min,n);
Figura 5: Implementazione della funzione setaccio
soddisfa la proprieta di essere uno heap. Qui di seguito descriviamo in linguaggionaturale la procedura.
faiUnoHeap(a1, . . . , an)
Per i che varia da n2 a 1:
setaccio(a1, . . . , an,i)
Una implementazione in linguaggio C e fornita in Figura 6.
/* n indice dell’ultimo elemento del vettore *//* ricorda che i vettori partono all’indice 0 */void faiUnoHeap(int a[],int n)int i;for (i=(n+1)/2-1;i>=0;i--)
setaccio(a,i,n);
Figura 6: Implementazione della funzione faiUnoHeap
28
• Siamo adesso giunti al punto cruciale: come usiamo lo heap per ottenere unvettore ordinato?
• Osserviamo che in cima allo heap abbiamo il minimo. Scambiamolo con l’ulti-mo elemento e consideriamo la sequenza a1, . . . , an−1. Essa non e uno heap acausa dello scambio, ma possiamo setacciare a1 e farlo scendere al posto giusto.L’elemento a1 che emerge e il minimo di a1, . . . , an−1 (cioe il secondo minimodella sequenza originaria).
• Procediamo facendo uno scambio tra a1 e an−1 ed un setacciamento, e cosı viafino a arrivare ad una sequenza di un elemento. Gli elementi a1, . . . , an sonoordinati in maniera descrescente.
• Quest’ultima parte costituisce il nucleo di HeapSort che puo essere descrittocome segue:
HeapSort(a1, . . . , an)
faiUnoHeap(a1, . . . , an)
Per i che varia da n a 2:
scambia a1 con aisetaccio(a1, . . . , ai−1, 1)
Si veda Figura 7 per una implementazione C.
La struttura dell’algoritmo e la seguente:
• rendiamo heap il vettore (procedura heapify), e questo e fatto in tempo O(n);
• a questo punto cancelliamo il minimo k volte e dopo ogni cancellazione ripri-stiniamo la proprieta di heap (procedura fixheap(A,N-1)) e questo e fatto intempo O(lg n).
Ricordiamo che uno heap puo essere equivalentemente rappresentato come vettore ecome albero binario in cui tutti i livelli sono completi al piu ad eccezione dell’ultimo,che viene riempito da sinistra a destra.
29
/*n e l’indice dell’ultimo elemento del vettore */void heapSort(int a[],int n)int i,temp;faiUnoHeap(a,n);for(i=n;i>=1;i--)
temp=a[0];a[0]=a[i];a[i]=temp;setaccio(a,0,i-1);
Figura 7: Implementazione di heapSort
Cosı complessivamente il tempo e O(n + k lg n). L’algoritmo (in pratica HeapSort),e il seguente:
Algoritmo Heapselect(array A, intero K)-> elem
1. heapify(A)
2. for i = 1 to k-1 do
3. scambia(a[1],A[N])
4. fixheap(A,N-1)
5. return A[1]
Si osservi che se il k-esimo minimo che si desidera reperire e in posizione pari ak = O( n
lg n), allora il tempo e O(n). Ma se applichiamo tale algoritmo alla ricercadel mediano, ovvero k = dn2e il tempo e O(n lg n), come un ordinamento.
30
4.2 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 cercando abbiamo finito,altrimenti procediamo ricorsivamente su A1 oppure A3 a seconda di quella cheoccupa la posizione che stiamo cercando.
• Si tratta di modificare partition di quicksort . La modifica e dettata da ordi-ni di efficienza e semplicita dell’analisi probabilistica (Figura 5.7, pagina 121).
• Prima di tutto notiamo che l’algoritmo termina, dato che A1 ed A3 contengonomeno elementi di A.
• Il caso peggiore si verifica (come con quicksort) quando le partizioni sonosbilanciate. In tal caso l’equazione di ricorrenza e
T (n) = O(n) + T (n− 1), T (1) = K ∈ N
che ha come soluzione T (n) = O(n2).
• Facciamo l’analisi probabilistica:
preso il perno x e considerata la partizione degli elementi in due insiemi S1 e S2
tali che S1 contiene tutti gli elementi ≤ x e S2 tutti gli elementi ≥ x, il medianosta sicuramente nell’insieme piu grande, la cui dimensione e ≥ n
2 .
• Quindi, a meno di non restituire il mediano, nel passo ricorsivo dell’algoritmoeliminiamo |A2|+ min(|A3|, |A1|) elementi.
• Si dimostra che il caso della selezione del mediano, cioe k = dn2e, e il peggiore,infatti per valori diversi di k, la probabilita di eseguire il passo ricorsivo sulla
31
partizione piu piccola aumenta. Quando k 6= dn2e puo accadere di fare il passoricorsivo su una partizione (quella che contiene la posizione k) il cui numero dielementi e minore di dn2e, cioe minore della meta degli elementi in A.
Questo mai accade se k = dn2e, cioe se k e la posizione del mediano. Quindiquando si deve stabilire il mediano la ricorsione e sempre fatta su partizioni checontengono piu di meta degli elementi.
• 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 sceltatra tutti i possibili x.
• Se ogni partizione e equiprobabile allora la chiamata ricorsiva avviene in ma-niera equiprobabile su array che hanno dimensione compresa tra n
2 e n− 1 e laprobabilita di incorrere su un array di dimensione i ∈ n2 , . . . , n− 1 e
1
n− 1− n2 + 1
=2
n
• Se l’array ha dimensione n viene partizionato in 3 con n − 1 confronti usandoun array di supporto oppure con 2(n− 1) confronti operando in loco. Quindi ilnumero 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;
32
Induzione:C(n) = (n− 1) + 2
n
∑n−1i=n
2C(i), per hp induttiva segue:
C(n) ≤ (n− 1) + 2n
∑n−1i=n
2t · i
C(n) ≤ (n− 1) + 2n · t
∑n−1i=n
2i
C(n) ≤ (n− 1) + 2n · t(
∑n−1i=1 i−
∑n2−1i=1 i)
C(n) ≤ (n− 1) + 2n · t(
(n−1)n2 − (n/2−1)n/2
2 )
C(n) ≤ (n− 1) + t(3/4n− 1/2)
C(n) ≤ n(3/4t + 1)− 1/2t− 1
C(n) ≤ n(3/4t + 1) ≤ tn⇒ t ≥ 4
• Concludiamo quindi che il numero di confronti atteso e lineare in nella quantitadi dati.
In Figura 8 forniamo un’implementazione in linguaggio C della procedura Seleziona,che implementa quickselect.
int seleziona(int a[],int sx,int dx,int k)int q;if (sx == dx ) return a[k];q=partiziona(a,sx,dx);if (k <= q ) return seleziona(a,sx,q,k);else return seleziona(a,q+1,dx,k);
Figura 8: Implementazione della funzione seleziona
33
4.3 Calcolo Deterministico del Mediano
• L’algoritmo che presentiamo e deterministico nel senso che l’elemento x su cuifare la partizione e scelto in modo deterministico mediante chiamata ricorsiva.
• In questo modo si garantisce che il partizionamento basato su x divida l’arrayin tre parti tali che le loro dimensioni dipendano da un fattore costante. Inparticolare,
• l’obiettivo e di selezionare x in modo che non disti troppo dal mediano cosıda garantire che ogni chiamata sia, ad esempio, su un array grande al piu 3
4 diquello di input. L’obiettivo e raggiunto applicando l’idea di calcolare il medianodei mediani, come segue:
1. Se il numero di elementi su cui calcolare il mediano e piccolo si usa un algoritmodi ordinamento, altrimenti si procede come segue:
2. l’insieme degli elementi e frazionato in tanti gruppi da 5. Si ottengono dn5e grup-pi in cui l’ultimo puo contenere eventualmente meno di 5 elementi. Abbiamocosı S1, . . . , Sdn
5 e gruppi;
3. di ogni gruppo, calcoliamo il mediano con un qualsiasi algoritmo. Chiamiamotali mediani m1, . . . ,mdn
5 e;
4. per chiamata ricorsiva troviamo il mediano M dei mediani m1, . . . ,mdn5 e;
5. usiamo l’algoritmo (modificato) di partizionamento di quicksort dove l’ele-mento pivot x vale M ;
6. procediamo ricorsivamente sulla regione piu estesa (o su quella contenente laposizione k di interesse).
L’algoritmo descritto sopra puo essere schematizzato come segue, dove l e r sonorispettivamente indice dell’elemento piu a sinistra e piu a destra della sequenza, k ela posizione di interesse all’interno della sequenza di input.
34
medianoDet(a1, . . . , an, l, r, k)->intero0. SE r-l inferiore a 10
ALLORA ordina la sequenza al, . . . , ar e restituisci l’elemento di posto
k;1. sia gruppi=
(r−l+1)5 e avanzo= (r − l + 1)%5, cioe gruppi denota
il numero di gruppi da 5 elementi in cui possono essere suddivisi
gli elementi da al, . . . , ar e avanzo il numero di elementi nell’ultimo
gruppo.
SE avanzo 6= 0 poniamo totGr=gruppi+1,
ALTRIMENTI totGr=gruppi.
2. Per i che varia da 1 a gruppi esegui:
3. sia mi il mediano di a5∗(i−1)+1, . . . , a5∗(i−1)+5
4. SE avanzo 6= 05. ALLORA sia mtotGr il mediano di
a5∗gruppi+1, . . . , a5∗gruppi+avanzo;
6. M=medianoDet(m1, . . . , mtotGr, 1, totGr, totGr/2)7. j=partizionaV2(a1, . . . , an, l, r, M)8.SE k <= j ALLORA return medianoDet (a1, . . . , an, l, j, k)
9.ALTRIMENTI return medianoDet (a1, . . . , an, j + 1, r, k)
Di seguito forniamo una possibile implementazione in linguaggio C. Il passo base eeseguito tramite selectionSort opportunamente adattato.
In Figura 11 presentiamo la funzione di partizionamento partizionaV2, variantedella usuale funzione di partizionamento di quicksort. La funzione partizionaV2
ha tra i suoi parametri formali il pivot x. Si lascia come esercizio la modifica di questafunzione di partizionamento in modo che il partizionamento divida gli elelementinelle tre regioni A1, A2, e A3.
35
int medianoDet(int a[],int l,int r,int k)/* l: indice primo elemento,
r: indice ultimo elemento,k: posizione da estrarre, tra gli estremi l e r */
int gruppi, avanzo,totGr;int m[r]; /* vettore dei mediani dei gruppi:
m[0] contiene il mediano del primo gruppo etc...*/int M;int i,j;
if ((r-l+1)< 10 ) /* passo base: con pochi elementi uso un metodo quasiasi */selectionSort(a,l,r);return a[k];
gruppi=(r-l+1)/5;avanzo=(r-l+1)%5;
if (avanzo != 0) totGr=gruppi+1;else totGr=gruppi;
for(i=0;i<gruppi;i++) /* calcolo del mediano di 5 elementi,uso un metodo qualsiasi */
selectionSort(a,5*i+l , 5*i+4+l); /* osserva +l*/m[i]=a[5*i+2+l];
if (avanzo !=0 ) /* osserva che la variabile i vale gruppi *//* calcolo del mediano per il gruppo, se esiste,
con meno di 5 elementi */selectionSort(a,5*i+l , 5*i+(avanzo-1)+l);m[i]=a[5*i+(avanzo-1)/2+l];
M=medianoDet(m,0,i,i/2); /* calcolo del mediano dei mediani */j=partizionaV2(a,l,r,M);if (k<=j) return medianoDet(a,l,j,k);else return medianoDet(a,j+1,r,k);
Figura 9: Implementazione del Mediano deterministico
36
int indexMin(int a[],int start,int stop)/* start: indice della prima cella,
stop: indice dell’ultima */int i,idxmin;idxmin=start;for(i=start+1;i<=stop;i++)
if (a[idxmin]>a[i]) idxmin=i;return idxmin;
void selectionSort(int a[],int start,int stop)/* start e stop sono gli estremi del vettore a*/
int i,idxMin,help;for(i=start;i<=stop;i++)
idxMin=indexMin(a,i,stop);help=a[i];a[i]=a[idxMin];a[idxMin]=help;
Figura 10: Versione di selectionSort per il calcolo del mediano
37
int partizionaV2(int a[],int sx,int dx, int x)int i,j,temp;
i=sx-1;j=dx+1;
while (1)do i++; while (a[i]<x);do j--; while (a[j]>x);if (i< j)temp=a[i];a[i]=a[j];a[j]=temp;
else return j;
Figura 11: La funzione partizionaV2, variante di partiziona
38
4.3.1 Analisi di complessita
Esiste un metodo che permette di trovare il mediano tra 5 elementi facendo solo 6confronti (esercizio!), quindi tutti i mediani mi possono essere trovati in 6dn5e passi.
Il calcolo del mediano dei mediani e fatto per chiamata ricorsiva e quindi richiedetempo T (dn5e) <= T (n5 + 1).
Il vero problema e sapere su quale dimensione dell’array e fatta la chiamata ricorsiva,cioe la dimensione che il partizionamento produce.
Il seguente lemma stabilisce che la chiamata ricorsiva viene fatta su una frazionedegli elementi di input:
Lemma 4.2 La chiamata ricorsiva e effettuata su al piu 710n + 3 elementi.
D imostrazione:
Ad ogni passo dopo aver partizionato scartiamo gli elementi uguali a M piu quelli opiu grandi o piu piccoli. Supponiamo di scartare quelli piu grandi, quanti elementiscartiamo in tutto?
Dato che M e mediano degli mi almeno meta di questi e scartata, e quindi almenod1
2dn5ee = d n10e dato che gli mi sono dn5e.
Ora, ciascun mi e mediano del proprio gruppo Si di 5 elementi quindi e garantitodalla definizione di mediano che almeno altri due elementi di Si siano maggiori dimi e quindi siano scartati.
Cosı quei gruppi Si tali che mi ≥ M hanno almeno 3 elementi ≥ M che quindivengono scartati. I gruppi Si con 5 elementi tali che mi ≥ M sono, per quantoosservato sopra, d n10 − 1e (-1 e dovuto al fatto che l’ultimo gruppo potrebbe nonavere 5 elementi).
Cosı e garantito che vengano scartati almeno 3n10 − 3 elementi.
Con un ragionamento assolutamente analogo possiamo dimostrare che il medesimonumero di elementi e scartato se la chiamata ricorsiva scarta quelli piu piccoli.
Se ne deduce che la chiamata ricorsiva e fatta su 7n10 + 3 elementi.
39
Theorem 4.3 Nel caso peggiore select esegue O(n) confronti.
D imostrazone:
ci vuole tempo 6dn5e < 6(n5 + 1) per il calcolo degli mi;
il mediano dei mediani M e calcolato per chiamata ricorsiva su dn5e elementi, quindiil tempo e T (dn5e).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) ≤ 11
5n + T (dn
5e) + T (
7
10n + 3) + 5
A questo punto per sostituzione si puo dimostrare che T (n) ha un andamento lineare,cioe T (n) = Kn, con K ∈ N . In particolare dimostriamo che esiste un valore perK tale che
T (n) ≤ 11
5n + T (dn
5e) + T (
7
10n + 3) + 5 ≤ Kn
Se T (n) ha un andamento lineare allora
T (n) ≤ 11
5n + K(
n
5+ 1) + K(
7
10n + 3) + 5 ≤ Kn
Trascurando il termine 4K che non dipende da n, possiamo dividere le ultime duedisequazioni per n ottenendo
11
5+
K
5) + K
7
10≤ K
11
5+
9
10K ≤ K
Che e soddisfatta per K ≥ 22. Abbiamo quindi dimostrato che l’andamento di T (n)e lineare ed il fattore moltiplcativo di n e 22.
40
5 Tecniche Algoritmiche
• La tecnica greedy costruisce la soluzione applicando di volta in volta la scel-ta localmente piu promettente. Molti problemi di ottimizzazione ammettonoalgoritmi greedy ottimali.
41
6 Tecnica Divide et Impera
• La tecnica divide et impera e una tecnica che consiste nel dividere l’istanzadel problema da risolvere in sottoistanze le quali vengono risolte ricorsivamentee le cui soluzioni sono ricombinate per ottenere la soluzione dell’istanza.
• E’ una tecnica top-down nel senso che si parte dall’istanza generale e si dividein istanze piu piccole.
• Lo sforzo del progettista consiste nell’individuare sia come dividere il problemasia (ma soprattutto) come ricombinare le soluzioni parziali.
6.1 MergeSort
E un algoritmo di ordinamento che ha una chiara struttura ricorsiva: richiamase stesso piu volte per trattare istanze piu semplici di quella data in input. Inquesto caso istanza piu semplice e sinonimo di sequenza piu corta rispetto aquella fornita in input.
Data una sequenza a1, . . . , an, MergeSort opera come segue:
1. divide la sequenza da ordinare in due sottosequenze di n2 elementi ciascuna;
2. ordina le due sottosequenze ricorsivamente usando MergeSort;
3. fonde le due sottosequenze ordinate per produrre la risposta ordinata.
– Si osservi che nel passo 2 la base della ricorsione si ha quando la sequenzada ordinare e lunga 1.
– L’operazione chiave di MergeSort e il passo 3, dove si fondono due sequenzeordinate.
Nelle Figure 12 e 13 forniamo un’implementazione C degli algoritmi.
42
/* p e l’indice del primo elemento della sequenza,r e l’indice dell’ultimo elemento della sequenza
*/void mergesort(int a[],int p,int r)int q;if (p<r)
q=(p+r)/2;mergesort(a,p,q);mergesort(a,q+1,r);merge(a,p,q,r);
Figura 12: Implementazione in linguaggio C di mergesort
6.2 Quicksort
Anche quicksort ha una chiara struttura dividi et impera. Data una sequenzaS di elementi:
1. dividi: scegli un elemento x e usalo per partizionare S in due:A, quella contenente solo gli elementi minori o uguali a x;B, quella contenente solo gli elementi maggiori o uguali a x;
2. impera:procedi ricorsivamente su A come se fosse S, ottenendo A′;procedi ricorsivamente su B come se fosse S, ottenendo B′;
3. A′ seguito da B′ costituisce l’ordinamento di S.
Nota che in tal caso la terza fase, quella di ricombinazione delle soluzioni parzialie molto facile. Al contrario la fase di dividi e sofisticata. Si osservi come nelaso di mergeSort la fase di dividi sia banale mentre la fase di ricombinazione esofisticata.
43
void merge(int a[],int p,int q,int r)int b[r+1]; /* conterra il risultato della fusione*/int i,j,t;/*i punta alla testa della sottosequenza di sxj punta alla testa della sottosequenza di dxt punta alla prima cella libera di b
*/i=p;j=q+1;t=1;
/* itera il corpo finche entrambe le sottosequenza hanno elementi*/while (i<=q && j<=r)
if (a[i]<a[j]) b[t]=a[i];i++;t++; else b[t]=a[j];t++;j++;
/* copia della coda della sottosequenza non terminata*//* nota: solo uno dei due seguenti while parte */while (i<=q)
b[t]=a[i]; i++; t++;
while (j<=r)b[t]=a[j]; j++; t++;
/* copia b in a, adesso le due sottosequenze sono fuse in un’unicasequenza ordinata che sta in b */
for(i=1,j=p; i<t; i++,j++)a[j]=b[i];
Figura 13: Implementazione in Linguaggio C della funzione merge
44
6.3 Esercizi
– Scrivere una procedura che dato un vettore v ed un elemento x stabilisca sev e partizionato rispetto a x. In caso affermativo deve restituire la posizionedi confine tra le due regioni altrimenti -1.
– Modificate MergeSort, cosı che divida la sequenza di dati in 3 parti e nondue.
45
6.4 Moltiplicazione di interi di grandezza arbitraria
• La moltiplicazione di numeri che non stanno in una cella di memoria non puoessere considerata a tempo costante.
• Presi 2 numeri di n cifre X = xn−1 . . . x0 e Y = yn−1 . . . y0 entrambi di n cifre,la moltiplicazione prende tempo O(n2), dove la moltiplicazione di 2 cifre prendetempo costante.
• Supponiamo per semplicita che n sia potenza di 2 e suddividiamo ciascunnumero 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 . . . yn2.
• CosıXY = (X110
n2 + 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.
46
• Per semplicita nell’analisi seguente consideriamo i numeri su cui si fanno lemoltiplicazioni di n
2 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 tempodi fare somme e shift (le moltiplicazioni per 10) di numeri a n cifre, quindi iltempo e:
T (n) = 3T (n2 ) + K2 · n, n > 1T (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
1
2i= O(nlg2 3)
Esercizio Scrivere un programma C per fare operazioni aritmetiche con nume-ri di lunghezza arbitraria. Per cominciare si consideri il seguente frammento diprogramma:
#include<stdio.h>#define LUNGHEZZA 10
/* primo addendo, posizione del’unita’ del primo addendo, secondo addendo,posizione unita’ del secondo addendo, vettore risultato*/int somma(int add1[], int startAdd1, int add2[], int startAdd2, int ris[]);
/*vettore e sua dimensione*/void printAdd(int add[],int dim)int i;for(i=0;i<dim;i++) printf("%d",add[i]);
/* ritorna la posizione delle unita’ */
47
int leggiAddendo(int add[])int i;char cifra;
scanf("%c",&cifra);
i=0;while (cifra != ’\n’)add[i]=cifra-’0’;i++;scanf("%c",&cifra);
return --i;
int main()int ris[LUNGHEZZA+1],add1[LUNGHEZZA],add2[LUNGHEZZA], i,j, add1Dim,add2Dim;char cifra;
printf("Primo addendo:");add1Dim=leggiAddendo(add1);printf("secondo addendo:");add2Dim=leggiAddendo(add2);
somma(add1,add1Dim,add2,add2Dim,ris);
printAdd(ris,LUNGHEZZA);printf("\n");return 0;
Esercizio 1. Per poter elaborare numeri di grandezza arbitraria e necessario poterfare confronti tra due numeri di lunghezza arbitraria, quindi bisgona ridefinire glioperatori relazionali >, <, =, implementandoli come funzioni; 2. implementare lasottrazione tra interi di grandezza arbitraria; 3. implementare la divisione intera(quoziente e resto) tra numeri di grandezza arbitraria. Dato che la divisione
Tra l’altro
48
6.5 Polinomi e Trasformata Veloce di Fourier (FFT)
...To Be Prepared...
49
6.6 La Programmazione Dinamica
• Tipicamente, la tecnica della programmazione dinamica si basa sulla fi-losofia bottom-up. Procediamo dai sottoproblemi piu piccoli verso quelli piugrandi.
• E’ una tecnica utile quando le sottoistanze non sono una indipendente dall’altraed una stessa sottoistanza dell’istanza originaria puo comparire piu volte. Que-sto in pratica significa che analizzando l’albero delle chiamate ricorsive si notache ci sono due o piu chiamate ricorsive aventi con gli stessi parametri attuali;
• Le soluzioni delle sottoistanze sono memorizzate in una tabella, cosı qualorala medesima sottoistanza dovesse essere reincontrata sara sufficiente esaminarel’elemento della tabella che ne contiene la soluzione.
• La tecnica algoritmica Programmazione dinamica, prende nome dal fattoche si basa su una tabella (mono o pluridimensionale) la quale memorizza lesoluzioni dei sottoproblemi del problema originario e tale tabella viene compilatao meglio programmata dinamicamente, a run-time.
• E’ una tecnica bottom up in quanto la tabella e compilata partendo dai sot-toproblemi piu semplici, cioe dai casi base e passando poi a sottoproblemi piudifficili combinando in maniera opportuna le soluzioni dei problemi piu sempliciper ottenere quelle dei problemi piu difficili.
• In opposizione, la tecnica top-down affronta l’istanza del problema generale ela divide man mano in sottoistanze piu piccole. La tecnica di programmazionedinamica procede come segue:
1. si identificano i sottoproblemi del problema originario e si utilizza una tabellaper memorizzare le soluzioni 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
50
(cioe un entry della tabella) in funzione dei valori delle soluzioni dei sottopro-blemi gia risolti;
4. si restituisce la soluzione del problema originario.
51
6.7 Associativita del prodotto tra matrici
• Di seguito ci occupiamo della moltiplicazione di matrici. E’ noto che M1M2 = Mpuo essere fatto se il numero di colonne di M1 e uguale al numero di righe diM2 e la matrice M ha il numero di righe di M1 ed il numero di colonne di M2.
• Il prodotto di matrici e associativo ma non commutativo. Di seguito considere-remo 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 numero di operazioni dimoltiplicazione?
• Il modo di associare le matrici influenza il modo in cui operiamo. Ad esempio,siano M1(10, 20), M2(20, 30), M3(30, 2).
• E’ facile verificare che il numero di moltiplicazioni varia di molto a seconda chesi faccia M1(M2M3) o (M1M2)M3. Infatti:M1 ∗M2 e una matrice di dimensione 10x30 e per calcolare ciascun elementooccorrono 20 moltiplicazioni;(M1 ∗M2) ∗M3 e una matrice 10x2 e per calcolare ciscun elemento occorrono30 moltiplicazioni.Segue quindi che il prodotto (M1 ∗M2) ∗M3 richiede 6600 moltiplicazioni.D’altronde, la stessa matrice puo essere calcolata associando M1 ∗ (M2 ∗M3),in tal caso:M2 ∗M3 ha 20x2 elementi, ciascuno calcolato con 30 moltiplicazioni;M1 ∗ (M2 ∗M3) ha 10x2 elementi, ciascuno calcolato con 20 moltiplicazioni.Segue quindi che il prodotto M1 ∗ (M2 ∗M3) richiede 1600 moltiplicazioni.
• questo semplice esempio contiene il succo della strategia: conoscendo il costodelle associazioni (M1 ∗ M2) e (M2 ∗ M3) possiamo scegliere quella definitivaper la moltiplicazione delle 3 matrici. Nota la nostra scelta e ottima perche(banalmente) ottime sono le associativita scelte per la moltiplicazione di (M1 ∗M2) e (M2 ∗M3).
52
• Prima di vedere il problema generale, illustriamo l’idea di base, supponendo didover moltiplicare M1 ∗M2 ∗M3 ∗M4.
• Osserviamo che ci sono diverse associazioni possibili per ottenere la matricerisultato:M1 ∗ (M2 ∗M3 ∗M4), (M1 ∗M2) ∗ (M3 ∗M4), (M1 ∗M2 ∗M3) ∗M4.
• Osserviamo quindi che se conoscessimo il costo della moltiplicazione di M2∗M3∗M4, M1 ∗M2, M3 ∗M4, M1 ∗M2 ∗M3, potremmo decidere quale associazione ciconviene fare conteggiando per ciascuno dei 3 casi il numero di moltiplicazioni.Ovviamente, decideremmo per l’associativita che produce il numero inferiore dimoltiplicazioni;
• inoltre se sapessimo anche che i costi delle moltiplicazioni M2∗M3∗M4, M1∗M2,M3 ∗M4, M1 ∗M2 ∗M3 sono ottimi, cioe minimi, potremmo anche affermare cheil numero di moltiplicazioni per l’associtivita scelta e il minimo possibile.
• Ma per fare questa affermazione qualcuno dovrebbe calcolare i costi minimi perla moltiplicazione di M2 ∗M3 ∗M4, M1 ∗M2, M3 ∗M4, M1 ∗M2 ∗M3. Questosignifica, in particolare trovare l’associativita migliore per tali moltiplicazioni dimatrici, in particolare per M2 ∗M3 ∗M4 e M1 ∗M2 ∗M3, dato che per M1 ∗M2,M3 ∗M4 la scelta e obbligata.
• Consideriamo di avere le matrici M1(10, 2), M2(2, 5), M3(5, 20), M4(20, 50). Ledimensioni sono quindi
l1 = 10, l2 = 2, l3 = 5, l4 = 20, l5 = 50
E’ immediato calcolare il costo della moltiplicazione tra 2 matrici: basta molti-plicare tra loro le rispettive dimensioni. Per quanto rigarda la moltiplicazioneM1M2M3 abbiamo due possibili casi:(M1M2)M3 che costa 100+1000;M1(M2M3) che costa 200+400;Quindi (M1M2)M3 e la parentesizzazione migliore, e 600 e il valore inserito inriga 1 colonna 3 ad esprimere il fatto che 600 e il numero minimo di moltipli-cazioni da fare per ottere il risultato di M1M2M3.
53
Procediamo analogamente per la moltiplicazione di M2M3M4 ottenendo che(M2M3)M4 e l’associativita piu economica dato che richiede solo 2200 moltipli-cazioni contro le 5500 richiesta dall’associativita M2(M3M4).Per moltiplicare M1M2M3M4 abbiamo 4 possibili modi di associare le matrici,per ciascuno dobbiamo calcolarne il costo. Scopriremo che 3200=2200+1000 eil costo minimo ottenuto associando M1(M2M3M4). Possiamo quindi compilarela tabella
ada
1 2 3 4
1 0 100 600 3200
2 0 200 2200
3 0 5000
4 0
Oltre alla matrice dei costi data qui sopra, possiamo compilare la matrice del-la soluzione, che permetta di ricostruire come fare l’associazione. La matricesoluzione e analoga a quella dei costi: le celle significative sono solo quelle so-pra la diagonale principale e se j e il valore che compare alle coordianate (r,c)significa che la moltiplicazione di Mr . . . Mc deve essere fatta con associazione(Mr . . . Mj)(Mj+1 . . . Mc). Svolgendo l’esempio dato sopra si ottiene la seguentematrice soluzione:
ada
1 2 3 4
1 1 1 1
2 2 3
3 3
4
Quindi da questa matrice deduciamo che M1M2M3M4 devono essere associatecome M1(M2M3M4) e che M2M3M4 devono essere associate come (M2M3)M4
• Torniamo al problema con n matrici. Indichiamo con P (i, j) il sottoproblemache consiste nel moltiplicare le matrici Mi . . . Mj.
54
• Quindi il problema originario e P (1, n). Abbiamo che
1. I sottoproblemi che dobbiamo risolvere sono i P (i, j) con i ≤ j; il costoottimo lo memorizziamo in una matrice C bidimensionale, che risulta unatriangolare superiore, nell’entry (i, j);
2. i sottoproblemi del tipo P (i, i), i = 1, . . . , n, sono banali perche ci sono 0moltiplicazioni, quindi C[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 problemaMi . . . Mj in funzione dei sottoproblemi piu piccoli gia risolti cioe gia sapendocome associare prodotti di un numero di matrici inferiori a j−i+1, in particolaresapendo come associare in modo ottimo prodotti di sequenze di matrici del tipoMi . . . Mr e Mr . . . Mj. Per fare questo dobbiamo tentare tutti i possibili valoridi r e vedere quale di questi produce il minimo di
C[i, r] + C[r + 1, j] + lilr+1lj
cioe porremo
C[i, j] = mini≤r≤j−1
C[i, r] + C[r + 1, j] + lilr+1lj
• Si tratta quindi di compilare in maniera sistematica gli entry della matrice,partendo dai problemi con una matrice (casi base), passando con quei problemicon due matrici, poi a quelli con 3 etc. Questo significa compilare la matricemuovendosi per diagonali a partire da quella principale e poi salendo via via suquelle parallele.
• Quello che si ottiene e l’algoritmo in Figura 14 (vedi anche pagina 252), in cuiviene anche compilata S, la matrice soluzione.
Theorem 6.1 L’algoritmo ordinematrici richiede tempo O(n3), dove n e ilnumero di matrici.
55
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; S[i,j]=i;7. for r=i+1 to (j-1) do8. if C[i,j]>(C[i,r]+C[r+1,j]+lilr+1lj)9. then10. C[i,j]=C[i,r]+C[r+1,j]+lilr+1lj11. S[i,j]=r12. return C[1,n]
Figura 14: Associativita di matrici
• D imostrazione: nella diagonale d, 1 ≤ d ≤ n − 1 ci sono n − d elementi e perciascuno di essi, che rappresenta un problema di moltiplicazione di d+1 matrici,ci sono d− 1 possibilita (i possibili valori di r sono d− 1).
56
• 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 imperain cui presa l’istanza Mi . . . Mj per ogni r = i, . . . , j − 1 faccia una chiamataricorsiva su Mi . . . Mr e Mr+1 . . . Mj per trovare la partizione ottima e poi decidequale r e il migliore per partizionare Mi . . . Mj. Molti sottoproblemi di Mi . . . 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, altri-menti non potrebbe esserlo(Mi . . . Mr)(Mr+1 . . . Mj).
57
• Questo significa che il problema dell’associativita del prodotto di matrici verificail principio della sottostruttura ottima: se la soluzione ad un problema e ottimaallora anche le soluzioni ai sottoproblemi sono ottime.
• Molti problemi riguardanti i grafi ammettono algoritmi progettati secondo latecnica di programmazione dinamica.
Eserczio Progettare e codificare in C un algoritmo che date le dimensioni l1, . . . , ln+1
di n matrici stampi a video l’associativita ottima ed il costo. Sul nostro esempiointroduttivo il programma dovrebbe stampare a video M1((M2M3)M4) come soluzionee 3200 come costo.
58
Stampa di una tabella di associativita di dimensione 6x6.
#include<stdio.h>
void stampaAssociativita(int s[][6],int i,int j)
if (i==j) printf("A%d",i);
else
printf("(");
stampaAssociativita(s,i,s[i][j]);
stampaAssociativita(s,s[i][j]+1,j);
printf(")");
/* Main di prova */
int main(void)
/*Inizializza la matrice di programmazione dinamica */
int s[6][6]=
0,0,0,2,2,2,
0,1,1,2,2,2,
0,0,2,2,2,2,
0,0,0,3,3,4,
0,0,0,0,4,4,
0,0,0,0,0,5
;
int i,j;
stampaAssociativita(s,0,5);
return 0;
59
60
Knapsack
• Il problema dello zaino e il seguente:
• si ha a disposizione uno zaino di capacita C nel quale si vogliono mettere deglioggetti, ciascun tipo di oggetto ha un peso ed un valore.
• Il problema e di massimizzare il valore posto nello zaino senza superare il pesoC che lo zaino in tutto puo trasportare. Di ogni tipo di oggetto sono disponibiliun numero illimitato di copie.
• Per scrivere un algoritmo che risolve il problema osserviamo che se per ciascuntipo di oggetto i conosco il valore della soluzione ottima del problema dellozaino quando la capacita e C − peso(i) (C − peso(i) ≥ 0) allora posso calcolareil valore della soluzione ottima del problema dello zaino con capacita C vedendoper ogni oggetto i qual e quello che aggiunto allo zaino ne massimizza il valore.
61
Knapsack (2)
• Piu formalmente potremmo dire che date le soluzioni ottime ott(1), . . . , ott(n)ai problemi con zaini di capacita C−peso(1), . . . , C−peso(n) aggiungiamo allozaino quell’oggetto j tale che ott(j)+valore(j) = maxi=1,...,n(ott(i)+valore(i)).
• Una prima soluzione a questa idea potrebbe essere la seguente:
zaino(intero capacita, array peso, array valore)-> intero
1. if capacita <= 0 return 0
2. 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 max
10.
62
Knapsack (3)
• Questo algoritmo ricalcola piu volte la soluzione al medesimo problema. Cosı iltempo e esponenziale rispetto al valore di capacita e al numero di oggetti.
• Una analisi delle chiamate ricorsive dell’algoritmo evidenzia come il medesimosottoproblema possa essere risolto piu volte.
• Per ridurre il numero di chiamate dobbiamo memorizzare il valore delle soluzioniottime mano a mano che le troviamo cosı da evitare delle chiamate inutili.
• Siccome i problemi differiscono tra loro per il diverso valore di capacita intro-duciamo un vettore di C + 1 celle, una cella per ogni possibile valore che lacapacita dello zaino puo assumere nei sottoproblemi del problema originario.
63
Knapsack (3)
zaino2(intero capacita, array peso, array valore,
array soluzioneottima)->intero
if (soluzioneottima[capacita] <> -1 )
return soluzioneottima[capacita]
else
max=0
for(i <- 1; i <= nroOgg ; i++)
if (capacita-peso[i]>=0)
ris=zaino2(capacita-peso[i],peso,valore,
soluzioneottima)+valore[i]
if (ris > max) max=ris
soluzioneottima[capacita]=max
return max
64
Knapsack (4)
• Possiamo apportare un’altra modifica all’algoritmo procedendo bottom-up, cioecercare di compilare il vettore delle capacita dalle capacita piu piccole allecapacita piu grandi.
• Se abbiamo il problema dello zaino con capacita C e gia abbiamo le soluzioniper tutte le capacita piu piccole di C non c’e bisogno di fare chiamate ricorsiveper risolvere i sottoproblemi per zaini di capacita C − peso(i), per i = 1, . . . , n,basta fare un ciclo su i che va da 1 a n perche il valore ottimo per il problemaC−peso(i) gia l’abbiamo. Il passo base del problema e ovviamente per lo zainodi capacita uguale a zero, il cui ottimo e zero.
zaino3(capacita, array peso, array valore, array soluzioneottima)
for c <- 1 to capacita do
max <- 0
for 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;
65
Knapsack (5)
• Differente e l’idea se abbiamo uno zaino di capacita C ed n tipi di oggetti1, . . . , n, ciascuno con un peso p(1), . . . , p(n) ed un valore v(1), . . . , v(n), madi ogni oggetto abbiamo solo una copia, quindi nella soluzione ottima ciascunoggetto o compare, o non compare.
• Se l’oggetto 1 compare nella soluzione ottima, allora la soluzione senza l’oggetto1 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 compare nella soluzione ottima allora la soluzione e ugualealla soluzione ottima per il problema con uno zaino di capacita C e n−1 tipi dioggetti 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 senzatale oggetto e soluzione ottima del problema senza tale oggetto con uno zainoche ha capacita diminuita del peso dell’oggetto; se l’oggetto non appartienealla soluzione ottima, allora basta risolvere il problema in cui l’oggetto non epresente.
• Una prima soluzione che non usa la programmazione dinamica e la seguente:
66
Knapsack (6)
zaino4(intero capacita,array peso,array valore,intero lastobj)-> intero
if (capacita <= 0 || lastobj<0) return 0
else
ris1=zaino4(capacita, peso, valore, lastobj-1)
ris2=zaino4(capacita-peso[lastobj],peso,valore,lastobj-1)
+valore[lastobj]
if ris1 > ris2 return ris1
else return ris2
• Questa soluzione soffre comunque del fatto che il medesimo problema puo esseresottoproblema di piu problemi e quindi risolto piu volte, come indica una facileanalisi delle chiamate ricorsive.
• Cio che distingue un problema dai suoi sottoproblemi sono gli oggetti presentie la capacita dello zaino. Possiamo quindi utilizzare una matrice che ha tantecolonne quanti sono gli oggetti nell’istanza del problema e tante righe quantoe il valore della capacita dello zaino e nella posizione di indice (j, i) l’ottimodel sottoproblema la cui istanza ha i primi i oggetti dell’istanza del problemaoriginario ed uno zaino di capacita j.
67
Knapsack (7)
zaino5(intero capacita, array peso, array valore,
intero lastobj, matrice soluzioneottima)-> intero
if (capacita <= 0 || lastobj<0) return 0
else
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]=ris1
else soluzioneottima[capacita,lastobj]=ris2
return soluzioneottima[capacita,lastobj];
68
6.8 Longest Common Subsequence (LCS)
Data una sequenza di elementi una sua sottosequenza e ottenuta privando la se-quenza di un numero qualsiasi di elementi. Ad esempio le parole sono sequenze dilettere e una sottosequenza di “MAGGIO” e “MGG”.
Formalmente, date due sequenze X = 〈x1, . . . , xn〉 e Z = 〈z1, . . . , zk〉 diremo che Ze sottosequenza di X se esiste una sequenza di indici di X 〈i1, . . . ik〉 strettamentecrescente e tale che per ogni j = 1, . . . , k, Xij = Zj. Date due sequenze X e Y , Z esottosequenza comune di X e Y se Z e sottosequenza sia di X che si Y .
Nel problema di trovare la sottosequenza piu lunga ci vengono date due sequenzeX = 〈x1, . . . , xm〉 e Y = 〈y1, . . . , yn〉 e dobbiamo trovare la sottosequenza comunepiu lunga.
Vediamo come possiamo risolvere il problema usando la programmazione dinamica.Innanzitutto e immediato vedere che un algoritmo a forza bruta che enumeri tuttele 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 la programmazione dinamica e applicabile se vale il principio della sot-tostruttura ottima. Dimostriamo tale proprieta nel seguente teorema:
69
Theorem 6.2 Siano X = 〈x1, . . . , xm〉 e Y = 〈y1, . . . , yn〉 due sequenze e Z =〈z1, . . . , zk〉 una LCS di X e Y . 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 essere allungata aggiungendo xm e troveremmo una nuovasottosequenza comune tra X e Y piu lunga di Z, contro l’hp del teorema che diceche Z e LCS. Quindi deve essere zk = xm(= yn). A questo punto 〈z1, . . . , zk−1〉 eLCS 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 unLCS di lunghezza maggiore 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〉 e Y = 〈y1, . . . , yn〉. D’altronde non puo esistere in 〈x1, . . . , xm−1〉e Y = 〈y1, . . . , yn〉 una sottosequenza W con piu di k elementi, altrimenti essasarebbe anche sottosequenza di X e Y , quindi Z di k elementi non sarebbe LCSdi X e Y . Cosı Z e una LCS di 〈x1, . . . , xm−1〉 e Y .
3. simmetrico al punto precedente.
70
Il teorema precedente ci dice come analizzare i sottoproblemi per ottenere la solu-zione al problema dato:
1. se xm = yn allora cerchiamo un LCS di 〈x1, . . . , xm−1〉 e 〈y1, . . . , yn−1〉 e unavolta trovata l’allunghiamo con 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 a soluzione migliore la quale e anche quella per X e Y .
Esempio Calcoliamo una LCS tra X = 〈A, B, C, B, D, A,B〉 e Y = 〈B, D, C, A, B, A〉.E’ facile rendersi conto che molti sottoproblemi si sovrappongono, ovvero puo capi-tare di dover ricalcolare piu volte una LCS tra medesime sequenze.
Ovviamente se una delle due sequenze ha lunghezza 0 allora la LCS ha lunghezza0. 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 = yjmaxC[i, j − 1], C[i− 1, j], altrimenti
Quindi un primo algoritmo risolutivo computa la matrice procedendo ricorsivamentetop-down. Possiamo risparmiare le chiamate ricorsive e procedere nella compilazionedella matrice secondo uno schema bottom up tenendo conto che la prima riga e laprima colonna valgono zero.
Vediamo come con il nostro esempio dato sopra.
Esercizio Determinare una LCS tra 〈1, 0, 0, 1, 0, 1, 0, 1〉 e 〈0, 1, 0, 1, 1, 0, 1, 1, 0〉La Figura 15 mostra dell’algoritmo in versione bottom-up: 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).Nota: nello pseudolinguaggio consideriamo che le componenti degli array siano indi-cizzate a partire da 0 e che le lettere che realmente fanno parte della sequenza sianomemorizzate a partire dall’indice 1.
71
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-1])7. then c[i,j]=c[i-1,j]8. else c[i,j]=c[i,j-1]
Figura 15: Algoritmo per LCS calcolata in versione bottom-up
Un’ulteriore analisi dei valori da porre nelle celle C[i, j], se i, j > 0 mostra chepossiamo ottenere la risposta facendo uso di una matrice di sole due righe.
Nel seguente algoritmo la matrice C ha due righe, quella di indice 0 e quella di indice1. 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
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]
Figura 16: Algoritmo per LCS ottimizzato
Infine si osservi che a patto di complicare ulteriormente l’algoritmo e possibile dareun’implemntazione che utilizzi solo un vettore e 2 variabili.
Nei problemi di ottimizzazione determinare il valore ottimo e solo uno degli aspetti.L’altro e determinare una soluzione ottima.
Vediamo come determinare una sottosequenza ottima. A tale scopo e necessario te-nere in memoria l’intera matrice C. Se applichiamo l’algoritmo illustrato in Figura 15al problema di trovare la massima lunghezza di una LCS tra 〈A, B, C, B, D, A,B〉 e
72
〈B, D, C, A, B, A〉 compileremo la seguente matrice:
∅ B D C A B A
∅ 0 0 0 0 0 0 0A 0 0 0 0 1 1 1B 0 1 1 1 1 2 2C 0 1 1 2 2 2 2B 0 1 1 2 2 3 3D 0 1 2 2 2 3 3A 0 1 2 2 3 3 4B 0 1 2 2 3 4 4
Da questa matrice e possibile procedendo a ritroso stabilire una soluzione ottima. Ilmodo di procedere a ritroso e dettato dal modo che abbiamo impiegato per costruirela matrice.
Esercizio Scrivere un programma che date 2 sequenze di caratteri ASCII (tipo char
del C) computi la lunghezza di una LCS e stampi una LCS.Esercizio Variante del precedente esercizio: il programma deve stampare l’elencodi tutte le LCS di due sequenze date.
73
7 Grafi
Definizione di grafo:
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) ∈ E vale (y, x) ∈ E si parla di grafo non orientato, altrimenti il grafo si consideraorientato.
Dato (x, y) ∈ E diremo che (x, y) incide sui vertici x e y. Per grafi non orientati si dice che x e ysono adiacenti.
Un cammino 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 cammino e semplice se i vertici sono distinti.
Un cammino che inizia e finisce nello stesso nodo e un ciclo. Il ciclo e semplice se i nodi intermedidel cammino sono tutti distinti tra loro.
Un grafo non orientato e connesso se esiste un cammino tra ogni coppia di nodi del grafo. Un grafoorientato e fortemente connesso se esiste un cammino orientato tra ogni coppia di vertici del grafo.
7.1 Come 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. In Figura 17 un esempio di codice che permette di memorizzare gli archi di un grafocome lista.
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. In figura 18 un esempio di codice in Linguaggio C chemanipola un grafo mediante liste di adiacenza.
Liste di incidenza: si elencano gli archi in una struttura, come nel primo caso, ed inoltre perogni nodo v si mantiene una lista che elenca gli archi incidenti su v. In Figura 19 un esempio diprogramma C che manipola un grafo mediante liste di incidenza.
matrice di adiacenza: matrice M di dimensione |V | × |V |, indicizzata dai nodi del grafo, taleche M [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 camminidi lunghezza 1 tra i nodi, per trovare nodi a distanza 2 basta moltiplicare la matrice per se stessa,
74
#include<stdio.h>#include<stdlib.h>typedef structint Info; Nodo;typedef structint from, to; Arco;
int main(void)int nroNodi, nroArchi,i;Arco *listaArchi;Nodo *listaNodi;
scanf("%d%d",&nroNodi, &nroArchi);listaNodi=malloc(nroNodi*sizeof(Nodo));listaArchi=malloc(nroArchi*sizeof(Arco));for(i=0;i<nroArchi;i++)
printf("Nodo di uscita: ");scanf("%d", &listaArchi[i].from);printf("Nodo di entrata: ");scanf("%d", &listaArchi[i].to);
for(i=0;i<nroArchi;i++)printf("(%d,%d)\n",listaArchi[i].from,listaArchi[i].to);
return 0;
Figura 17: Esempio di Grafo manipolato con lista di archi
75
#include<stdio.h>#include<stdlib.h>typedef structint Info, *listaNodiAdiacenti, nroAdiacenti; Nodo;
int main(void)int nroNodi, i,j;Nodo *listaNodi;
scanf("%d",&nroNodi);listaNodi=malloc(nroNodi*sizeof(Nodo));
for(i=0;i<nroNodi;i++)printf("Nro nodi adiacenti al nodo %d:",i);scanf("%d",&listaNodi[i].nroAdiacenti);listaNodi[i].listaNodiAdiacenti=malloc(listaNodi[i].nroAdiacenti*sizeof(int));for(j=0; j<listaNodi[i].nroAdiacenti; j++)
printf("Nodo adiacente al nodo %d: ",i);scanf("%d", &listaNodi[i].listaNodiAdiacenti[j]);
for(i=0;i<nroNodi;i++)printf("Lista dei nodi adiacenti al nodo %d:\t",i);for(j=0; j<listaNodi[i].nroAdiacenti; j++)
printf("%d; ",listaNodi[i].listaNodiAdiacenti[j]);printf("\n");
return 0;
Figura 18: Esempio di Grafo manipolato con liste di adiacenza
76
#include<stdio.h>#include<stdlib.h>typedef struct int info, *listaDiIncidenza, dimListaDiIncidenza; Nodo;typedef structint from, to; Arco;int main(void)
int nroNodi, nroArchi,i,j,pos;Arco *listaArchi;Nodo *listaNodi;scanf("%d%d",&nroNodi, &nroArchi);/* Alloca spazio per la lista dei nodi */listaNodi=malloc(nroNodi*sizeof(Nodo));/*Inizializza il campo dimListaDiIncidenza a zero */for(i=0;i<nroNodi;i++) listaNodi[i].dimListaDiIncidenza=0;listaArchi=malloc(nroArchi*sizeof(Arco));for(i=0;i<nroArchi;i++)
printf("Nodo di uscita: ");scanf("%d", &listaArchi[i].from);/* NOTA BENE: consideriamo grafi orientati */listaNodi[listaArchi[i].from].dimListaDiIncidenza++;printf("Nodo di entrata: ");scanf("%d", &listaArchi[i].to);
for(i=0;i<nroNodi;i++)if (listaNodi[i].dimListaDiIncidenza>0)
/* dichiara il vettore che rappresenta la lista di Incidenza */listaNodi[i].listaDiIncidenza=malloc(listaNodi[i].dimListaDiIncidenza*sizeof(int));
else listaNodi[i].listaDiIncidenza=NULL;
/* per ogni nodo costruisce la lista di incidenza */for(i=0;i<nroNodi;i++)pos=0;for(j=0;j<nroArchi;j++)if (listaArchi[j].from == i )
/* se il j-esimo arco parte dal nodo i,allora si memorizza che l’arco j-esimo esce dal nodo i-esimo */
listaNodi[i].listaDiIncidenza[pos]=j;pos++;
printf("Lista Archi: \n");for(i=0;i<nroArchi;i++) printf("(%d,%d)\n",listaArchi[i].from,listaArchi[i].to);printf("Informazioni sui nodi:\n");for(i=0; i<nroNodi; i++)printf("Nodo %d ha %d archi uscenti: ", i,listaNodi[i].dimListaDiIncidenza);for(j=0;j<listaNodi[i].dimListaDiIncidenza;j++) printf("%d ", listaNodi[i].listaDiIncidenza[j]);printf("\n");
return 0;
Figura 19: Grafo manipolato con liste di incidenza
77
e cosi’ via per trovare nodi connessi tra loro con cammini di lunghezza 3, 4 etc. In Figura 20 unesempio di programma C per la gestione di un grafo mediante matrice di adiacenza.
matrice di incidenza: matrice M di dimensione |V |x|E|, dove le righe sono indicizzate dai nodi,le colonne dagli archi. Se il grafo orientato contiene un arco (i, j) allora lungo una certa colonnac della matrice che rappresenta l’arco (i, j) varra che M [i, c] = 1, M [j, c] = −1 e altrove lungo lacolonna i valori saranno 0. M [i, c] = 1, denota che l’arco e uscente da i, M [j, c] = −1 denota chel’arco e entrante in j. Per grafi non orientati si usa semplicemente 1 per denotare i nodi su cui l’arcoassociato alla colonna c incide. In Figura 21 un esempio in linguaggio C.
78
#include<stdio.h>#include<stdlib.h>int main(void)int nroNodi, nroArchi,*matrice, from, to;
scanf("%d%d",&nroNodi,&nroArchi);matrice=malloc(nroNodi*nroNodi*sizeof(char));
/*Inizializzazione della matrice */for (from=0;from< nroNodi;from++)
for(to=0;to<nroNodi;to++)matrice[from*nroNodi+to]=’0’;
doprintf("Nodo Uscente:");scanf("%d",&from);printf("Nodo Entrante:");scanf("%d",&to);matrice[from*nroNodi+to]=’1’;nroArchi--;
while (nroArchi>0);
printf("Matrice di Adiacenza:\n");for (from=0;from< nroNodi;from++)
for(to=0;to<nroNodi;to++)printf("%c ", matrice[from*nroNodi+to]);
printf("\n");return 0;
Figura 20: Grafo manipolato mediante matrice di adiacenza
79
#include<stdio.h>#include<stdlib.h>int main(void)int nroNodi, nroArchi,*matrice, from, to,i;
scanf("%d%d",&nroNodi,&nroArchi);matrice=malloc(nroNodi*nroArchi*sizeof(int));
/*Inizializzazione della matrice */for (from=0;from< nroNodi;from++)
for(to=0;to<nroArchi;to++)matrice[from*nroArchi+to]=0;
for(i=0;i<nroArchi;i++)printf("Nodo Uscente:");scanf("%d",&from);printf("Nodo Entrante:");scanf("%d",&to);matrice[from*nroArchi+i]=1;matrice[to*nroArchi+i]=-1;
printf("Matrice di Incidenza:\n");for (from=0;from< nroNodi;from++)
for(to=0;to<nroArchi;to++)printf("%d ", matrice[from*nroArchi+to]);
printf("\n");return 0;
Figura 21: Grafo manipolato mediante matrice di incidenza
80
7.2 Visite di Grafi
Visitare un grafo significa accedere ai nodi di un grafo G = (V, E) dato a partire da un nodo sorgentes ∈ V .
Ci sono due startegie per visitare i nodi di un grafo: visita in ampiezza (breadth-first) e visita inprofondita (depth-first).
7.3 Visita in ampiezza
Consideriamo un grafo G = (V, E), orientato o meno, ed un suo nodo s ∈ V .
Visitare in ampiezza G a partire da s significa
accedere a tutti i nodi r1, . . . , rn raggiungibili direttamente da s. A questo punto per ogni nodori appartenenente alla lista di nodi r1, . . . , rn si accede ai nodi direttamente raggiungibili dari
purche non siano gia stati precedentemente raggiunti.
Si viene cosı a determinare una seconda lista di nodi t1, . . . , tm: sono quelli raggiungibili das attraversando due archi. Si procede iterativamente in questa maniera costruendo una nuovalista di nodi a partire dai nodi in t1, . . . , tm sino ad aver raggiunto tutti i nodi del grafo:questo corrispondera ad ottenere una lista vuota.
Vediamo un esempio.
Per tenere conto dei nodi gia visitati e necessario marcarli, cioe sapere se un certo nodo e gia statovisitato precedentemente. Per rendere piu chiara la dinamica dell’algoritmo e utile marcare i nodicon i colori nero, grigio e bianco.
Inizialmente tutti i vertici sono bianchi, cioe non marcati. Il vertice designato come sorgente e ilprimo ad essere scoperto e viene marcato di grigio. Tutti i suoi vicini, cioe i vertici raggiungibili das mediante un arco uscente ad s, che siano bianchi, vengono scoperti, marcati di grigio e accodatiad una lista contenente nodi grigi. A questo punto dato che tutti i vicini di s sono stati scopertimarchiamo s di nero. L’algoritmo procede come su s prendendo il primo nodo grigio dalla lista deinodi grigi. Quanto abbiamo appena descritto e un modo di esplorare il grafo che fa uso di un’unicalista. I nodi che progressivamente vengono scoperti piuttosto che andare a formare una nuova listavengono accodati all’unica lista di nodi grigi. La lista di nodi grigi ha quindi un capo ed una codadetti tecnicamente testa della lista e coda della lista. Quando una struttura dati quale la listadei nodi grigi viene manipolata come illustrato sopra la lista viene detta coda (queue, in inglese),per enfatizzare il fatto che nella struttura i dati vengono inseriti da un estremo (la coda) e vengonoprelevati dall’altro (il capo).
Quindi i nodi grigi possono essere considerati nodi di frontiera, cioe nodi scoperti ma i cui vicinipotrebbero non ancora essere stati esplorati. Si noti che nell’esecuzione dell’ algoritmo un nodo da
81
bianco diventa grigio e non puo piu tornare bianco. Analogamente un nodo grigio che diventa neronon puo piu tornare grigio o bianco.
Un nodo che diventa nero e un nodo che viene considerato esplorato ed e sinonomo del fatto che chetutti i nodi appartenenti alla sua lista di adiacenza sono stati scoperti, cioe sono diventati grigi.
Dato che di un nodo da esplorare interessano i suoi vicini, ne segue che l’algoritmo lavora efficien-temente quando il grafo e rappresentato mediante lista di adiacenza. A questo punto, dato che (i)esplorare un nodo significa scandirne la lista di adiacenza, (ii) tale scansione e fatta al piu una volta(iii) la somma delle lunghezze delle liste di adiacenza e il numero di archi (iv) inizialmente dobbiamomarcare di bianco tutti i nodi, segue che il tempo e proporzionale alla somma tra numero di nodi earchi di G e quindi lineare nell’ampiezza della rappresentazione a liste di adiacenza di G.
Durante l’esplorazione e possibile tenere conto degli archi del grafo che vengono attraversati. Taliarchi vanno a costituire un albero detto di breadth-first. Si osservi che in base al modo di procedere laricerca definisce in modo naturale l’albero dei nodi raggiungibili da s. Per ogni nodo v raggiungibileda s il percorso nell’albero dei nodi corrisponde al percorso piu breve da s a v, cioe il percorsocontenente il minor numero di archi.
Di seguito diamo di visita in profondita in dettaglio.
Algoritmo VisitaBFS(grafo G, vertice s)-> albero
1. Rendi tutti i nodi marcati di bianco;
2. Sia T l’albero formato dal solo nodo s;
3. Sia F l’insieme vuoto;
4. marca di grigio il vertice s
5. aggiungi s in coda a F
6. while (F non e’ vuoto ) do
7. estrai da F il primo vertice u;
8. visita il vertice u;
9. for each ( arco (u,v) di G ) do
10. if (v e’ bianco) then
11. marca v di grigio
12 aggiungilo in coda a F;
12. rendi u padre di v in T
(cioe metti in T l’arco (u,v));
13. marca di nero u
14. return T
Esercizio Codificare in C l’algoritmo VisitaBFS. In particolare bisogna decidere come tenere contodella marcatura dei nodi. Occorre anche memorizzare gli archi che formano l’albero di breadth-first.Esercizio Estendere l’algoritmo dell’esercizio precedente affiche stampi il percorso di ogni nodo delgrafo raggiungibile dalla sorgente;
82
Esercizio Modificare il programma svolto nell’esercizio precedente affinche di ogni nodo del grafostampi il percorso. Si osservi che non e detto che tutti i nodi del grafo siano nell’albero breadth-first.Infatti mancano quelli che dalla sorgente non sono raggiungibili. In pratica si tratta di determinarequali siano i nodi che dalla sorgente sono irraggiungibili.
83
7.4 Visita in profondita
Consideriamo un grafo G = (V, E) orientato o meno ed un suo nodo s ∈ V . Visitare in profonditaG a partire da s significa
accedere a tutti i nodi r1, . . . , rn direttamente raggiungibili da s. A questo punto si marca sdi nero (nodo esplorato). Si considera l’ultimo nodo nella lista 〈r1, . . . , rn〉. Se da rn sonoraggiungibili nodi non marcati di nero allora si aggiungono tutti alla lista, si marca rn dinero e si prosegue come illustrato considerando l’ultimo nodo. Se da rn non sono raggiungibilinuovi nodi allora si marca di nero rn, lo si cancella dalla lista. Si cerca a ritroso nella lista ilprimo nodo che non sia marcato di nero, cancellando i nodi marcati di nero. Se tutti i nodinella lista sono marcati di nero allora ovviamente la lista diventa vuota e la visita termina,altrimenti trovato un nodo non nero si procede come mostrato per rn.
Si osservi come in questo caso la procedura esplori l’ultimo nodo inserito nella lista, cercando discoprire sempre nuovi nodi. Quando non e piu possibile la procedura torna indietro (backtrack) suipropri passi cercando nuovi nodi da scoprire a partire da un nodo precedentemente considerato.
Si osservi come la lista dei nodi venga trattata secondo uno schema diverso rispetto allo schema acoda del caso precedente. Qui un unico estremo della lista funge a punto di entrata e uscita.Quando una struttura dati viene manipolata inserendo i dati dallo stesso punto da cui vengono fattiuscire e viceversa si dice che la struttura dati e una pila (stack, in inglese). Dato che lo stackpossiede uno stesso estremo sia per l’inserimento che la cancellazione dei dati, segue che il dato cheviene cancellato e l’ultimo ad essere entrato, ecco perche si dice che in uno stack vale il principio dellast-in first-out.
L’algoritmo descritto sopra puo piu compattamente essere descritto come procedura ricorsiva (Figu-ra 22).
Una procedura iterativa basata su una lista di nodi e data in Figura 23.
Si osservi come tale algoritmo formalizzi direttamente la descrizione data a inizio paragrafo.
In tale algoritmo possiamo notare che:1. si fa uso dei colori bianco e nero;2. il ciclo for in linea 11 si occupa di aggiungere nodi non marcati di nero alla lista;3. in riga 9 si stabilisce se la lista dei nodi grigi sia o meno estendibile con nuovi nodi non neri.
Concludiamo osservando che esiste un algoritmo alternativo a quello di Figura 23. Nella descrizionedata a inizio paragrafo si dice:
Se da rn sono raggiungibili nodi non marcati di nero allora si aggiungono tutti allalista, si marca rn di nero...
Questo corrisponde alle righe 11-14 dell’algoritmo. La variante che proponiamo consiste nell’ag-giungere alla lista solo un successore alla volta. I successori aggiunti sono quelli NON ANCORA
84
Algoritmo visitaDFS(grafo G, vertice s)1. Sia T l’albero vuoto;2. Colora di bianco tutti i vertici;3. VisitaDFSRicorsiva(grafo G, vertice s, albero T);13. return T
Algoritmo VisitaDFSRicorsiva(grafo G, vertice v, albero T)1. Marca di grigio e visita il vertice v;2. Per ogni arco (v,w) in G esegui:3. if (w e marcato bianco) then4. aggiungi l’arco (v,w) a T5. VisitaDFSRicorsiva(grafo G, vertice w, albero T)6. colora di nero v
Figura 22: Visita in profondita: algoritmo in versione ricorsiva
Algoritmo VisitaDFS(grafo G, vertice s)-> albero1. Rendi tutti i nodi marcati di bianco;2. Sia T l’albero formato dal solo nodo s;3. Sia F l’insieme vuoto;4. aggiungi s in coda a F5. while (F non e’ vuoto ) do6. sia u l’ultimo vertice in F;7. visita il vertice u;8. marca il vertice u di nero9. if (esiste arco (u,v) di G tale che v non e marcato di nero)10. then11. for each ( arco (u,v) di G ) do12. if (v non e’ marcato nero)13. then14. aggiungi v in testa a F;15. sia t l’ultimo nodo in F;16. aggiungi l’arco (u,t) in T17. else18. while (ultimo vertice di F e nero)19. do estrai ultimo vertice di F20. return T
Figura 23: Visita in profondita: algoritmo in versione iterativa
85
SCOPERTI. Questo significa che a differenza del precedente algoritmo un nodo compare nella listaal massimo una volta. Un nodo cambia la sua marcatura in nero per il fatto di essere nella listadei nodi. Viene cancellato dalla lista dei nodi quando tutti i suoi vicini sono gia stati esplorati, cioenessuno dei vicini e bianco.
Anche questo algoritmo puo essere agevolmente descritto con una marcatura a due colori.
Algoritmo VisitaDFS(grafo G, vertice s)-> albero
1. Rendi tutti i nodi marcati di bianco;
2. Sia T l’albero vuoto;
3. Sia F l’insieme vuoto;
4. marca come nero il vertice s
5. aggiungi s in coda a F
6. visita s
6. while (F non e’ vuoto ) do
7. sia u l’ultimo vertice in F;
8. marca il vertice u di nero
9. if (esiste arco (u,v) di G tale che v non e marcato di nero)
10. then
11. aggiungi v in testa a F;
12. visita v
13. aggiungi l’arco (u,v) in T
14. else
15. estrai ultimo vertice di F
16. return T
Concludiamo con la seguente osservazione. Per quanto riguarda la visita in profondita la nozione dinodo sorgente non e rilevante come nel caso della visita in ampiezza. Quello a cui si e interessati ecominciare l’esplorazione da un nodo bianco, cioe non visitato. Se al termine dell’esplorazione delgrafo ci sono nodi bianchi, cioe inespolari, cioe irraggiungibili dal nodo da cui si era partiti, alloral’esplorazione riparte da uno dei nodi bianchi. L’esplorazione quindi si considera terminata quandonel grafo non ci sono piu nodi bianchi.
Esercizio. Riscrivere gli algoritmi dati per fare una visita in profondita completa.
L’effetto e quindi quello di una iterazione della visita in profondita da piu nodi sorgenti che porta allacostruzione di un singolo albero per ogni nodo sorgente. Il risultato e che i dati in T rappresentanonel caso generale una serie di alberi, cioe una foresta.
86
7.5 Cammini minimi in grafi pesati: l’algoritmo di Dijkstra
Ci sono problemi in cui e necesario associare ad ogni arco un peso o costo. In tal caso si parla di grafipesati e per cammino di costo minimo non si intende un cammino che minimizza il numero di archiattraversati ma un cammino che minimizza il totale della somma dei costi degli archi attraversati.
L’algoritmo di Dijkstra permette di trovare il percorso minimo da un nodo sorgente verso tutti inodi di un grafo pesato in cui i pesi degli archi siano non negativi. L’algoritmo e una variantedella procedura di visita in ampiezza. L’input dell’algoritmo e un grafo pesato ed un nodo sorgente.L’output associa ad ogni nodo v del grafo il costo minimo del cammino dalla sorgente a v e un insiemedi archi che determinano un albero che contiene, a partire dalla sorgente, il percorso migliore versoogni nodo del grafo raggiungibile dalla sorgente.
Anche in questo algoritmo marchiamo i nodi come bianchi, grigi o neri. I nodi neri sono i nodiper cui si e gia determinata la distanza minima dalla sorgente; i nodi grigi sono quei nodi che sonoraggiungibili da un nodo marcato di nero. Questo implica che un nodo grigio e un nodo che appartienead una delle liste di adiacenza dei nodi neri e che per un nodo grigio e stato determinato un percorsodalla sorgente ma non e detto che sia ottimo. I nodi bianchi non sono ancora stati scoperti, quindinon fanno parte di alcuna delle liste di adiacenza dei nodi neri.
Cio che distingue l’algoritmo di Dijkstra dall’algoritmo di ricerca in ampiezza e il criterio usato perselezionare il nodo grigio la cui lista di adiacenza deve essere scandita.
L’algoritmo associa ad ogni nodo v del grafo una distanza, misurata rispetto al costo degli archiche costituiscono il percorso dalla sorgente s al nodo v. Di seguito con d(v) indicheremo la distanzada s associata a v. Tale distanza inizialmente viene posta a zero per il nodo s e a infinito per tuttigli altri nodi, quindi:
d(s) = 0, d(v) =∞ per ogni nodo v ∈ V \ s
Questo significa che inizialmente l’algoritmo suppone che tutti i nodi abbiano distanza infinita da s.
La sorgente e il primo nodo a diventare grigio, gli altri sono bianchi.
Si scandisce la lista di adiacenza di s e si aggiornano le distanze dei nodi che in essa vi compaiono.Tali nodi diventano grigi, s diventa nero.
Si osservi come i nodi non raggiunti restino bianchi e con distanza infinita, mentre i nodi grigi e neri,i nodi raggiunti, abbiano una distanza finita. I nodi neri sono i nodi la cui lista di adiacenza e statascandita e per essi il percorso ottimo da s e stato calcolato. Dei nodi grigi la lista di adiacenza none stata scandita; si ha un valore per un pecorso a partire da s ma non si e ancora stabilito se sial’ottimo.
La scelta del nodo grigio di cui scandire la lista di adiacenza e fatta secondo il seguente criterio:
si sceglie il nodo grigio con distanza minore da s.
87
La lista di adiacenza del nodo grigio viene scandita ed il nodo diventa nero.
Osservazione: dato che il nodo selezionato ha distanza minima da s la sua distanza da s non necessitadi essere aggiornata.
Se ne deduce che i nodi neri sono i nodi di cui non e piu necessario verificare la distanza da s perchegia sappiamo essere minima.
Per ogni nodo r nella lista di adiacenza del nodo grigio t appena selezionato si eseguono le seguentioperazioni:
se k e la distanza tra t e s (cioe d(t) = k) e l’arco (t, r) pesa z allora affermiamo che esisteun percorso da s a r che passa per t di peso d(t) + z. A questo punto la distanza d(r) vieneaggiornata col valore d(t) + z se tale valore e inferiore a quello attualmemte presentein d(r).
Dopo aver scandito la lista di adiacenza di t si annerisce t e si ripete il procedimento fino a quandoci sono nodi grigi da selezionare.
Si noti quindi come durante l’esecuzione, per ogni nodo v del grafo, il valore in d(v) contenga semprela minor distanza sa s relativamente a quei percorsi finora analizzati, cioe relativamente a quegliarchi per ora attraversati.
Per quanto riguarda i nodi grigi, si noti anche che il percorso che l’algoritmo trova a partire da sverso di loro e costituito da archi che collegano tra loro nodi neri. Se ne deduce che se un percorsoche conduce ad un nodo grigio non e ottimo allora non lo e a causa dell’ultimo arco, cioe quelloentrante nel nodo grigio.
Riassumendo, per ogni nodo l’algoritmo produce il miglior percorso a partire da s perche durante lasua esecuzione vengono soddisfatte le due seguenti condizioni:
1. per ogni nodo nero la distanza stabilita e ottima;
2. per ogni nodo non-nero la distanza stabilita e ottima relativamente agli archi attraversati.
Di seguito formalizziamo l’algoritmo appena descritto:
Algoritmo Dijkstra(Grafo G, vertice s)->albero
1. per ogni vertice v in G poni d(v) a infinito e padre[v]=nil;
2. marca tutti i nodi di bianco;
3. poni d[s]=0 e padre[s]=s;
4. marca s di grigio;
5. finche ci sono nodi grigi esegui:
6. sia v il nodo grigio con d[v] piu piccolo;
7. marca v di nero;
88
8. per ogni vertice x nella lista di adiacenza di v esegui:
9. marca x di grigio
10. se d[x]> d[v]+costo(v,x)
11. allora
12. d[x]=d[v]+costo(v,x)
13. padre[x]=v;
14. return padre
Per quanto riguarda l’analisi di complessita in tempo, ad ogni iterazione viene eseguita una ricerca diminimo. Tale ricerca viene effettuata tante volte quanti sono i nodi del grafo. Viene poi scandita lalista di adiacenza del nodo. La lunghezza totale delle liste di adiacenza e il numero di archi del grafo.Tutte le altre operazioni di inizializzazione dipendono anch’esse dal numero di nodi e richiedonocomplessivamente tempo proporzionale al numero di nodi del grafo. Quindi il tempo della procedurae quadratico nel numero di nodi del grafo.
Si osservi che se le distanze minime vengono memorizzate in una struttura dati opportuna (piusofisticata di un vettore lineare come abbiamo supposto noi) il tempo diventa O(|E|+ |V | log |V |).
7.6 Raggiungibilita tra ogni coppia di nodi
Questa parte contiene le idee di base per sviluppare algoritmi che calcolino il costo mnimo delcammino tra ogni coppia di nodi di un grafo.
Il problema di determinare l’esistenza di un qualche percorso tra ogni coppia di nodi di un grafoe chiaramente un problema piu semplice rispetto a quello di calcolare un percorso ottimo tra ognicoppia di nodi. Dati due nodi x e y di un grafo G = (V, E), determinare se esiste un cammino tra xe y significa stabilire se esiste una sequenza di nodi x = v0, v1, . . . , vn = y tale che (vi, vi+1) ∈ E peri = 0, . . . , n− 1.
Per risolvere questo tipo di problemi si considera la rappresentazione di grafi mediante matrice diadiacenza. Come vedremo la determinazione dell’esistenza di cammini tra ogni coppia di nodi di ungrafo dato corrispondera ad una elaborazione algebrica della matrice di adiacenza ed in particolareal suo elevamento a potenza. Per renderci conto del ruolo giocato dalla moltiplicazione di matricianalizziamo un problma ancora piu semplice:
per ogni coppia di nodi x e y di un grafo dato vogliamo determinare l’esistenza di camminidi lunghezza al massimo 2, cioe cammini tali che per raggiungere y a partire da x si debbanoattraversare al massimo due archi, transitando quindi, al massimo, per un nodo intermedio.
Quanto detto sopra puo essere parafrasato dicendo che
per ogni coppia di nodi x e y di un grafo dato vogliamo determinare l’esistenza di un camminoda x a y del tipo x, z, y, dove z e nodo intermedio, cioe tale che (x, z) e (z, y) sono archi delgrafo dato.
89
Quindi, affinche da x sia raggiungibile y con un cammino di lunghezza al piu 2 deve accadere che
nel grafo dato esiste l’arco (x, y)
oppure
esiste un nodo z tale che (x, z), (z, y) ∈ E.
Quindi se v1, . . . , vn sono gli archi del grafo deve valere che
(x, v1), (v1, y) ∈ E, oppure
(x, v2), (v2, y) ∈ E, oppure
. . .
(x, vn), (vn, y) ∈ E
Vediamo cosa questo significa in termini di matrice di adiacenza su un esempio conceto. Per comoditain Figura 24 riportiamo 2 copie della matrice di adiacenza
a 1 2 3 4 5 6da1 0 0 0 0 0 02 1 1 0 0 0 03 0 1 0 0 0 14 1 0 0 0 1 05 0 1 0 0 0 06 0 1 1 0 0 0
a 1 2 3 4 5 6da1 0 0 0 0 0 02 1 1 0 0 0 03 0 1 0 0 0 14 1 0 0 0 1 05 0 1 0 0 0 06 0 1 1 0 0 0
Figura 24: matrice di adiacenza di un grafo orientato
Dal nodo 3 c’e un cammino di lunghezza 2 al nodo 1 sse
• c’e un arco dal nodo 3 al nodo 1 oppure
• c’e un arco dal nodo 3 al nodo 2 e dal nodo 2 al nodo 1, oppure
• c’e un arco dal nodo 3 al nodo 3 e dal nodo 3 al nodo 1, oppure
• c’e un arco dal nodo 3 al nodo 4 e dal nodo 4 al nodo 1, oppure
• c’e un arco dal nodo 3 al nodo 5 e dal nodo 5 al nodo 1, oppure
90
Questo corrisponde a moltiplicare la terza riga con la prima colonna della matrice di adiacenzasecondo la nozione di prodotto riga per colonna. Quindi e sufficiente che uno degli addendi delprodotto riga per colonna valga 1 affinche ci sia un cammino di lunghezza 2.
La generalizzazione e immediata:
elevare al quadrato la matrice di adiacenza produce come risultato una matrice tale che la celladi coordinate (i, j) vale 1 sse esiste un cammino di lunghezza minore o uguale a 2 tra il nodo ied il nodo j.
Ne segue che elevando alla k-esima potenza la matrice di adiacenza M di un grafo dato si ottiene lamatrice Mk tale che
Mk[i][j] = 1 sse essste un cammino da i a j di lunghezza minore o uguale a k.
Se ci sono n nodi, allora essite un cammino da un nodo x ad un nodo y di un grafo dato G purcheMn[i][j] = 1. Quindi per determinare la raggiungibilita tra qualsiasi coppia di nodi di un grafo G esufficiente calcolare la potenza n-esima della sua matrice di adiacenza M .Ovviamente la matrice Mn puo a sua volta essere interpretata come la matrice di adiacenza di unnuovo grafo, usualmente denotato con G∗, detto la chiusura transitiva di G: il grafo G∗ contienel’arco (x, y) sse in G esiste un cammino da x a y.
91
8 Array e Allocazione della Memoria
Il modo piu frequente di dichiarare un array e attraverso una allocazione statica della memoria,esempio:
int x[20][30];
In questo caso le dimensioni di x sono costanti, decise a priori dal programmatore e non dipendonodai dati di input.
D’altronde per taluni problemi puo essere opportuno poter dichiarare gli array cosı che la loro di-mensione dipenda dai dati di input. In tal caso si parla di allocazione dinamica della memoriadato che il numero di celle di cui e composto l’array non e noto a priori al programmatore e perdifferenti esecuzioni del programma l’array puo assumere dimensioni differenti. Versioni recenti dicompilatori C mettono a disposizione questa caratteristica. E’ quindi corretto il seguente frammentodi programma:
int x;
scanf("%d",&x);
int v[x][x*x];
in cui le dimensioni di v dipendono dalla variabile x. Si osservi come non sia possibile determinare apriori le dimensioni dell’array, le quali potranno variare ad ogni esecuzione del frammento di codice.Si osservi anche come diventi quindi possibile mischiare dichiarazioni di variabili e istruzioni. Datoche gli array possono essere usati come parametri attuali di funzioni ed essendoci in tal caso piccoledifferenze tra array monodimensionali e pluridimensionali trattiamo i due casi separatamente.
Gli array monodimensionali (vettori) sono un caso particolare di quelli pluridimensionali. Per quantoriguarda i vettori allocati dinamicamente non ci sono differenze rispetto al loro utilizzo come prametriformali nelle funzioni. Consideriamo il frammento
int x;
scanf("%d",&x);
int v[x];
f(v,x);
La funzione f definita come:
void f(int v[],int x)
.....
92
e perfettamente adatta a trattare ogni vettore di interi indipendentemente dalla lunghezza delparametro attuale che gli viene passato. Si osservi che anche
void f(int v[50],int x)
.....
va bene, dato che la costante 50 non viene considerata in fase di compilazione e neppure di esecuzione.Deduciamo che non vi e alcun cambiamento nel trattamento dei vettori allocati dinamicamente.
Per quanto riguarda le matrici bi o pluridimensionali dei cambiamenti ci sono. Di un parametroformale di tipo matrice occorre dichiarare la dimensione di tutte le componenti ad eccezione dellaprima. Quindi se una funzione ha come parametro formale una matrice bidimensionale occorredichiarare da quante colonne e composta:
void f(int v[][50],int x)
.....
Questa funzione puo essere chiamata passando una matrice di qualsivoglia righe ma con 50 colonne.La necessita di conoscere il numero di colonne del parametro formale e legato a come una matricee realmente memorizzata: essa e un vettore di elementi memorizzati per righe. Quindi per saperedove, ad esempio, inizia il primo elemento della riga di indice 2 occorre sapere quante sono le colonnedella matrice. Quindi per sapere dove e memorizzato l’elemento alle coordinate (i, j) della matricebasta applicare la formula
i * numero di colonne della matrice + j
Quindi, tornando all’esempio, l’assegnamento
void f(int v[][50],int x)
....
z= v[3][8]
....
prevede di applicare la formula 3 ∗ 50 + 8 per ritrovare l’elemento posto logicamente alle coordinate(3, 8). Attenzione che se il parametro attuale corrispondente a v non e una matrice con 50 colonne, ilprogramma verra comunque compilato ma in fase di esecuzione non si comportera come ci si aspetta.
Esercizio. Come prova di quanto detto sopra, scrivete una funzione che debba stampare a videol’elemento di posto (5,9) di una matrice con 50 colonne. Fate 2 chiamate a f: la prima passando
93
come parametro attuale una matrice con 50 colonne, la seconda passando una matrice di 20 colonne.Vedrete che in questo secondo caso non viene stampato l’elemento che ci si aspetta.
Per quanto detto dovendo, ad esempio, stampare a video la diagonale principale di una matrice qua-drata, non sapremmo come scrivere un’unica funzione. Abbiamo il problema di rendere parametricoil numero di colonne. Abbiamo alcuni modi diversi per raggiungere questo obiettivo.
Il primo modo e quello di scrivere una intestazione come segue:
void f(int x,int v[][x])
in cui il numero di colonne non e piu una costante ma una variabile. In tal caso il numero di colonnedel parametro formale v e funzione del primo parametro formale x. E’ un tipo di scrittura chenon tutti i compilatori accettano. L’esempio di Figura 25 mostra la soluzione per il problema dellastampa della diagonale di 2 matrici aventi numero di colonne l’uno diverso dall’altra.
Il secondo modo e quello di usare le variabili globali. Una variabile globale e una variabile che adifferenza di quelle locali dichiarate nel corpo delle funzioni, sono visibili a tutte le funzioni. Essevengono poste prima delle funzioni. Nell’esempio di Figura 26 la variabile nrocol e globale.
Questo metodo comunque non rappresenta un buono stile di programmazione. Il modo miglioree fare riferimento al fatto che una matrice altro non e che un vettore le cui righe sono disposteuna dietro l’altra. Come programmatori trattiamo quindi il parametro formale matrice come unvettore, associando le coordiante di riga e colonna alla posizione del vettore mediante la formula dataprecedentemente. La relativa implementazione e in Figura 27. Questa versione puo dare dei warningdal momento che il compilatore rileva che il parametro formale e unidimensionale mentre quelli attualisono bidimensionali, ma il programma viene eseguito correttamente. Infine l’intestazione
void f(int v[], int dimcol)
puo essere sostituita equivalentemente con
void f(int *v, int dimcol)
Per quanto riguarda l’allocazione dinamica di vettori e matrici, il modo piu consueto di farlo eattraverso la funzione malloc. Il frammento di codice
.....
int *z,*k;
scanf("%d%d", &x,&y);
z=malloc(sizeof(int)*x*x);
k=malloc(sizeof(int)*y*y);
ha lo stesso effetto della dichiarazione di z e k come matrici, cioe come sequenza di un certo numerodi elementi.
94
Scopo della funzione malloc, il cui prototipo e in stdlib.h (header che deve quindi essere inclusonel programma), e riservare spazio in memoria. Essa riserva un numero di byte pari al valore delparametro attuale con cui e invocata. Avendo bisogno di x*x interi il numero di byte complessivoche deve essere allocato e x*x moltiplicato per il numero di byte occupato da un intero. Il comandosizeof restituisce la spazio occupato dal suo argomento. Di fatto al termine della chiamata z e k
hanno la stessa natura di due vettori dichiarati dinamicamente come
int z[x*x],k[y*y];
La funzione malloc restituisce un indirizzo di memoria. L’indirizzo restituito e quello dove comincial’area di memoria riservata, cioe dove comincia il vettore di interi. L’informazione restituita consentedi accedere all’area di memoria riservata e quindi l’indirizzo viene memorizzato in una variabilepuntatore. A questo punto per accedere alle diverse celle del’area di memoria si utilizza la stessanotazione usata per le variabili di tipo vettore: si usano le parentesi quadrate.
Il seguente e un esempio di allocazione dinamica di un vettore di strutture.
#include<stdio.h>
#include<stdlib.h>
typedef structint x;double y; float z; Tripletta;
void f(Tripletta *v, int dim)
int i;
for(i=0;i<dim;i++)
printf("%d, %f, %f\n",v[i].x, v[i].y, v[i].z);
int main(void)
int nroElementi,i;
Tripletta *T;
scanf("%d",&nroElementi);
/*T = malloc(sizeof(Tripletta)*nroElementi);*/
T = calloc(nroElementi, sizeof(Tripletta));
for(i=0;i<nroElementi;i++)
T[i].x=i;
T[i].y=0.5;
T[i].z=1.5;
f(T,nroElementi);
95
return 0;
96
#include<stdio.h>void f(int x,int v[][x])int i;for(i=0;i<x;i++)
printf("%d;\n ",v[i][i]);
int main(void)int e,x,y,i,j;
scanf("%d%d",&x,&y);int z[x][x];int k[y][y];
e=0;for(i=0;i<x;i++)
for(j=0;j<x;j++)
z[i][j]=e;printf("z[%d][%d]=%d;\n",i,j,z[i][j]);e++;
f(x,z);for(i=0;i<y;i++)for(j=0;j<y;j++)
k[i][j]=e;printf("k[%d][%d]=%d;\n",i,j,k[i][j]);e++;
f(y,k);return 0;
Figura 25: Stampa della diagonale Versione 1
97
#include<stdio.h>int nrocol;void f(int v[][nrocol])int i;for(i=0;i<nrocol;i++)
printf("%d;\n ",v[i][i]);
int main(void)int e,x,y,i,j;
scanf("%d%d",&x,&y);int z[x][x];int k[y][y];
e=0;for(i=0;i<x;i++)
for(j=0;j<x;j++)
z[i][j]=e;printf("z[%d][%d]=%d;\n",i,j,z[i][j]);e++;
nrocol=x;f(z);for(i=0;i<y;i++)for(j=0;j<y;j++)
k[i][j]=e;printf("k[%d][%d]=%d;\n",i,j,k[i][j]);e++;
nrocol=y;f(k);return 0;
Figura 26: Stampa delle diagonali: uso delle variabili globali
98
#include<stdio.h>
void f(int v[], int dimcol)int i;for(i=0;i<dimcol;i++)
printf("%d;\n ",v[i*dimcol+i]);
int main(void)int e,x,y,i,j;
scanf("%d%d",&x,&y);int z[x][x];int k[y][y];
e=0;for(i=0;i<x;i++)
for(j=0;j<x;j++)
z[i][j]=e;printf("z[%d][%d]=%d;\n",i,j,z[i][j]);e++;
f(z,x);for(i=0;i<y;i++)for(j=0;j<y;j++)
k[i][j]=e;printf("k[%d][%d]=%d;\n",i,j,k[i][j]);e++;
f(k,y);return 0;
Figura 27: Stampa della diagonale: versione con array
99
9 Nota su sprintf
La funzione sprintf e simile a printf. Mentre printf stampa a video, sprintf stampa “dentrouna stringa” cioe cio che dovrebbe essere emesso a video (printf) viene emesso in una variabile ditipo vettore di caratteri. Esso un esempio banale:
#include<stdio.h>
int main(void)
char v[20];
int i;
/*inizializzazione di v*/
for(i=0;i<10;i++) v[i]=’\0’;
printf("Salve Mondo\n");
sprintf(v,"Salve Mondo\n");
printf("%s",v);
printf(v);
return 0;
L’esempio mette in evidenza un’altra caratteristica di printf e cioe che il parametro attuale a primoargomento puo essere una variabile di tipo stringa. Infatti, vale la pena ricordare che il prototipo diprintf e:
int printf(char *format, ...);
Quello di sprintf e
int sprintf(char *str, char *format, ...);
A questo punto diventa agevole rendere parametrico l’output di printf, come nel seguente esempio:
#include<stdio.h>
int main(void)
char v[20];
int i,dim,x;
/*inizializzazione di v*/
for(i=0;i<10;i++) v[i]=’\0’;
scanf("%d%d",&x,&dim);
100
sprintf(v,"%c%dd",’%’,dim);
printf("stringa di formato:%s\n",v);
printf(v,x);
return 0;
10 Le Funzioni C per la Generazione di Numeri Casuali
Per evitare di dover inserire a mano dati di input, puo essere comodo generare casualmente deinumeri.
• la funzione C
long int random(void)
restituisce un numero casuale compreso tra 0 e RAND MAX;
• la funzione C
void srandom(unsigned int seed)
inizializza la sequenza casuale. Il modo piu comune di farlo e per mezzo della chiamata allafunzione
time t time(time t *t)
che restituisce il tempo trascorso dal 1 gennaio 1970, misurato in secondi.
• Tipicamente la chiamata
srandom(time(NULL));
inizializza il generatore di numeri casuali.
• Le funzioni random() e srandom() sono nella libreria stdlib.h, mentre time() e compresanella libreria time.h, occore quindi ricordarsi di includerle.
In Figura 28 vi e un programma che genera e stampa a video 1000 numeri casuali.
101
#include <stdlib.h>#include<time.h>#include<stdio.h>int main(void)int a;srandom(time(NULL));for(a=0;a<1000;a++)
printf("%d\n", random());return 0;
Figura 28: Esempio di Generazione di Numeri Casuali
102
![Algoritmi e Strutture Dati - Algoritmi Golosi (Greedy)computerscience.unicam.it/merelli/algoritmi06/[12]strategiaGolosa.pdf · Algoritmi e Strutture Dati Algoritmi Golosi (Greedy)](https://static.fdocumenti.com/doc/165x107/5c71c4f409d3f2cc4d8b53b1/algoritmi-e-strutture-dati-algoritmi-golosi-greedy-12strategiagolosapdf.jpg)
