Appunti Algoritmi e strutture dati

IMPARA BENE COSA E' K CHE LO CHIEDE ALL'ORALE

Quindi è k che andiamo a confrontare con l'indice della statistica. Se k=i, allora siamo stati fortunati perché cercavamo la statistica di ordine i e nel vettore ci sono proprio i elementi minori del pivot: restituiamo proprio A[q]. Altrimenti, cosa dobbiamo fare? Se la statistica di ordine i cercata è minore di k, allora dobbiamo andare a cercare la statistica di ordine i nella porzione di A che va da p a q-1. Altrimenti, andiamo a cercare tra gli indici q+1 ed r e la statistica cercata avrà ordine i-k.

Per quest'algoritmo il tempo peggiore è sempre TETA(n al quadrato). Se il pivot viene scelto in maniera tale da essere o il più piccolo o il più grande del sottovettore, se si presenta in tutti i casi, avremo una complessità del tipo TETA(n al quadrato). Quest'algoritmo utilizza la versione randomizzata per evitare che a priori sia nota un'istanza.

del problema che finisce sempre nel caso peggiore, perché ad ogni invocazione della funzione utilizziamo un seme differente per la generazione dei numeri casuali. Se ci sono elementi ripetuti, l'algoritmo funziona correttamente.

Dovremo calcolare un valore atteso del tempo di esecuzione: per fare questo, introduciamo una variabile aleatoria. La variabile aleatoria che introduciamo è Xk, variabile indicatrice che può valere 0 oppure 1; il pedice k indica che la variabile è funzione di un valore k. In particolare questa variabile vale 1 se nella porzione del vettore A considerato ci sono k elementi minori/uguali del pivot; 0 altrimenti.

Se indichiamo con n il numero di elementi presenti nel sotto-vettore che stiamo considerando, k sarà compreso tra 1 ed n. Avremo n variabili aleatorie, e di queste ovviamente solo 1 avrà valore 1 e tutte le altre varranno 0.

Questo in realtà, a rigore, quando gli elementi della porzione di vettore sono tutti distanti.

Infatti, se noi come sotto-vettore abbiamo ad esempio: avremo le variabili x1, x2, x3, fino ad x7. Ogni variabile indica quanti elementi sono minori/uguali del pivot scelto. Quello che succede è che ciascuna di queste variabili è una variabile aleatoria discreta, per cui la media statistica di ciascuna di esse è data dalla combinazione lineare dei valori assunti ciascuno pesato per la probabilità di quel valore. Quindi abbiamo: per tutte le Xk. Siccome noi il pivot lo scegliamo casualmente, abbiamo un uguale probabilità che il pivot sia il primo elemento più piccolo, il secondo più piccolo e così via. In questo caso, abbiamo che la probabilità che una generica Xk sia pari ad 1 è uguale a 1/n, proprio perché con uguale probabilità possiamo scegliere come pivot il primo elemento più piccolo, il secondo più piccolo e così via. Se consideriamo però il caso di questo vettore, in cui non ci

sono tutti elementi distinti :possiamo scegliere come pivot gli elementi 1,2,4,5. Abbiamo 4 valori distinti di pivot che possiamo scegliere : se scegliamo il valore 2 come elemento pivot, quello che succede è che ci sono 3 elementi minori/uguali del pivot (1,2,2) ; se scegliamo 1 ne avremo 1 ; se scegliamo 4 ne avremo 4 ; se scegliamo 5 ne avremo 7.

Questo vuol dire che di queste 7 variabili aleatorie non hanno tutte la probabilità 1/7 di essere scelte :

• x1 è vera quando c'è un elemento minore/uguale del pivot. Questa variabile sarà vera se scegliamo 1 come pivot : probabilità 1/7.
• x2 è pari ad 1 con probabilità pari a 0, perché non ci saranno mai due elementi minori/uguali del pivot, ma ne avremo 3.
• x3 vale 1 quando ci sono tre elementi minori uguali del pivot : 2/7, perché possiamo scegliere uno dei due 2, in entrambi i casi il numero di elementi minori/uguali di 2 è sempre 3.
• x4 vale 1 quando ci sono 4

elementi minori del pivot : succede quando scegliamo 4 ->probabilità 1/7- x5 vale 1 quando abbiamo 5 elementi minori/uguali del pivot : non succede mai- x6 vale 1 quando abbiamo 6 elementi minori/uguali del pivot : non succede mai- x7 la probabilità è 3/7

In che senso vogliamo valutare un tempo di esecuzione atteso?

Abbiamo detto che anche se fissiamo la sequenza di valori e l’ordine della statistica che vogliamo cercare, se eseguiamo più volte l’algoritmo avremo tempi di esecuzione diversi e per un’esecuzione potremmo anche finire nel caso peggiore, perché ne fare diverse invocazioni può capitare di essere sfortunati e capitare nel caso peggiore.

Quindi, il tempo di esecuzione nei diversi casi rappresenta una variabile aleatoria e noi ne vogliamo calcolare la media statistica che ne rappresenta i tempi di esecuzione nelle diverse esecuzioni dell’algoritmo.

Ovviamente noi ad ogni invocazione ricorsiva della RandomizeSelect,

se non rientriamo nel caso banale, o siamo fortunati e il pivot è la statistica di ordine cercata e termine l'esecuzione dell'algoritmo, oppure dobbiamo continuare la ricerca.

Quello che vogliamo valutare è comunque il valore atteso del tempo di esecuzione maggiore possibile data la scelta del pivot.

Come possiamo esprimere il tempo di esecuzione dell'algoritmo in quest'ipotesi?

