Clasele 9-10 lecția 26 - 22 apr 2015

Algoritmi randomizați

Un algoritm randomizat este un algoritm care încorporează numere aleatoare. Prin comparație, algoritmii pe care îi studiem noi de obicei se numesc algoritmi determiniști.

Scop

Algoritmii randomizați pot avea avantaje față de cei determiniști:

• Timpul de rulare poate fi mai bun, în cazul mediu.
  • Uneori nu cunoaștem algoritmi determiniști polinomiali pentru o problemă.
• Algoritmii pot fi mai ușor de scris decât cei determiniști.

Algoritmii randomizați nu presupun date de intrare randomizate! Dimpotrivă, ei sunt foarte folositori în cazuri patologice sau atunci când datele de intrare provin de la un adversar sau atacator care încearcă producă un caz defavorabil.

Exemple introductive

Selecție și găsirea medianului

Selecția este o cărămidă de bază pentru quicksort (vezi secțiunea următoare) și pentru alți algoritmi. Cunoaștem un algoritm determinist de selecție în $O(n)$, bazat pe Medianul medianelor (numită și medianul din 5). (Discuție dacă este cazul)' Acest algoritm este relativ greu de implementat.

Un algoritm mai ușor de implementat este quickselect, care însă merge în $O(n^{2})$ în cazul cel mai rău. Pseudocodul este:

  quickselect(A, lo, hi, k):
    p := partition(A, lo, hi)
    if (k == p - lo) {
      return A[p];
    } else if (k < p - lo) {
      return quickselect(A, lo, p - 1, k);
    } else {
      return quickselect(A, p + 1, hi, k - (p - lo + 1));
    } 
  }

Algoritmul face un efort de O(n) pentru partiționare, după care reduce problema la una mai mică. Dar cât de mică? Depinde de calitatea rutinei de partiție. Dacă partiția împarte vectorul în două bucăți perfect egale, atunci timpul de rulare pentru algoritmul quickselect va fi:

$T(n)=O(n)+T(n/2)\implies T(n)=O(n)$

La rândul ei, eficiența partiționării depinde de capacitatea noastră de a alege un pivot cât mai aproape de medianul vectorului. Dacă alegem mereu primul element ca pivot, iar vectorul este deja ordonat, atunci algoritmul quickselect va face efortul:

$T(n)=O(n)+T(n-1)\implies T(n)=O(n^{2})$

Problema aceasta este reală atunci când datele provin de la un adversar. El va cunoaște algoritmul nostru și va produce date de test care cauzează timpi de rulare pătratici. De aceea folosim algoritmul quickselect randomizat, unde alegem ca pivot un element la întâmplare din intervalul [lo, hi].

Propoziție: Complexitatea așteptată a algoritmului quickselect randomizat este O(n).

Demonstrație: Algoritmul împarte vectorul în două bucăți cu suma lungimilor n - 1 (deoarece al n-lea element este chiar pivotul). Dacă avem noroc, în funcție de k, quickselect se va apela recursiv pe bucata scurtă. Să presupunem totuși că avem ghinion și ne reapelăm mereu pe bucata cea mai lungă și să calculăm numărul mediu de comparații. El este:

${\begin{aligned}T(n)&=n+medie{\Big (}T(n-1),T(n-2),...,T(n/2),T(n/2),...,T(n-2),T(n-1){\Big )}\\&=n+medie{\Big (}T(n/2),...,T(n-2),T(n-1){\Big )}\\\end{aligned}}$

Putem demonstra prin inducție că

$T(n)<4n$

(Știu că acest 4n pare scos din pălărie, dar demonstrația constructivă este ceva mai complicată).

Quicksort

Să considerăm algoritmul quicksort (credit: Wikipedia). Pseudocodul este:

  quicksort(A, lo, hi) {
    if lo < hi {
      p := partition(A, lo, hi);
      quicksort(A, lo, p - 1);
      quicksort(A, p + 1, hi);
    }
  }

Pentru eficiența algoritmului, este vital ca partition() să împartă intervalul (lo, hi) în două bucăți cât mai egale. În cazul ideal, când partition() împarte intervalul în două bucăți perfect egale, complexitatea algoritmului va fi $O(n\log n)$. La polul opus, când partition() împarte intervalul într-o bucată vidă și una de lungime (hi - lo), complexitatea algoritmului va fi $O(n^{2})$.

Așadar, operația-cheie este alegerea pivotului. Dacă alegem pivotul primul sau ultimul element din interval, algoritmul quicksort va fi lent pe date deja ordonate. Dacă alegem pivotul în mijloc, algoritmul va fi lent pe vectori ca ( 3 2 4 1 6 5 7 ). În general, adversarul poate studia orice algoritm determinist propunem noi și ne poate găsi date de intrare pe care quicksort rulează în $O(n^{2})$.

