Progettazione di algoritmi - appunti corso

Progettazione di algoritmi

1° lezione: prove in itinere o scritta e prova orale – tutorato

Un algoritmo è una qualsiasi procedura computazionale quindi un insieme di passi che trasformano l’I in O quindi descrive una procedura per ottenere la desiderata relazione tra I/O (Problema computazionale).

Es: ordinamento sequenza di numeri non decrescente; definizione formale Input: Una sequenza di n numeri x1, x2, …, xn Output: Una permutazione (scambio di numeri) x’1, x’2, …, x’n di x1, x2, …, xn | x’1<=x’2<=…<=x’n istanza.

Un algoritmo è corretto se, per ogni di I si ferma producendo l’O corretto (algoritmo non corretto o si ferma su alcuni I o risposta errata). Un algoritmo deve fornire una descrizione precisa della procedura computazionale che deve essere eseguita.

NB: Gli algoritmi e le metodologie sono importanti per ogni campo dell’informatica come routering, cloud computing, crittografia (teoria dei numeri), computer grafica (geometria computazionale), ecc.

Gordon Moore (nel 1965) disse che la densità dei transistor nei circuiti integrati avrebbe continuato a raddoppiare ogni 1 o 2 anni e che gli algoritmi saranno utilizzati per molte attività.

Analisi degli algoritmi

Analisi degli algoritmi: È possibile progettare diversi algoritmi per risolvere uno stesso problema.

Es: algoritmi di ordinamento di n numeri come Merge, Quick, Insertion, Bubble, Selection, Heap Sort.

Merge Sort: tempo proporzionale a nlogn - cnlogn con c costante non dipendente da n; Quick Sort n² (c’ n²).

Alcuni algoritmi di ordinamento non utilizzano strutture dati ausiliarie in quanto ordinano ”sul posto”. Questi algoritmi richiedono solo una piccola quantità di memoria aggiuntiva che è molto inferiore rispetto alla dimensione n dell’input. Esempi: Bubble Sort, Selection Sort, Insertion Sort, Heap Sort.

Per valutare la bontà di un algoritmo si vede l’efficienza (memoria/tempo) quindi codice macchina. Caratteristiche indipendenti dal e dalla limite inferiore (algoritmo migliore tra tanti)? Velocemente.

Efficienza: Un algoritmo è efficiente se, quando è implementato, viene eseguito su istanze input reali. Dove è eseguito l’algoritmo? Quale velocità? In base a quale input (piccolo o grande)? Molto buono.

Anche un algoritmo può richiedere molto tempo per essere eseguito se implementato male.

L’efficienza di un algoritmo dipende dalla dimensione dell’input: se è maggiore il tempo di esecuzione (temporizzazione) aumenta; è indipendente dal valore di istanza e dal processore.

Gli algoritmi di Forza Bruta considerano ogni possibile soluzione e tipicamente impiega tempo N² (o peggio) per input di dimensione N cioè un tempo esponenziale (come l’algoritmo esponenziale). Es: Ordinamento Soluzione (ingenua) esponenziale: permuto i numeri ogni volta in modo diverso fino a che ottengo la permutazione ordinata (N-1 confronti, confrontando ciascun elemento con il successivo) N.

Nel caso pessimo genero N! permutazioni NB: N! > 2 per n>3. Questo algoritmo è molto inefficiente.

Tempo polinomiale

Tempo polinomiale: un algoritmo impiega tempo polinomiale (poly-time) se quando la dimensione dell’input raddoppia, l’algoritmo risulta più lento solo di un fattore costante c.

MergeSort: per N --> tempo c x N x log N; per 2N --> tempo c x 2N x log(2N)= 2 x c x N x (logN +1) = 2 x c x N x logN + 2 x c x N (moltiplicato 1*2xcxN).

2 x c x N x logN + 2 x c x N x log N (si sommano i 2) Ricontrolla rivedendo lez ≤ = 4 x (c x N x logN) per ogni N>1; aumenta di al più 4 volte (quindi di un fattore c).

