Probleme de informatică
  Clasa a IX-a
1. Elementele de bază ale limbajului C++ (instructiunile limbajului) (46)
2. Subprograme predefinite (1)
3. Tablouri (145)
4. Fişiere text (2)
5. Algoritmi elementari (104)
6. Probleme diverse (12)
  Clasa a X-a
1. Subprograme definite de utilizator (87)
2. Şiruri de caractere (42)
3. Înregistrări (26)
4. Recursivitate (57)
5. Combinatorica (0)
6. Alocarea dinamică a memoriei (2)
7. Liste înlănţuite (25)
8. Algoritmul lui Lee (1)
  Clasa a XI-a

1. Metoda "Divide et impera" (12)
2. Metoda Backtracking (85)
3. Metoda Greedy (6)
4. Programare dinamică (18)
5. Grafuri neorientate (37)
6. Grafuri orientate (38)
7. Arbori (33)

  Clasa a XII-a
1. Elemente de baza C# (32)
2. POO in C# (13)
3. C# - Windows Form Application (24)
4. Admitere UBB (12)

   Home Bacalaureat 2016   |   Variante bacalaureat 2009   |   Atestat  |   Olimpiada       
Noutăţi
Subiecte admitere la Facultatea de informatica UBB Cluj-Napoca
Subiecte bacalaureat 2010-2017
Bacalaureat 2017 - competenţe digitale
C# - Windows Form Application - exemple
Modele de proiecte de atestat
Bacalaureat 2017
Subiecte si rezolvări 2010-2017
Rezolvari variante bacalaureat 2009
Competenţe digitale
Examen atestat
Rezumat documentatie
Teme proiect
php.doc
css.doc
exemple_php_si_css.rar
Modele de proiecte de atestat
Subiecte atestat 2014 CNLR
Olimpiada
Clasele V-VI
Clasele VII-VIII
Clasa a IX-a
Clasa a X-a
Clasele XI-XII
Noţiuni teoretice
Metode de sortare
Metoda backtracking


Metode de sortare  

Heapsort
Prin algoritmul heapsort se ordonează elementele în spaţiul alocat vectorului: la un moment dat doar un număr constant de elemente ale vectorului sunt păstrate în afara spaţiului alocat vectorului de intrare. Astfel, algoritmul heapsort combină calităţile a două tipuri de  algoritmi de sortare, sortare internă şi sortare externă.
Heapsort introduce o tehnica nouă de proiectare a algoritmilor bazată pe utilizarea unei structuri de date, numită de regula heap. Structura de date heap este utilă nu doar pentru algoritmul heapsort, ea poate fi la fel de utilă şi în tratarea eficientă a unei cozi de prioritate.
Termenul heap a fost introdus şi utilizat iniţial în contextul algoritmului heapsort, dar acesta se foloseşte şi în legătură cu alocarea dinamică, respectiv în tratarea memoriei bazate pe “colectarea reziduurilor” (garbage collected storage), de exemplu în limbajele de tip Lisp.
Structura de date heap nu se refera la heap-ul menţionat în alocarea dinamica, şi ori de câte ori, în aceasta lucrare voi vorbi despre heap, vom înţelege structura definită aici pentru heapsort.
Structura de date heap (binar) este un vector care poate fi vizualizat sub forma unui arbore binar aproape complet, conform figurii 1.8. Fiecare nod al arborelui corespunde unui element al vectorului care conţine valorile ataşate nodurilor. Arborele este plin, exceptând eventual nivelul inferior, care este plin de la stânga la dreapta doar până la un anumit loc. Un vector A care reprezintă un heap are doua atribute: lungime[A], reprezintă numărul elementelor din vector şi dimensiune-heap[A] reprezintă numărul elementelor heap-ului memorat în vectorul A. Astfel, chiar daca A[1..lungime[A]] conţine în fiecare element al sau date valide, este posibil ca elementele următoare elementului A[dimensiune-heap[A]], unde dimensiune- heap[A] ≤ lungime[A], să nu aparţină heap-ului. Rădăcina arborelui este A[1]. Dat fiind un indice i, corespunzător unui nod, se pot determina uşor indicii părintelui acestuia Parinte(i), al fiului Stânga(i) şi al fiului Dreapta(i).
Parinte(i)
      returneaza [i/2]
Stânga(i)
       returneaza 2i
