Tema - rezolvări

Rezolvări aici [1]

Lecţie

Tehnici de programare: divide et impera

Denumită și divide and conquer sau dezbină și stăpînește, este o tehnică cunoscută de mii de ani conducătorilor. Este o tehnică de cucerire sau menținere a puterii asupra unui grup care ar avea putere mai mare dacă s-ar uni. Ținînd acel grup dezbinat, fiecare facțiune în parte are putere mică și poate fi cucerită, sau condusă. Tehnica a fost aplicată de Cezar, Napoleon, iar, mai recent, de către Britanici în Africa și de către Stalin în Rusia. Dintre tehnicile folosite în lumea reală putem menționa:

Ajutorarea și promovarea celor care cooperează cu puterea, pedepsirea celor ce nu cooperează.
Încurajarea cheltuielilor prostești, pentru a reduce capitalul disponibil organizării sau luptei.
Încurajarea divizării oamenilor pentru a preveni formarea alianțelor.
Încurajarea turnătorilor, cei care trîmbițează orice alianță posibil periculoasă.
Sădirea de neîncredere între oameni.

O parte din aceste tehnici se regăsesc și în țara noastră, precum și în majoritatea țărilor lumii, inclusiv cele dezvoltate. De exemplu, toate țările lumii folosesc un număr uriaș de taxe și impozite, fiecare din ele relativ mici. Cînd le însumăm constatăm că în jur de 90% din banii noștri se duc pe aceste taxe și impozite. Dacă ar exista o taxă unică de 90%, oamenii s-ar revolta. Astfel, tehnica de împărțire a unor taxe mari în mai multe taxe mici îi face pe oameni să nu le observe și să nu se revolte.

Pentru exemple clasice de folosire a acestei tehnici în lumea reală vizitați pagina de divide et impera a wikipediei.

Tehnica divide et impera (divide and conquer) în informatică

În informatică divide et impera constă în împărțirea problemei în subprobleme mai mici, nesuprapuse (o tehnică în care subproblemele sînt suprapuse este programarea dinamică). Fiecare din aceste subprobleme se rezolvă separat, mai ușor, deoarece sînt mai mici. Rezultatul final se obține din combinația rezultatelor subproblemelor.

Tehnica divide et impera simplă (decrease and conquer)

În următoarele exemple de divide et impera problema se reduce la o singură problemă, mai mică. Este un caz degenerat, în care implementarea poate fi iterativă (nu necesită recursivitate).

Căutare binară

Precum știm, căutarea binară împarte vectorul original în două, apoi decide care din cele două jumătați ar putea să conțină elementul căutat. Apoi rezolvă problema mai mică. Complexitate: O(log n).

Algoritmul lui Euclid

Și acest binecunoscut algoritm poate fi văzut ca un exemplu de divide et impera. El reduce problema de la cmmdc(a, b) la o problemă mai mică, cmmdc(b, a mod b). Complexitate: O(log min(a, b)).

Puzzle balanţă

Avem 25 de bile care arată identic, una este ceva mai ușoară. Avem la dispoziție o balanță. Găsiți bila mai ușoară din trei cîntăriri.

Medianul unui vector

Complexitate: pe medie O(n), în cel mai rău caz O(n²). Este necesar la problema antitir.

Căutare punct fix

Se dă un vector sortat de n elemente întregi distincte. Să se găsească dacă există indicele i astfel încît v[i] == i. Găsiți un algoritm divide et impera care are complexitate O(log n).

Probleme vianuarena

Următoarele probleme de la vianuarena sînt de divide et impera degenerat:

Tehnica divide et impera propriu zisă

În următoarele exemple de divide et impera problema se reduce la două sau mai multe probleme mai mici. Implementarea este mult mai simplă dacă folosim recursivitate.

Puzzle pavare

Se dă o grilă de 2ⁿ x 2ⁿ pătrate din care lipsește un pătrat. Să se acopere cu piese formate din 3 pătrate aranjate în formă de litera L.

Mergesort