Vogliamo un limite superiore al tempo di esecuzione fissata la scelta del pivot: quello che impostiamo quando andiamo a calcolare il limite superiore è una disequazione, in questo caso ricorrente.

Non dobbiamo pensare al caso peggiore in assoluto, dobbiamo considerare il caso fissata la scelta del pivot.

Sono n le possibili scelte del pivot se abbiamo n elementi della sotto-porzione che andiamo a considerare.

Guardiamo solo quello che c'è tra parentesi: avremo k elementi minori/uguali del pivot, e quindi andiamo a cercare o nella partizione k-1 o nella partizione n-k.

Il limite superiore sarà ottenuto incorrispondenza della risoluzione del sotto-problema di dimensione maggiore : con "max"indichiamo la dimensione più grande tra le due partizioni. Per questo indichiamo con T(max(...))il tempo richiesto per invocare la Randomize Select sulla partizione maggiore (..) e in piùaggiungiamo il termine O(n) che è il tempo per effettuare la partition.Ora però quest'espressione, dipende da k, che dipende dalla scelta del pivot.Per tenere in conto tutte le possibile scelte del pivot che scelte in maniera casuale, utilizziamoquesta notazione di sommatoria di Xk che moltiplica quanto detto prima.Quest'espressione per una data realizzazione, una sola è pari ad 1 e tutte le altre sono pari a 0 :abbiamo una sommatoria di n termini, ma si traduce in un solo termine, tutti gli altri saranno 0perché moltiplicati per Xk che sarà pari a 0.Quindi, a secondo membro abbiamo il tempo diesecuzione di Randomize Select nel caso peggiore. A questo punto si fanno un po' di passaggi matematici: innanzitutto teniamo presente che nella sommatoria, solo un termine sarà non nullo, quindi l'O(n) lo possiamo portare al di fuori della sommatoria visto che non dipende da k: <p>Possiamo calcolare il tempo atteso in senso statistico:</p> Applichiamo la linearità della media statistica: <p>Facciamo l'ipotesi che le due variabili aleatorie Xk e T(..) siano quantità indipendenti, e quindi la media del prodotto è pari al prodotto delle medie:</p> E[k] lo abbiamo calcolato prima ed è pari ad 1/n. Dobbiamo fare delle considerazioni per valutare l'altra media. Abbiamo fissato n, il numero di elementi presenti all'interno della porzione di vettore considerata e k varia da 1 ad n: in maniera abbastanza semplice possiamo andare a considerare, ad esempio n=5 => k varia da 1 a 5, e dobbiamo individuare il max tra k-1 e n-k. Il valore massimo varia da

n-1 fino ad n/2 (approssimato per difetto), dopo di che abbiamo nuovamente gli altri valori; tutti i valori si presentano 2 volte, tranne n/2 che si presenta una sola volta.
Se n fosse stato pari, il valore più piccolo si presentava due volte ed era vero che tutti i valori tra n-1 e n/2 si presentavano due volte.
Questa considerazione ci consente di semplificare la nostra espressione, perché al variare di k tra 1 e n, il max è compreso tra n-1 e n/2:
Abbiamo esplicitato i valori assunti dal valore massimo.
Nel caso di n dispari, un valore lo dovremmo prendere una sola volta, ma poiché stiamo maggiorando, non è un problema.
Dobbiamo trovare una soluzione per questa ricorrenza.
La soluzione candidata è E[T(n)]=O(n). (non è stato detto da dove arriva questa soluzione candidata)
Lezione 14 (28.10.2020)
Proviamo per sostituzione che una soluzione della ricorrenza della lezione scorsa sia un O(n).
Quando risolviamo una ricorrenza per sostituzione,

applichiamo il metodo induttivo: in tal caso, la nostra ipotesi prevede che riusciamo ad individuare una costante positiva ed un n0 tale che il valore atteso sia minore di cn. Dobbiamo verificare che la relazione vale per un caso base e poi, assumiamo la tesi vera per un certo valore di n e dobbiamo dimostrarla vera anche per un valore successivo di n. In questo modo, riusciamo a dimostrare che la tesi vale per tutti gli n. Il nostro passo induttivo consisterà nell'assumere che la T(n) < cn, quindi la nostra tesi è vera in tutti i valori da cui dipende T(n) (quindi per n-1, n-2... fino ad arrivare a n/2); vogliamo poi dimostrarla vera anche per n. Assumere vera la tesi significa che E[T(k)] <= c*k. Qualunque sia la funzione O(n) sarà sicuramente maggiorabile con un "an" per la definizione di O(n). Ora dobbiamo fare dei calcoli per dimostrare E[T(n)] <= cn. "c" non dipende dalla sommatoria e lo possiamo portare fuori: Questa sommatoria ci

Ricorda la somma dei primi n numeri naturali; non abbiamo "k che va da 1 a n-1", però tuttavia riusciamo a convertire facilmente nella forma che vogliamo ottenere. Cerchiamo di toliere l'approssimazione per difetto: lo facciamo andando a maggiorare l'espressione. L'unica accortezza che dobbiamo avere, è che le quantità n/2 approssimato sono precedute da un segno meno:

Allora => Isoliamo il termine cn e facciamo una maggiorazione per andare ad eliminare -2/n:

In questa relazione cerchiamo di esplicitare il valore di n e vedere che condizione deve essere verificata su c ed a affinché la relazione sia vera. Se scegliamo c tale che c/4-a>0, ovvero c>4a: è un vincolo da tenere in considerazione nella determinazione della costante c che rende vera la nostra tesi.

Questo risultato cosa ci dice? Ci dice che se scegliamo la costante c maggiore di 4a (dove a è una costante determinata dalla notazione asintotica per il contributo