View source for Clasa VI/VII/VIII lecția 10 - 06 nov 2012

== Clasa a șasea și a șaptea împreună ==
=== Timpul de rulare al unui program ===
* Cum putem să măsurăm timpul de execuție al unui program? Vom include o bibliotecă care ne dă funcțiile necesare, și anume ''<nowiki><sys/time.h></nowiki>''. Apoi vom folosi o funcție ''gettimeofday'' care ne returnează o structură care conține secundele si microsecundele momentului chemării funcției. Apelăm această funcție la începutul programul și la final. Diferența ne dă timpul de execuție.
* Exemplu: 
<pre>#include <stdio.h>
#include <sys/time.h>

int main() {
  struct timeval tv;
  int tstart, tend;
  int i, j, sum;

  gettimeofday( &tv, NULL ); // timpul actual
  tstart = tv.tv_sec * 1000 + tv.tv_usec / 1000; // numar milisecunde

  // ... programul nostru ...
  sum = 0;
  for ( i = 0; i < 10000; i++ )
    for ( j = i; j < 10000; j++ )
      sum = sum + i + j;
  // ... sfirsit program ...

  gettimeofday(&tv, NULL);  // timpul actual
  tend = tv.tv_sec * 1000 + tv.tv_usec / 1000;   // numar milisecunde

  printf("Programul a rulat %d.%03ds\n",
         (tend - tstart) / 1000, (tend - tstart) % 1000);

  return 0;
}</pre>
* Pentru cei care folosesc GNU/Linux (sau Cygwin, un echivalent pe Windows), ei pot executa programul în linia de comandă cu comanda ''time'', care va afișa timpul de execuție al programului executat. Mult mai simplu :)

