Idei de subiecte 15-22 februarie 2013

Clasele IX-X

Skip lists

Avantaje:

• le-ar prinde bine o structură de căutare
• e bine să-și exerseze mâna cu pointeri

Idei de predare (bazate pe articolul original și pe ce am făcut la XI/XII):

Operații dorite

• inserare / ștergere / căutare / minim / maxim / cea mai apropiată valoare

Comparația cu alte structuri posibile

• arbori de căutare: oferă timpi logaritmici, dar echilibrarea este greoaie
• tabele hash: nu suportă ordonare
• listă: timpi de acces liniari

Noțiuni de probabilități

Avem nevoie de 3 valori așteptate. Cred că trebuie predate la clasele mici.

• experiment Bernoulli (valoarea 1 cu probabilitate p, 0 cu probabilitate q = 1 - p)
• exemple: zar, monedă măsluită
• valoarea așteptată pt. Bernoulli: $1\cdot p+0\cdot q=p$
• experiment binomial B(n, p) = o serie de n experimente Bernoulli
• valoarea așteptată pt. binomial: $n\cdot p$ (cele n experimente sunt independente, deci se pot aduna)
• numărul de experimente până la succes: distribuție geometrică
• exemplu: dau cu zarul până dau 1; fie evenimentul X = „numărul de aruncări până dau 1”
• atunci $P(X=1)={\frac {1}{6}}$, $P(X=2)={\frac {5}{6}}\cdot {\frac {1}{6}}$, ..., $P(X=k)=\left({\frac {5}{6}}\right)^{k-1}\cdot {\frac {1}{6}}$
• valoarea așteptată a distribuției binomiale: $E(X)=\sum _{k=1}^{\infty }k*P(X=k)=\sum _{k=1}^{\infty }kq^{k-1}p={\frac {1}{p}}$
  • se demonstrează așezând termenii într-un triunghi și însumând fiecare coloană, apoi însumând sumele.

${\begin{matrix}p&+\\qp&+&qp&+\\q^{2}p&+&q^{2}p&+&q^{2}p&+\\q^{3}p&+&q^{3}p&+&q^{3}p&+&q^{3}p&+\\...&&...&&...&&...&&...\\\hline =1&+&q&+&q^{2}&+&q^{3}&+&...&={\frac {1}{1-q}}={\frac {1}{p}}\end{matrix}}$

Idee pentru o structură imutabilă (fără inserări / ștergeri)

• listă cu toate elementele
• peste ea, o listă cu pointeri din 2 în 2 ⇒ e nevoie de n/2 + 1 comparații
• peste ele, o listă cu pointeri din 4 în 4 ⇒ e nevoie de n/4 + 2 comparații
• generalizare: $\log _{2}n$ liste
• timp de căutare logaritmic
• dar imposibil de întreținut la inserări / ștergeri

Structură probabilistică

• nivelul 0 conține toate elementele
• dacă un element apare la nivelul k, apare și la nivelul k + 1 cu probabilitatea p
• experiment binomial, deci nivelul 1 conține $pn$ elemente, nivelul 2 conține $p^{2}n$ elemente etc.
• p este 0,25 sau 0,5 în practică
• nivelul unui element este determinat la inserare și rămâne constant pe durata vieții elementului
• număr fixat de niveluri, circa $\log _{\frac {1}{p}}n$ pentru n elemente așteptate.
• pointeri de început pentru fiecare nivel; santinelă (valoare infinită) la sfârșit
• pseudocod pentru căutare (Pugh)
• analiză de complexitate. Cred că se poate mai intuitiv decât Pugh:
  • mergem de la elementul căutat (nivel 0) în stânga și în sus
  • câte elemente vom parcurge în stânga până găsim un element care urcă un nivel? Probabilistic, ${\frac {1}{p}}$
  • sunt $\log _{\frac {1}{p}}n$ niveluri
  • deci timp total $O({\frac {1}{p}}\cdot \log _{\frac {1}{p}}n)$
