View source for Clasa VII/VIII lecția 12 - 9 dec 2014

= Tema - rezolvări =

Rezolvări aici [http://solpedia.francu.com/wiki/index.php/Clasa_VII/VIII_lec%C8%9Bia_11_-_2_dec_2014]

= Lecție =
== Despre structura de date coadă ==
* Ideea de ''tip de date abstract'': un tip de date abstract este un ''model matematic'', ca și automatele. Acest model definește operații asupra tipului de date, precum și restricții asupra efectului acestor operații.Tipurile de date abstracte sînt utile în simplificarea algoritmilor, deaorece descompun problema în subprobleme mai mici, cunoscute și studiate.
* Exemplu: tipul de date abstract ''coadă'', care definește operațiile ''enqueue'', care adaugă un element la coadă, și ''dequeue'', care scoate un element din coadă. Restricțiile sînt asupra ordinii de returnare a elementelor și anume ele trebuie returnate după regula "primul venit primul plecat". De aceea se spune că o coadă este o structură de tip ''FIFO'' (first in, first out). Definim, de asemenea doua operații utile: ''empty'' (coadă goală) și ''full'' (coadă plină). [[Image:coada.gif|frame|none|Coada ca tip abstract de date]]
* Tipurile de date abstracte separă funcționalitatea de implementare. În cazul cozii există mai multe implementări posibile. Noi vom studia una dintre cele mai folosite.
* Implementarea cu vectori circulari
** Folosește un vector pentru a păstra elementele și doi indici, primul și ultimul care memorează poziția primului, respectiv ultimului element din coadă. Pentru a nu deplasa elemente atunci cînd scoatem un element din coadă vom incrementa doar poziția primului element. Atunci cînd adăugăm un element în coadă incrementăm poziția ultimului element.
** Pentru a refolosi golurile rămase în urmă la scoaterea din coadă și a nu deplasa cei doi indici la infinit vom defini o mărime maximă a cozii, n. Atunci cînd unul din indici depășește această mărime el revine la zero. Logic vorbind după ultimul element din vector urmează din nou primul. De aceea spunem că vectorul este circular. Formula de actualizare a indicilor devine <tt>primul = (primul + 1) % n</tt> și <tt>ultimul = (ultimul + 1) % n</tt>, unde n este numărul maxim de elemente din coadă. [[Image:coada-vector-circular.gif|frame|none|Implementare coadă cu vector circular]]
** Observăm că primul este poziția primului element din coadă, iar ultimul este poziția primului element liber din vector.
** Coadă goală. Cum răspundem la întrebarea "este coada goală"? Se observă că acest lucru se întimplă cînd primul == ultimul.
** Coada plină. Cum răspundem la întrebarea "este coada plină"? Observăm că aceasta se întîmplă tot atunci cînd <tt>primul == ultimul</tt>. Pentru a diferenția între aceste două cazuri vom "sacrifica" un element din vector, folosind numai n-1 poziții. În felul acesta testul de coadă plină va fi <tt>(ultimul + 1) % n = primul</tt>.
* În această implementare cele patru operații au complexitate O(1).
* Unul din avantajele acestei implementări, de care veți auzi în detaliu în facultate este că scoaterea de elemente se poate face în paralel cu adăugarea, de exemplu în cazul cînd un proces generează elementele de adăugat și un alt proces, independent, colectează elementele spre procesare.

== Maximum în fereastră glisantă (maximum over a sliding window) ==
* Enunț: dîndu-se un șir de ''n'' numere considerăm cele ''n – k + 1'' subsecvențe de ''k'' numere consecutive în șir (denumite și "ferestre" de lungime ''k''). Putem vedea aceste ferestre ca pe o singură fereastră, deplasabilă, care ne dă acces la ''k'' elemente din vector odată. Se cere ca pentru fiecare fereastră să se găsească maximul.
* Algoritmul de rezolvare trivial (forță brută) recalculează maximul pentru fiecare din ferestre, avînd complexitate ''O(kn)''.
* Pentru a reduce complexitatea găsirii maximului procedăm astfel: luăm prima fereastră, de la ''0'' la ''k-1''. Să spunem că maximul se află pe poziția ''p<sub>1</sub>''. Pe măsură ce vom deplasa fereastra este imposibil ca elementele din-naintea maximului să fie vreodată maximul ferestrei, deoarece ele vor face parte împreună cu maximul din această fereastră. Să considerăm poziția celui mai mare element după maxim și la dreapta lui, în fereastră. Fie ea ''p<sub>2</sub>''. Rezultă că nici un element pe pozițiile intermediare ''i'', ''p<sub>1</sub> < i < p<sub>2</sub>'', nu poate fi vreodată maxim în fereastră, deoarece aceste elemente vor fi împreună cu ''p<sub>2</sub>'' în toate ferestrele care le conțin. Similar, considerînd ''p<sub>3</sub>'' poziția următorului maxim, nici un element între ''p<sub>2</sub>'' și ''p<sub>3</sub>'' nu va putea fi maxim. Astfel apare următorul algoritm:
** Memorăm toate maximele descrescătoare din prima fereastră, într-o coadă. Primul element din coadă este maximul ferestrei.
** Cînd deplasăm fereastra trebuie să actualizăm structura de maxime din coadă. Pentru aceasta dăm atenție elementului care dispare din fereastră și celui care intră în fereastră.
** Dacă elementul care iese nu este maximul curent, nu avem nimic de făcut. 
** Dacă este maximul curent vom scoate primul element din coada de maxime.
** Dacă elementul proaspăt adăugat în fereastră este mai mic decît ultimul maxim din coadă se adaugă la coadă. În caz contrar el va "arunca" ultimul element, iar și încercăm din nou adăugarea în coadă.
** Rezultă că noul element din fereastră "aruncă" toate elementele de la urma cozii strict mai mici ca el, iar apoi îl adăugăm normal la coadă. [[Image:maximum-fereastra-glisanta.gif|frame|none|În figură noul maxim va elimina din coadă maximele 2 și 3. Coada rămasă va conține maximul 1 și maximul nou]]
* La prima vedere pare că acest algoritm are complexitate ''O(kn)''. Folosind analiza amortizată putem calcula complexitatea reală ca fiind ''O(n)''.
* Memoria suplimentară folosită este mărimea maximă a cozii, adică ''O(k)''.
* Observăm că putem folosi acest algoritm la problema [http://varena.ro/problema/cuburi cuburi]. Genul acesta de prelucrare, eliminarea unor cifre ale unui număr astfel încît numărul rămas să fie maxim (sau minim) apare des la olimpiade.
* La temă aveţi şi problema [http://varena.ro/problema/maxim maxim], o problemă de clasa a 5<sup>a</sup> la origine, adaptată pentru clasa a 8<sup>a</sup> şi analiză amortizată. Pentru cei cărora le plac provocările, încercaţi să rezolvaţi problema cu memorie ''O(1)''.

= Temă =
[http://varena.ro/runda/2015-12-03-clasa-7-tema-12 Tema 12 clasa a 7<sup>a</sup>]
* [http://varena.ro/problema/cuburi cuburi] dată la ONI 2012 clasa a 8<sup>a</sup>
* [http://varena.ro/problema/maxim maxim] dată la ONI 2007 clasa a 5<sup>a</sup>

Rezolvări aici [http://solpedia.francu.com/wiki/index.php/Clasa_VII/VIII_lec%C8%9Bia_12_-_9_dec_2014]