Dreapta(i)
       returneaza 2i + 1


Figura 1.8 Un heap reprezentat sub forma unui arbore binar (a) şi sub forma unui vector (b). Numerele înscrise în cercurile reprezentând nodurile arborelui sunt valorile ataşate nodurilor, iar cele scrise lângă cercuri sunt indicii elementelor corespunzătoare din vector.

În cele mai multe cazuri, procedura Stânga poate calcula valoarea 2i cu o singura instrucţiune, translatând reprezentarea binara a lui i la stânga cu o poziţie binara. Similar, procedura Dreapta poate determina rapid valoarea 2i + 1, translatând reprezentarea binara a lui i la stânga cu o poziţie binara, iar bitul nou intrat pe poziţia binara cea mai nesemnificativa va fi 1. În procedura Parinte valoarea [i/2]se va calcula prin translatarea cu o poziţie binara la dreapta a reprezentării binare a lui i. Într-o implementare eficienta a algoritmului heapsort, aceste proceduri sunt adeseori codificate sub forma unor “macro-uri” sau a unor proceduri “în-line”.
Pentru orice nod i, diferit de rădăcina, este adevărată următoarea proprietate de heap:
A[Parinte(i)] ≥ A[i]
adică valoarea ataşata nodului este mai mică sau egală cu valoarea asociată părintelui său. Astfel cel mai mare element din heap este păstrat în rădăcină, iar valorile nodurilor oricărui subarbore al unui nod sunt mai mici sau egale cu valoarea nodului respectiv.
Definim înălţimea unui nod al arborelui ca fiind numărul muchiilor aparţinând celui mai lung drum care leagă nodul respectiv cu o frunză, iar înălţimea arborelui ca fiind înălţimea rădăcinii. Deoarece un heap având n elemente corespunde unui arbore binar complet, înălţimea acestuia este Θ(log2 n). Vom vedea că timpul de execuţie al operaţiilor de bază, care se efectuează pe un heap, este proporţional cu înălţimea arborelui şi este Θ(log2 n). În cele ce urmează, vom prezenta trei proceduri şi modul lor de utilizare în algoritmul de sortare, respectiv într-o structura de tip coada de prioritate.

  • Procedura Reconstituie-Heap are timpul de execuţie Θ (log2 n) şi este de prima importanţa în întreţinerea proprietăţii de heap.
  • Procedura Construieste-Heap are un timp de execuţie liniar şi generează un heap dintr-un vector neordonat, furnizat la intrare.
  • Procedura Heapsort se executa în timpul O(n log2 n) şi ordonează un vector în spaţiul alocat acestuia.

Procedura Reconstituie-Heap este un subprogram important în prelucrarea heap-urilor.
Datele de intrare ale acesteia sunt un vector A şi un indice i din vector. Atunci când se apelează Reconstituie-Heap, se presupune că subarborii, având ca rădăcini nodurile Stânga(i) respectiv Dreapta(i), sunt heap-uri. Dar, cum elementul A[i] poate fi mai mic decât descendenţii săi, acesta nu respecta proprietatea de heap. Sarcina procedurii Reconstituie-Heap este de a “scufunda” în heap valoarea A[i], astfel încât subarborele care are în rădăcina valoarea elementului de indice i, să devina un heap.

Subalgoritm Reconstituie-Heap(A, i)
1: l ← Stânga(i)
2: r ←Dreapta(i)
3: daca l ≤ dimesiune-heap[A] şi A[l] > A[i] atunci
4:       maxim ←l
5: altfel
6:       maxim ←i
7: daca r ≤ dimesiune-heap[A] şi A[r] > A[maxim] atunci
8:       maxim ←r
9: daca maxim <> i atunci
10:      schimba A[i] ↔ A[maxim]
11:      Reconstituie-Heap(A, maxim)

