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  

Sortarea prin inserţie
Începem cu sortarea prin inserţie, care este un algoritm eficient pentru sortarea unui număr mic de obiecte. Sortarea prin inserţie funcţionează în acelaşi fel în care mulţi oameni sortează un pachet de cărţi de joc. Se începe cu pachetul aşezat pe masa cu faţa în jos şi cu mâna stânga goala. Apoi, luam câte o carte de pe masa şi o inseram în poziţia corectă în mâna stânga. Pentru a găsi poziţia corecta pentru o carte data, o comparăm cu fiecare dintre cărţile aflate deja în mâna stânga, de la dreapta la stânga (sau de la stânga la dreapta), aşa cum este ilustrat în Figura 1.1.

Figura 1.1 Modul de ordonare a cărţilor, folosind metoda sortării prin inserţie.
Pseudocodul pentru sortarea prin inserţie este prezentat ca o procedura numita Sorteaza-Prin-Inserţie, care are ca parametru un vector A[1..n] conţinând un sir de lungime n care urmează a fi sortat. (Pe parcursul codului, numărul de elemente ale lui A este notat prin lungime[A].) Numerele de intrare sunt sortate pe loc, în cadrul aceluiaşi vector A, cel mult un număr constant dintre acestea sunt memorate în zone de memorie suplimentare. Când Sorteaza-Prin-Inserţie se termina, vectorul iniţial A va conţine elementele şirului de ieşire sortat.


Subalgoritm Sorteaza-Prin-Inserţie(A)
1: pentru j ← 2, lungime[A] executa
2:     cheie ← A[j]   
3:     i ← j - 1
4:     cât timp i > 0 şi A[i] > cheie executa
5:            A[i + 1] ← A[i]
6:            i ← i – 1
7:     A[i + 1] ← cheie  {Insereaza A[j] în sirul sortat A[1..j - 1]}

Figura 1.2 ilustrează modul de funcţionare a acestui algoritm pentru A = (5, 2, 4, 6, 1, 3). Indicele j corespunde “cărţii” care urmează a fi inserată în mâna  stânga. Elementele A[1..j - 1] corespund mulţimii de cărţi din mâna, deja sortate, iar elementele A[j + 1..n] corespund pachetului de cărţi aflate încă pe masă. Indicele se deplasează de la stânga la dreapta în interiorul vectorului. La fiecare iteraţie, elementul A[j] este ales din vector (linia 2). Apoi, plecând de la poziţia j - 1, elementele sunt, succesiv, deplasate o poziţie spre dreapta până când este găsita poziţia corecta pentru A[j] (liniile 3–6), moment în care acesta este inserat (linia 7).

a1

a2

a3

a4

a5

a5

5

2

4

6

1

3

2

5

4

6

1

3

2

4

5

6

1

3

2

4

5

6

1

3

1

2

4

5

6

3

1

2

3

4

5

6

Figura 1.2 Modul de operare a procedurii Sorteaza-Prin-Inserţie asupra vectorului A =(5, 2, 4, 6, 1, 3).
Poziţia indicelui j este indicata prin colorarea celulei corespunzătoare din tabelul din figură.

