Note de curs, clasele 9-10, 17 octombrie 2013

Probleme de la OJI din anii trecuți

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

• clasa a 9-a
  • 2013 Betașah: parcurgere în 8 direcții; precalcularea direcțiilor; bordarea matricei; calcul de complexitate: dacă parcurgem după pătrate albe, rezultă O(N3), iar dacă parcurgem după dame, obținem O(DN2)
  • 2013 Clepsidru: simulare; accelerare a simulării pentru a elimina dependența de mărimea intervalelor
  • 2012 Elicop: numărare prin matrice; atenție la detalii (câte tipuri de triunghiuri există?); nu este nevoie de precalculare -- nu vă complicați
  • 2012 Roata: simulare; accelerare a simulării pentru a elimina dependența de numărul de rotații; nu decrementăm tot vectorul, ci incrementăm poziția minimă -- încă un factor de mărime
  • 2011 Cri: sume în matrice; nu este deloc clar care din celule sunt inevitabile
  • 2011 Vase: simulare; poate fi accelerată până la O(n) timp și O(1) memorie prin contorizarea volumelor la stânga / dreapta; memoria poate fi și ea importantă; caractere
  • 2010 Livada: algoritmul de majoritate; sau sortare prin numărare; vector shiftat; sau quicksort
  • 2010 Număr: numere mari, divizibilitate, împărțire printr-o constantă
  • A reieșit că le plac problemele de simulare a unui sistem, cu precizarea că simularea trebuie accelerată pentru încadrarea în timp. Algoritmii naivi nu trec.
  • Le mai plac diverși algoritmi pe vectori sau matrice: numere mari, sortări, parcurgeri.
  • Am discutat în detaliu problemele Vase și Număr.
• clasa a 10-a
  • 2013 Calcule: șiruri crescătoare; sume modulo k; greedy pe vector (demonstrație netrivială); precalculare sume parțiale; sume de secvențe prin diferențe de sume parțiale; căutare binară
  • 2013 Zona: fill pe matrice; codificarea direcțiilor; codificarea celor 4 pereți ai unei celule; alternativ, formula pentru arie ca sumă de trapeze
  • 2012 Compresie: divide et impera; caractere; matrice
  • 2012 Culori: numere mari; programare dinamică (recurență)
  • 2011 AI: coliniaritate / divizibilitate; algoritmul lui Lee; găsirea celei mai lungi secvențe compacte într-o matrice
  • 2011 Expresie: parser, stive, algoritm pentru median, subsecvența de sumă maximă, recursivitate ciclică
  • 2010 Expoziție: programare dinamică (zero creativitate) sau combinări cu repetiție, numere mari
  • 2010 Text: parser litere / whitespace (simpluț), programare dinamică, stocarea a 26 de coloane pentru algoritm O(n)
  • Destul de des apar programarea dinamică, diverse parsere de text / procesări de stringuri, fill și algoritmul lui Lee pe matrice, precalculări pe matrice
  • Am discutat în detaliu problema Calcule -- cum demonstrăm că un algoritm greedy este corect?

Analiză amortizată

• analizează un algoritm care face pe o structură de date diverse operații cu diverse costuri
• încercăm să găsim o limită cât mai strânsă pentru costul mediu al unei operații
• există trei metode:

Analiză agregată

• calculează costul total al celor n operații și împarte la n pentru a afla costul mediu al unei operații

Metoda contabilității

• cere credit suplimentar pentru operațiile ieftine, încercând ca prin aceasta să plătească operațiile mai scumpe
• ne duce cu gândul la un contabil care nu dorește să dea nimic pe datorie. Imediat ce îi prezentăm un element pentru inserarea în structură, contabilul ne cere să plătim și transformările viitoare pe care le poate suferi elementul
• echivalent, metoda urmărește evoluția unui element prin structura de date, pe toată durata vieții lui

Metoda potențialului

• alegem o funcție Φ cu valori pozitive. Această funcție se numește potențial și asociază fiecărei stări a structurii de date un număr nenegativ. Fie C_R(i) costul real al operației cu numărul i. Atunci definim costul amortizat ca

$C_{A}(i)=C_{R}(i)+\Phi (i)-\Phi (i-1)$

• deși poate părea magică, însumând costul total pentru operațiile 1, 2, ..., 'n', obținem:

$\sum _{i=1}^{n}C_{A}(i)=\sum _{i=1}^{n}C_{R}(i)+\Phi (n)-\Phi (0)$

• așadar, suma costurilor amortizate este o limită superioară pentru suma costurilor reale, cu condiția ca potențialul final să fie mai mare decât cel inițial
• cum alegem funcția-potențial? Aici este arta.
• empiric, dorim ca potențialul să „echilibreze” costurile amortizate, atunci când costurile reale variază asimptotic
• vrem ca operațiile ieftine să fie însoțite de o creștere (mică) de potențial, iar operațiile scumpe să fie însoțite de o cădere mare de potențial
• intuitiv, potențialul mare al structurii indică posibilitatea ca următoarea operație să fie scumpă, iar potențialul mic indică probabilitatea ca următoarele câteva operații să fie ieftine

Exemple, toate analizate prin cele trei metode

Nearest neighbor

Problema: Dându-se un vector V, să se calculeze un alt vector W unde W(i) este cel mai mare indice j < i pentru care V[j] < V[i].