Soluția probabilistică este să alegem un pivot la întâmplare din intervalul [lo, hi]. Atunci adversarul nu va mai putea anticipa pivotul pe care îl alegem. Probabilitatea este infimă să dăm peste un caz patologic. Timpul de rulare așteptat pentru algoritmul quicksort randomizat este $O(n\log n)$. Iată o demonstrație digerabilă (sursă).

Fie $C_{ij}$ numărul de comparații efectuate între al i-lea și al j-lea element în vectorul final (sortat). Numărul așteptat de comparații între ele este așadar $E[C_{ij}]$. Fie $C$ numărul total de comparații între oricare două elemente, adică exact complexitatea totală a algoritmului. Atunci

$C=\sum _{i=1}^{n-1}\sum _{j=i+1}^{n}C_{ij}$

$E[C]=\sum _{i=1}^{n-1}\sum _{j=i+1}^{n}E[C_{ij}]$

Să-l analizăm pe $C_{ij}$. Fie p poziția pivotului ales la primul nivel din quicksort.

1. Dacă i < p < j, atunci elementele i și j nu vor fi comparate niciodată, căci ele vor fi plasate în intervale separate. Așadar $C_{ij}=0$.
2. Dacă p = i sau p = j, atunci elementele vor fi comparate exact o dată, căci pivotul este comparat cu toate elementele din interval pentru partiționare. Așadar $C_{ij}=1$.
3. Dacă p < i sau p > j, atunci vom repeta întrebarea la nivelul următor din quicksort, căci i și j vor fi plasate în același interval.

Cu alte cuvinte, repetăm pasul (3) cât timp pivotul cade în afara intervalului [i, j], apoi $C_{ij}\in \{0,1\}$ după cum suntem în cazul 1 sau 2. (De aici mai aflăm ceva interesant și care nu este imediat evident: că $C_{ij}\leq 1$, deci oricare două elemente nu vor fi comparate mai mult de o dată).

Știind că suntem în cazul 1 sau 2, care este probabilitatea să fim în cazul 2? Întrucât intervalul [i, j] are j - i + 1 elemente, din care doar două capete, probabilitatea este

$E[C_{ij}]={\frac {2}{j-i+1}}$

De aici rezultă că

$E[C]=2\sum _{i=1}^{n-1}\sum _{j=i+1}^{n}{\frac {1}{j-i+1}}=2\sum _{i=1}^{n-1}{\Big (}{\frac {1}{2}}+{\frac {1}{3}}+...+{\frac {1}{n-i+1}}{\Big )}$

Expresia din paranteze o recunoaștem, este suma armonică și este mărginită superior de $\ln n$. Așadar,

$E[C]=2n\ln n$

Calcularea lui π

• Acul lui Buffon
• Cercul înscris în pătrat

Central limit theorem ne învață că valoarea calculată converge la π, dar greu. Pentru a extrage o zecimală în plus, trebuie să creștem numărul de experimente de 100 de ori!

Clase de algoritmi determiniști

• Las Vegas: întotdeauna dau răspunsul corect; cu probabilitate mare sunt rapizi
• Monte Carlo: întotdeauna sunt rapizi; cu probabilitate mare dau răspunsul corect

În ce clasă se încadrează exemplele de mai sus?

Am întâlnit deja algoritmi randomizați în structuri de date probabilistice (mai mult la seniori, mai puțin la juniori):

• skip lists
• treaps

Alte exemple

Verificarea produsului de matrice (Algoritmul lui Freivalds)

Se dau trei matrice A, B și C. Trebuie să decidem dacă AB = C, da sau nu.

Algoritmul determinist calculează efectiv produsul AB și îl compară cu C. Înmulțirea de matrice se face în mod naiv în $O(n^{3})$ și în circa $O(n^{2.37})$ cu algoritmi neimplementabili.

Algoritmul probabilistic al lui Freivalds rulează în $O(kn^{2})$ și are probabilitatea de eroare ${\frac {1}{2^{k}}}$, pentru k ales de noi.

  verificare(A, B, C) {
    de k ori {
      alege un vector aleator r ∈ {0,1}^n
      dacă A(Br) ≠ Cr {
        return false;
      }
    }
    return true;
  }

Este evident că algoritmul poate greși într-un singur sens. Dacă $A\cdot B=C$, sigur algoritmul va declara aceasta. Dacă $A\cdot B\neq C$, există o șansă ca algoritmul să nu descopere aceasta. Să analizăm probabilitatea de eroare (sursă: Wikipedia).