Forza bruta: per N tempo c x (N-1) x N! Per 2N tempo c x (2N-1) x (2N)! = c x (2N-1) x (2N x (2N-1) x ... x (N+1) x N!) (fattoriale di 2N) > c x 2 x (N-1) x N! X N! = (2xN!)x c x (N-1) xN! (ultima disuguaglianza perchè (2N-1) > 2x(N-1) e 2N x (2N-1) x ... x (N+1) > N! ) 2xN! non è una costante P.

Algoritmi polinomiali: si ha un tempo di esecuzione polinomiale limitato superiormente. Esistono due costanti c,d > 0 | su ciascun input di dimensione N, il numero di passi è limitato da dc N . d d d d dSe l’I viene raddoppiato (2N) allora il tempo di esecuzione passa da cN a c (2N) = c2 N N.B: 2 costante.

Analisi del caso pessimo

Analisi del caso pessimo: Un algoritmo deve essere veloce indipendente dell’I dall’istanza quindi, nello studio di efficienza, si considera il Caso Pessimo come possibile I, per una stima che andrà bene per tutti gli input visto che si considera un bound sul più grande tempo di esecuzione possibile. Molto usata.

Si può considerare anche il Caso Medio considerando un input random ma è difficile se non si possono modellare in modo accurato istanze reali e ovviamente, se l’algoritmo si comporta con un I in un modo, si potrebbe comportare molto peggio in presenza di altre distribuzioni di input.

Un algoritmo è efficiente se il suo tempo di esecuzione nel caso pessimo è polinomiale.

Tempo polinomiale nel caso pessimo: gli algoritmi in tempo polinomiale sono efficienti se le costanti c e d non sono troppo alte (poco efficienti). Eccezioni: algoritmi polinomiali che hanno costanti e/o esponenti grandi sono inutili nella pratica. Algoritmi esponenziali sono molto usati perché il caso pessimo c’è raramente (algoritmo del simplesso).

4° lezione

Tempo cubico

Tempo cubico: Dati n insiemi S1, …, Sn ciascuno dei quali è un sottoinsieme di {1, 2, …, n}, c’è qualche coppia di insiemi che è disgiunta? Soluzione O(n3). Per ogni coppia insiemi, determinare se sono disgiunti.

Se false non sono disgiunti, considera altra coppia.

Se è true nessun elemento €Sj.

Il tempo è cubico.

Importante è ricordare le proprietà logaritmi: log x= (log x) /(log a)-> log x= 1/(log a).a b b a x funzioni logaritmiche.

Regole notazione asintotica

Regole notazione asintotica (le prime 5 valgono anche con omega e teta)

• 1. d(n) = O(f(n)) ⇒ ad(n) = O(f(n)), ∀ costante a > 0 Es.: log n = O(n) ⇒ 7 log n = O(n)
• 2. d(n)=O(f(n)), e(n) =O(g(n)) ⇒ d(n)+e(n) = O(f(n)+g(n)) Es.:log n=O(n),√n=O(n)⇒logn√n=O(n)
• 3. d(n)=O(f(n)), e(n)=O(g(n))⇒ d(n)e(n) =O(f(n)g(n)) Es.:log n =O(√n), =O(√n)⇒ logn√n √n=O(n)
• 4. d(n) = O(f(n)), f(n) = O(g(n)) ⇒ d(n) = O(g(n)) Es.: log n = O( = O(n) ⇒ log n = O(n)√n), √nd d 7 4 3
• 5. f(n) = a n + ··· a n + a ⇒ f(n) = O(n ) Es.: 5n + 6n + 3n + 100 = O(n7)d 1 0n 100 n
• 6. nx = O(a ), ∀ costanti x > 0,a> 1 Es.: n = O(2 )

Dimostrazioni delle regole

Dim 1. Per a positiva (chiede all’esame) d(n)=O(f(n)) -> esistono due costanti c’>0 ed n’ t.c. d(n)≤c’f(n) (definizione di O) per ogni ≥00n n’≥ 0.

Moltiplicando entrambi i membri della disuguaglianza per a il verso si conserva perché a>0. Quindi si ha ad(n)≤ac’f(n) per ogni n n’ . Se a per c’ è costante anche c è costante.≥ 0.

Abbiamo quindi trovato le costanti c ed n per cui vale la definizione di O(f(n)) basta porre 0c=ac’ ed n0 = n’0 NB: ac’ è una costante > 0 perché sia a che c’ sono costanti >0.

