Note de curs, clasele 11-12, 24 mai 2013

Arbori splay (încheiere)

• demonstrație că operația de splay are complexitate logaritmică
• folosim metoda potențialului
  • potențialul unui nod după i pași dintr-o operație de splay este logaritmul mărimii subarborelui său: $\Phi _{i}(x)=\log |T_{i}(x)|$
  • potențialul arborelui este suma potențialelor nodurilor
• analizăm rotația zig-zig
• demonstrăm că costul amortizat este $C_{A}(i)<3(\Phi _{i}(x)-\Phi _{i-1}(x))$
• prin însumare telescopică, costul real al operației de splay este $C_{R}<3\Phi _{k}(x)=3\log n$

Algoritmi randomizați

• necesitate: să obținem algoritmi mai rapizi sau mai simplu de implementat folosind probabilitățile
• două metode:
  • Monte Carlo: număr fixat de iterații, k; poate produce un răspuns incorect, dar probabilitatea acestui eșec scade pe măsură ce k crește
  • Las Vegas: întotdeauna produce răspunsul corect; numărul de iterații este variabil și poate fi mare într-un caz nefericit, dar valoarea așteptată este mică
• exemple deja întâlnite:
  • skip lists
  • treaps
  • quicksort cu randomizarea pivotului
• toate folosesc metoda Las Vegas: dau răspunsul corect, dar pot fi ineficiente dacă avem ghinion la generarea de numere aleatoare

Calculul lui $\pi$ prin metoda Monte Carlo

• teorie, aria pătratului și a sfertului de cerc înscris
• central limit theorem
• soluția propusă de algoritm converge la ${\frac {\pi }{4}}$cu ${\sqrt {n}}$; cu alte cuvinte, pentru a calcula încă o zecimală exactă, trebuie să înmulțim n cu 100.
• nu este practic (evident)

Verificarea unui produs de matrice în O(k n²) prin metoda Monte Carlo

• se dau trei matrice A, B și C (pătrate, pentru simplitate). Să se verifice dacă $A\cdot B=C$.
• prin înmulțire propriu-zisă: O(n³) banal, ajungând până la O(n^2,37) cu algoritmi neimplementabili
• algoritm probabilistic: k iterații. La fiecare iterație, alege un vector aleator r de n elemente 0 și 1 și verifică dacă $A\cdot (B\cdot r)=C\cdot r$
• complexitate: O(k n²)
• poate greși, dar î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.
• probabilitatea de eroare este ${\frac {1}{2^{k}}}$
• demonstrație (la fiecare iterație, probabilitatea de a găsi o diferență între $A\cdot (B\cdot r)$ și $C\cdot r$ este minim 1/2)

Closest pair O(n) prin metoda Las Vegas

• am studiat problema la lecția de geometrie computațională și am găsit un algoritm O(log n)
• există și algoritmi O(log log n), dar sunt greu de implementat
• algoritm: pornim cu S₁ = S
• dintr-un set S_i, alegem un punct la întâmplare x_i. Calculăm explicit d(x_i). Eliminăm din set toate punctele x pentru care d(x) > d(x_i). Setul rămas este S_{i + 1}
• în final, fie $d(x_{i}^{*})$ ultima distanță găsită. Ea este de cel mult trei ori mai mare decât $\delta (S)$ pe care îl căutăm
• detalii de implementare: rețeaua de latură b
• demonstrații pentru diverse afirmații
  • că $d(x_{i}^{*})\leq \delta (S)$
  • că rețeaua de latură b permite filtrarea punctelor în O(n)
  • că algoritmul are timp de rulare așteptat O(n)