1Utilizarea si programareacalculatoarelor

D. Cosma

2

Eficienta algoritmilor

Curs 5

3

Cuprins

1. Cautarea minimului intr-un sir.1. Cautarea minimului intr-un sir.

2. Ordonarea crescatoare a unui sir2. Ordonarea crescatoare a unui sir

3. Concatenarea a 2 siruri ordonate3. Concatenarea a 2 siruri ordonate

4. Strategia divide and conquer4. Strategia divide and conquer

5. Sortarea sirurilor. Buble-sort.5. Sortarea sirurilor. Buble-sort.

4

Exemplu de algoritm (1)

Problema: Cutarea celui mai mic numr ntr-un ir aleator.

639428

Care este cel mai mic?

5Procedura instinctiv de cutare

Se ia primul numr i se compar cu al doilea. Se reine cel mai mic (MIN).

MIN se compar cu al treilea numr i se reine cel mai mic care devine MIN.

MIN se compar cu al patrulea numr i se reine cel mai mic care devine MIN.

...

6

Secvena 1: Cutarea celui mai mic numr

Pas 1: Alege primul numr din ir i presupune c acesta este cel mai mic. (Min = 8)

639428

Pas 2: Compar minimul cu urmtorul numr i alege cel mai mic dintre ele (Min = 2)

639428Pas 3: Compar minimul cu urmtorul numr i alege cel mai mic dintre ele (Min = 2)

639428

7

Secvena 1: Cutarea celui mai mic numr

Pas 4: Compar minimul cu urmtorul numr i alege cel mai mic dintre ele (Min = 2)

639428Pas 5: Compar minimul cu urmtorul numr i alege cel mai mic dintre ele (Min = 2)

639428

Pas 6: Compar minimul cu urmtorul numr i alege cel mai mic dintre ele (Min = 2)

639428

8

Soluie problem 1 Cel mai mic numr este 2. Am parcurs un algoritm de cutare ntr-o

singur secven avnd ase pai!

639428

Are ase pai pentru c erau ase numere n ir?

9Exemplu de algoritm (2)

Problema: Ordonarea cresctoare a unui ir aleator.

639428

Cum le ordonm?10

Procedura instinctiv de sortare Cutarea numrul cel mai mic din ir i

trecerea n prima csu. Reinut c din lista iniial a fost scos

numrul respectiv. Din lista rmas ai cutarea celui mai

mic i trecerea pe poziia doi. Din lista rmas cutarea celui mai mic

numr i trecerea pe poziia trei. ...

11

Secvena 1: Cutarea celui mai mic numr

Pas 1: Alege primul numr din ir i presupune c acesta este cel mai mic. (Min = 8)

639428

Pas 2: Compar minimul cu urmtorul numr i alege cel mai mic dintre ele (Min = 2)

639428Pas 3: Compar minimul cu urmtorul numr i alege cel mai mic dintre ele (Min = 2)

63942812

Secvena 1: Cutarea celui mai mic numr

Pas 4: Compar minimul cu urmtorul numr i alege cel mai mic dintre ele (Min = 2)

639428Pas 5: Compar minimul cu urmtorul numr i alege cel mai mic dintre ele (Min = 2)

639428

Pas 6: Compar minimul cu urmtorul numr i alege cel mai mic dintre ele (Min = 2)

639428

13

Rezultat secvena 1

Secvena 1 s-a terminat n 6 pai. Cel mai mic numr din ir este 2.

639428 2

irul rmne cu 5 numere dintre care vom cuta cel mai mic!

63948

14

Secvena 2: Cutarea celui mai mic numr

Pas 1: Alege primul numr din ir i presupune c acesta este cel mai mic. (Min = 8)

63948

Pas 2: Compar minimul cu urmtorul numr i alege cel mai mic dintre ele (Min = 4)

63948Pas 3: Compar minimul cu urmtorul numr i alege cel mai mic dintre ele (Min = 4)

63948

15

Secvena 2: Cutarea celui mai mic numr

Pas 4: Compar minimul cu urmtorul numr i alege cel mai mic dintre ele (Min = 3)

Pas 5: Compar minimul cu urmtorul numr i alege cel mai mic dintre ele (Min = 3)

63948

63948

16

Rezultat secvena 2