Dim 2. Additività.

1. d(n)=O(f(n)) -> esistono due costanti c’>0 ed n’0≥0 t.c. d(n)≤c’f(n) per ogni n n’0≥.

2. e(n)=O(g(n)) -> esistono due costanti c’’>0 ed n’’0≥0 t.c. e(n)≤c’’g(n) per ogni n≥ n’’0.

La 1 -> d(n) per ogni n n’0 , la 2 ->e(n) per ogni n n’’0≤c’f(n) ≥ ≤c’’g(n) ≥.

Conseguenza d(n)+e(n)≤c’f(n) +c’’g(n) max{c’,c’’}f(n) + max{c’,c’’}g(n) = max{c’,c’’}≤(f(n)+g(n)) €n>n’0,n’’0.

Ponendo c= max{c’,c’’} ed n0=max{n’0, n’’0}, possiamo quindi affermare che d(n)+e(n) per ogni n n0 e cio` implica d(n)+e(n)=O(f(n)+g(n))≤c(f(n)+g(n)) ≥.

Dim 4. Transitività.

1. d(n)=O(f(n)) -> esistono due costanti c’>0 ed n’ t.c. d(n)≤c’f(n) per ogni n n’0≥0 ≥0.

2. f(n)=O(g(n)) -> esistono due costanti c’’>0 ed n’’0≥0 t.c. f(n)≤c’’g(n) per ogni n n’’0≥.

La 1 à-> d(n) per ogni n n’0 , la 2 -> f(n) per ogni n n’’0 - d(n)≤c’f(n) ≥ ≤c’’g(n) ≥ ≤c’f(n) per ogni n maggiore di n’0 e n’’0 .≤c’(c’’g(n))=c’c’’g(n).

Ponendo c=c’c’’ ed n =max{n’0, n’’0}, possiamo affermare che d(n) per ogni n n0 e ≤cg(n) ≥0 -> d(n)=O(g(n)).

Bound asintotici per logaritmi

Bound asintotici per Logaritmi: La base di un algoritmo, se costante, non influisce sull’andamento della funzione asintotica, infatti la base si omette.

- O (log n)=O (log n) per ogni costante a, b > 0 (anche Ω/teta).a b

Dim per O: dalla proprietà 1 dei logaritmi si ha, log n= log n/(log a) (*)a b b.

Siccome banalmente log n = O (log n ) allora per la regola 1 della notazione asintotica, si b bha log n/(log a)= O(log n ) (si moltiplica per costante 1/log a) siccome dalla (*)b b b blog n = log n/(log a) allora log n = O(log n ) analogamente possiamo dimostrare che log na b b a b b= O(log n )a.

- log n= O(n) Dim per induzione: Dimostriamo per induzione che log n <n per ogni2n>1.

Base: Vero per n=1.

Passo Induttivo: Supponiamo log n n vera per n. Dimostriamo che è vera per n+1.≤2.

1. log (n+1) log (2n) = log 2 + log n = 1 + log n - per ipotesi induttiva log n≤2 2 2 2 2 2n e quindi≤.

2. 1+log n n+1 quindi log (n+1) n+1.≤ ≤2 2.

Parte intera inferiore e superiore

Parte intera inferiore: x-1<⌊x⌋≤x - Es. ⌊4.3⌋=4 , ⌊6.9⌋=6 , ⌊3⌋=3.

Proprietà 1: L’intero più piccolo strettamente maggiore di x è ⌊x⌋+1. Dim. Dalla def. di ⌊x⌋ si ha x-1< ⌊x⌋ x . La prima disequazione implica x < ⌊x⌋+1 . Le disequazioni x < ⌊x⌋+ 1 e ⌊x⌋ x≤ ≤ implicano la proprietà . Proprietà 2: ⌊⌊a/b⌋/c⌋ = ⌊a/(bc)⌋, per a, b e c interi con b e c maggiori di 0.

Parte intera superiore: x ⌈x⌉ < x+1 – Es. ⌈4.3⌉ =5 , ⌈6.9⌉ =7 , ⌈3⌉=3≤.

Proprietà 3: L’intero più grande strettamente minore di x è ⌈x⌉ -1. Dim. Dalla def. di ⌈x⌉ si ha x ⌈x⌉ < x. Le disequazioni x ⌈x⌉ e ⌈x⌉ -1 < x implicano la proprietà .≤ ≤.

Proprietà 4: ⌈ ⌈ a/b ⌉ / c⌉ = ⌈ a/(bc) ⌉ per a, b e c interi con b e c diversi da 0.

Tempo logaritmico

Tempo logaritmico: Θ(log n) Tipicamente si ha quando ogni passo riduce di un fattore costante il numero di passi che restano da fare.

Dim: Ad ogni iterazione il valore di i è della metà del valore che aveva in precedenza ->≤ k dopo la k-esima iterazione i = ⌊..⌊ n/2⌋ /2⌋ K divisioni= ⌊ n/2 ⌋ per la proprietà 2 della parte intera inferiore. k k k.

Il ciclo termina con il più piccolo k per cui ⌊ n/2 ⌋ < 1 . Cioè k tale che ⌊ n/2 ⌋ < 1 e ⌊ n/2 -1 ⌋1≥ k k k⌊ n/2 ⌋ < 1 n/2 < 1 2 > n > log n (1)  k 2k-1 k-1 k-1⌊ n/2 ⌋ 1 1 n k-1 log n (2)n/2 2 ≥ ≥ ≤ ≤ 2k è quindi il piccolo intero > di log2 n ; per la proprietà 1 si ha k=⌊log2 n ⌋ + 1.

NB: Se il valore di i viene * per una generica costante c>1 allora la base del log è c ma ai fini della valutazione asintotica non cambia niente.

5° lezione

Tempo logaritmo

Tempo logaritmo: Θ(log n).

Dim: Il for termina quando i>n. Ad ogni iterazione il valore di i raddoppia dopo la k-esima  più piccolokiterazione i=2 . Per sapere dopo quante iterazioni termina il for dobbiamo trovare ilk k k k k kk per cui 2 > n. k tale che 2 >n e 2 -1 ≦ n quindi 2 >n e 2 -1 n otteniamo 2 >nk>log n≤ 2ke 2 -1 ≦ n log nk-1 ≤ 2.

Le due disuguaglianze ottenute implicano log n -1 < k -1 log n e si ha k-1=⌊log n⌋ da cui≤2 2 2kk= ⌊log n ⌋ +1. Dopo esattamente k=⌊log n ⌋ +1 iterazioni i=2 diventa >n  Numero2 2iterazioni è ⌊log n⌋ +1 =Θ(log n)2.

Ricerca binaria

Es: Ricerca Binaria con struttura dati che consente un accesso in tempo costante ad un elemento(i) Elementi ordinati in ordine decrescente.

//finchè c’è un elemento si va al centro-1 //calcolo centro //se è minore, la ricerca si farà a sx //se è maggiore, ricerca a dx.

Se la dimensione r-l+1 dell’intervallo [l,r] è pari allora il sottointervallo di destra [c+1,r] ha un elemento in più rispetto a quello di sinistra. In caso contrario i due sottointervalli hanno la stessa dimensione. Caso r-l+1 pari: intervallo di sinistra ha ⌊(r-l+1)/2⌋ - 1 elementi e quello di destra ⌊(r-l+1)/2⌋. Caso r-l+1 dispari: entrambi gli intervalli hanno ⌊(r-l+1)/2⌋ elementi. vuoto.

Analisi: Il while termina quando l>r, cioè quanto il range [l,r].

• Inizialmente [l,r]=[0,n-1] e quindi contiene n elementi
• Dopo la prima iterazione, [l,r] contiene al più ⌊n/2⌋ elementi
• Dopo la seconda iterazione, [l,r] contiene al più ⌊ ⌊n/2⌋/2⌋= ⌊n/4⌋ elementi
• Dopo la terza iterazione, [l,r] contiene al più ⌊⌊n/4⌋/2⌋= ⌊n/8⌋ elementi ecc…k
• Dopo la k-esima iterazione, [l,r] contiene al più ⌊n/2 ⌋ elementi k
• Per sapere quando termina il while dobbiamo trovare il più piccolo k per cui ⌊n/2 ⌋<1
• Abbiamo già dimostrato che questo k è Θ(log n)
• NB: per sbarazzarci delle parti intere inferiori annidate abbiamo usato la proprietà2.

Tempo O(n log n) e O(√n)

Tempo O(n log n): Tipicamente viene fuori quando si esamina la complessità di algoritmi basati sul divide et impera (es.merge-sort).

Tempo O(√n) Analisi: Il while termina quando i>n. All’iterazione k al valore di i viene sommato j=k per cui dopo aver iterato il while k volte il valore di i è (1+2+3+...+k)=k(k+1)/2 e si interrompe con k(k+1)/2>n.

2 2Per semplicità osserviamo che k /2< k(k+1)/2 se k /2>n allora k(k+1)/2>n .2 2 1/2Risolviamo k2/2 >n . k /2 >n k >2n k > (2n) . (consideriamo Quindi abbiamo  ).

1/2trovato un k per il quale k(k+1)/2>n. Dalla proprietà 1, ⌊(2n) ⌋+1 è il più piccolo intero>1/2(2n) per cui dopo ⌊(2n)1/2 ⌋+1 = O(√n) iterazioni il while termina.

Il tempo logaritmico è sempre meglio di quello con una radice.

Radici

Radici: Per ogni costante x>0, log n=O(n^x). (N.B. x può essere < 1)x x.

Dim. Se x si ha n≤ n per ogni n≥0 e quindi n=O(n ). Già dimostrato log n=O(n) per cui≥1 xdalla proprietà transitiva si ha log n=O(n ). x.

Consideriamo il caso x<1. Vogliamo trovare le costanti c>0 e n0≥0 | log n con n≥n≤cn 0x xSiccome sappiamo che log m<m per ogni m≥1 allora ponendo m=n con n≥1, si ha log n2 2x x x<n da cui xlog n<n e dividendo entrambi i membri per x si ha log n<1/x n .Perchè la2 2xdisequazione log n≤ cn sia soddisfatta per ogni n≥n0, basta quindi prendere c=1/x e n =1.2 0b x.

Polinomi

Polinomi: Per ogni x>0 e b>0 costanti, (log n) =O(n ).b x b.

Dim: Trovare costanti c>0 e n tali che (log n) per ogni n≥n . Risolviamo (log n) cnx :≥0 ≤cn ≤0 0b x x 1/b 1/b x/b(log n) log n (cn ) = c n ( vale log n>0). Troviamo c>0 ed n tali che log≤cn ≤ ≥001/b x/bn c n per ogni n≥n0.≤ y.

Abbiamo già dimostrato nella slide precedente che log n=O(n ) per ogni y>0. Ciò vale anchex/bse poniamo y= x/b. Quindi esistono due costanti c’>0 e n’0≥0 tali che log n per ogni≤c’nn≥n’0. 1/bDi conseguenza basta imporre c = c’ ed n0 = n’0 da cui c=(c’)b ed n0 = n’0.a b x.

È possibile dimostrare che per ogni x > 0 , a>0 e b>0 costanti , (log n ) = O(n ).x x.

Dim: per ogni x>0 costante, log n non è Ω(n ). Per definizione di Ω: log n =Ω(n ) esistonox x xdue costanti c>0 e n ≥0 tali che log n ≥ cn per ogni n≥n0 . log n ≥ cn ≤ (log n)/n .c0 x.

Quindi le costanti c ed n0 devono essere tali che c ≤ (log n)/n per ogni n≥n0 .xIl limite di (log n)/n con n->∞ è 0 per cui comunque scegliamo c esisterà un n per cui (logcx xn)/n <c quindi per qualsiasi costante c non è possibile trovare un n0 per cui log n ≥ cn per ogni n ≥ n0.

Massimo insieme indipendente

Massimo insieme indipendente: il massimo insieme di nodi tale che, per ogni coppia di nodi, non c’è un arco che li congiunge. Per trovare un massimo insieme di k nodi:

Insieme indipendente di dimensione k (k costante). Dato un grafo, esistono k nodi tali che nessuna coppia di nodi è connessa da un arco? Soluzione O(n ) tempo polinomiale: Enumerare tutti i sottoinsiemi di k nodi. 2Controllare se S è un insieme indipendente = O(k )Numero di sottoinsiemi di