Algoritmi e Strutture Dati
Capitolo 17 - Algoritmi probabilistici
Alberto Montresor
Università di Trento
This work is licensed under the Creative Commons Attribution-NonCommercial-ShareAlike License. To view a
copy of this license, visit http://creativecommons.org/licenses/by-nc-sa/2.5/ or send a letter to Creative
Commons, 543 Howard Street, 5th Floor, San Francisco, California, 94105, USA.
© Alberto Montresor
1
Introduzione
“Audentes furtuna iuvat” - Virgilio
✦
Se non sapete quale strada prendere, fate una scelta casuale
✦
Abbiamo già incontrato il concetto di casualità
✦
Analisi del caso medio - si calcola una media su tutti i possibili dati di ingresso,
dopo aver individuato una distribuzione di probabilità per essi
✦
Esempio: caso medio Quicksort, si assume che tutte le permutazioni siano
equiprobabili
✦
Negli algoritmi probabilistici
✦
Il calcolo delle probabilità è applicato non ai dati di input, ma ai dati di output
✦
Due possibilità
✦
Algoritmi corretti, il cui tempo di funzionamento è probabilistico
✦
Algoritmo la cui correttezza è probabilistica
✦
© Alberto Montresor
2
Esempio - espressione polinomiale nulla
Definizione: data un’espressione algebrica polinomiale p(x1 , ... , xn) in n variabili,
determinare se p è identicamente nulla oppure no
✦
Discussione
✦
Assumiamo che non sia in forma di monomi - altrimenti è banale
✦
Gli algoritmi basati su semplificazioni sono molto complessi
✦
Algoritmo
✦
Si genera una n-pla di valori v1, ..., vn
✦
Si calcola x= p(v1 , ... , vn)
✦
Se x ≠ 0, p non è identicamente nullo
✦
Se x = 0, p potrebbe essere identicamente nullo
✦
Se vi = random(1, 2d), dove d è il grado massimo del polinomio, allora la
probabilità di errore non supera 1/2.
✦
Si ripete k volte, riducendo la probabilità di errore a (1/2)k
✦
© Alberto Montresor
3
Statistica
Algoritmi statistici su vettori: Estraggono da un vettore numerico alcune
caratteristiche statisticamente rilevanti
✦
Esempi
✦
Media: μ = (A[1] + A[2] + ... + A[n])/n
✦
Varianza (sample variance):
✦
Moda: il valore più frequente (o i valori)
✦
Mediano: il valore che occuperebbe la posizione ⎡n/2⎤ se l'array fosse ordinato
✦
Selezione:
✦
Dato un array A[1..n] di valori distinti e un valore 1 ≤ k ≤ n, trovare l'elemento che
è maggiore di esattamente k-1 elementi
✦
© Alberto Montresor
4
Selezione: casi particolari
Ricerca del minimo, massimo
✦
T(n) = n-1 = θ(n) confronti
✦
Possiamo dimostrare che questo algoritmo è ottimale?
✦
Idea: scelta del minimo come un “torneo”
✦
Tutti gli elementi (tranne il vincitore) deve perdere almeno un “partita”
✦
Quindi il problema è Ω(n)
✦
© Alberto Montresor
5
Selezione: casi particolari
Ricerca del secondo minimo
✦
Trovare il secondo elemento più piccolo dell'array
✦
Domanda: Analisi del caso peggiore e medio
✦
© Alberto Montresor
6
Selezione: casi particolari
Ricerca del secondo minimo
9
✦
L'albero del torneo permette di trovare il
secondo minimo in O(n + log n) confronti
nel caso pessimo
✦
8
9
Dimostrazione
✦
n passi necessari per la ricerca del minimo
✦
8
7
9
3
Siano M e S il minimo e il secondo minimo
✦
Sicuramente c'è stato un “incontro” fra M e S, dove M ha “vinto”
✦
Se così non fosse, esisterebbe un valore X<S che ha
“battuto” S → assurdo dalla definizione di S
✦
Quindi, basta cercare nei log n valori “battuti” direttamente da M per trovare il
secondo minimo. Totale: O(n + log n)
✦
© Alberto Montresor
7
Selezione per piccoli valori di k
Intuizione
✦
L'albero del torneo può essere “simulato” da uno heap
✦
L'algoritmo può essere generalizzato a valori generici di k > 2
✦
Complessità computazionale: O(n + k log n)
✦
Se k = O(n/log n), il costo è O(n)
✦
Non va ancora bene per k = n/2
✦
Codice
✦
heapselect(Item[] A, integer n, integer k)
buildHeap(A)
for i := 1 to k-1 do
deleteMin(A, n)
return min(A)
© Alberto Montresor
8
Selezione

Idea


