Cata at 15:39, 5 February 2013

2013-02-05T15:39:40Z

New page

= 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 [ftp://ftp.cs.umd.edu/pub/skipLists/skiplists.pdf articolul original] și pe [[Note de curs, clasele 11-12, 18 ianuarie 2013|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:''' <math>1 \cdot p + 0 \cdot q = p</math>
* experiment binomial B(''n'', ''p'') = o serie de ''n'' experimente Bernoulli
* '''valoarea așteptată pt. binomial:''' <math>n \cdot p</math> (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 <math>P(X = 1) = \frac{1}{6}</math>, <math>P(X = 2) = \frac{5}{6} \cdot \frac{1}{6}</math>, ..., <math>P(X = k) = \left ( \frac{5}{6} \right ) ^{k - 1} \cdot \frac{1}{6}</math>
* '''valoarea așteptată a distribuției binomiale:''' <math>E(X) = \sum_{k=1}^\infty k * P(X = k) = \sum_{k=1}^\infty k q^{k-1} p = \frac{1}{p}</math>
** se demonstrează așezând termenii într-un triunghi și însumând fiecare coloană, apoi însumând sumele.

<math>
\begin{matrix}
p & + \\
q p & + & q p & + \\
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}
</math>

=== 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: <math>\log_{2} n</math> 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 <math>p n</math> elemente, nivelul 2 conține <math>p^{2} n</math> 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 <math>\log_{\frac{1}{p}} n</math> 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, <math>\frac{1}{p}</math>
** sunt <math>\log_{\frac{1}{p}} n</math> niveluri
** deci timp total <math>O(\frac{1}{p} \cdot \log_{\frac{1}{p}} n)</math>
* 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
** <math>2 \log n</math> în loc de <math>\log n</math> înseamnă că primul algoritm procesează ''n'' valori, iar al doilea ''n''2

=== 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(log2 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 <math>\sqrt{n}</math> ==

Avantaje:

* introduce noțiunea de preprocesare + query
* introduce artificiul cu <math>\sqrt{n}</math>, 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. <math>O(\sqrt{n})</math> sau <math>O(\log{n})</math> 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(n2) memorie necesară
** precalcularea poate fi făcută naiv în O(n3) sau cu programare dinamică în O(n1)
** apoi, O(1) per interogare
** dorim cel mult O(n) memorie suplimentară, vezi secțiunea următoare

=== Artificiul cu <math>\sqrt{n}</math> ===

* explicație pentru RMQ
* multe exemple similare pe [http://infoarena.ro/blog/square-root-trick 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 <math>\sqrt{n}</math>?
** dacă împărțim vectorul în <math>p</math> segmente, atunci efortul necesar este <math>O(p + \frac{n}{p})</math>
** ecuație de gradul doi, minimul se atinge pentru <math>p = \sqrt{n}</math>

=== LCA ===

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

=== Opțional, algoritmi cu <math>O(n \log n)</math> preprocesare, <math>O(n \log n)</math> memorie necesară și <math>O(\log n)</math> per interogare ===

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

Idei de subiecte 15-22 februarie 2013 - Revision history

Cata at 15:39, 5 February 2013