• pseudocod pentru inserare, ștergere (Pugh)
• pseudocod pentru alegerea aleatoare nivelului la inserare, conform distribuției geometrice (Pugh)
• atenție la factorii constanți la probleme subliniare
  • $2\log n$ în loc de $\log n$ înseamnă că primul algoritm procesează n valori, iar al doilea n²

Structură deterministă (opțional / nu pentru concurs)

Numite 1-2 skip lists, sunt deterministe, dar mai lente și mai greu de implementat.

• între oricare 2 noduri de înălțime h există 1 sau 2 noduri de înălțime h - 1.
• inserare: dacă apar 3 elemente la același nivel, elementul din mijloc este înălțat cu 1
  • presupune realocare, deci poate fi O(log² n)
• la ștergere, elementele pot fi urcate sau coborâte cu un nivel
• deoarece înălțimea nodurilor variază, numărul de pointeri spre dreapta se poate schimba pe parcursul vieții unui element
• soluție 1: listă de pointeri în loc de vector de pointeri
  • dublează necesarul de memorie și numărul de indirectări
  • fragmentarea memoriei
  • anulează beneficiul cacheului de procesor
• soluție 2: pointerii next pentru fiecare element sunt într-un vector de pointeri realocat dinamic (dublare / înjumătățire când este cazul)

Drumuri în grafuri

Avantaje:

• trebuie neapărat făcute înainte de olimpiadă

Algoritmi:

• Bellman-Ford
• Dijkstra
  • alegerea următorului nod cu vector sau cu min-heap
• Floyd-Warshall
• analize de complexitate

Structuri de mulțimi disjuncte

Avantaje:

• banal de implementat
• apar des în practică

Le-am predat pe fugă pentru algoritmul lui Kruskal. Ar merita reluate, dar probabil nu vor umple decât vreo oră.

Parcurgeri Euler / LCA / RMQ / artificiul cu ${\sqrt {n}}$

Avantaje:

• introduce noțiunea de preprocesare + query
• introduce artificiul cu ${\sqrt {n}}$, util în multe situații
• mulți algoritmi clasici ușurei
• oricare din problemele astea pot fi date și ca teme de gândire

Nu cred că trebuie dusă până la soluția cu O(1) per query. $O({\sqrt {n}})$ sau $O(\log {n})$ este suficient pentru ei.

Idei de predare:

Parcurgere Euler

• definiție, exemplu
• aplicație: se dă un arbore și n interogări de forma (u, v). Să se spună, în fiecare caz, dacă (a) u este strămoș al lui v, (b) v este strămoș al lui u sau (c) niciuna dintre acestea.

RMQ

• expunerea problemei
• fără precalculare, răspunsuri în O(n)
• cu precalcularea tuturor sumelor, O(n²) memorie necesară
  • precalcularea poate fi făcută naiv în O(n³) sau cu programare dinamică în O(n¹)
  • apoi, O(1) per interogare
  • dorim cel mult O(n) memorie suplimentară, vezi secțiunea următoare

Artificiul cu ${\sqrt {n}}$

• explicație pentru RMQ
• multe exemple similare pe infoarena. Aș alege două:
  • suma unei subsecvențe (elementele se pot actualiza dinamic)
  • calcularea celei mai lungi subsecvențe comune cu mai puțin de O(m * n) memorie
• de ce tocmai ${\sqrt {n}}$?
  • dacă împărțim vectorul în $p$ segmente, atunci efortul necesar este $O(p+{\frac {n}{p}})$
  • ecuație de gradul doi, minimul se atinge pentru $p={\sqrt {n}}$

LCA

• expunerea problemei
• legătura cu parcurgerea Euler și RMQ: parcurgerea Euler reduce problema la RMQ

Opțional, algoritmi cu $O(n\log n)$ preprocesare, $O(n\log n)$ memorie necesară și $O(\log n)$ per interogare

• de exemplu, pentru RMQ stocăm toate sumele de lungimi 1, 2, 4, 8, ...