Approccio divide-et-impera simile al Quicksort
Ma essendo un problema di ricerca, non è necessario cercare in entrambe le
partizioni, basta cercare in una sola di esse
1
primo
j
ultimo n
q
© Alberto Montresor
9
Complessità
Caso pessimo: O(n2)
✦
Caso ottimo: O(n)
✦
Caso medio
✦
Assumiamo che perno() restituisca con la stessa probabilità una qualsiasi posizione
j del vettore A
✦
© Alberto Montresor
10
Dimostrazione
Per sostituzione
✦
© Alberto Montresor
11
Versione probabilistica
Siamo partiti dall’assunzione
✦
j assume equiprobabilisticamente tutti i valori compresi fra 1 e n
✦
E se non è vero?
✦
Lo forziamo noi
✦
A[random(primo, ultimo)] ↔ A[primo]
✦
Questo accorgimento vale anche per QuickSort
✦
© Alberto Montresor
12
Selezione in tempo pessimo lineare
Algoritmo deterministico
✦
Deterministico: non necessita di randomizzazione
✦
Algoritmo complesso, con fattori coinvolti molto alti
✦
Interessante dal punto di vista della tecnica
✦
Sviluppiamo l'idea
✦
Supponiamo di avere un algoritmo “black box” che mi ritorni il mediano di n valori
in tempo O(n)
✦
Domanda
✦
Potrei utilizzarlo per ottimizzare il problema della selezione?
✦
Che complessità otterrei?
✦
© Alberto Montresor
13
Selezione in tempo pessimo lineare
Se conoscessi tale algoritmo
✦
il problema della selezione sarebbe quindi risolto
✦
... ma dove lo trovo un simile algoritmo?
✦
Rilassiamo le nostre pretese
✦
Supponiamo di avere un algoritmo “black box” che mi ritorni un valore che dista al
più n/4 dal mediano (nell'ordinamento)
✦
Domanda
✦
Potrei utilizzarlo per ottimizzare il problema della selezione?
✦
Che complessità otterrei?
✦
Un algoritmo del genere esiste!
✦
© Alberto Montresor
14
Selezione deterministica - cenni
L'idea dell'algoritmo
✦
Suddividi i valori in gruppi di 5. Chiameremo l'i-esimo gruppo
Si, con i ∈ [1, ⎡n/5⎤]
✦
Trova il mediano mi di ogni gruppo Si
✦
Tramite una chiamata ricorsiva, trova il mediano M dei mediani mi
✦
Usa M come pivot e richiama l'algoritmo ricorsivamente sull'array opportuno, come
nella selezione() randomizzata
✦
Caso base
✦
Possiamo utilizzare un algoritmo d'ordinamento per trovare il mediano quando la
dimensione scende sotto una certa soglia
✦
© Alberto Montresor
15
Selezione deterministica - cenni
select(Item[] A, integer primo, integer ultimo, integer k)
if (ultimo-primo+1) ≤ 10 then
ordina A[primo...ultimo] ;
return k-esimo elemento di A[primo...ultimo]
{ partiziona A in ⎡n/5⎤ sottoinsiemi Si di 5 elementi }
for i ← 1 to ⎡n/5⎤ do mi ← median5(Si)
M ← select( {mi : i=1..⎡n/5⎤}, 1, ⎡n/5⎤ , ⎡n/5⎤/2)
j ← perno(A, primo, ultimo, M)
q ← j-p+1
// Indice di M in [primo..ultimo]
if q = k then
return M
else if q < k then
return select(A, primo, q-1, k)
else
return select(A, q+1, ultimo, k-q)
© Alberto Montresor
16
Seleziona deterministica - cenni
Lemma 1
✦
Il calcolo dei mediani mi richiede al più 6⎡n/5⎤ confronti.
✦
Lemma 2
✦
La prima chiamata ricorsiva dell'algoritmo select() viene effettuata su circa n/5
(esattamente ⎡n/5⎤)
elementi
✦
Lemma 3
✦
La seconda chiamata ricorsiva dell'algoritmo select() viene effettuata al massimo
su 7n/10 elementi (esattamente n - 3⎡⎡n/5⎤/2⎤)
✦
Teorema
✦
L'algoritmo select() esegue nel caso pessimo O(n) confronti
✦
Equazione di ricorrenza: T(n) ≤ T(n/5) + T(7n/10) + 11/5n
✦
E' possibile dimostrare che T(n) = O(n)
✦
© Alberto Montresor
17
Lemma 1
© Alberto Montresor
18
Alcune note storiche
Il problema della selezione nella storia...
✦
Nel 1883 Lewis Carroll (!) notò che il secondo premio nei tornei di tennis non
veniva assegnato in maniera equa.
✦
Nel 1932, Schreier dimostrò che sono necessari n + log n - 2 incontri sono sempre
sufficienti per trovare il secondo posto
✦
Nel 1973, a opera di Blum, Floyd, Pratt, Rivest e Tarjan, appare il primo algoritmo
deterministico
✦
© Alberto Montresor
19
Bucket sort
Ipotesi sull'inputI valori da ordinare sono numeri reali uniformemente
distribuiti nell'intervallo [0, 1)Qualunque insieme di valori distribuiti uniformemente
può essere normalizzato nell'intervallo [0, 1)IdeaDividere l'intervallo in n sottointervalli
di
dimensione 1/n, detti bucket, e poi
distribuire gli n numeri nei bucketPer l'ipotesi di uniformità, il numero
atteso di valori nei bucket è 1I singoli bucket possono essere ordinati con
0.0
Insertion Sort
✦
0.1
0.2
0.3
0.4
0.5
0.6
0.7
0.8
0.9
© Alberto Montresor
20