Algoritmi e Strutture Dati con domande riassuntive

Algoritmi

1.1: Algoritmi ​

● Algoritmo: sequenza di istruzioni elementari che portano alla soluzione di

problemi computazionali ​ ​ ​ ​

● Problema computazionale: f

ornire parametri che descrivano input e output​ .

​

○ Input: un array di interi

​

○ Output: un numero intero

​

○ Vincoli: descrivono il legame fra input e output

​

○ Istanza: si ottiene specificando i valori nell’input -> esempi di input (gli input

sono diversi se contengono diversi valori)

● Esercizio: ordinare array

​

○ Input: array di n interi

​

○ Output: un array (può essere anche uno diverso) di n interi

​

○ Vincoli: L’array di output è la permutazione dell’array di input tale che:

primo elemento <= secondo elemento <= terzo elemento ecc.

​

○ Istanza: 10 7 9 3 4 74 3

​

● T​ (n): Caso peggiore, ossia l’algoritmo più lento nell’effettuare l’operazione

p​

● T​ (n):​ Caso migliore, ossia l’algoritmo più veloce nell’effettuare l’operazione

m​ ​

● T​ (n): Caso medio, ossia “tempo dell’esecuzione previsto” (linea sopra la M

M​

piccola)

Elementi utilizzati per gli algoritmi

● Pseudocodice simil Java - C

● If / else / then (poco usato)

