Appunti per l'esame di Algoritmica, FRANCESCO ROMANI

ALGORITMICA E STRUTTURE DATI ​

1.RUOLO DEGLI ALGORITMI NELL’ELABORAZIONE DEI DATI (pag 5-12)

1.1 Algoritmi

Un algoritmo è una procedura di calcolo ben definita che prende un certo valore (o un

insieme di valori) come input e restituisce un valore (o un insieme di valori) come output.

Possiamo dunque considerare un algoritmo come uno strumento utile per risolvere un

problema computazionale ben definito.

Ad esempio, supponiamo di dover ordinare una sequenza di numeri in ordine crescente

(gli algoritmi di ordinamento sono molto frequenti in informatica). Formalmente possiamo

definire il problema dell’ordinamento nel seguente modo:

- Input: una sequenza di n numeri <a​ , a​ , …, a​ >

1​ 2​ n​

- Output: una permutazione dell’input tale che a’​ <a’​ <...<a’​ (dunque una lista <a’​ , a’​ , …,

1​ 2​ n​ 1​ 2​

a’​ >).

n​

Consideriamo ad esempio la lista <31,41,59,26,41,58> presa in input, come risultato

dovremo ottenere <26,31,41,41,58,59>. Tale sequenza viene chiamata istanza di un

problema, ossia l’insieme di elementi richiesti per calcolare una soluzione del problema.

Un algoritmo si definirà corretto se, comunque presa un’instanza, esso ci darà l’output

corrispondente corretto. Diremo dunque che l’algoritmo risolve il problema dato.

1.2 Algoritmi come tecnologia

Lo studio degli algoritmi è sempre consigliato, anche qualora avessimo a disposizione un

computer con memoria e velocità illimitate, poiché ci permette di verificare che sia

funzionale il programma.

- Efficienza:​ esistono molti algoritmi per risolvere un dato problema, ma tra di loro hanno

una differente efficienza (che a volte dipende semplicemente da Hardware e Software).

Esempi di algoritmi simili, sono quelli di ordinamento: stesso risultato, ma efficienza

diversa in base al numero di elementi in input. I primi algoritmi di ordinamento sono

2​

l’Insertion Sort e il Merge Sort. Mentre il primo impiega cn​ per ordinare n elementi (dove c

è una costante libera da n, mentre n è il numero di elementi da ordinare), il secondo

impiega cn lg n (dove lg n è log​ n). Generalmente la costante di InsSort ha una costante

2​

minore di MerSort, ma ciò al momento influisce poco sul costo. Per notare la differenza tra

i due, assumiamo di dover ordinare n=1.000 elementi. Per l’InsSort avremo un tempo pari

a 1.000.000, mentre per il MerSort avremo 1.000 * lg 1.000 (che è circa 10) e quindi

10.000 circa sarà il tempo di esecuzione. Ciò dimostra che per una n molto grande, il

MerSort sarà più efficiente dell’InsSort.

Un modo per vedere l’efficienza di entrambi gli algoritmi e l’indipendenza dall’uso del tipo

di computer, assumiamo di usare un Computer A molto veloce che esegue l’InsSort e un

Computer B molto lento che esegue il MerSort. Dobbiamo ordinare circa 10 milioni di

numeri. Supponiamo pure che il C.A esegua 10 miliardi di istr. al secondo, mentre il C.B

10 milioni al secondo, quindi A 1.000 volte più potente di B. Per far notare ancora di più

2​

l’efficienza, stabiliamo che l’InsSort sia stato progettato per eseguire in 2n​ , mentre il

MerSort in 50n lg n. Dunque, per calcolare il tempo usiamo il rapporto

Istruzioni/(Istruzioni/Secondo) e avremo che:

2

( )

7

2 10 istruzioni

*

l’InsSort impiegherà = 2 0.000s (piùdi5.5ore)

10 istr

10 secondo

7 7

50 10 lg10 istruzioni

*

il MerSort impiegherà .

≈ 1 .163secondi (menodi20minuti)

7 istruzioni

10 secondo

Vediamo dunque come in realtà il tipo di computer è relativo, conta di più l’efficienza di un