Secvena 2 s-a terminat n 5 pai. Cel mai mic numr din ir este 3.

63948 32

irul rmne cu 4 numere dintre care vom cuta cel mai mic!

6948

17

Secvena 3: Cutarea celui mai mic numr

Pas 1: Alege primul numr din ir i presupune c acesta este cel mai mic. (Min = 8)

6948

Pas 2: Compar minimul cu urmtorul numr i alege cel mai mic dintre ele (Min = 4)

6948Pas 3: Compar minimul cu urmtorul numr i alege cel mai mic dintre ele (Min = 4)

6948

18

Secvena 3: Cutarea celui mai mic numr

Pas 4: Compar minimul cu urmtorul numr i alege cel mai mic dintre ele (Min = 4)

6948

19

Rezultat secvena 3

Secvena 3 s-a terminat n 4 pai. Cel mai mic numr din ir este 4.

6948 432

irul rmne cu 3 numere dintre care vom cuta cel mai mic!

698

20

Secvena 4: Cutarea celui mai mic numr

Pas 1: Alege primul numr din ir i presupune c acesta este cel mai mic. (Min = 8)

698

Pas 2: Compar minimul cu urmtorul numr i alege cel mai mic dintre ele (Min = 8)

Pas 3: Compar minimul cu urmtorul numr i alege cel mai mic dintre ele (Min = 6)

698

698

21

Rezultat secvena 4

Secvena 4 s-a terminat n 3 pai. Cel mai mic numr din ir este 6.

698 6432

irul rmne cu 2 numere dintre care vom cuta cel mai mic!

98

22

Secvena 5: Cutarea celui mai mic numr

Pas 1: Alege primul numr din ir i presupune c acesta este cel mai mic. (Min = 8)

98

Pas 2: Compar minimul cu urmtorul numr i alege cel mai mic dintre ele (Min = 8)

98

23

Rezultat secvena 5

Secvena 5 s-a terminat n 2 pai. Cel mai mic numr din ir este 8.

98 86432

irul rmne cu 1 numr.

9

24

Secvena 6: Cutarea celui mai mic numr

Pas 1: Alege primul numr din ir i presupune c acesta este cel mai mic. (Min = 9)

9

Secvena 6 s-a terminat ntr-un pas. Cel mai mic numr din ir este 9.

9 986432

Rezultat secvena 6

25

Concluzii rezolvare (1)

Rezolvarea s-a realizat n ase secvene. Prima secven a avut ase pai, al doilea cinci pai, iar ultimul un singur pas.

Numrul pailor nu depinde de ordinea iniial a numerelor din irul original.

Numrul total de pai de rezolvare a problemei este 20 pentru ase elemente din ir.

26

Concluzii rezolvare (2) Generaliznd pentru n elemente din ir

numrul de pai se poate calcula.

Orice algoritm care rezolv aceast problem din mai puini pai este un algoritm mai eficient !!!

= n1

nN

Ordonarea simpla a unui sir de numere

0

20000

40000

60000

80000

100000

0 100 200 300 400Numere in sir (buc)

N

u

m

a

r

d

e

p

a

s

i

(

b

u

c

)

27

Exemplu de algoritm (3)

Problema: Concatenarea a dou iruri ordonate ntr-un singur ir ordonat.

201372

121191

28

I. Fr a ine cont de ordonarea existent

Practic metoda din Problema 1. Cautm cel mai mic dintre toate cele opt

numere (nu intereseaz c ele sunt pe iruri). l punem pe acesta pe prima poziie n noul ir. Din ce a rmas cautm cel mai mic numr i l

punem pe poziia doi al noului ir. Din ce a rmas cautm cel mai mic numr i l

punem pe poziia trei al noului ir. ...

29

II. innd cont de ordonarea existent

tiind c cele dou iruri sunt deja ordonate comparm primele numere din iruri.

Pe cel mai mic dintre cele dou l trecem n prima csu a noului ir.

Numrul care l-am trecut n noul ir dispare din irul doi iniial.

Comparm acum primul numr al celor dou iruri rmase (n al doilea unu a disprut deja) i cel mai mic dintre ele l trecem pe poziia doi din noul ir.

... 30

Sec. 1: Identificarea celui mai mic numr

201372

121191

1

Pas 1: Comparm primele dou numere (Min = 1)