● Commenti */ /*

● Assegnamenti x <- 1 / x = 1 / x:= 1

● Test x == 1 ​

● Variabili locali a meno dei vettori

● Array V[i] 1...n (​ si parte da 1, non da 0​

)

● Puntatori

● Passaggio di parametri (per valore)

● Macchina su cui si eseguono gli algoritmi è la RAM (Random Access Machine)

● Esempio: 6

​

○ Algoritmo elabora 10​ op.\sec.

○ Dimensioni del input: n

○ T​ (n) ?

p

​ Tempo alg.\ n 20 100 10000

1000n 0.02” 0.1” 1”

10n (1/100)*0.02” 100” 1/100”

2

100n​ 0.04” 10” 2’

n 6

​

2​ 1” 3*10​ anni

1000000n 20” 1000”

● Esercizio: Ricerca Sequenziale (trovare valore K nel vettore V)

○ Input: vettore V, valore K

○ ricercaSequenziale(V,K)

○ i = 1

○ while(i < V.length && V[i] == K)

○ i++;

○ if (i <= length(V)

○ return(i)

○ else

○ return(-1)

○ Calcolo tempo dell’esecuzione

Istruzione Tempo Descrizione

i = 1 C1

while C2 t​ -> quante volte viene eseguito

wi​

while

​

i++ C3 t​ -1 -> eseguito una volta in meno

wi​

del while

if C4 ​

return C5 t​ -> eseguito ogni volta che if = true

if​

else non conta mai nel tempo di

esecuzione

return C6 t​ -> eseguito ogni volta che if = false

if​

​ ​ ​ ​

○ Caso migliore: K è in V[1] (array vanno da 1 a n). t = 1

wi​

​

○ Caso peggiore: K non c’è in V

​

○ Caso medio: K si trova in V[n/2]

​

○ Tempo: C1 + C2 * t​ + C3 * t​ -1 + C4 + C5 * t​ + C6 * t​

wi wi if if

​ ​ ​

​

○ T​ (n): C1 + C2 * 1 + C3 * 0 + C4 + C5 * 1 + C6 * 0

mig​ ​

○ T​ (n): C1 + C2 * (n + 1) + C3 * n + C4 + C5 * 0 + C6 * 1

p​ ​

○ T​ (n): C1 + C2 * ((n + 1)/2) + C3 * (n/2) + C4 + C5 * 1 + C6 * 0

M​

● Esercizio: Ricerca Dicotomica (per trovare valore K nel vettore V provo a

vedere se si trova a metà. Il programma mi dirà in quale metà si trova e si

opererà su essa e così via)

○ Input: vettore V, valore K

○ ricercaDicotomica(V[],K)

○ sx = 1

○ dx = length(V);

○ m = (sx + dx)/2;

○ while (V[m]!=k && dx >= sx) {

○ if V[m] > k {

○ dx = m - 1

○ else sx = m + 1 }

○ m = (sx + dx)/2 }

○ if sx <= dx

○ return(m)

○ else return(-1)

○ Calcolo tempo dell’esecuzione

Istruzione Temp Valore

o

sx = 1 C1

dx = length(V) C2

m = (sx + dx)/2 C3

while C4 t​ -> quante volte viene

wi

eseguito while

​

if V(m) C5 t​ -1 -> eseguito una volta in

wi​

meno del while

​

dx = m -1 C6 t​ -> eseguito ogni volta che if =

if

true

​

sx = m + 1 C7 f​ -> eseguito ogni volta che if =

if

true ​

m = (sx + dx)/2 C8 t​ -1 -> eseguito una volta in

wi​

meno del while

if sx <= dx C9 ​

return C10 t​ -> eseguito ogni volta che if

if2

= true

​

return C11 f​ -> eseguito ogni volta che if

if2

= true

​ ​ ​ ​

○ Caso migliore: K è in posizione m. t = 1 V[m] = k

wi​

​

​ ​ ​ ​ ​ ​ ​ ​ ​ ​

○ Caso peggiore: K non c’è in V. t = max. t + f = t -1

​

wi​ if​ if wi​

○ Caso medio:

ciclo while

1 passo n

2 passi n/2

3 passi n/3

i - passi n/2^i

n/2^i = 1 2^ì = n i = log​ n -> max = log​ n

2 2

​ ​

​ ​ ​ ​ ​ ​

○ Tempo: C1 + C2 + C3 + C4​ t + C5(​

t -1) + C6​

t + C7​ f + C8(​

t -1​ ) + C9 +

wi wi​ if if wi​

​ ​

C10​ t + C11​ f

if2​ if2

​

○ T​ (n): C1 + C2 + C3 + C4 + C9 + C10. 6 istruzioni

mig​ ​

○ T​ (n): C1 + C2 + C3 + C4 * max + C5 * max + C6 (max - 1) + C8 (max - 1) +

p​

C9 + C11

○ T​ (n):​ ( log​ n)/2

2

​

M​

Algoritmi di ordinamento

● Selection sort

○ Cerca minimo e lo mette in 1

○ Riparte da 2 -> cerca minimo -> mette in 2

○ ecc.

● sel_sort(V[])

○ for i = 1 to length V[] - 1

○ pmin = 1

○ for j = i + 1 to n

○ if V[j] < V[pmin]

○ pmin = j

○ Scambia (V, i, pmin) 3 istruzioni

Istruzione Tempo Valore

for i C1 n

pmin = 1 C2 n - 1

n-2​

for j C3 ∑​ i

i=1​

n-2​

if C4 ∑​ i

i=1​

pmin = j C5 t​ if

scambia C6 3n

​ ​ ​ ​

○ Caso migliore: A rray già ordinato. t = 0

if​

​ ​ ​ ​

○ Caso peggiore: Array ordinato al contrario. t = max

if​

n-2​

​ ​

○ Tempo: (​ C1 + C2 + 3C6)n + (C3 + C4)(​ ∑ i)​ + C5​ t

i=1​ if

n-2​

​

○ T​ (n): (​ C1 + C2 + 3C6)n + (C3 + C4)(​ ∑ i)

mig​ i=1​

n-2​

​

○ T​ (n): (​ C1 + C2 + 3C6)n + (C3 + C4 + C5)(​ ∑ i)

p​ i=1​

● Insertion sort

○ Array diviso in due: ordinati e non ordinati

○ si prendono gli elementi non ordinati e si inseriscono nella apposita posizione

● void ins_sort(V[])

○ for i = 2 to n

○ k = V[i]; j = i -1;

○ while k < V[j] and j > 0

○ V[j + 1] = V[j]

○ j--;

○ V[j+1] = k

Istruzione Tempo Valore

for i C1 n

k = V[i]; j = i -1; C21 + n - 1

C22 n​

while C3 ∑​ t​ (​ tempo in cui il while è

i=2 wi

vero all’esecuzione i-esima)

n​

V[j + 1] = V[j] C4 ∑​ t​ -1

i=2​ wi​

n​

j--; C5 ∑​ t​ -1

i=2​ wi​

V[j+1] = k C6 n - 1

​ ​ ​ ​

○ Caso migliore: A rray già ordinato. t = 1 + 1 + 1.. = n -1

wi​

​ ​ ​ ​

○ Caso peggiore: Array ordinato in modo decrescente. t = i

wi​

n n

​ ​ ​

○ Tempo: C1n + (C21 + C22 + C6)(n - 1) + C3( t​ ) + (C4 + C5)( t​ -1​ )

∑ ∑

wi​ wi​

i=2 i=2

​ ​

○ T​ (n): C1n + (C21 + C22 + C6)(n - 1) + C3(​

n-1​ ) -> asintotico a n

mig​ n n

​ ​

○ T​ (n):​ C1n + (C21 + C22 + C6)(n - 1) + C3( i​ ) + (C4 + C5)( i - 1​ )

∑ ∑

​

p​ i=2 i=2

n n

( +1)

n ​

■ i =

∑ −1

2

​

i=2 n n

( +1)

n n−1

​

​ ​

■ i - 1 = = 2 + 3 + 4 +...(n-1) = i

∑ ∑

2

​ ​

i=2 i=2

2

​ ​

■ Il tempo peggiore è asintotico a n

2

n

​

○ Tempo medio = 2

Limiti asintotici

Si eliminano le costanti e i termini di ordine inferiore

​

● O(f(n)) = limite asintotico superiore ( O grande)

​

● Ω(f(n)) = limite asintotico inferiore (Omega grande)

​

● = limite asintoticamente stretto ( Theta)

ϴ(f(n))

O grande - limite asintoticamente superiore (caso peggiore)

​

● t(n) =O(f(n)) se esiste n , c | n > n , t(n) < c*f(n)

∀

0 0 0

● Esempio:

2 2

n O n

○ 3 = (2 )

○ c = 2 n​ = 1

0

​ 2 2

2 2

n c n x x x vero

○ 3 ≤ (2 ) → 3 1 ≤ 2 2 1 → 3 ≤ 4

Omega grande - limite asintoticamente inferiore (caso migliore)

​

● t(n) =Ω​ (f(n)) se esiste n , c > 0 | n > n , t(n) > c*f(n)

∀

0 0

● Esempio:

2 2

n n

○ 3 = Ω( )

○ c = 2 n​ = 1

0

​

2 2

x x vero

○ 3 1 ≥ 2 1 → 3 ≥ 2

Theta - limite asintoticamente stretto

​ ​

● t(n) = (g(n)) se e solo se t (n) =O(f(n)) e t(n) = Ω(g(n))

● (g(n)) = {f(n) : esistono costanti positive c , c e n tali che 0 < c g(n) < c g(n) per

1 2 0 1 2

ogni n > n }

0

● Una funziona f(n) appartiene all’insieme se esistono costanti positive c​ , c​

ϴ(g(n)) 1 2

​

tali che f(n) possa essere compresa tra le due costanti, per un valore sufficentemente

grande di n.

● In sostanza theta esiste se e solo se O grande e Omega grande sono uguali.

​

● Nel grafico, se dopo n​ f(n) coincide e sta sotto a c g(n) e coincide o sta sopra a

0 ​ 1

​

c g(n), allora si dice che g(n) è un limite asintoticamente stretto per f(n)​ .

2 ​ ​

● f(n) deve essere non negativa quando n è sufficentemente grande (ovvero nessun

​ ​

membro di f(n) appartenente a (g(n)) deve essere asintoticamente non negativo​

.

Algoritmo

● V​ e V​ sono due array contenenti n valori. Contare quanti elementi di V​ stanno

1 2 2

in V​ 1

○ c = 0

○ for i = 1 to V​ length

2

​

■ j = 1

■ while(V​ [i] != V​ [j]) and (j < V​ length)

2 1 2

​ ​ ​

● j++

​ ​

■ if j < V​ length

1 ​

● c++

○ return c

Istruzione Valore

c = 0 c

for i = 1 to V​ length c * n

2

​

j = 1 c * n

n

while(V​ [i] != V​ [j]) and (j < V​ t​

∑

2 1 2

​ ​ wi

length) i=1

n

j++ t​

∑ wi

i=1

​ ​

if j < V​ length c * n

1 ​

c++ c* t​ if

return c c

Tempo

⇒ n

​ C C n C t

wi C t

if

● t(n) = 2 + 3 · + 2 · ∑ + ·

i=1

● Caso peggiore:​ non ci sono elementi di V​ in V​

2 1

​

​ ​ ​

○ t​ = n; t = 0

​

wi if​ n 2 2

​ C C n C n C C n C n O n

○ tp(n) = 2 + 3 · + 2 · ∑ ~ 2 + 3 · + 2 · ~ ( )

i=1

​ ​

● Caso migliore: V ha un solo numero ripetuto n volte e quel numero è al primo posto di

2

V​ 1 ​ ​ ​

○ t​ = 0; t = n

​

wi if​ C C n C n n

○ tm(n)​ = 2 + 3 · + · ~ Ω

( ) ​

● N.B: O e Ω sono diversi, quindi non esiste

Limiti asintotici

2 2 3

n O n o n

● 3 → ( ) → ( ) 2​

(n​ )

2 2

n n w n

● 3 → Ω

( ) → ( )

2 2 3

n n O n o n

● 4 − 2 → ( ) → ( ) 2​

(n​ )

2 2

n n n w n

● 4 − 2 → Ω

( ) → ( ) 2

2​ n n

esiste una costante che, dopo un certo n​ , moltiplicata per n​ sia più piccola di 4 − 2

0​

2 1

​ ​

n n n = 10 c =

4 − 2 0 100

​ 2

2 2 10

n

4

(10 ) − 2(10) = 380 Ω

( ) = =1

100

l

og n O n sarebbe meglio nlogn o n

● ( ) → ( ) ( ( )) → ( )

l

og n logn w

● ( ) → Ω

( ) → (1)

k k

l

og n O nlogn l

og n k log n

● k è costante quindi va via

( ) → ( ) → =

● max{f(n); g(n)} 2

f n n

○ ( ) = 3

g n n

○ ( ) =

○ considero la più grande quindi f(n)

2 2

f n n O n

○ ( ) = 3 → ( ) 2​

(n​ )

2 2

f n n n

○ ( ) = 3 → Ω

( )

N.B: b ​ ​

n a a,b sono costanti!

( + )

b

O n

( )

Esempio:

7 7

n O n

( + 1

0) ( ) 7

n

NON risolvere tanto tutte le n con esponente minore di 7 vanno via!

( + 1

0)

Algoritmo

2 array contenenti n bit da sommare in un terzo array di dimensioni n + 1

Esempio:

A 10110 +

B 10100 =

C 101010

● void Somma (A[], B[])

● resto = 0

● for i = n down to 1

○ C[i+1] = A[i] + B[i] + resto

​ ​

○ if C[i+1] < 1

■ resto = 0

○ else

■ C[i+1] = C[i+1] - 2

■ resto = 1

● C[i] = resto Istruzione Valore

resto = 0 c

for i = n down to 1 c * n

C[i+1] = A[i] + B[i] + resto c * n

​ ​

if C[i+1] < 1 c * n

resto = 0 c* t​ if

C[i+1] = C[i+1] - 2 c* f​ if

resto = 1 c* f​ if

return c c

Tempo ​ C C n C tif Cfif

● t(n) = 2 + 3 · + + 2

● Caso peggiore: 0101 ultimo bit di A e B = 1 e poi A[i] o B[i] = 1

1011

c’è sempre riporto

​ ​ ​

● t​ = 0; f = n

​

if if​

C Cn Cn C Cn O n

● tp(n)​ = 2 + 3 + 2 = 2 + 5 = ( )

● Caso migliore:​ non si ha mai riporto

○ A[i] and B[i] = 0

​ ​ ​

○ t​ = n; f = 0

​

if if​

​ C Cn Cn C Cn n

○ tm(n) = 2 + 3 + + 0 = 2 + 4 = Ω

( )

​ ​

n O n n

● Siccome nel caso migliore è e nel peggiore l’algoritmo è ϴ

Ω

( ) ( ) ( )

Cn

C Cn

● Tempo medio: 2 + 4 + 2

Algoritmo

trasformare numero da decimale a binario

● z = n

● t = 0

● while z > 0

○ x = z mod 2

○ z = z div 2

○ if x == 0 then

■ for i = 1 to n

● t = t + 1

● return t Istruzione Valore

z = n c

t = o c

while z > 0 c* t​ wi

x = z mod 2 c* t​ wi

z = z div 2 c* t​ wi

if x == 0 then c* t​ wi

for i = 1 to n c* n * t​ if

t = t + 1 c* n * t​ if

return t c

Tempo ​ C C t

wi Cn t

if

● t(n) = 3 + 4 · + 2 ·

● Caso peggiore: h

n h log n

○ n = potenza di 2 = 2 → = ( )

2

​ ​ ​

● t​ = h; t = h

​

wi if​

Cn log n

● tp(n)​ = 2 + ( )

2

O n log n

● = ( )

● Caso migliore:

h

n

○ - 1

= 2 ​ ​ ​

○ t​ = h; t = 0

​

wi if​

​ C C l

ogn

○ tm(n) = 3 + 4 · + 0

logn

○ Ω = ( )

Algoritmo

● for i = 1 to n

○ b[i] = 0

○ j = n

○ while j > i

■ b[i] = b[i] + a[j]

■ j--

Istruzione Valore

for i = 1 to n c * n ​

b[i] = 0 c * n (sarebbe n-1 ma fa

niente)

j = n c * n

n

while j > i ​

n i

c* ∑ − (è un for)

i=1

n

b[i] = b[i] + a[j] n i

c* ∑ −

i=1

n

j-- n i

c* ∑ −

i=1

● Non c’è caso migliore o peggiore perchè sono due for e devono essere eseguiti

per forza n n−1 ( )

(n−1)n

​

● t(n) = 2

Cn C n i Cn C i Cn C n

ϴ

3 + 3 · ∑ − = 3 + 3 · ∑ = 3 + 3 = ( )

2

i=1 i=1

Algoritmo con cicli For innestati

● for i = 1 to n

○ for j = 1 to n

■ for k = 1 to j - 1

● A[k] = B[j]

Istruzione Valore

for i = 1 to n c * n 2

for j = 1 to n c * n * n = c * n​

n

for k = 1 to j - 1 j

c * n * ∑ −1

j=1

n

A[k] = B[j] j

c * n * ∑ −1

j=1

3

● 3 for innestati = n​ 3

● non è mai maggiore di n​

● può essere minore di se il for più interno viene eseguito poche volte

● non c’è caso migliore o peggiore perchè devono essere eseguiti tutti almeno

una volta

Tempo n n ( )

(n−1)n

​

● t(n) = 2 2

C n C n Cn j C n C n Cn j C n C n Cn

+ + 2 · ∑ − 1 = + + 2 · ∑ = + + 2 · =

2

j=1 j=0

3

n

○ = ϴ

( )

Sommatorie cicli innestati

n−1 n(n+1) i(i+1)

∑ − =

2 2

i=1 n−1

n(n+1) i(i+1)

(

n − 1

) · −∑ =

2 2

i=1

n−1

n(n+1) 1

(

n − 1

) · − ∑ i

(i + 1

) =

2 2 i=1

n−1

n(n+1) 2

1

(

n − 1

) · − ∑ i + i =

2 2 i=1

n−1

n(n+1) 2

1

(

n − 1

) · − ∑ i + i =

2 2 i=1

( )

n−1 n−1

n(n+1) 2

1

(

n − 1

) · − ∑ i + ∑ i =

2 2 i=1 i=1 n−1

n(n+1) n(n+1)(2n+1) 1

(

n − 1

) · − + ∑ i =

2 6 2 i=1

n(n+1) n(n+1)(2n+1) n(n−1)

(

n − 1

) · − +

2 6 2

3 3 ​

n n

Ordine massimo quindi , in questo caso non c’è caso migliore o un caso peggiore

ϴ

( )

perchè in ogni caso i 3 for vengono eseguiti

Principio di induzione & Ricorsione

​

● La ricorsione è basata sul principio di induzione matematica

○ Proprietà p(n)

n

1. p(n) vera n​

≥

∀ 0

a. p(n​ ) vera

0

​

b. p(n) implica p(n+1) vera

​ ​ ​ ​

2. n​ < m < n-1 p(m) implica p(n)

0

​

● L’induzione si basa sull