Complexitate: O(n log n), dar O(n) memorie suplimentară (aceasta e problema principală a algoritmului).

Quicksort

Am discutat despre cum funcționează algoritmul quick sort. Iată, mai jos, o implementare diferită de cea care se predă în școală, ceva mai simplă, mai eficientă și, cred, mai ușor de ținut minte. Această implementare este mai aproape de implementarea din lumea reală.

void myqsort( int begin, int end ) {
  int aux, b = begin, e = end,
    pivot = v[(begin + end) / 2]; // pivotul poate fi orice pozitie intre begin si end

  while ( b <= e ) {
    while ( v[b] < pivot ) b++;
    while ( v[e] > pivot ) e--;
    if ( b <= e ) {
      aux = v[b]; v[b] = v[e]; v[e] = aux;
      b++; e--;
    }
  }
  // acum [begin..e] sint mai mici sau egale cu pivotul
  // si [b..end] sint mai mari sau egale cu pivotul
  if ( begin < e ) myqsort( begin, e );
  if ( b < end ) myqsort( b, end );
}

De remarcat (diferenţe faţă de implementarea clasică):

Ne oprim din căutare şi dacă găsim un element egal cu pivotul.
Indicii vor înainta cel puţin o dată în interiorul buclei while.
În buclele de avans al indicilor b şi e nu testăm dacă ei depăşesc vectorul; acesta este avantajul de viteză al acestei implementări
Apelurile recursive nu se fac, aşa cum ne-am aştepta, de la begin la b şi de la e la end, deoarece oprirea din buclă se face atunci cînd indicii se încalecă, ei vor fi în ordine inversă în final.

Ce complexitate are şi cîtă memorie foloseşte? Quick sort are timp O(n log n) pe cazul mediu și O(n²) pe cazul cel mai rău. El folosește O(log n) memorie pe cazul mediu și O(n) memorie pe cazul cel mai rău. Cu toate acestea, prin eliminarea recursiei la coadă, se demonstrează că quick sort folosește memorie O(log n) pe cazul cel mai rău. Pentru a ajunge la această memorie folosită trebuie să avem grijă ca al doilea apel recursiv să fie cu vectorul de lungime mai mare.

Aplicații quick sort

Selecţia (folosind pivotarea), al k-ulea element în vectorul sortat, folosind algoritmul quick select. Un caz particular al selecţiei este găsirea medianului, menţionată mai devreme.

Ziua regelui

Un rege organizează o petrecere mare de ziua lui. Petrecerea începe peste 24 de ore. Regele află că una din cele 1000 de sticle de vin pe care le va servi este otrăvită. Otrava acționează ciudat: omul care bea chiar și cea mai mică cantitate din această otravă nu are nici un simptom vreme de 24 de ore, apoi moare subit. Regele are sclavi la dispoziție pe care îi poate folosi. Lui nu îi pasă cîți sclavi mor, dar îi pasă cîți sclavi beau vin, deoarece un sclav care a băut vin nu poate fi folosit la treabă, ci trebuie izolat spre observare. Care este numărul minim de sclavi cu care regele poate afla sticla otrăvită?

Probleme temă

Problemele de la temă sînt probleme de divide et impera propriu zise:

Temă

Clasa a 7-a

Tema 27 clasa a 7^a
Opţional: Tema 27 clasa a 7^a opţională
Opţional: participaţi la concursul de nivel baraj gimnaziu la clasa a 8^a, iar apoi rezolvaţi tema.
Opţional: încercaţi să găsiţi rezolvări (fără implementare) la problemele enunţate în lecţia aceasta, inclusiv la puzzle-uri.

Clasa a 8-a

Concurs clasa a 8^a miercuri 1 aprilie ora 17:00 (nu e păcăleală :) )
Tema 27 clasa a 8^a aceleaşi probleme ca la concurs
Opţional: tema opţională de la clasa a 7^a

Rezolvări aici [2]

Clasa VII/VIII lecția 27 - 31 mar 2015

Contents