Figura 1.9 ilustrează efectul procedurii Reconstituie-Heap. La fiecare pas se determina cel mai mare element dintre A[i], A[Stânga(i)] şi A[Dreapta(i)], iar indicele sau se păstrează în variabila maxim. Daca A[i] este cel mai mare, atunci subarborele având ca rădăcină nodul i este un heap şi procedura se termina. În caz contrar, cel mai mare element este unul dintre cei doi descendenţi şi A[i] este interschimbat cu A[maxim]. Astfel, nodul i şi descendenţii săi satisfac proprietatea de heap. Nodul maxim are acum valoarea iniţiala a lui A[i], deci este posibil ca  subarborele de rădăcină maxim să nu îndeplinească proprietatea de heap. Rezulta că procedura Reconstituie-Heap trebuie apelata recursiv din nou pentru acest subarbore.
Timpul de execuţie al procedurii Reconstituie-Heap, corespunzător unui arbore de rădăcină i şi dimensiune n, este Θ(1), timp în care se pot analiza relaţiile dintre A[i], A[Stânga(i)] şi A[Dreapta(i)] la care trebuie adăugat timpul în care Reconstituie-Heap se executa pentru subarborele având ca rădăcină unul dintre descendenţii lui i. Dimensiunea acestor subarbori este de cel mult 2n/3 – cazul cel mai defavorabil fiind acela în care nivelul inferior al arborelui este plin exact pe jumătate – astfel, timpul de execuţie al procedurii Reconstituie-Heap poate fi descris prin următoarea inegalitate recursiva:
T(n) ≤ T(2n/3) + Θ(1):
Timpul de execuţie al procedurii Reconstituie-Heap pentru un nod de înălţime h poate fi exprimat alternativ ca fiind egal cu Θ(h).

Figura 1.9 Efectul procedurii Reconstituie-Heap(A, 2), unde dimesiune-heap[A] = 10. (a)
Configuraţia iniţiala a heap-ului, unde A[2] (pentru nodul i = 2), nu respecta proprietatea de heap deoarece nu este mai mare decât descendenţii săi. Proprietatea de heap este restabilita pentru nodul 2 în (b) prin interschimbarea lui A[2] cu A[4], ceea ce anulează proprietatea de heap pentru nodul 4. Apelul recursiv al procedurii Reconstituie-Heap(A, 4) poziţionează valoarea lui i pe 4. Dupa interschimbarea lui A[4] cu A[9], aşa cum se vede în (c), nodul 4 ajunge la locul sau şi apelul recursiv Reconstituie-Heap(A, 9) nu mai găseşte elemente care nu îndeplinesc proprietatea de heap.

Construirea unui heap
Procedura Reconstituie-Heap poate fi utilizata “de jos în sus” pentru transformarea vectorului A[1..n] în heap, unde n = lungime[A]. Deoarece toate elementele subşirului A[([n/2]+1)..n] sunt frunze, acestea pot fi considerate ca fiind heap-uri formate din câte un element. Astfel, procedura Construieste-Heap trebuie să traverseze doar restul elementelor şi să execute procedura Reconstituie-Heap pentru fiecare nod întâlnit. Ordinea de prelucrare a nodurilor asigura că subarborii, având ca rădăcină descendenţi ai nodului i să formeze heap-uri înainte ca Reconstituie-Heap să fie executat pentru aceste noduri.

Subalgoritm Construieste-Heap(A)
1: dimesiune-heap[A] ← lungime[A]
2: pentru i ← [lungime[A]/2],1 executa
3:       Reconstituie-Heap(A, i)

Figura 1.10 ilustrează modul de funcţionare al procedurii Construieste-Heap.


Figura 1.10 Modul de execuţie a procedurii Construieste-Heap. În figura se vizualizează structurile de date în starea lor anterioara apelului procedurii Reconstituie-Heap (linia 3 din procedura Construieste-Heap). (a) Se considera un vector A având 10 elemente şi arborele binar corespunzător. Dupa cum se vede în figura, variabila de control i a ciclului, în momentul apelului Reconstituie- Heap(A, i), indica nodul 5. (b) reprezintă rezultatul, variabila de control i a ciclului acum indica nodul 4. (c) - (e) vizualizează iteraţiile succesive ale ciclului pentru din Construieste-Heap. Se observa că, atunci când se apelează procedura Reconstituie-Heap pentru un nod dat, subarborii acestui nod sunt deja heap-uri. (f) reprezintă heap-ul final al procedurii Construieste-Heap.

