Note de curs, clasele 11-12, 17 octombrie 2013

From Algopedia
Jump to navigationJump to search

Probleme de la OJI din anii trecuți

Am enumerat rapid tipurile de probleme date în anii trecuți la OJI.

  • 2013 Biperm: grafuri, permutări, descompunerea unei permutări în cicluri, indexare
  • 2013 Subsecvențe: hash table sau trie, sau KMP / Rabin-Karp pentru punctaj parțial
  • 2012 Blis: subșir crescător în O(n log n), programare dinamică
  • 2012 Parc: teorema lui pitagora, puteri ale lui 2
  • 2011 Suma: dinamică (zero creativitate)
  • 2011 Ubuntzei: Dijkstra pe un graf extins, sau alți algoritmi de drumuri pentru punctaje parțiale
  • 2010 Immortal: backtracking (permutări)
  • 2010 Joc: programare dinamică, 2 linii și k coloane

Apar preponderent subiecte de programare dinamică, grafuri, alte structuri de date, ceva matematică.

Analiză amortizată

Aceeași materie clasele 9-10, predată la viteză mai mare.

The Master Theorem

  • introducere: calculul complexității merge sort prin vizualizarea grafică a arborelui de apeluri
    • costul exprimat recurent este T(n) = 2 T(n/2) + n, iar cel nerecurent este T(n) = Θ(n log n)
  • una mai grea: T(n) = 2 T(n/2) + O(n log n)
    • încă mai putem face calculul de mână, folosind o sumă de logaritmi sau schimbarea de variabilă h = log2 n
    • rezultă că T(n) = Θ(n log2 n).

The Master Theorem ne oferă o rețetă pentru calculul complexității algoritmilor recursivi. Fie recurența T(n) = aT(n/b) + f(n), unde:

  • a >= 1, constant
  • b > 1, constant
  • f(n) asimptotic pozitivă

Fie x = logb a. Atunci:

  1. dacă f(n) = O(nx - ε), pentru ε > 0, atunci T(n) = Θ(nx)
  2. dacă f(n) = Θ(nx), atunci T(n) = Θ(nx log n)
    • Cazul 2 extins: dacă f(n) = Θ(nx logk n), atunci T(n) = Θ(nx logk+1 n)
  3. dacă f(n) = Ω(nx + ε), pentru ε > 0, și dacă f(n) satisface condiția de regularitate, atunci T(n) = Θ(f(n))
    • condiția de regularitate: există c < 1 a.î., pentru orice n suficient de mare, a f(n / b) <= c f(n)

Intuitiv, MT arată dacă este mai scump să rezolvăm cazurile de bază (frunzele din arborele de apeluri) sau să combinăm subarborii.

  • noțiune de logaritmi: alogb n = alogb n
  • MT nu acoperă toate cazurile; exemple când nu se poate:
    • a este de forma 2n: a trebuie să fie constant
    • f(n) este n/log n sau n log n: diferența nu este polinomială (nu există ε)
    • a = 0,5: nu putem avea mai puțin de o subproblemă
    • f(n) = -n log n: f(n) trebuie să fie asimptotic pozitiv
  • exemple deja cunoscute (verificăm că MT dă ceea ce știm deja că este corect):
    • căutarea binară T(n) = T(n / 2) + 1
    • traversarea unui arbore binar: T(n) = 2 T(n / 2) + 1
      • traversarea unui arbore k-ar: T(n) = k T(n / k) + 1
    • merge sort
    • înmulțirea a două numere mari prin divide et impera: T(n) = 4 T(n / 2) + n
      • cu numai 3 înmulțiri: T(n) = 3 T(n / 2) + n
  • alte exemple:
    • T(n) = 2 T(2n/3) + O(n) sau O(1)
    • T(n) = T(2n/3) + O(n)
    • T(n) = T(99n/100) + O(n)
    • T(n) = T(99n/100) + O(1)
    • T(n) = 2 T(n/2) + O(n log n) - cazul 3 nu merge, dar merge cazul 2
    • T(n) = 4 T(n/2) + O(n2 log n)
    • T(n) = T(sqrt(n)) + 1, prin calcul direct, căci nu se aplică MT.

La final, am făcut o mini-demonstrație cu arbori. Cazul al doilea este ușor de demonstrat.

  • presupunem că n este putere a lui b, a este întreg.
  • pe fiecare nivel efortul este ak f(n/bk); calculăm suma acestor costuri când f(n) = nlogb a
  • există alogb n = nlogb a frunze, fiecare cu efort Θ(1)