Idei de subiecte 15-22 februarie 2013

From Algopedia
Revision as of 15:39, 5 February 2013 by Cata (talk | contribs)
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
Jump to navigationJump to search

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⋅p+0⋅q=p
  • experiment binomial B(n, p) = o serie de n experimente Bernoulli
  • valoarea așteptată pt. binomial: n⋅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)=16, P(X=2)=56⋅16, ..., P(X=k)=(56)k−1⋅16
  • valoarea așteptată a distribuției binomiale: E(X)=∑k=1∞k*P(X=k)=∑k=1∞kqk−1p=1p
    • se demonstrează așezând termenii într-un triunghi și însumând fiecare coloană, apoi însumând sumele.

p+qp+qp+q2p+q2p+q2p+q3p+q3p+q3p+q3p+...............=1+q+q2+q3+...=11−q=1p

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: log2n 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 p2n 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 log1pn 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, 1p
    • sunt log1pn niveluri
    • deci timp total O(1p⋅log1pn)
  • 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
    • 2log⁡n în loc de log⁡n înseamnă că primul algoritm procesează n valori, iar al doilea n2

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 n

Avantaje:

  • introduce noțiunea de preprocesare + query
  • introduce artificiul cu 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(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(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 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 n?
    • dacă împărțim vectorul în p segmente, atunci efortul necesar este O(p+np)
    • ecuație de gradul doi, minimul se atinge pentru p=n

LCA

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

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

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