Timpul de execuţie al procedurii Construieste-Heap poate fi calculat simplu, determinând limita superioara a acestuia: fiecare apel al procedurii Reconstituie-Heap necesita un timp Θ(log2 n) şi, deoarece pot fi Θ(n) asemenea apeluri, rezulta că timpul de execuţie poate fi cel mult Θ(n log2 n). Aceasta estimare este corecta, dar nu este suficient de tare asimptotic.
Vom obţine o limita mai tare observând că timpul de execuţie a procedurii Reconstituie-Heap depinde de înălţimea nodului în arbore, aceasta fiind mica pentru majoritatea nodurilor.
Estimarea noastră mai riguroasa se bazează pe faptul că un heap având n elemente are înălţimea log2n şi că pentru orice înălţime h, în heap exista cel mult [n/2h+1]noduri de înălţime h.
Timpul de execuţie a procedurii Reconstituie-Heap pentru un nod de înălţime h fiind Θ(h), obţinem pentru timpul de execuţie a procedurii Construieste-Heap:

Astfel, timpul de execuţie al procedurii Construieste-Heap poate fi estimat ca fiind:

De aici rezulta că se poate construi un heap dintr-un vector într-un timp liniar.

Algoritmul heapsort
Algoritmul heapsort începe cu apelul procedurii Construieste-Heap în scopul transformării vectorului de intrare A[1..n] în heap, unde n = lungime[A]. Deoarece cel mai mare element al vectorului este ataşat nodului rădăcină A[1], acesta va ocupa locul definitiv în vectorul ordonat prin interschimbarea sa cu A[n]. În continuare, “excluzând” din heap cel de-al n-lea element (şi micşorând cu 1 dimesiune-heap[A]), restul de A[1..(n - 1)] elemente se pot transforma uşor în heap, deoarece subarborii nodului rădăcină au proprietatea de heap, cu eventuala excepţie a elementului ajuns în nodul rădăcină.


SubalgoritmHeapsort(A)
1: Construieste-Heap(A)
2: pentru i ← lungime[A], 2 executa
3:         schimba A[1] ↔ A[i]
4:         dimesiune-heap[A] ← dimesiune-heap[A] - 1
5:         Reconstituie-Heap(A, 1)

Apelând procedura Reconstituie-Heap(A, 1) se restabileşte proprietatea de heap pentru vectorul A[1..(n - 1)]. Acest procedeu se repeta micşorând dimensiunea heap-ului de la n - 1 până la 2.
Figura 1.11 ilustrează, pe un exemplu, modul de funcţionare a procedurii Heapsort, dupa ce în prealabil datele au fost transformate în heap. Fiecare heap reprezintă starea iniţiala la începutul pasului iterativ (linia 2 din ciclul pentru).
Timpul de execuţie al procedurii Heapsort este Θ(n log2 n), deoarece procedura Construieste-Heap se executa într-un timp Θ(n), iar procedura Reconstituie-Heap, apelata de n-1 ori, se executa în timpul Θ(log2 n).

Figura 1.11 Modul de funcţionare a algoritmului Heapsort. (a) Structura de date heap, imediat dupa construirea sa de către procedura Construieste-Heap. (b)-(j) Heap-ul, imediat dupa câte un apel al procedurii Reconstituie-Heap (linia 5 în algoritm). Figura reprezintă valoarea curenta a variabilei i. Din heap fac parte doar nodurile din cercurile nehaşurate. (k) Vectorul A ordonat, obţinut ca rezultat.




  Clasa a IX-a
1. Elementele de bază ale limbajului C++ (instructiunile limbajului) (46)
2. Subprograme predefinite (1)
3. Tablouri (145)
4. Fişiere text (2)
5. Algoritmi elementari (104)
6. Probleme diverse (12)
  Clasa a X-a
1. Subprograme definite de utilizator (87)
2. Şiruri de caractere (42)
3. Înregistrări (26)
4. Recursivitate (57)
5. Combinatorica (0)
6. Alocarea dinamică a memoriei (2)
7. Liste înlănţuite (25)
8. Algoritmul lui Lee (1)
  Clasa a XI-a

1. Metoda "Divide et impera" (12)
2. Metoda Backtracking (85)
3. Metoda Greedy (6)
4. Programare dinamică (18)
5. Grafuri neorientate (37)
6. Grafuri orientate (38)
7. Arbori (33)

  Clasa a XII-a
1. Elemente de baza C# (32)
2. POO in C# (13)
3. C# - Windows Form Application (24)
4. Admitere UBB (12)

Calculatoare si accesorii second hand
Copyright 2009-2017 Muresan Vasile Ciprian - mcip.ro