Analiza sortării prin inserţie
Timpul de execuţie necesar procedurii Sorteaza-Prin-Inserţie depinde de intrare: sortarea a o mie de numere ia mai mult timp decât sortarea a trei. Mai mult decât atât, Sorteaza-Prin-Inserţie poate să consume timpi diferiţi pentru a sorta două şiruri de numere de aceeaşi dimensiune, în funcţie de măsura în care acestea conţin numere aproape sortate. În general, timpul necesar unui algoritm creşte odată cu dimensiunea datelor de intrare, astfel încât este tradiţional să se descrie timpul de execuţie al unui program în funcţie de dimensiunea datelor de intrare. În acest scop, trebuie să definim cu mai multă precizie termenii de “timp de execuţie” şi “dimensiune a datelor de intrare”.
Definiţia dimensiunii datelor de intrare depinde de problema studiată. Pentru multe probleme, inclusiv  sortarea, cea mai naturală măsură este numărul de obiecte din datele de intrare – de exemplu, pentru sortare, un vector de dimensiune n. Pentru multe alte probleme, ca spre exemplu înmulţirea a doi întregi, cea mai buna măsură pentru dimensiunea datelor de intrare este numărul total de biţi necesari pentru reprezentarea datelor de intrare în notaţie binară. Uneori, este mai potrivit să exprimăm dimensiunea datelor de intrare prin două numere în loc de unul. De exemplu, dacă datele de intrare ale unui algoritm sunt reprezentate de un graf, dimensiunea datelor de intrare poate fi descrisa prin numărul de vârfuri şi muchii ale grafului. În cazul sortării unui vector de numere, putem descrie dimensiunea datelor prin numărul de valori şi prin mărimea acestora ca numere. Pentru fiecare problema pe care o vom studia, vom indica măsura utilizată pentru dimensiunea datelor de intrare.
Timpul de execuţie a unui algoritm pentru un anumit set de date de intrare este determinat de numărul de operaţii primitive sau “paşi” executaţi. Este util să definim noţiunea de “pas” astfel încât să fie cât mai independent de calculator. Pentru execuţia unei linii din pseudocod este necesară o durată constantă de timp. O anumita linie poate avea nevoie de un timp de execuţie diferit decât o alta, dar vom presupune că fiecare execuţie a liniei i consuma timpul ci, unde ci este o constantă. Acest punct de vedere este conform cu modelul RAM şi, în acelaşi timp, reflectă, destul de bine, modul în care pseudocodul poate fi, de fapt, utilizat în cele mai multe cazuri concrete.
În prezentarea care urmează, expresia noastră pentru timpul de execuţie al algoritmului Sorteaza-Prin-Inserţie va evolua de la o formulă relativ complicată, care foloseşte toate costurile de timp ci, la una mult mai simplă în notaţii, care este mai concisă şi mai uşor de manevrat. Aceasta notaţie mai simplă va face, de asemenea, uşor de determinat dacă un algoritm este mai eficient decât altul.
Începem prin a relua prezentarea procedurii Sorteaza-Prin-Inserţie, adăugând “costul” de timp pentru fiecare instrucţiune şi un număr care reprezintă de câte ori aceasta este efectiv executata. Pentru fiecare j = 2, 3, … , n, unde n = [A], vom nota cu tj numărul de execuţii ale testului cât timp din linia 5 pentru valoarea fixata j. Vom presupune că un comentariu nu este o instrucţiune executabila, prin urmare nu cere timp de calcul.


Subalgoritm  Sorteaza-Prin-Inserţie(A)

cost

timp

1: pentru j ← 2, lungime[A] executa

c1

n

2:          cheie ← A[j]

c2

n-1

3:           i ← j - 1

c3

n-1

4:          cât timp i > 0 şi A[i] > cheie executa

c4

Σnj=2tj

5:                      A[i + 1] ← A[i]

c5

Σnj=2(tj-1)

6:                      i ← i - 1

c6

Σnj=2(tj-1)

7:          A[i + 1] ← cheie

c7

n-1

Timpul de execuţie al algoritmului este suma tuturor timpilor de execuţie corespunzători fiecărei instrucţiuni executate: o instrucţiune care consuma timpul ci pentru execuţie şi este executată de n ori, va contribui cu cin la timpul total de execuţie. Pentru a calcula T(n),timpul de execuţie pentru Sorteaza-Prin-Inserţie, vom aduna produsele mărimilor indicate în coloanele cost şi timp, obţinând

Chiar pentru date de intrare de aceeaşi mărime, timpul de execuţie al unui algoritm dat poate să depindă de conţinutul datelor de intrare. De exemplu, pentru Sorteaza-Prin-Inserţie, cazul cel mai favorabil apare când vectorul de intrare este deja sortat. Pentru fiecare j = 2,3, …  n,vom găsi că A[i] ≤ cheie în linia 4, când i are valoarea iniţiala j - 1. Rezulta tj = 1 pentru j = 2, 3, …, n şi timpul de execuţie în cazul cel mai favorabil este
T(n) = c1n + c2(n - 1) + c3(n - 1) + c4(n - 1) + c7(n - 1)
= (c1 + c2 + c3 + c4 + c7)n - (c2 + c3 + c4 + c7)
Acest timp de execuţie poate fi exprimat sub forma an + b pentru anumite constante a şi b care depind doar de timpii de execuţie ci, fiind astfel o funcţie liniara de n.
Daca vectorul este sortat în ordine inversa – adică, în ordine descrescătoare – obţinem cazul cel mai defavorabil. În aceasta situaţie trebuie să comparăm fiecare element A[j] cu fiecare element din subvectorul A[1..j - 1], şi, astfel, tj = j pentru j = 2, 3, …, n. Observând că

Găsim că în cazul cel mai defavorabil timpul de execuţie pentru Sorteaza-Prin-Inserţie este

