Introduzione al complessità

(1)

Introduzione al complessità

Paolo Bison

Fondamenti di Informatica Ingegneria Meccanica

Università di Padova A.A. 2008/09

Introduzione alla complessit`a, Paolo Bison, FI08, 2008-09-29 – p.1

Complessità

analisi degli algoritmi in termini di indici di qualitá

algoritmo “migliore”

indici:

occupazione di memoria

tempo di esecuzione

f (n)

calcolo del valore dell’indice in funzione della dimensione dei dati di ingresso

distribuzione dei dati in ingresso

caso peggiore

caso migliore

caso medio

valore di un polinomio

dato polinomio

A

_m

x

^m

+ A

_m₋₁

x

^m⁻¹

+ . . . + A

₁

x + A

₀

valutarlo in x

₀

dimensione n = m-1 numero dei coefficienti A

_i

valore di un polinomio

algoritmo 1

pol← A⁰ i← 1 while i≤^m

pot← 1 k←ⁱ while k>₀

pot←^pot× x⁰ k←^{k - 1} pol← Ai×^{pot + pol} i←ⁱ⁺¹

¯¯¯|^C⁰

|

¯¯¯|

|^C1(n − 1)

|

¯¯¯|

| C2∑ⁿ_l=1l= C2n(n−1) 2

|

¯¯¯|^C3(n − 1)

|

tempo di esecuzione

f

_T^‘

(n) = C

₀

+ C

₁

(n − 1) + C

2

n (n − 1)

2 + C

₃

(n − 1)

(2)

valore di un polinomio

algoritmo 2 regola di Horner

(. . . (A

m

x + A

m−1

)x + A

m−2

)x . . . + A

1

)x + A

0

pol← Am

i←^m-1 while i≥^{0 do}

pol←^pol×^x⁰⁺Ai

i←^i-1

¯¯¯|^D0

|

¯¯¯|

|^D¹(n − 1)

|

tempo di esecuzione

f

_T^”

(n) = D

₀

+ D

₁

(n − 1)

algoritmo “migliore” ?

comportamento asintotico per n → ∞

notazione O

f (n) è O(g(n))

se esistono due costanti positive c e n

₀

tali che 0 ≤ f (n) ≤ cg(n)

per ogni n ≥ n

0

n₀

c g(n)

n f(n)

g(n) è un limite asintotico superiore per f (n)

limite superiore di f (n) a meno di un fattore costante

limite superiore alla complessità dell’algoritmo

classi di complessità k costante log n logaritmica

√ n

n lineare

n log n subquadratica n

²

quadratica n

³

cubica n

^a

polinomiale a

ⁿ

esponenziale n! fattoriale

10 20 30 40 50 60

2 log(x) sqrt(x) x x**2 2**x

valore di un polinomio f

^‘

(n) = O(n

²

) f

^”

= O(n)

caveat

f (n) equivalenti a meno di un fattore costante

0 500 1000 1500 2000

0 2 4 6 8 10

1000*x 10*x

valori di n sufficientemente grandi

per valori piccoli di n un algoritmo di complessità maggiore potrebbe essere più efficiente

differenti complessità nei casi migliore, peggiore e medio

(3)

Radice intera

calcolo della radice quadrata intera di un numero n > 0

la radice intera è quel numero m che soddisfa le condizioni m

²

≤ n ^e (m + 1)

²

> n

Radice intera - I

program isqrt0 integer :: n,m,i

read *,n do i=1,n

if ((i*i<=n) .and. ((i+1)*(i+1)>n)) then m=i

end if end do print *,m

end program isqrt0

O(n)

Radice intera - II

program isqrt1 integer :: n,m

read *,n m=0 do

m=m+1

if (((m*m)<=n) .and. ((m+1)*(m+1)>n)) then exit

end if end do print *,m

end program isqrt1

O( √ n)

Radice intera - III

program isqrt2 integer :: n,m,min,max read *,n

min=1; max=n; m=(min+max) / 2 do

if (min==max-1 .or. min==max) then ; exit; end if if (m*m>n) then

max=m else

min=m end if

m=(min+max) / 2 end do

print *,m

end program isqrt2

O(log n)

passo 1 2 . . . k . . . log₂n dim. n/2 n/4 . . . n/2^k . . . 1

(4)

radice intera - prestazioni

tempi di esecuzione in sec.

n √

n I II III

500 22 5.44 0.38 0.16 5000 70 50.98 1.19 0.17 50000 223 547.77 3.79 0.21

programma III più efficiente, ma ...

I II III

√ 1000000 998215 1000 458753

Problemi P e NP

P problemi trattabili: soluzione data da un algoritmo di complessità al massimo polinomiale

NP una soluzione può essere verificata con un algoritmo a complessità polinomiale

NP-completi NP e nessun altro problema NP ha

complessità maggiore a meno di una fattore polinomiale:

- soddisfacibilità di formule logiche - commesso viaggiatore

NP-hard intrinsecamente più difficili degli NP - ottimizzazione di problemi NP-completi:

- percorso minimo in un grafo

Soluzione di problemi NP

approccio esaustivo

generazione di tutte le possibili configurazioni di uscita

ricerca in questo spazio di una soluzione o di quella migliore

commesso viaggiatore

combinazione di tutti i percorsi possibili

ricerca della combinazione che soddisfa i vincoli

Generazione delle configurazioni - I

disposizione con ripetizione di N elementi do i0=1,N

do i1=1,N ....

do iN_2=1,N do iN_1=1,N

call config(i0,i1,...,iN_2,iN_1)

O(N

^N

)

numero dei cicli do dipende dalla dimensione N

(5)

Generazione delle configurazioni - II

algoritmo ricorsivo

recursive subroutine genera_disp(config_array,N, liv) integer,dimension(:),intent(inout) :: config_array integer,intent(in) :: liv,N

integer ::i do i=1,N

config_array(liv)=i if (liv==N) then

call config(config_array,N) else

call genera_disp(config_array,N,liv+1);

end if end do

end subroutine genera_disp

attivazione

call genera_disp(config_array,N,1)

Generazione delle configurazioni - III

permutazioni semplici di N elementi O(n!)

recursive subroutine genera_perm(config_array,N, sub_array,sub_N,liv) integer,dimension(:),intent(inout) :: config_array

integer,intent(in) :: liv,N,sub_N

integer,dimension(:),intent(in) :: sub_array

integer,dimension(sub_N-1) :: local_sub_array; integer ::i,k,l if (sub_N==1) then

config_array(liv)=sub_array(1) call config(config_array,N) else; do i=1,sub_N

config_array(liv)=sub_array(i) l=1; do k=1,sub_N

if (k/=i) then;local_sub_array(l)=sub_array(k);l=l+1; end if end do

call genera_perm(config_array,N,local_sub_array,sub_N-1,liv+1);

end do end if

end subroutine genera_perm

call genera perm(config array,N,data array,N,1) Introduzione alla complessit`a, Paolo Bison, FI08, 2008-09-29 – p.18

Knapsack problem

Dati N elementi, caratterizzati ciascuno da un peso ed un valore monetario, da introdurre in uno zaino con una data capacità, trovare l’insieme di elementi che massimizza il valore senza superare la capacità.

algoritmo

si analizza tutte le 2

^N

− 1 possibili combinazioni degli N elementi e si sceglie quella con valore massimo che non supera la capacità dello zaino

programma knapsack.f90

Algo + efficienti

complessità dipende dalle funzionalità dell’esecutore

ordinamento

computer: quadratica

uomo: lineare

dati N elementi da ordinare:

- si taglino N bastoncini di lunghezza proporzionale al valore di ciascun elemento - tenendoli con una mano si appoggi una loro estremità su un piano

percorso minimo tra due nodi di un grafo

computer: esponenziale (NP-completo)

uomo: lineare

dati N nodi e M archi:

- si prendano N anelli

- si taglino M fili di lunghezza proporzionale agli archi - si leghino gli N anelli con gli M fili

- si prenda il nodo iniziale e quello finale e si tiri in maniera da avere una parte del grafo ben tesa tra i due anelli

Introduzione al complessità