algoritmo appunto.

o (g (n) ) = {f (n) : c, n > 0 .0 ≤ f (n) < c

g (n) n ≥ n } e

ω (g (n)

) = {f (n) : c, n > 0 .0 ≤ c g (n) < f (n) n ≥

∃ ∀ ∃ ∀

0 0 0

​

3. CRESCITA DELLE FUNZIONI (pag. 37-51)

Quando operiamo con dimensioni dell’input abbastanza grandi da rendere rilevante

soltanto il tasso di crescita del tempo di esecuzione (e coprire le costanti), stiamo

effettivamente studiando l’efficienza asintotica degli algoritmi. In altre parole, ci interessa il

come cresce all’aumentare della dimensione dell’input. Generalmente un algoritmo

asintoticamente efficiente sarà migliore con qualsiasi input, tranne che con n piccolo.

3.1 Notazione asintotica

Generalmente le notazioni che useremo per descrivere il tempo di esecuzione sono

definite nel dominio dei N. Tali notazioni sono comode per descrivere la funzione T(n),

tempo di esecuzione nel caso peggiore, che di solito è definita soltanto con dimensioni

intere dell’input. A volte può essere utile estenderla però nel dominio di R.

​

- Notazione Θ: abbiamo precedentemente detto che il tempo di esecuzione nel caso

2​ 2​

peggiore di InsSort è T(n​ )= Θ(n​ ). Definiamo adesso cosa significa: indichiamo con

Θ(g(n)) l’insieme delle funzioni tali .

Θ (g (n) ) = {f (n) : c , c , n > 0 .0 ≤ c g (n) ≤ f (n) ≤ c g (n) , n ≥ n }

∃ ∀

1 2 1 2 0

Dunque f(n) appartiene a Θ(g(n)) se esistono delle costanti c​ , c​ tali che racchiudano la

1​ 2​

funzione tra c​ g(n) e c​ g(n) per valori sufficientemente grandi di n. Poiché Θ(g(n)) è un

1​ 2​

insieme, dovremmo scrivere , ma scriveremo semplicemente

f (n) Θ (g (n)

)

∈

per esprimere lo stesso concetto. Se diremo che g(n) è un

f (n) = Θ (g (n) ) f (n) = Θ (g (n)

)

limite asintoticamente stretto per f(n) per n≥n​ .

0​

La definizione Θ(g(n)) richiede che ogni membro di f(n)=Θ(g(n)) sia asintoticamente non

negativo, ovvero che f(n) sia non negativa quando n è sufficientemente grande. Di

conseguenza anche g(n) deve essere asintoticamente non negativa, in quanto Θ(g(n))

sarebbe vuoto. Questa ipotesi varrà anche per le altre notazioni.

​

- Notazione O: mentre la notazione Θ limita sia sopra che sotto la funzione f(n), la

notazione O la limita superiormente e indica l’insieme

.

O (g (n) ) = {f (n) : c, n > 0 .0 ≤ f (n) ≤ c

g (n) n ≥ n }

∃ ∀

0 0

Dunque per qualsiasi valore di n a destra di n​ , f(n) starà sempre al di sotto o coincidente a

0​

cg(n). Come per Θ, scriveremo f(n)=O(g(n)) per indicare che la funzione appartiene

all’ordine di O. In quanto la notazione Θ è la più “forte”, scriveremo che

2​ 2​

, quindi se f(n)=Θ(n​ ), allora f(n)=O(n​ ).

Θ (g (n) ) O (g (n)

)

⊆

- Notazione Ω:​ così come O fornisce un limite asintotico superiore, Ω fornisce un limite

asintotico inferiore. Denotiamo l’insieme .

Ω (g (n) ) = {f (n) : c, n > 0 .0 ≤ c

g (n) ≤ f (n) n ≥ n }

∃ ∀

0 0

Al contrario di O(g(n)), dato un n a destra di n​ , la funzione f(n) si troverà al di sopra o

0​

coincidente a cg(n). Invece, come per O(g(n)), , quindi se f(n)=Θ(n),

Θ (g (n)

) Ω (g (n)

)

⊆

allora f(n)=Ω(n).

​

Teorema: per ogni coppia di funzioni f(n) e g(n), si ha f(n)=Θ(g(n)) se e solo se

f(n)=O(g(n) e f(n)=Ω(g(n)).

Come dimostrazione del teorema, preso an²+bn+c= Θ(n²) per qualsiasi valore di a,b,c con

a>0, implica che an²+bn+c=O(n²) e an²+bn+c=Ω(n²).

​

- Notazione o e ω: queste due notazioni sono le corrispondenti di O(g(n)) e Ω(g(n)),

tranne per la relazione tra f(n) e g(n) dove gli insiemi sono così caratterizzati:

3.2 Notazioni standard e funzioni comuni

- Funzioni monotòne:​ una funzione è monotonicamente crescente se m≤n implica

f(m)≤f(n), analogamente è monotonicamente decrescente se m≤n implica f(m)≥f(n). È

strettamente crescente(/decrescente) qualora non c’è la relazione di uguaglianza.

​

- Floor e ceiling: dato un numero reale x, indichiamo con (floor di x) l’intero più

⌊ x⌋

grande che è minore o uguale a x, analogamente (ceiling di x) l’intero più piccolo che è

⌈ x⌉

maggiore o uguale a x.

Per qualsiasi numero reale x valgono le seguenti proprietà:

- ;

⌊ ⌈

x −1 < x⌋ ≤ x ≤ x⌉ < x + 1

n n

- ;

⌈ ⌉ ⌊ ⌋

+ = n

2 2

n n

⌈ ⌉ ⌊ ⌋

n n

⌈ ⌉ ⌈ ⌉e⌊ ⌋ ⌊ ⌋

= =

- ;

a a

b ab b ab

(a+(b−1)) (a−(b−1))

a a

⌈ ⌉ ⌋

≤ e⌊ ≥

- .

b b b b

Le funzioni di floor e ceiling sono monotonicamente crescenti.

​

- Aritmentica modulare: per qualsiasi intero a e qualsiasi intero positivo n, il valore a mod

a

n è il resto (o residuo) del quoziente a/n: da cui segue .

⌋n

a modn = a −⌊ 0 ≤ a modn < n

n

Una volta definito il resto della divisione tra due interi, è comodo utilizzare la notazione

delle congruenze e diremo che a è congruo a b mod n. In

(amodn) = (bmodn) a ≡ b modn

⇒

altre parole, se a/n e b/n hanno lo stesso resto. d i

∑

​

- Polinomi: Dato un intero d>0, un polinomio in n di grado d è una funzione p(n) a n

i

i=0

dove le costanti a​ , a​ , …, a​ sono i coefficienti del polinomio a​ ≠0. Un polinomio è

​

0​ 1​ n d​

asintoticamente positivo se e soltanto se a​ >0. Per un polinomio asintoticamente positivo

d​

d​

p(n) di grado d, si ha p(n)=Θ(n​ ). Si dice che una funzione f(n) è polinomialmente limitata

k​

se f(n)=O(n​ ) per qualche costante k.

- Esponenziali:​ per a>0, m e n reali qualsiasi, si hanno le seguenti identità:

0​

- a​ =1

1​

- a​ =1

-1​

- a​ =1/a

m​ n​ n​ m​ mn

- (a​ )​ =(a​ )​ =a​

m​ n​ m+n

- a​ a​ =a​ n​

Per qualsiasi n e a≥1, la funzione a​ è monotomicamente crescente in n. Si assume che

0​

0​ =1.

La velocità di crescita delle funzioni polinomiali ed esponenziali sono correlate dal

b

n

seguente fatto: per tutte le costanti a e b, con a>1 avremo da cui possiamo dire

= 0

n

a

b​ n​

n​ =o(a​ ). Da ciò deduciamo che qualsiasi funzione esponenziale cresce più rapidamente di

una qualsiasi funzione polinomiale.

​

- Logaritmi: per b>1 e n>0, la funzione log​ n è strettamente crescente. Per qualsiasi

b​

reale a, b, c>0 e n, si ha (in tutte queste, le basi dei log deve essere diversa da 1):

log​ a

- a = b​ b​

- log​ (ab)=log​ a+log​ b

c​ c​ c​

n​

- log​ a​ = n log​ a

b​ b​

- log​ a=log​ a/log​ b

b​ c​ c​

- log​ (1/a)=-log​ a

b​ b​

- log​ a=1/log​ b

b​ a​

log​ c​ log​ a

- a​ =c​

b​ b​ 2 3 4 5

x x x x

C’è un semplice sviluppo in serie di ln(1+x) quando |x|<1 e la

l n (1 + x

) = x

− + − + −...

2 3 4 5

x

disuguaglianza per x>-1 (l’uguaglianza vale solo se x=0).

≤ l n (1 + x

) ≤ x

(1+x) k​

Una funzione si dice polilogaritmicamente limitata se f(n)=O(lg​ n) per qualche costante k.

​

- Fattoriali: la notazione n! è definita per i numeri interi n≥0 ed è

1 sen = 0 n· (n−1) sen > 0

data dal sistema:

quindi n!=1·2·...·n. n​

Un limite superiore non stretto per la funzione fattoriale è n!≤n​ , in quanto ciascuno degli n

termini del prodotto fattoriale è al massimo n. L’approssimazione di Stirling

n

( ) ( ( ))

n 1

√2πn

n ! = · 1 + θ dove e è la base del logaritmo naturale (e=2,71828…), fornisce

e n

un limite superiore più stretto e anche un limite inferiore.

​

2. PER INCOMINCIARE (pag. 25-33)

2.3 Progettare gli algoritmi

Esistono varie tecniche per progettare algoritmi, ad esempio per InsSort usiamo un

approccio incrementale (vedremo poi nello specifico): dopo aver ordinato il sottoarray

A[1,j-1], inseriamo il singolo elemento A[j] nella posizione appropriata, ottenendo il

sottoarray ordinato A[1,j].

Tramite il Divide et Impera possiamo semplificare il costo dell’algoritmo.

2.3.1 Il metodo Divide et Impera

Molti algoritmi usano la tecnica ricorsiva per risolvere un determinato problema (ossia

richiamano sé stessi fino al raggiungimento del caso base). Generalmente questo tipo di

algoritmi adottano un approccio divide et impera, ossia dividono il problema in

sottoproblemi simili a quello iniziale, ma più piccolo, risolvono i sottoproblemi e infine

ricombinano nella soluzione del problema originale.

Il paradigma Divide et Impera prevede 3 passi per ogni ricorsione:

- Divide: il problema viene diviso in sottoproblemi che sono istanze più piccole del

problema stesso

- Impera: i sottoproblemi vengono risolti in maniera ricorsiva. Quando essi hanno una

dimensione sufficientemente piccola, vengono risolti direttamente

- Combina: le soluzioni dei problemi vengono combinate per generare la soluzione finale

L’argoritmo del Merge Sort è conforme al paradigma D. et I., nel modo seguente:

- Divide: divide la sequenza di n elementi in due sottosequenze di n/2 elementi ciascuna

- Impera: ordina le due sottosequenze in modo ricorsivo usando l’algoritmo del MerSort

- Combina: fonde le due sottosequenze ordinate per ottenere quella principale

La ricorsione si ferma quando le sottosequenze raggiungono una lunghezza di 1 e quindi,

banalmente, sono ordinate.

L’operazione chiave del MerSort è la fusione delle sottosequenze tramite una procedura

ausiliaria che chiameremo MERGE(A, p, q, r), dove A è un array e p,q,r sono indici

dell’array tali che p≤q<r. La procedura assume che A[p,q] e A[q+1,r] siano ordinati, dunque

li fonde per formare un sottoarray A[p,r]. MERGE impiega un tempo Θ(n), dove n=r-p+1 è

il numero totale di elementi da fondere. Il seguente pseudocodice implementa il MERGE:

MERGE(A,p,q,r)

1. n1=q-p+1

2. n2=r-q

3. Crea L[1,n1] e R[1,n2+1]

4. for i=1 to n1

5. L[i]=A[p+i-1]

6. for j=1 to n2

7. R[j]=A[q+j]

8. L[n1+1]=INT_MAX

9. R[n2+1]=INT_MAX

10. i=1

11. j=1

12. for k=p to r

13. if L[i]<=R[j]

14. A[k]=L[i]

15. i++

16. else A[k]=R[j]

17. j=j+1

In fondo ad ognuno dei due sottoarray (L ed R) inseriamo delle sentinelle uguali

(INT_MAX assegna l’intero più grande raggiungibile) per fermare i cicli di inserimento.

Vediamo in dettaglio:

- le righe 1 e 2 calcolano le lunghezze dei sottoarray e la riga 3 crea L[n1+1] ed R[n2+1];

- dalla riga 4 alla 7, tramite due cicli, copio gli elementi di A/2 in L e in R;

- righe 8 e 9 inserisco delle sentinelle alla fine di L ed R, 10 e 11 reinizializzo i e j;

- dalla riga 12 alla 17 inserisco gli elementi ordinati di L ed R in A.

Per verificare che la procedura MERGE viene eseguita in un tempo Θ(n), ci basta notare

che le righe 1-3 e 8-11 impiegano un tempo costante c, i cicli for alle righe 4, 6 e 12

impiegano un tempo pari a Θ(n​ +n​ +n)=Θ(n), sommando tutto il tempo è appunto Θ(n).

1​ 2​

Adesso possiamo usare la funzione MERGE come subroutine nel MERGE-SORT(A,p,r) la

quale ordina gli elementi nel sottoarray A[p,r]. Se p≥r, il sottoarray ha al massimo un

elemento e dunque è già ordinato, altrimenti il passo “divide” calcola semplicemente un

indice q che separa A[p,r] in due sottoarrat A[p,q] e A[q+1, r], contenenti n/2 elementi

ciascuno.

MERGE-SORT(A,p,r)

1. if p<r

2. q=floor{(p+r)/2}

3. MERGE-SORT(A,p,q)

4. MERGE-SORT(A,q+1,r)

5. MERGE(A,p,q,r)

Dunque chiamiamo ricorsivamente la funzione MERGE-SORT finché non arriviamo al

caso base e quindi inizieremo ad ordinare gli elementi top-down e poi a ricombinarli

bottom-up.

2.3.2 Analisi degli algoritmi Divide et Impera

Una ricorrenza per il tempo di esecuzione di un algoritmo Divide et Impera si basa sui tre

passi del paradigma di base. Come in precedenza, supponiamo di avere T(n) il tempo di

esecuzione di un problema con n elementi. Se la dimensione del problema è

sufficientemente piccola, ad esempio n≤c per qualche costante c, la soluzione avrà tempo

costante e noi indicheremo con Θ(1). Supponiamo invece che la risoluzione richieda la

suddivisione per 1/b in a sottoproblemi, avremo che il tempo necessario a risolverli sia

aT(n/b), in più impieghiamo un tempo D(n) per dividerlo e un tempo C(n) per ricombinarli.

Otteniamo così un sistema del tipo:

( )

n

T (n) = Θ (1) sen ≤ c aT + D (n) + C (n) sen > c

b

​ ​

- Analisi di MerSort: anche se il MerSort funziona anche con valori di n%2≠0, per

semplificare useremo per n, dei valori potenza di 2. Ogni passaggio genera n/2 sottoarray.

Per trovare la ricorrenza per T(n) possiamo fare il seguente ragionamento:

- Divide: questo passo calcola semplicemente il centro dell’array (tempo costante,

D(n)=Θ(1));

- Impera: risolviamo in maniera ricorsiva i due sottoarray, ciascuno di n/2 elementi, dunque

il tempo di esecuzione è pari a 2T(n/2);

- Combina: abbiamo visto che la procedura MERGE usa un tempo pari a Θ(n), quindi

C(n)=Θ(n).

Adesso uniamo tutto e otteniamo un sistema del tipo:

( )

n

T (n) = θ (1) sen = 1 2T + θ (n) + θ (1) sen > 1 (Θ(1) nella seconda equazione si potrebbe

2

rimuovere)

Risc