Pas 2: Eliminm cel trecut n irul concatenat201372

12119

31

Sec. 2: Identificarea celui mai mic numr

201372

12119

21

Pas 1: Comparm primele dou numere (Min = 2)

Pas 2: Eliminm cel trecut n irul concatenat20137

12119

32

Sec. 3: Identificarea celui mai mic numr

20137

12119

721

Pas 1: Comparm primele dou numere (Min = 7)

Pas 2: Eliminm cel trecut n irul concatenat2013

12119

33

Sec. 3: Identificarea celui mai mic numr

2013

12119

9721

Pas 1: Comparm primele dou numere (Min = 9)

Pas 2: Eliminm cel trecut n irul concatenat2013

1211

34

Sec. 4: Identificarea celui mai mic numr

2013

1211

9721 11

Pas 1: Comparm primele dou numere (Min = 11)

Pas 2: Eliminm cel trecut n irul concatenat2013

12

35

Sec. 5: Identificarea celui mai mic numr

2013

12

9721 1211

Pas 1: Comparm primele dou numere (Min = 12)

Pas 2: Eliminm cel trecut n irul concatenat2013

36

Sec. 6: Identificarea celui mai mic numr

2013

9721 131211

Pas 1: Pentru c nu mai exist numr pe irul doi urmtorul de pe irul unu este minim. (Min = 13)

Pas 2: Eliminm cel trecut n irul concatenat20

37

Sec. 6: Identificarea celui mai mic numr

20

9721 20131211

Pas 1: Pentru c nu mai exist numr pe irul doi urmtorul de pe irul unu este minim. (Min = 20)

Pas 2: Eliminm cel trecut n irul concatenat

38

Comparaia celor doi algoritmi

Primul algoritm are nevoie de 36 pai. Al doilea algoritm are nevoie de 16 pai

(de dou ori numrul total de numere). Deci al doilea algoritm este mai eficient

dect primul. Putem discuta de eficiena unui algoritm !!!!

39

Strategia divide and conquer (1)

Exemplul anterior poate s furnizeze o idee. Dac avem de ordonat un ir de 8 numere cu

metoda simpl (Problema 1) avem nevoie de 36 pai.

Dac mprim irul n dou iruri de cte 4 numere, ca s ordonm irurile astfelobtinute avem nevoie de 10+10=20 pai. Plus pentru concatenat nc 16 pai. n total 36 pai.

Nu pare s fie diferen!!!40

Strategia divide and conquer (2)

La un ir de 4.000 de numere. Prima metod are nevoie de 8.002.000

(adic opt milioane) de pai s ordoneze un ir.

41

Strategia divide and conquer (3)

4000

500 500 500 500

Ordonare 8x125.250=1.002.000

500 500 500 500

1000 100010001000 4x1.000=4.000 pai

20002000 2x2.000=4.000 pai4000 1x4.000=4.000 pai

42

Strategia divide and conquer (4)

Dac mprim irul n opt iruri de cte 500 numere, pentru ordonarea irurilor avem nevoie de 8x125.250=1.002.000 (un milion) de pai.

Pentru concatenarea a cte dou iruri de 500 n iruri de 1000 de numere sunt necesare 4x1.000=4.000pai.

Pentru concatenarea a dou de 1000 n una de 2000 ne sunt necesare 2x2.000=4.000 pai.

Pentru concatenarea celor dou de 2000 n cel final de 4000 de numere ordonate, 4.000 pai.

Adic n total 1.002.000+4.000+4.000+4.000=1.014.000 pai.

DE OPT ORI MAI PUIN!!

43

Exemplu de algoritm (4)

Problema: Ordonarea cresctoare a unui ir aleator.

639428

Cum ordonm?44

Metoda bulelor (Bouble-sort)

S parcurgem numerele. Comparm cte dou numere consecutive. Dac ele sunt n ordinea dorit (primul este

mai mic) nu facem cu ele nimic. Dac nu sunt n ordinea dorit (primul este mai

mare) schimbm ordinea lor. Repetm parcurgerea de la nceput de attea

ori pn toate numerele ajung n ordine cresctoare.

45

Sec 1: Schimbm toate perechilePas 1: Comparm primele dou numere (trebuie

schimbate)

639428Reinem primul numr

Schimbm al doilea cu primul

