LICEUL TEORETIC “NEAGOE BASARAB”-OLTENITA

Lucrare de atestat

ELEV: Pietrusel Raluca-Florentina

PROFESOR INDRUMATOR:CHIŢU LUCIAN

MAI-2014

Cuprins

1. Algoritmul de căutare...................................................................4

1.1. Căutare binară.............................................................................................................4

1.2. Arbori binari de căutare………………………………………………………9

Bibliografie………………………………………………………..13

Introducere

Căutarea şi sortarea sunt două dintre cele mai des întâlnite subprobleme în programare. Ele constituie o parte esenţială din numeroasele procese de prelucrare a datelor. Operaţiile de căutare şi sortare sunt executate frecvent de către oameni în viaţa de zi cu zi, ca de exemplu căutarea unui cuvânt în dicţionar sau căutarea unui număr în cartea de telefon.

Căutarea este mult simplificată dacă datele în care efectuăm această operaţie sunt sortate (ordonate, aranjate) într-o anumită ordine (cuvintele în ordine alfabetică, numerele în ordine crescătoare sau descrescătoare).

Sortarea este o metoda  (un algoritm), prin intermediul careia se poate ordona o anumita clasa de obiecte concrete sau abstracte, dupa unul sau mai multe criterii impuse iar cautarea este o metoda, prin intermediul careia, se poate cauta, dupa

criterii precizate, pentru regasire un anumit obiect concret sau abstract intr-o multime ordonata sau nu de obiecte concrete sau abstracte

Ca exemple se pot da :-          sortarea (ordonarea) crescatoare sau descrescatoare a unui sir de

numere reale si cautarea unui numar sau a mai multor numere in acest sir de numere

-          sortarea unei liste de persoane in ordinea alfabetica a numelor si prenumelor acestora si cautarea unei persoane sau a mai multor persoane cu anumite caracteristici precizate.

-          ordonarea unei liste de persoane dupa importanta muncii lor si cautarea unor persoane dupa criterii precizate.

-          ordonarea unei liste de persoane dupa anumite criterii preferentiale si cautarea in aceasta lista.etc.

Caracteristici ale sortariiSortare stabila se numeste acea sortare care in urma executarii sale face ca

inregistrarile cu chei egale sa isi pastreze pozitiile relative.Sortare interna este aceea sortare care pastreaza, pe tot parcursul executarii

sale toate inregistrarile in memoria interna a calculatorului.Sortare externa este aceea sortare care, din cauza numarului mare de

inregistrari, nu pastreaza, pe tot parcursul executarii sale toate inregistrarile in memoria interna a calculatorului si foloseste pentru memorare si spatii pe memoriile externe (discuri magnetice, flexibile, optice, etc.)..                Pentru simplificarea prezentarii problemelor de sortare se vor aplica principalii algoritmi de sortare asupra unor vectori care contin cheile de sortare iar pentru ca implementarea lor in C sa fie cat mai fireasca se va considera ca primul element al oricarui vector ocupa pozitia zero si are, in consecinta, indexul zero.

Sortarea datelor consta în rearanjarea colecţiei de date astfel încat un câmp al elementelor colecţiei să respecte o anumită ordine. De exemplu în cartea de telefon fiecare element (abonat) are un câmp de nume, unul de adresă şi unul pentru numărul de telefon. Colecţia aceasta respectă ordinea alfabetică după câmpul de nume.

Dacă datele pe care dorim să le ordonăm, adică să le sortăm, sunt în memoria internă, atunci procesul de rearanjare a colecţiei îl vom numi sortare internă.

Fiecare element al colecţiei de date se numeşte articol iar acesta la randul sau este compus din unul sau mai multe componente. O cheie C este asociată fiecărui articol şi este de obicei unul dintre componente. Spunem că o colecţie de n