Soluție: Menținem o stivă de elemente „interesante” din V văzute până acum. La pasul i, ștergem din stivă toate elementele mai mari ca V[i] (operație numită multipop, apoi inserăm V[i].

Analiză agregată: Operațiile push sunt clar O(1). Fiecare operație multipop poate fi O(n), dar costul tuturor operațiilor multipop nu poate depăși O(n), căci nu putem scoate din stivă mai multe elemente decât am introdus. Deci costul mediu al unei operații este O(1).

Metoda contabilității: La introducerea în stivă a unui element plătim $2. Costul instantaneu este $1, iar $1 rămâne într-o „pușculiță” alăturată elementului. Când elementul este scos din stivă, contabilul consumă și al doilea dolar. Deci costul per element este $2.

Metoda potențialului: Φ(i) este numărul de elemente din stivă după a i-a operație

Incrementarea unui contor binar

Problema: Un vector de k elemente stochează valori de 0 sau 1, reprezentând un număr binar. Inițial, toate elementele sunt 0. Incrementăm contorul de n ori. Care este costul mediu per incrementare?

Analiză agregată: Există operații de cost k, dar acestea sunt puține (o fracție de 1 / 2^k din numărul total). 1/2 dintre incrementări se fac cu cost real 1, 1/4 se fac cu cost real 2 etc. Suma acestor costuri este o sumă de puteri a lui 2 care nu depășește 2 n.

Metoda contabilității: Fiecare operație de incrementare schimbă toți biții de 1 la sfârșitul numărului în 0 și (opțional) ultimul bit de 0 în 1. Când modificăm un bit din 0 în 1, plătim $2, din care $1 este consumat, iar $1 este depozitat alături de bit. Când bitul trece din nou pe 0, este consumat și acest dolar. Deoarece la fiecare incrementare schimbăm cel mult un bit din 0 în 1, vom plăti cel mult $2.

Metoda potențialului: Φ(i) este numărul de biți din contor după a i-a operație

Simularea unei cozi folosind două stive

Problema: Se cere să implementăm o coadă, dar ni se cere să folosim numai două stive ca structură internă.

Soluție: Fie S și T cele două stive. Pentru a adăuga elemente în coadă, le adăugăm la S. Pentru a extrage elemente din coadă, le extragem din T; dacă T este goală, mutăm toate elementele din S în T.

Analiză agregată: Suma costurilor mutărilor din S în T este O(n), căci fiecare element este mutat o singură dată (nu se mai întoarce în S).

Metoda contabilității: Inserarea costă $3, din care unul este costul imediat, iar $2 rămân lângă element. Mutarea din S în T costă $1. Extragerea din T costă ultimul $1.

Metoda potențialului: Φ(i) este numărul de elemente din stiva S după a i-a operație

Delete-Larger-Half

Problema: Să concepem o structură care stochează numere și admite două operații: (1) insert(x) inserează x în structură și (2) deleteLargerHalf() șterge jumătate dintre elementele existente în structură, cele mai mari.

Soluție: Stocăm elementele într-un vector nesortat. Pentru deleteLargerHalf(), căutăm medianul în vector și reducem dimensiunea vectorului la jumătate.

Analiză amortizată: Și mai greu de dus la capăt.

Metoda contabilității: Un element poate rezista la infinit în structură. Cât credit să cerem la inserare? Din fericire, există un artificiu ingenios. Creditul la inserare este $3. Inserarea costă $1. Ștergerea este gratuită (căci trebuie doar calculat k = k / 2). Pentru deleteLargerHalf(), toate elementele plătesc câte $1 pentru găsirea medianului în O(k). Elementele care vor fi șterse plătesc ultimul lor dolar elementelor care rămân în vector.

Metoda potențialului: Φ(i) este numărul de elemente din vector după a i-a operație.

Stivă cu backup (Cormen)

Problema: O stivă poate stoca maxim k elemente. După fiecare k operații, facem o copie a întregii stive, pentru backup. Să se arate că costul amortizat al operațiilor pe stivă este tot O(1).

Analiză amortizată: Costul a k operații este k pentru operațiile propriu-zise (push și pop) și k pentru copierea stivei la final. Deci costul amortizat este constant, 2.

Metoda contabilității: La fiecare operație de push sau pop cerem $2: unul pentru operația în sine, iar celălalt este depozitat, în ordine, pe câte o căsuță din stivă. După k operații vom avea $k acumulați, suficienți ca să plătim pentru operația de backup.

Metoda potențialului: Φ(i) este numărul de operații simple trecute de la ultima operație de backup. Atunci operația scumpă (backup) este însoțită de o cădere de potențial de la k la 0, iar costul amortizat este 2 pentru toate operațiile.

Teme

• Simularea unui deque folosind trei stive: Să se implementeze un deque, adică o coadă unde putem insera și șterge la oricare din capete, folosind trei stive ca structură internă.
• Stivă dinamică, numai push: O stivă poate numai să crească (se fac doar operații push). Ea este dimensionată pentru un singur element. Când stiva se umple, ea își dublează capacitatea pentru a putea găzdui noi elemente. Calculați costul amortizat al n operații push.
• Stivă dinamică: Generalizați problema anterioară pentru a admite și contractarea stivei. Dacă stiva se golește, este păcat să menținem ocupat tot spațiul pe care l-am alocat la punctul de maxim. Găsiți un algoritm de contractare a stivei care să ducă la un cost amortizat O(1) pentru operațiile push și pop.
• Coadă de priorități monotonă (Cormen)