Note de curs, clasele 9-10, 20 februarie 2014

From Algopedia
Revision as of 10:00, 26 January 2015 by Cata (talk | contribs) (→‎Probleme)
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
Jump to navigationJump to search

Numere mari

Lucrul cu numere mari devine necesar atunci când datele problemei nu mai încap pe 64 de biți (long long sau unsigned long long). Numărul maxim ce poate fi reprezentat pe 64 de biți fără semn este 264 - 1 (duh), adică aproximativ 1,8 ⨯ 1019. Dincolo de această limită, ne trebuie o reprezentare proprie.

Reprezentare

În general, problema cere să tipăriți un număr în baza 10. De aceea, reprezentarea noastră internă va fi tot în baza 10, respectiv:

  • numărul de cifre ale numărului
    • decizie de design: stocăm exact numărul de cifre semnificative sau permitem zerouri la stânga?
  • un vector cu cifrele numărului
    • elementul de pe poziția i stochează cifra corespunzătoare lui 10i

Există și alte reprezentări, în funcție de necesități:

  • Dacă spațiul este o problemă, putem reprezenta câte o cifră pe patru biți (două cifre pe octet).
  • Tot acolo putem ajunge stocând numerele în baza 100. Atunci fiecare cifră din vector va reprezenta două cifre în baza 10.
  • Putem stoca numerele în orice altă bază (până la 255), dar în momentul afișării vom avea nevoie de timp și memorie suplimentară pentru a face conversia la baza 10.

Operații de implementat (după caz)

  • inițializarea cu 0
  • inițializarea cu o singură cifră
  • inițializarea cu un număr de mai multe cifre
  • adunarea cu un int
  • adunarea a două numere mari
  • înmulțirea cu o constantă
  • înmulțirea a două numere mari
    • Aceasta merită o discuție detaliată. Algoritmul naiv face O(n2) operații. Algoritmul lui Karatsuba este un algoritm divide et impera cu formula de recurență T(n) = 3 T(n/2) + n. Prin eliminarea recurenței obținem complexitatea O(nlog2 3</sup).
    • Pentru n = 10.000, algoritmul naiv face 100.000.000 de operații, iar algoritmul Karatsuba numai 2.200.000!
  • împărțirea cu o constantă
  • împărțirea a două numere mari
  • compararea

Probleme

  • Implementați algoritmul lui Karatsuba.
  • Extindeți algoritmul lui Karatsuba la trihotomie (împărțirea numerelor în trei segmente egale).
    • Câte înmulțiri sunt necesare?
    • Care este complexitatea recurentă a algoritmului? Dar cea nerecurentă?
    • Este algoritmul mai rapid decât cel al lui Karatsuba?


Heaps

Un heap (engl. „grămadă”) este o structură de date care reține n elemente și ne permite următoarele operații:

  • inițializarea heapului în O(n)
  • aflarea minimului în O(1)
  • inserarea și ștergerea din heap în O(log n)
    • cu mențiunea că, pentru ștergere, trebuie să pasăm un pointer către element (heapul nu suportă căutări)
  • modificarea valorii unui element în O(log n)
    • idem

Cum ați implementa, naiv această structură? Ce complexități au variantele:

  • vector
  • vector ordonat
  • listă înlănțuită

Reprezentare

Conceptual, un heap se reprezintă pe un arbore binar complet. Exemplu.

În practică, nu avem nevoie de arbori. Un heap se reprezintă pe un vector.

Analiza complexității. Singurul caz neclar este heapify: de ce este O(n)?

Aplicații

  • sortare (heapsort)
  • coadă de priorități

Probleme

  • Probleme Varena
  • Problema Infoarena
  • De ce lucrăm cu heapuri binare? Nu este mai eficient un heap ternar? Sau cuaternar?
  • Să se interclaseze k vectori sortați a câte n elemente fiecare
    • Există două metode, una cu heap și una fără, ambele de complexitate O(kn log k)
  • Se dă un vector. Să se tipărească, pentru fiecare poziție i, medianul secvenței v[1...i]
  • Se dă un vector nesortat cu n elemente. Să se tipărească cele mai mici k elemente
    • Variațiuni: cele k elemente pot fi tipărite în orice ordine / trebuie tipărite în ordine crescătoare
    • Soluția optimă este prin selecție (găsirea celui de-al k-lea element), dar există două soluții rezonabil de bune, una cu min-heap și una cu max-heap.