Riassunto Algoritmi e Strutture dati

ANALISI PROBABILISTICA E ALGORITMI RANDOMIZZATI

Introduciamo un nuovo problema computazionale per studiare un metodo di analisi degli algoritmi

ed un nuovo approccio alla realizzazione di algoritmi ad esso correlato.

Supponiamo di dover assumere una nuova persona per un posto di lavoro, e di voler assumere il

migliore impiegato possibile da una lista di n candidati. I candidati sono forniti da un’agenzia di

lavoro, che richiede un piccolo compenso per ogni colloquio con un candidato, ed un compenso

molto più sostanzioso per ogni assunzione. Non sappiamo nulla di un candidato finché non

veniamo a colloquio con lui, perciò se a seguito di un colloquio questi si dimostra migliore

dell’attuale impiegato, licenziamo quest’ultimo ed assumiamo il nuovo candidato. Il seguente

pseudocodice realizza la procedura appena descritta per il problema delle assunzioni:

HIRE-ASSISTANT(n)

1 migliore = 0 //crea candidato fittizio

2 for i = 1 to n

3 colloquio con candidato i

4 if candidato i migliore dell’impiegato migliore

5 migliore = i

6 assumi candidato i

Siamo dunque interessati a sapere quale sarà il costo totale da sostenere.

Osserviamo che dobbiamo sempre effettuare n colloqui, ed un numero variabile m di assunzioni

dipendenti dalla lista di candidati fornita dall’agenzia e dall’ordine in cui essi arrivano. Indicando

con c il costo di un colloquio e c il costo di un’assunzione, il costo totale della procedura è O(n*c

c a c

+ m*c ). Dato che il numero di assunzioni è fisso e comunque c è molto minore di c concentriamo

a c a

la nostra analisi sul costo derivante dalle assunzioni.

Il caso peggiore si verifica quando i candidati arrivano in ordine crescente di competenza: in tal

caso dovrà essere effettuata un’assunzione ad ogni iterazione, ed il costo sarà di O(n*c ).

a

Siamo però interessati a sapere quale sarà il costo sostenuto nel caso medio.

Possiamo usare l’analisi probabilistica per effettuare una media sul tempo di esecuzione di tutti

gli input possibili, e ricavare un tempo di esecuzione medio. L’analisi probabilistica consiste

nell’uso della probabilità per analizzare un problema. Per utilizzare l’analisi probabilistica però

dobbiamo avere informazioni sulla distribuzione degli input o almeno fare ipotesi su di essa. Nel

nostro caso possiamo supporre che la distribuzione in input sia casuale. Dato che siamo in grado

di determinare, dati due candidati, qual è il più qualificato, (esiste un ordine totale nei candidati)

supponiamo di assegnare un numero d’ordine da 1 a n, detto rango, ad ogni candidato, con la

convenzione che maggiore è il rango maggiore è la qualifica. La lista in input <rango(1), rango(2),

… rango(n)> sarà una permutazione della lista <1, 2, … n>. Supporre che l’input sia casuale

equivale a supporre che la lista in input sia una qualsiasi delle n! permutazioni dei numeri da 1 a n,

ossia i ranghi formano una permutazione casuale uniforme.

Non sempre però è possibile fare ipotesi sulla distribuzione degli input, e di conseguenza non

possiamo applicare l’analisi probabilistica su un dato algoritmo. Possiamo però ovviare a ciò

rendendo casuale parte di esso. Nell’esempio del problema delle assunzioni abbiamo supposto

che l’input fosse casuale, ma non sappiamo se ciò sia effettivamente vero: per esserne certi

potremmo scegliere per ogni colloquio un candidato a caso tra quelli non ancora esaminati, invece

che affidarci alla lista in input. Stiamo perciò imponendo che l’input sia casuale. Un algoritmo si

dice randomizzato quando il suo comportamento è determinato, oltre che dal suo input, da un

generatore di numeri casuali. Quando analizziamo il tempo di esecuzione di un algoritmo

randomizzato nel caso medio, stiamo studiando il suo tempo di esecuzione atteso.

Dunque mentre nel primo caso facciamo l’ipotesi che l’input sia casuale, e studiamo

successivamente il tempo di esecuzione medio dell’algoritmo, nel secondo caso imponiamo un

input casuale e studiamo il tempo di esecuzione atteso.

ANALISI PROBABILISTICA DEL PROBLEMA DELLE ASSUNZIONI

Per effettuare l’analisi useremo le variabili casuali indicatrici. Dato S lo spazio dei campioni e un

evento A, la variabile casuale indicatrice I{A} associata all’evento è definita nel modo seguente:

{ }

1 se si verifica A

I A

{ }= 0 se non si verifica A

Un lemma ci dice inoltre che ponendo X = I{A}, E[X ] = Pr{A}, cioè il valore atteso di una variabile

A A

casuale indicatrice è uguale alla probabilità dell’evento cui è associata.

Definiamo ora la variabile casuale X, il cui valore è uguale al numero di volte in cui assumiamo un

nuovo impiegato. Se definiamo n variabili casuali indicatrici X , ciascuna associata all’evento che il

i

candidato i sia assunto, possiamo esprimere X come: X = X + X + … + X . Per calcolare il valore

1 2 n

atteso di ciascuna variabile dobbiamo calcolare la probabilità che il candidato i venga assunto. Al

momento della decisione se assumere o meno il candidato i, si sono presentati i candidati, ed

avendo ipotizzato che arrivassero in ordine casuale, ognuno di essi ha la stessa probabilità di

essere il più qualificato. Ne deriva che il candidato i ha probabilità 1/i di essere il più qualificato fra