Fie $D=A\cdot B-C$ și fie $p=D\cdot r$. Atunci egalitatea $A\cdot (B\cdot R)\neq C\cdot R$ este echivalentă cu $D\cdot r\neq 0$. Algoritmul nostru dă un răspuns greșit dacă $D\neq 0$, dar noi nu descoperim aceasta. Fie $d_{ij}$ un element nenul al lui D. Atunci

$p_{i}=\sum _{k=1}^{n}d_{ik}r_{k}=d_{ij}r_{j}+\sum _{k\neq j}d_{ik}r_{k}=d_{ij}r_{j}+y$

• dacă $y=0$, atunci $P[p_{i}=0]=1/2$, căci trebuie ca $r_{j}$ să fie și el 0, iar $r_{j}$ este ales aleator între 0 și 1.
• dacă $y\neq 0$, atunci $P[p_{i}=0]\leq 1/2$, căci trebuie ca $r_{j}=1$ și să avem și norocul ca $d_{ij}=-y$.

Mai mult, până aici am presupus că există un singur element nenul $d_{ij}$. În practică, pot fi mult mai multe, caz în care probabilitatea de a obține accidental $p=0$ va fi mult sub 1/2.

Pentru a amplifica această probabilitate, rulăm verificarea de k ori. Cei k vectori r sunt aleși independent, deci probabilitățile de eroare se pot înmulți până la ${\frac {1}{2^{k}}}$.

Test de primalitate (Fermat)

Cei mai buni algoritmi determiniști cunoscuți rulează în $O(\log ^{6}n)$. Are sens să ne gândim la $\log n$ ca numărul de biți din reprezentarea lui n. De altfel, în criptografie operăm curent cu numere pe 512, 1024, chiar 2048 de biți.

Să trecem la algoritmul probabilistic. Mica teoremă a lui Fermat spune că, pentru orice p prim și pentru orice 0 < a < p,

$a^{p-1}\equiv 1{\pmod {p}}$

(Dacă este nevoie, vom da o demonstrație foarte digerabilă a acestei teoreme prin metoda mărgelelor.)

Din teoremă obținem următorul test de primalitate a lui p:

  primalitate-fermat(p, k) {
    de k ori {
      alege a uniform din [1, p - 1];
      dacă a^(p - 1) % p != 1 {
        returnează false;
      }
    }
    returnează true;
  }

Complexitatea algoritmului este $O(k\log ^{3}n)$, deoarece exponențierea logaritmică face $\log n$ înmulțiri de numere pe $\log n$ biți.

Analiza erorii este complicată și nu o vom demonstra complet. Există o clasă de numere, numite numere Carmichael, care trec testul de primalitate pentru orice a și totuși sunt compuse. Cel mai mic număr Carmichael este 561 = 3 * 11 * 17. Aceste numere sunt rare (există 250.000 de numere Carmichael mai mici decât $10^{16}$).

Pentru numerele compuse care nu sunt Carmichael, însă, cel puțin jumătate din valorile lui a vor da un răspuns diferit de 1 la test. Așadar avem șanse de cel puțin 50% să depistăm dacă numărul este compus. Mai mult, dacă facem k teste avem o probabilitate de eroare de cel mult $1/2^{k}$.

Discuție despre Expii

Aici ne bazăm pe Iulius. :-) Eu voi puncta doar că:

• crowdsourcing-ul este bun
• donarea de timp pentru comunitate, în cantități rezonabile, este un lucru bun
• chestiuni de licență etc.

Prezentare de proiect: Colibri

După cum știți, vreau să facem o lecție de show and tell. Cei din voi care doriți, ideal toată lumea, puteți veni să vorbiți 10-15-20 de minute despre un proiect al vostru. Această lecție este bună și necesară pentru că:

• Este distractiv! Pun pariu că cei care aveți proiecte nu aveți simulatoare de piețe financiare, ci chestii atractive și distractive.
• Vă învață nu doar să faceți lucruri, ci și să povestiți despre ele. Ruptura care există astăzi între oamenii de știință și oamenii din afara științei există tocmai pentru că oamenii de știință trăiesc într-un turn de fildeș. Această atitudine deschide poarta către pseudo-știință și șarlatanie. Când omul de rând nu înțelege cum funcționează știința, când pentru el știința e ca un fel de magie, cum poate el să facă diferența între motorul cu aburi și motorul cu apă?
• Vă poate îndemna pe cei care nu aveți proiecte personale să vă apucați de unul. Trebuie să începeți să faceți tranziția între programe de 300 de linii și programe de 10.000 de linii.

Ca să vă faceți o idee despre formatul pe care mi-l doresc, voi ține eu o prezentare de 15 minute despre un proiect al meu: File:Prezentare-colibri.pdf.