• Non ci sono risultati.

Introduzione alla complessità

N/A
N/A
Protected

Academic year: 2021

Condividi "Introduzione alla complessità"

Copied!
20
0
0

Testo completo

(1)

Introduzione alla complessità

Paolo Bison

Fondamenti di Informatica 1 A.A. 2004/05

Universit`a di Padova

(2)

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

(3)

valore di un polinomio

 dato polinomio

A m x m + A m −1 x m −1 + . . . + A 1 x + A 0 valutarlo in x 0

 dimensione n = m-1

numero dei coefficienti A i

(4)

valore di un polinomio

 algoritmo 1

pol ← A 0 i ← 1

while i ≤ m pot ← 1 k ← i

while k > 0

pot ← pot × x 0 k ← k - 1

pol ← A i × pot + pol i ← i+1

¯¯¯|C 0

|

¯¯¯|

| C 1 (n − 1)

|

¯¯¯|

| C 2 P n

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

|

¯¯¯| C 3 (n − 1)

|

 tempo di esecuzione

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

+ C (n − 1)

(5)

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 ← A m i ← m-1

while i ≥ 0 do

pol ← pol × x 0 +A i i ← i-1

¯¯¯|D 0

|

¯¯¯|

| D 1 (n − 1)

|

 tempo di esecuzione

f T (n) = D 0 + D 1 (n − 1)

 algoritmo “migliore” ?

 comportamento asintotico per n→ ∞

(6)

notazione O

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

se esistono due costanti positive c e n 0 tali che 0 ≤ f(n) ≤ cg(n)

per ogni n ≥ n 0

n

0

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

(7)

classi di complessità k costante

log n logaritmica

√ n

n lineare

n log n subquadratica n 2 quadratica

n 3 cubica

n a polinomiale a n esponenziale

n ! fattoriale

10 20 30 40 50 60

10 20 30 40 50 60

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

 valore di un polinomio

f (n) = O(n 2 ) f = O(n)

(8)

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

(9)

Radice intera

 calcolo della radice quadrata intera di un numero n > 0

 la radice intera è quel numero m che soddisfa le

condizioni m 2 ≤ n e (m + 1) 2 > n

(10)

Radice intera - I

 metodo

static public int isqrtI(int n) {

int i,m=0;

for (i=1;i<=n; i++)

if ((i*i<=n)&&((i+1)*(i+1)>n)) m=i;

return m;

}

 O (n)

(11)

Radice intera - II

 metodo

static public int isqrtII(int n) {

int m;

m=1;

while ((m*m>n)||((m+1)*(m+1)<=n)) m = m+1;

return m;

}

 O ( √

n )

(12)

Radice intera - III

 metodo

static public int isqrtIII(int n) {

int m,min,max;

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

while (min!=max-1){

if (m*m>n) max=m;

else min=m;

m=(min+max)/2;

}

return m;

}

 O (log n)

passo 1 2 . . . k . . . log 2 n

dim. n/2 n/4 . . . n/2 k . . . 1

(13)

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

(14)

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

(15)

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

(16)

Generazione delle configurazioni - I

 disposizione con ripetizione di N elementi for (i0=0;i0<N;i0++)

for (i1=0;i1<N;i1++) ....

for (iN_2=0;iN_2<N;iN_2++)

for (iN_1=0;iN_1<N;iN_1++)

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

 O (N N )

 numero dei for dipende dalla dimensione N

(17)

Generazione delle configurazioni - II

 algoritmo ricorsivo

genera(int[] i, int liv, int N){

if (liv==N-1)

for(i[liv]=0;i[liv]<N;i[liv]++) config(i);

else for(i[liv]=0;i[liv]<N;i[liv]++) genera(i,liv+1,N);

}

 attivazione

genera(i,0,N)

(18)

Generazione delle configurazioni - III

 permutazioni semplici di N elementi

genera(int[] i, int[] ii, int liv){

int k,j,l;

if (ii.length==1){

i[liv]=ii[0];config(i); } else for(k=0;k<ii.length;k++){

i[liv]=ii[k];

int[] localii= new int[ii.length-1];

for (j = 0,l=0; j < ii.length; j++) if (j != k) localii[l++]=ii[j];

genera(i,localii,liv+1);

} }

}

(19)

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

 progetto Bluej: knapsack

(20)

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

Riferimenti

Documenti correlati

Definiti i limiti naturali e di specificazione, per impostare l’analisi della capacità dei processi è opportuno ricordare che una scarsa capacità di un processo è sempre dovuta

Anche in quelle ipotesi – come, ad esempio, lo stato vegetativo – in cui parlare di sup- porto nell’effettuazione di una scelta (in luogo della sostituzione) non sembra altro che

FLEX WE/WD Modalità di conferimento delle capacità secondarie di iniezione e di erogazione su base giornaliera avente ad oggetto ciascun giorno del periodo WE con

The study covers the period 1935-1953, and concerns scholarly interaction at five foreign academies in Rome – the Swedish Institute in Rome SIR, the British School at Rome BSR,

 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

 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

 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

Prendendo spunto dalle nozioni acquisite, disegna e riporta sul foglio, gli esercizi ( non meno di 10 stazioni a circuito)che ritieni siano adeguati per allenare : la