quelli finora esaminati e di essere di conseguenza assunto, dunque E[X ] = 1/i. Sfruttando la

i

linearità del valore atteso possiamo adesso calcolare il numero medio di candidati assunti:

n n

∑ ∑

E[ X E[ X E[ X

] = ] = ]

i i

i=1 i=1

n

∑ 1 ln(n)+ O(1)

= /i =

i=1

Quindi su n candidati ne vengono in media assunti circa ln(n). Ne consegue che il costo medio per

le assunzioni di HIRE-ASSISTANT è O(c *ln(n)).

a

RANDOMIZZAZIONE DI UN ALGORITMO

Nel problema delle assunzioni, anziché ipotizzare che i candidati arrivino in ordine casuale,

possiamo imporre tale casualità permutando l’array di input prima di eseguire l’algoritmo. Così

facendo l’algoritmo cessa di essere deterministico (ad un dato input non corrisponde sempre lo

stesso flusso di esecuzione e lo stesso costo) e nessun input particolare causerà

sistematicamente il caso peggiore. L’ipotesi di casualità dell’input è ora sicuramente vera, e

l’algoritmo è identico al precedente a meno della permutazione iniziale dell’input, perciò le

considerazioni fatte circa il costo medio di HIRE-ASSISTANT valgono anche per la versione

randomizzata, che avrà un costo atteso di O(c *ln(n)).

a

Abbiamo visto che un modo per randomizzare un algortimo è permutare l’array di input. Una

procedura che fa ciò è la seguente

RANDOMIZE-IN-PLACE(A)

1 n = A.lenght

2 for i = 1 to n

3 scambia A[i] e A[Random(i, n)]

dove Random(i, n) genera un numero casuale compreso fra i e n (estremi inclusi). RANDOMIZE-

IN-PLACE viene eseguito nel tempo O(n).

Una procedura di questo tipo randomizza correttamente un algoritmo se genera una permutazione

casuale uniforme, ossia se ogni permutazione possibile ha la stessa probabilità di essere

generata. Definiamo una k-permutazione di A come una permutazione che contiene k degli n

elementi di A (in un insieme di n elementi ci sono n!/(n-k)! possibili k-permutazioni) e dimostriamo

la correttezza di RANDOMIZE-IN-PLACE tramite la seguente invariante di ciclo:

Appena prima dell’i-esima iterazione del ciclo for, per ogni possibile (i – 1)-permutazione di A,

A[1 … i – 1] contiene questa (i – 1)-permutazione con probabilità (n – i + 1)!/n!.

Dobbiamo dimostrare che l’invariante è vera prima della prima iterazione del ciclo, che ogni

iterazione conserva l’invariante e che quando il ciclo termina l’invariante fornisce un’utile proprietà

per dimostrare la correttezza.

Inizializzazione: prima dell prima iterazione i = 1. L’invariante ci dice che per ogni 0-

• permutazione A[1 … 0] contiene questa 0 permutazione con probabilità n!/n! = 1. Dato che

A[1 … 0] è vuoto e una 0-permutazione non contiene elementi l’invariante è verificata.

Conservazione: supponiamo che prima dell’i-esima iterazione l’invariante sia vera e

• dimostriamo che prima della successiva ogni possibile i-permutazione abbia probabilità (n

-i)!/n! di apparire in A[1 … i].

Consideriamo una i-permutazione <x , x , … x > ed osserviamo che essa è formata da una

1 2 i

(i – 1)-permutazione seguita dal valore x . Definiamo E come l’evento che ha portato alla

i 1

creazione della (i – 1)-permutazione considerata; per l’invariante abbiamo che Pr{E } = (n –

1

i + 1)!/n!. Definiamo inoltre E come l’evento in cui il particolare elemento x viene posto

2 i

nella i-permutazione generata dall’i-esima iterazione. La i-permutazione considerata viene

generata quando si verificano E e E calcoliamo quindi Pr{E ∩E }:

1 2 1 2

Pr {E ∩E }=Pr {E ∣E }Pr {E }

1 2 2 1 1

Pr è uguale a 1/(n-i+1) perché x viene scelto a caso tra gli n – i + 1 valori

{E ∣E } i

2 1

presenti in A[i … n], perciò 1)!

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

Pr {E ∩E }= ⋅ =

1 2 n−i+1 n! n!

e l’invariante è dimostrata.

Conclusione: alla fine del ciclo, i = n + 1 e ogni n-permutazione ha la stessa probabilità (n-

• n)! / n! = 1/n! di comparire in A[1 … n].

RANDOMIZE-IN-PLACE genera una permutazione casuale uniforme ed è quindi corretto.

QUICK SORT 2

È un algoritmo di ordinamento il cui tempo di esecuzione nel caso peggiore è Θ(n ), come

INSERTION-SORT, tuttavia risulta uno degli algoritmi più usati per il problema dell’ordinamento in

quanto il suo tempo di esecuzione nel caso migliore e medio è Θ(n*lg(n)), con fattori costanti

migliori di quelli di MERGE-SORT. Ha inoltre il vantaggio rispetto a quest’ultimo di ordinare l’array

di input sul posto.

Anche quicksort si affida al modello divide et impera; dato in input un arrai A[p … r]:

Divide: divide l’array di input in due sottoarray A[p … q – 1] e A[q + 1 … r], tali che ogni

• elemento del primo è minore o uguale a A[q], che a sua volta è minore o uguale ad ogni

elemento del secondo.

Impera: ordina ricorsivamente i due sottoarray. Il caso base si ha quando p >= r e l’array di

• input è dunque vuoto o composto da un solo elemento, e quindi già ordinato

Combina: poiché i due sottoarray sono già ordinati, l’intero array è o