=== Liste ===
* [http://en.wikipedia.org/wiki/Linked_list Definiție]: în informatică o listă înlănțuită este o structură de date care constă dintr-un grup de noduri care împreună reprezintă o secvență. În forma ei cea mai simplă fiecare nod este format din date și o referință (înlănțuire) către nodul următor în secvență. Lista înlănțuită permite inserarea și ștergerea eficientă a elementelor de pe orice poziție în secvență. [[Image:lista-exemplu.gif|frame|none|Exemplu de listă înlănțuită]]
* Implementare. O primă implementare posibilă este folosind doi vectori: un vector ''v'' care memorează elementele listei (numere întregi de exemplu) și un vector ''next'', care memorează <nowiki>indicele următorului element din listă. Perechea (v[i], next[i]) conține un nod al listei.</nowiki>
* Operații cu liste:
** Inserare
{|
| valign="top"|[[Image:lista-inserare-desen.gif|frame|none|Inserare element - concept]]
| valign="top"|[[Image:lista-inserare-implementare.gif|frame|none|Inserare element - implementare]]
<pre>// pos conține poziția nodului de inserat
next[pos] = next[i];
next[i] = pos;</pre>
|-
| <center>Inserare element în listă după elementul i</center>
|}
** Ștergere
{|
| valign="top"|[[Image:lista-stergere-desen.gif|frame|none|Ștergere element - concept]]
| valign="top"|[[Image:lista-stergere-implementare.gif|frame|none|Ștergere element - implementare]]
<pre>next[i] = next[next[i]];</pre>
|-
| <center>Ștergere element din listă după elementul i</center>
|}
* Aplicație: n copii numerotați de la 1 la n și așezați în cerc numără la ''v-ați ascunselea'', din k în k, începînd cu copilul 1. Date n și k să se afișeze ordinea în care ies copiii din cerc.
** O rezolvare simplă este să memorăm numerele de la 1 la n într-un vector și apoi să avansăm k elemente și să afișăm elementul curent, iar apoi să îl setăm pe zero. Reluăm căutarea de n ori, ignorînd elementele zero. Deoarece avansul cu k copii poate să dureze n (căci sărim peste elemente zero) soluția are complexitate O(n<sup>2</sup>):
{|
| valign="top"|<pre>#include <stdio.h>

int v[100];

int main() {
  int n, k, i, j, pos;

  scanf( "%d%d", &n, &k );
  for ( i = 0; i < n; i++ )
    v[i] = i + 1;
  pos = n - 1;
  for ( i = 0; i < n; i++ ) {
    // avanseaza k elemente nenule
    for ( j = 0; j < k; j++ ) {
      pos = (pos + 1) % n;
      while ( v[pos] == 0 )
        pos = (pos + 1) % n;
    }
    printf( "%d ", v[pos] );
    v[pos] = 0;
  }
  printf( "\n" );

  return 0;
}</pre>
|-
| <center>''Numărare în cerc, soluție cu vector''</center>
|}
** O soluție mai eficientă, care folosește liste, are complexitate O(n∙k):
{|
| valign="top"|<pre>#include <stdio.h>

int v[100], next[100];

int main() {
  int n, k, i, j, pos;

  scanf( "%d%d", &n, &k );
  // initializam lista
  for ( i = 0; i < n; i++ ) {
    v[i] = i + 1;
    next[i] = (i + 1) % n;
  }

  pos = n - 1; // pos e pozitia copilului din-nainte de copilul de eliminat
  for ( i = 0; i < n; i++ ) {
    // avanseaza k - 1 elemente deoarece eliminarea conteaza ca un element
    for ( j = 1; j < k; j++ )
      pos = next[pos];
    printf( "%d ", v[next[pos]] );
    next[pos] = next[next[pos]];
  }
  printf( "\n" );

  return 0;
}</pre>
|-
| <center>''Numărare în cerc, soluție cu listă''</center>
|}

=== Radix Sort ===
* Este o sortare care nu face comparații. Ea lucrează cu vectori similari cu vectorii de frecvență. Are la bază un algoritm mai simplu de sortare numit ''sortare prin numărare'' (''counting sort''<nowiki>). Sortarea prin numărare creează un vector de frecvență al fiecărui număr din vectorul de sortat. Astfel, pentru fiecare element v[i] se execută num[v[i]]++. În final se parcurge vectorul num și se afișează indicii diferiți de zero.</nowiki>
* Counting sort funcționează pentru numere relativ mici. Dacă vrem să ordonăm numere mari, sau perechi de numere, sau șiruri vom avea nevoie de prea multă memorie.
* Să considerăm exemplul sortării de perechi (i, j), unde 0 ≤ i, j ≤ 100000. Dacă am folosi sortarea prin numărare am avea nevoie de un vector de 100000 ∙ 100000 = 10 miliarde de elemente. Radix sort procedează astfel: folosește un vector ''r'' de 100000 de elemente. Un element este o listă de perechi. În primul pas vom trece prin toate perechile. Pentru fiecare pereche (i, j) vom adăuga acea pereche în lista de la poziția j. La final vom trece prin vectorul r și vom colecta toate elementele, în ordinea în care apar ele. Apoi, la pasul doi, vom trece iarăși prin toate perechile și pentru fiecare pereche (i, j) vom adăuga acea pereche în lista de la poziția i. În final vom colecta toate elementele din r. Ele vor fi sortate. Exemplu: să presupunem că vrem să ordonăm perechile (4, 5) (1, 3) (1, 5) (4, 3): 

{|
| valign="top"|[[Image:radix-sort-pas-1.gif|frame|none|''Pasul 1'']]
| valign="top"|[[Image:radix-sort-pas-2.gif|frame|none|''Pasul 2'']]
|}
* Implementarea va avea nevoie de trei vectori suplimentari: unul este deja familiar, ''next'', care pentru fiecare pereche memorează elementul următor in listă. Un altul este vectorul ''prim'', care memorează începuturile listelor create în timpul pașilor de sortare. Mai avem nevoie de un vector ''ultim'', care să memoreze sfîrșitul listelor create, pentru o concatenare mai rapidă. Iată o implementare posibilă:
<pre>#include <stdio.h>

#define NIL -1
#define MAXNR 100000

int v[1000000][2], next[1000000];
int prim[MAXNR + 1], ultim[MAXNR + 1];

int main() {
  int n, p, i, pas, primul, ultimul;

  // citim lista si cream legaturile
  scanf( "%d", &n );
  primul = 0;
  scanf( "%d%d", &v[0][0], &v[0][1] );
  for ( i = 1; i < n; i++ ) {
    scanf( "%d%d", &v[i][0], &v[i][1] );
    next[i - 1] = i;
  }
  next[n - 1] = NIL;
  ultimul = n - 1;

  for ( pas = 1; pas >= 0; pas-- ) {
    // toate listele sint vide initial
    for ( i = 0; i <= MAXNR; i++ )
      prim[i] = ultim[i] = NIL;
    // distribuim perechile dupa nr pe pozitia pas
    p = primul;
    while ( p != NIL ) {
      // distribuie perechea p in lista lui v[p][pas]
      if ( prim[v[p][pas]] == NIL ) // lista nu exista, o cream
        prim[v[p][pas]] = ultim[v[p][pas]] = p;
      else {
        next[ultim[v[p][pas]]] = p;
        ultim[v[p][pas]] = p;
      }
      p = next[p];
    }

    // colecteaza perechile in ordinea din prim/ultim
    primul = ultimul = NIL; // nu stim unde incepe lista, o facem vida
    for ( i = 0; i <= MAXNR; i++ ) {
      if ( prim[i] != NIL ) { // avem o lista la elementul i
        if ( primul == NIL ) {
          // prima lista, intializam primul si ultimul
          primul = prim[i];
          ultimul = ultim[i];
        } else {
          // adaugam la final
          next[ultimul] = prim[i];
          ultimul = ultim[i];
        }
      }
      next[ultimul] = NIL;
    }
  }

  // afisam perechile in ordine incepind cu primul
  p = primul;
  while ( p != NIL ) {
    printf( "(%d, %d) ", v[p][0], v[p][1] );
    p = next[p];
  }
  printf( "\n" );

  return 0;
}</pre>
* Discuție: generalizare pentru tupluri de oricîte numere, numere întregi, șiruri de caractere
* Aplicație: problema bile6. O vom rezolva prin sortarea obstacolelor (perechi de coordonate) prin radix sort și apoi actualizarea vectorului de bile la fiecare obstacol. Rămîne ca temă.
* Aplicație: problema zigzag. Putem parcurge matricea de codificare în zigzag și stoca coordonatele ca perechi. Apoi sortăm perechile după linie și apoi după coloană. Fiecare pereche primește un caracter de la intrare, în ordine. În final parcurgem perechile în ordinea originală și obținem decodificarea tetului. Rămîne ca temă.

=== Simulare ===
* Despre simulare.
** Trebuie să avem un model, numit sistem. Sistemul evoluează, își schimbă starea. Deci avem o stare a sistemului. Ea trebuie descrisă complet, prin variabile.
** Avem un ceas, așa numitul ''tact'' al sistemului, bătaia lui de inimă, precum are și procesorul. De obicei tactul sistemului este impus de problemă.
** Avem o buclă, care avansează timpul cu un tact și modifică starea sistemului. Bucla testează un steguleț de oprire. În buclă se determină condiția de terminare și se setează stegulețul.
* Aplicații, cu explicația variabilelor care descriu complet starea:
** Problema joc16 (campion) ONI 2011 clasa a 6-a. Starea constă din poziția celor doi copii și din cîte un vector de fiecare copil care memorează pentru fiecare poziție dacă copilul a fost acolo. Simularea se termină fie cind indicii celor doi copii devin egali, fie cînd unul din copii sare pe un element 1 în vectorul său. Vom număra de cîte ori s-a executat bucla pentru a putea răspunde de cîte ori au sărit copiii. La ieșirea din bucla de simulare, vom calcula numărul de elemente zero în ambii vectori. Rămîne ca temă.
** Problema tetris (campion) ONI 2009 clasa a 6-a. Starea constă dintr-o matrice care conține tabla de joc. Pentru a face algoritmul mai rapid vom ține minte pentru fiecare coloană din matrice cîte piese avem pe acea coloană. Vom avea nevoie, deci, de un vector suplimentar. La așezarea unei piese vom căuta prima coloană care are număr maxim de piese la vîrf similare cu piesa curentă. Totodată vom memora și coloana cea mai mică, pentru a putea hotărî, în final, unde se depune piesa curentă. Rămîne ca temă.

=== Lămuriri probleme din urmă ===
* Rezolvare problema [http://varena.ro/problema/trigrame trigrame] aici [http://solpedia.francu.com/wiki/index.php/Clasa_VI/VII/VIII_lec%C8%9Bia_7_-_16_oct_2012]

== Clasa a șasea ==
=== Temă clasa a șasea ===
* Probleme din urmă: joc16 (campion), xy (campion), trigrame (vianuarena) (rezolvare trigrame aici [http://solpedia.francu.com/wiki/index.php/Clasa_VI/VII/VIII_lec%C8%9Bia_7_-_16_oct_2012])
* Problema bile6 (campion) ONI 2012 clasa 7, folosind radix sort '''sau '''problema zigzag (campion) ONI 2012 clasa 7, folosind neapărat radix sort
* Problema tetris (campion) ONI 2009, clasa 6, pentru simulare
* '''Opțional''': macheta (campion) ONI 2011 clasa 8

== Clasa a șaptea și a opta ==
=== Lămuriri la probleme din urmă ===
* Maxim (vianuarena): folosiți algoritmul de maxim în fereastră glisantă. Cum reducem la O(1) memorie? Observînd că coada conține numai cifre în ordine descrescătoare. Deci o putem codifica ca perechi (cifră, număr apariții), avînd astfel maxim 10 elemente.
* Optim (campion): programare dinamică, pentru cei interesați (Alex Pascadi, Ori Pavel, Bogdan Crețu) și cine mai vrea, temă de gîndire.

=== Analiză amortizată ===
* Problema skyline (vianuarena): dreptunghiul de arie maximă sub o histogramă (maximal rectangle under a skyline), discuție cum se face, pe scurt și analiza amortizată a algoritmului. Rămîne ca temă.

=== Temă clasa a șaptea ===
* Rămasă din urmă: mesaj3 (campion) ONI 2011 clasa 7
* Problema bile6 (campion) ONI 2012 clasa 7, folosind neapărat radix sort '''sau''' problema zigzag (campion) ONI 2012 clasa 7, folosind neapărat radix sort
* Problema tetris (campion) ONI 2009 clasa 6, pentru simulare
* '''Opțional''': macheta (campion) ONI 2011 clasa 8
* '''Opțional''': skyline la vianuarena

=== Temă clasa a opta ===
* Ramase din urmă: macheta (campion) oni 2011 clasa 8, skyline (vianuarena)
* Problema bile6 ONI 2012 clasa 7, folosind neapărat radix sort
* '''Opțional''': puncte5
* '''Opțional''': zeratul
* '''Opțional''': taburet baraj 2011