articole este ordonată crescator după cheia C dacă )()( jCiC pentru nji 1 ,

iar dacă )()( jCiC atunci şirul este ordonat descrescător.

1. Algoritmul de căutare

1.1. Căutare binară

Algoritmul de căutare binară este un algoritm de căutare folosit pentru a găsi un element într-o listă ordonată (tablou unidimensional/vector). Algoritmul funcționează pe baza tehnicii divide et impera. Valoarea căutată este comparată cu cea a elementului din mijlocul listei. Dacă e egală cu cea a acelui element, algoritmul se termină. Dacă e mai mare decât acea valoare, algoritmul se reia, de la mijlocul listei până la sfârșit, iar dacă e mai mică, algoritmul se reia pentru elementele de la începutul listei până la mijloc. Întrucât la fiecare pas cardinalul mulțimii de elemente în care se efectuează căutarea se înjumătățește, algoritmul are complexitate logaritmică.

Se dau un vector naaaA ,...,, 21 şi o valoare x . Se cere să se determine dacă x se află printre elementele vectorului A .

Dacă A este un vector oarecare, atunci trebuie parcurse secvenţial elementele vectorului. Această modalitate necesită cel mult n comparaţii în cazul unei căutări

cu succes şi exact n comparaţii în cazul căutării fără succes. Numărul mediu de

comparaţii în cazul unei căutări cu succes este: 2

1...21

n

n

n

Dacă A are elementele în ordine crescătoare - situaţie des întâlnită în practică – atunci există posibilitatea de a efectua o căutare mai performantă. Deci în

continuare vom lucra în ipoteza n21 ... aaa .Vom folosi metoda „Divide et impera” , începând prin a compara x cu

elementul „din mijloc”, adică cu ia unde

2

1ni

. Dacă xai , atunci căutarea

se încheie cu succes. În caz contrar, vom căuta x în secvenţa }...{ 11 iaa dacă iax

sau în secvenţa },...,{ n1 aai dacă iax . Vom presupune că dorim ca soluţia să fie exprimată sub forma:

(1)}1,,...,1{,),0(

},...,1{,),1(),(

1

nniaxadacăi

niaxdacăiis

ii

i

unde 10 , naa . Atunci metoda descrisă este corectată în procedura araCautareBin , în care p şi u sunt primul, respectiv ultimul indice din secvenţa

curentă în care se află x .

end

returnwrite

repeat

endcase

returnwrite

case

while

array

procedure

;,;0

1:

;,;:

1:

2

;1

)(

),,(

pss

iuxa

isisxa

ipxa

upi

up

nup

xA

xnAaraCautareBin

i

i

i

Singura explicaţie necesară este legată de cazul în care căutarea se termină fără succes. Observăm că situaţia up este precedată de situaţia în care valorile lui p

şi u sunt pşi u cu iup . Dacă iax avem pp deci pax ; dacă iax

atunci 11 ipp deci pi aax 1 . Rezultă că valoarea p tipărită este corectă.

Analiza timpui de lucruÎn acest scop vom încerca să determinăm numărul de comparaţii care au loc

între x şi ia . Acest număr este cel care va dicta eficacitatea algoritmului deoarece,

pe de o parte, elementele }{ ia pot fi matrici, polinoame etc., iar pe de altă parte numărul de atribuiri şi numărul de comparaţii impuse de execuţia ciclului while diferă cu o unitate de numărul căutat. Un prim rezulatat este următorul:

Pentru kk n 22 1 , în cazul unei căutări cu succes se fac cel mult k

comparaţii, iar în cazul unei căutări fără succes se fac 1k sau k comparaţii.Înainte de a face demonstraţia, vom ataşa algoritmului un arbore binar astfel: pentru 1n arborele se reduce la (1), pentru 0n arborele este vid

pentru o valoare n oarecare arborele are forma din Fig.1, unde

2

1ni

, S este arborele corespunzător lui 1i , iar D este arborele corespunzător lui

in , în care numerele vârfurilor sunt mărite cu i .

Astfel pentru 5n obţinem arborele din Fig.2Numele de căutare binară se datorează tocmai acestui arbore binar ataşat.Pentru a demonstra propoziţia de mai sus este suficient să arătăm că vârfurile

care au mai puţin de 2 descendenţi se află pe nivelele 1k şi k , ceea ce se poate arăta prin inducţie după n.

Ne interesează să nu ne mărginim la studiul cazului cel mai defavorabil, ci să studiem valoarea medie a numărului de comparaţii. În acest scop este convenabil să transformăm arborele binar construit ca mai sus într-un arbore binar strict astfel: fiecărui vârf i care are mai puţin de doi descendenţi îi adăugăm un descendent stâng notat (dacă i nu are descendent stâng) şi un descendent drept notat

i

S D

Fig.1

3

1

2

4

5

Fig.2

i

i+1

(dacă i nu are descendent drept). Conform notaţiei, vom numi aceste vârfuri (care sunt vârfuri terminale în arbore) vârfuri pătratice. Pentru exemplul considerat mai sus, obţinem arborele binar strict din Fig.3.

Pentru a determina numărul p al vârfurilor pătratice, vom număra muchiile

arborelui în două moduri. Arborele având pn vârfuri, are 1 pn muchii. Pe de altă parte, ţinând cont că din fiecare vârf circular (intern) diverg două muchii,

arborele are n2 muchii. Egalând obţinem că 1np .Este evident că vârfurile pătratice pot apărea numai pe nivelele k şi 1k .Să observăm că vârfurile pătratice corespund intervalelor dintre elementele

vectorului. Mai precis, vârful i corespunde intervalului ),( 1 ii aa . Aceasta devine şi mai clar dacă observăm că vârfurile arborelui binar sunt în ordinea următoare:

Se vede că oricare arbore binar cu n vârfuri corespunde unei metode de

căutare binară într-un vector ),...,( 1 naaA având elementele ordonate crescător. Într-adevăr, completăm arborele la un arbore binar strict prin adăugarea de vârfuri pătratice şi numerotăm în inordine vârfurile arborelui obţinut cu

.

Un arbore obţinut în acest mod se numeşte arbore de căutare.

Exemplu. În Fig.4 este ilustrată o astfel de corespondenţă:

3

1

1

3

2

2

4

4

5

5

6

Fig. 3

1 1 2 2 ... n n n+1

1 1 2 2 ... n n n+1

Întrebarea pe care ne-o punem este dacă arborele ataşat algoritmului araCautareBin este „optim” în privinţa numărului mediu de comparaţii printre toţi

arborii binari stricţi construiţi ca mai sus.Este momentul de a defini numărul mediu de comparaţii. Vom presupune că

probabilităţile cu care se caută numerele naa ,...,1 sunt egale. De asemenea vom

presupune că intervalele ) ,(a ),a ,(a, ... ),a ,(a ),a ,(- nn1-n211 sunt egal probabile.Numărul de comparaţii necesar în cazul unei căutări cu succes este egal cu

nivelul vârfului respectiv (reamintim că rădăcina se află pe nivelul 1), adică este egal cu distanţa vârfului respectiv faţă de rădăcină plus unu. Dacă definim lungimea drumului intern ca fiind suma distanţelor faţă de rădăcină a tuturor

vârfurilor interne şi o notăm cu nI , atunci numărul mediu de comparaţii nC în

cazul unei căutări cu succes va fi dat de n

nIC n

n

.Numărul de comparaţii în cazul unei comparări fără succes este egal cu

distanţa faţă de rădăcină a vârfului pătratic corespunzător. Definind lungimea

drumului extern nE ca fiind suma distanţelor faţă de rădăcină a tuturor vârfurilor

externe, atunci numărul mediu de comparaţii nC în cazul unei căutări fără succes

este dat de 1

n

EC n

n.

Propoziţie.nIE nn 2

Vom face demonstraţia prin inducţie după n. Pentru 1n , arborele are forma din Fig.5.

1

1 3

6

6 7

2 4

2 3 4 5

Fig.4

5

0,2 11 IE , şi deci 111 IE

Presupunând 111 IE pentru toţi arborii binari stricţi cu n vârfuri interne, să considerăm un arbore cu 1n vârfuri interne. Punem în evidenţă un vârf intern pentru care ambii descendenţi sunt vârfuri pătratice; fie k nivelul pe care se află acest vârf. Eliminând cele două vârfuri terminale (pătratice) şi înlocuind vârful intern respectiv cu unul pătratic obţinem un arbore binar cu n vârfuri interne.

Conform ipotezei de inducţie, 111 IE . Eliminarea vârfului intern face ca )1(1 kII nn . Eliminarea a două vârfuri pătratice de pe nivelul 1k şi

adăugarea unui vârf pătratic pe nivelul k face ca 121 kkEE nn . Din nIE nn 2 rezultă că:

nkIkE nn 211 11 , adică )1(211 nIE nn (ceea ce trebuia demontrat)

Pe baza acestui rezultat minimizarea lui nC se face concomitent cu cea a lui nC

deoarece n

nCn

n

nnE

n

nIC nnn

n

)1(2

adică 1

1

nn Cn

nC

. Rezultă că

valorile nC , nC sunt minime dacă nE este minimă.

Propoziţie. nE minimă vârfurile terminale apar pe cel mult două nivele consecutive.

Să considerăm un arbore cu n vârfuri interne pentru care nE are valoare minimă. Fie m şi M cel mai mic, respectiv, cel mai mare nivel pe care apar vârfurile terminale. Să presupunem prin absurd că 2Mm . Fie atunci a un vârf terminal de pe nivelul m şi fie b un vârf de pe nivelul M . Vom construi un nou

arbore în care dc, vor deveni descendenţii vârfului a (Fig.6).

1

1 2

fig.5

Fie nE lungimea drumului extern pentru noul arbore. Ea se obţine din nE ţinând cont că s-au eliminat drumurile de la rădăcină la ca, şi d şi s-au adăugat

drumurile de la rădăcină la dcb ,, adică: nnnnn EmMEmMEmMMmEE 12122)1(21

ceea ce contrazice faptul că arborele de la care am plecat are valoarea nE minimă.Reciproc, să considerăm un arbore binar strict în care vârfurile terminale

apar pe cel mult două nivele consecutive şi fie nE lungimea drumului său extern.

Fie nE valoarea minimă a drumului extern, valoare realizată pentru un arbore . Dacă în vârfurile terminale nu apar pe cel mult două nivele consecutive, atunci

valoarea nE poate fi îmbunătăţită aşa cum s-a arătat mai sus; contradicţie. Dacă în vârfurile terminale apar pe cel mult două nivele consecutive k şi 1k , atunci

pe nivelul k apar atât în cât şi în 12 k vârfuri, iar pe nivelul 1k apare în

arbori acelaşi număr 1212 kn de vârfuri. Ca urmare nn EE .

Concluzie. Algoritmul araCautareBin este optim în clasa algoritmilor de căutare reprezentabili pe arbori binari.

Afirmaţia rezultă imediat din propoziţia anterioară şi din faptul că arborele corespunzător algoritmului araCautareBin are vârfurile terminale situate pe cel mult două nivele consecutive.

1.2. Arbori binari de căutareReamintim că un arbore binar de căutare este un arbore binar strict, etichetat, în

care cele n vârfuri neterminale (interne, circulare) sunt numerotate conform

inordinii şi în care pentru orice vârf i , valoarea (eticheta) ia asociată lui este mai mare decât cea asociată vârfurilor care îl preced şi mai mică decât a vârfurilor care îi succed în inordine în cadrul subarborelui care îl admite ca rădăcină. Cele 1n

vârfuri terminale (pătratice) sunt etichetate cu 1,...,2,1 n şi corespund în ordine

intervalelor 121 ,...,, nIII unde:

101 ;);,( nkkk aaaaI

m

M

m

m+1

M-1

a a

b

b

c

c

d

d

Fig.6

M-1

Tot în paragraful precedent s-a făcut o analiză completă a problemei căutării

unui element x în vectorul ),...,( 1 naa , folosind strategii reprezentabile prin astfel

de arbori, în ipoteza că valorile naa ,...,1 , precum şi intervalele 11 ,..., nII sunt egal probabile (apar cu aceeaşi frecvenţă). În acest paragraf vom generaliza problema pentru cazul unor probabilităţi oarecare date. Mai precis vom presupune că

probabilitatea ca x să fie egal cu ka este kp , iar probabilitatea ca kIx este kp .

Bineînţeles este satisfăcută relaţia: 1

1

11

n

ii

n

ii qp

Să observăm că în cazul unei căutări cu succes terminate cu kax , numărul

necesar de comparaţii este egal cu nivelul vârfului k , notat prin kniv . În cazul unei

căutări fără succes, terminate deci într-un vârf pătratic }1,...,1{ nk , numărul de

comparaţii este egal cu 1kniv . Atunci definim în mod natural pentru un arbore de

căutare binar A „măsură” )(A a numărului mediu de comparaţii (costul arborelui A ) prin:

n

k

n

kkkkk nivqnivpA

1

1

1

)1()(

şi căutăm arborele binar de căutare optim, adică acel arbore de căutare binar

pentru care valoarea )(A este minimă.Vom rezolva această problemă prin metoda programării dinamice. Prima

decizie constă în a determina vârful k ce trebuie ales ca rădăcină. Să observăm că este satisfăcut principiul optimalităţii, deoarece dacă A este un arbore de căutare

optim pentru },...,{ 1 naa având rădăcina k , atunci subarborii săi stâng şi drept sunt

arbori de căutare optimali pentru },...,{ 11 kaa , respectiv },...,{ 1 nk aa .

Pentru a putea scrie relaţiile de recurenţă, vom nota prin ),( jiC costul arborelui

de căutare pentru secvenţa },...,,{ 11 jii aaa , în care intervin probabilităţile jjii qppq ,,...,, 1 .

Este valabilă relaţia:

)2(...

1,1...,11,1

111

1211

knnkk

kk

pqppq

nkCqpqpqkCnC

deoarece prin „coborârea” arborilor pentru {a1,…,ak-1}, {ak+1,…,an} cu un nivel şi considerarea în plus a rădăcinii, costul se măreşte cu knnkkkk pqppqqppq 111111 ......

Să introducem notaţia:jjjiiij qpqpqr 11 ...

Se verifică imediat că:

)3(}1,...,1,{,1

iij

jkkikij

qr

jiikrprr

Atunci relaţia (2) devine: )2(1,1,11,1 1,1 nrnkCkCnC

relaţia în care, reamintim, s-a presupus că rădăcina este k . Dacă nu ştim acest lucru este evident că:

)4(}1,1,1{min1,1 1,11

n

nkrnkCkCnC

Generalizând, obţinem relaţia de recurenţă )5(},1,{min,

1ij

jkrjkCkiCjiC

cu condiţiile iniţiale:

)6(0),( jiC

corespunzătoare faptului ca ),( jiC reprezintă costul arborelui pentru secvenţa vidă.

Recapitulând, ne interesează să determinăm valoarea )1,1( nC ştiind că

}),1(),({min),(

}1,...,2,1{,,0),(

ijjki

iij

rjkCkiCjiC

niqrjiC

unde )7(11, jijiij qprr

(această formulă a lui ijr se obţine luând 1 jk în (3)).Vom proceda analog ca în problema determinării ordinii de înmulţire optimă a

matricilor, adică vom calcula succesiv ijr , ijC , pentru ij luând succesiv valorile n,...,2,1 . În particular în ),( jiC unde ji vom păstra valoarea k pentru care se

ralizează minimul în relaţia (5). Ca rezultat obţinem procedura ara1CautareBin .

end

repeat

for

for

repeat

for

float

procedure

][),(

),1(),({min),(

;

:1,1

/*/*,1

0),(;

1,1

)1,1(),1,1(),1(),(

),,,,(1

1,

susmaideminimulobtinesecarepentrukluivaloareajiC

rjkckiCjiC

qrrmij

mni

ijdiferentaaintreprezmnm

iiCqr

ni

nnrnnCnqnp

rCqpnaraCautareBin

ijjki

jjiij

iu

Mai rămâne de construit efectiv arborele binar de căutare optim. Vom construi mai întâi un arbore binar strict astfel:

rădăcina este etichetată cu )1,1( n

dacă un vârf este etichetat cu ),( ji unde ji , atunci descendenţii săi vor fi

etichetaţi cu ),( ki şi ),1( jk , unde );,( jik

vârfurile terminale sunt etichetate cu ),( ii

Plecând de la acest arbore, un arbore de căutare optim se obţine imediat,

schimbând etichetele ),( ji cu ji în k , unde ),( jiCk , iar etichetele ),( ii în Analiza eficacităţii algoritmului se face în acelaşi mod ca în problema

determinării ordinii optime de înmulţire a unui şir de matrici.

Bibliografie

[1] Leon Livovschi, Horia Georgescu – „Sinteza şi analiza algoritmilor”, Editura Ştiintifică Bucureşti, 1986

[2] Robert Sedgewick – „Algorithms”, Addison-Wesley Publishing, Reading, Massachusetts London, 1983

[3] Robert Sedgewick – „Algorithms in Java: Parts 1-4, Third Edition”, Addison Wesley Publishing, London, 2002

[4] Alan Parker – „Algorithms and Data Structures in C++”, CRC Press, 1993

[5] Douglas Baldwin, Greg W. Scragg – „Algorithms and Data Structures: The Science of Computing”, Charles River Media, 2004

[6] Niklaus Wirth – „Algorithms and Data Structures”, Prentice Hall, 1985[7] Robert Lafore – „Data Structures & Algorithms in Java”, Sams, 1998

i

[8] Alfred V. Aho, Jeffrey D. Ullman, John E. Hopcroft – „Data Structures and Algorithms”, Addison-Weslez, 1982

[9] Peter Drake – „Data Structures and Algorithms in Java”, Prentice Hall, 2005

[10] Mark Allen Weiss – „Data Structures And Problem Solving Uusing C++, Second Edition”, Addison-Wesley, 2003

[11] Jimm Keogh, Ken Davison – „Data Structures Demystified”, McGraw, Osborne, 2004

[12] Sandra Andersen – „Data Structures in Java”, Jones And Bartlett Publishiers, Sudbury, Massachusetts, 2002

[13] Thomas H Cormen, Charles E Leiserson, Ronald L Rivest – „Introduction to Algorithms, Second Edition”, Prentice Hall, Massachusetts London, 2001

[14] Robert Lafore – „Sams Teach Yourself Data Structures and Algorithms in 24 Hours”, Sams, Indianopolis, Indiana, 1999