Rezulta că timpul de execuţie în cazul cel mai defavorabil poate fi exprimat sub forma an2 + bn + c, unde constantele a, b şi c depind, din nou, de costurile ci ale instrucţiunilor, fiind astfel o funcţie pătratica de n.
În analiza sortării prin inserţie am cercetat ambele situaţii extreme: cazul cel mai favorabil, în care vectorul de intrare era deja sortat, respectiv cel mai defavorabil, în care vectorul de intrare era sortat în ordine inversa. În continuare (pe tot parcursul acestei lucrări), ne vom concentra, de regula, pe găsirea timpului de execuţie în cazul cel mai defavorabil, cu alte cuvinte, a celui mai mare timp de execuţie posibil relativ la orice date de intrare de dimensiune constanta n. Precizăm trei motive pentru aceasta orientare:

  • Timpul de execuţie al unui algoritm în cazul cel mai defavorabil este o margine superioară a timpului de execuţie pentru orice date de intrare de dimensiune fixă. Cunoscând acest timp, avem o garanţie că algoritmul nu va avea, niciodată, un timp de execuţie mai mare. Nu va fi nevoie să facem presupuneri sau investigaţii suplimentare asupra timpului de execuţie şi să sperăm că acesta nu va fi, niciodată, mult mai mare.
  • Pentru anumiţi algoritmi, cazul cel mai defavorabil apare destul de frecvent. De exemplu, în căutarea unei anumite informaţii într-o baza de date, cazul cel mai defavorabil al algoritmului de căutare va apare deseori când informaţia căutată nu este de fapt prezentă în baza de date. În anumite aplicaţii, căutarea unor informaţii absente poate fi frecventă.
  • “Cazul mediu” este, adesea, aproape la fel de defavorabil ca şi cazul cel mai defavorabil. Să presupunem că alegem la întâmplare n numere şi aplicam sortarea prin inserţie. Cât timp va fi necesar pentru a determina locul în care putem insera A[j] în subvectorul A[1..j -1]? În medie, jumătate din elementele subvectorului A[1..j - 1] sunt mai mici decât A[j], şi cealaltă jumătate sunt mai mari. Prin urmare, în medie, trebuie verificate jumătate din elementele subvectorului A[1..j-1], deci tj = j/2. Daca ţinem seama de aceasta observaţie, timpul de execuţie mediu va apărea tot ca o funcţie pătratică de n, la fel ca în cazul cel mai defavorabil.

În anumite cazuri particulare, vom fi interesaţi de timpul mediu de execuţie al unui algoritm. O problema care apare în analiza cazului mediu este aceea că s-ar putea să nu fie prea clar din ce sunt constituite datele de intrare “medii” pentru o anumita problema. Adesea, vom presupune că toate datele de intrare având o dimensiune dată sunt la fel de probabile. În practica, aceasta presupunere poate fi falsă, dar un algoritm aleator poate, uneori, să o forţeze.
Ordinul de complexitate (sau de creştere)
Pentru a uşura analiza procedurii Sorteaza-Prin-Inserţie, am utilizat mai multe presupuneri simplificatoare. În primul rând, am ignorat costul real al fiecărei instrucţiuni, folosind constantele ci pentru a reprezenta aceste costuri. Apoi, am observat că, prin aceste constante, obţinem mai multe detalii decât avem nevoie în mod real: timpul de execuţie în cazul cel mai defavorabil este de forma an2+bn+c pentru anumite constante a, b şi c care depind de costurile ci ale instrucţiunilor. Astfel, am ignorat nu numai costurile reale ale instrucţiunilor, dar şi costurile abstracte ci.
Vom face acum încă o abstractizare simplificatoare. Ceea ce ne interesează de fapt, este rata de creştere sau ordinul de creştere a timpului de execuţie. Consideram, prin urmare, doar termenul dominant al formulei (adică an2) deoarece ceilalţi termeni sunt relativ nesemnificativi pentru valori mari ale lui n. Ignorăm, de asemenea, şi factorul constant c, deoarece, pentru numere foarte mari, factorii constanţi sunt mai puţin semnificativi decât rata de creştere în determinarea eficienţei computaţionale a unor algoritmi. Astfel, vom spune, de exemplu, că sortarea prin inserţie are un timp de execuţie în cazul cel mai defavorabil de Θ(n2) (pronunţat “teta de n pătrat”).
În mod uzual, vom considera un algoritm ca fiind mai eficient decât altul dacă timpul său de execuţie în cazul cel mai defavorabil are un ordin de creştere mai mic. Aceasta evaluare ar putea fi incorecta pentru date de intrare de dimensiune mica, dar în cazul unor date de intrare de dimensiuni foarte mari, un algoritm de tipul Θ(n2), de exemplu, va fi executat în cazul cel mai defavorabil mult mai repede decât unul de tipul Θ(n3).
Aşadar, sortarea prin inserţie are un ordin de complexitate Θ(n2).




  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