Rezult

639428

639428

63948246

Sec 1: Schimbm toate perechilePas 2: Comparm urmtoarea pereche (trebuie

schimbate)

639482Reinem primul numr

Schimbm al doilea cu primul

Rezult

639428

639428

639842

47

Sec 1: Schimbm toate perechile

Pas 3: Comparm urmtoarea pereche (nu trebuie schimbate)

639842

48

Sec 1: Schimbm toate perechilePas 4: Comparm urmtoarea pereche (trebuie

schimbate)

639842Reinem primul numr

Schimbm al doilea cu primul

Rezult

638429

638429

693842

49

Sec 1: Schimbm toate perechilePas 5: Comparm urmtoarea pereche (trebuie

schimbate)

693842Reinem primul numr

Schimbm al doilea cu primul

Rezult

638429

638429

96384250

Rezultat secvena 1

Dup secvena 1 avem irul:

963842

51

Sec 2: Schimbm toate perechilePas 1: Comparm primele dou numere (nu trebuie schimbate)

963842

Pas 2: Comparm primele dou numere (nu trebuie schimbate)963842

52

Sec 2: Schimbm toate perechilePas 3: Comparm urmtoarele dou numere (trebuie

schimbate)

963842Reinem primul numr

Schimbm al doilea cu primul

Rezult

963428

963428

968342

53

Sec 2: Schimbm toate perechilePas 4: Comparm urmtoarele dou numere (trebuie

schimbate)

968342Reinem primul numr

Schimbm al doilea cu primul

Rezult

963428

963428

98634254

Sec 2: Schimbm toate perechilePas 5: Comparm urmtoarele dou numere (nu trebuie

schimbate)

986342

Dup secvena 2 avem irul:986342

Rezultat secvena 2

55

Sec 3: Schimbm toate perechile

Pas 1: Comparm primele dou numere (nu trebuie schimbate)

986342

56

Sec 3: Schimbm toate perechilePas 2: Comparm urmtoarele dou numere (nu trebuie

schimbate)

986342Reinem primul numr

Schimbm al doilea cu primul

Rezult

986324

986324

986432

57

Sec 3: Schimbm toate perechilePas 3: Comparm urmtoarele dou numere (nu trebuie

schimbate)

986432

Pas 4: Comparm urmtoarele dou numere (nu trebuie schimbate)

986432

Pas 5: Comparm urmtoarele dou numere (nu trebuie schimbate)

98643258

Rezultat secvena 3

Dup secvena 3 avem irul:

986432

tim dac irul este ordonat? NU!!!

59

Sec 4: Schimbm toate perechilePas 1: Comparm primele dou numere (nu trebuie schimbate)

986432Pas 2: Comparm urmtoarele dou numere (nu trebuie

schimbate)

986432

Pas 3: Comparm urmtoarele dou numere (nu trebuie schimbate)

98643260

Sec 4: Schimbm toate perechilePas 4: Comparm primele dou numere (nu trebuie schimbate)

986432Pas 5: Comparm urmtoarele dou numere (nu trebuie

schimbate)

986432

Am parcurs o secven n care nu am fcut nici o schimbare de poziie!

Ce nseamn acest lucru? nseamn c irul a fost deja ordonat!!!

61

Performana algoritmului (1) Numrul de parcurgeri (i de pai) depinde de

ordinea iniial a numerelor. Dac numerele au fost n ordine cresctoare

o singur parcurgere n NR-1 pai este suficient.

Situaia cea mai defavorabil apare cnd numerele au fost aranjate descresctor. n acest caz avem nevoie de cei mai muli pai.

Putem discuta de eficiena unui algoritm !!!! Dar eficiena nu este constant, ci depinde de ordinea iniial a datelor de intrare.

62

Performana algoritmului (2)

Numar parcurgeri in metoda Bulelor

0

500

1000

1500

2000

2500

3000

0 10 20 30 40 50

Min(Deja sortate)

Max(Sortate invers)1nNmin =

1)(nnNmax =

63

Concluzie

Este esenial ca la dezvoltarea unui program de calcul (mai ales la unu intensiv din punct de vedere matematic) s studiem eficiena algoritmului utilizat!!!

64

http://cemsig.ceft.utt.ro/cursuri/

Utilizarea si programarea calculatoarelor