Capitolul 5

Sortare i cutare

5.1 Metoda de sortare prin generare i testare Utiliznd structura de control a limbajului Prolog, se poate realiza foarte simplu sortarea unei secvene de elemente, folosind metoda generare i testare. Aceast metod de rezolvare a problemelor, utilizat n inteligena artificial, dar puin potrivit pentru o sortare, are la baz urmtoarea idee: o component generatoare construiete soluii candidate i o a doua component, componenta de testare, verific fiecare soluie candidat pentru a vedea dac este sau nu o soluie a problemei. n acest fel, se pot obine fie toate soluiile problemei, fie una singur. Aceast metod poate fi exprimat succint n Prolog astfel:

gaseste(Solutie) :- genereaza(Solutie), testeaza(Solutie).

Metoda este n general ineficient, chiar n cazul problemelor tipice de inteligen artificial care necesit un proces de cutare a soluiei. Metoda este extrem de ineficient n cazul rezolvrii problemelor de sortare, pentru care exist algoritmi eficieni de rezolvare. Cu toate acestea, se prezint n continuare soluia de sortare n ordine cresctoare a unei liste de ntregi prin metoda generare i testare ca exerciiu Prolog.

% sortare(+Lista, -ListaSortata) - sortare prin metoda generare si testare sortare(Lista, ListaSortata) :- permut(Lista, ListaSortata), ordonata(ListaSortata).

% permut(+Lista, -PermutareLista) permut([], []). permut(Lista, [Prim | Rest]) :- elim(Prim, Lista, L), permut(L, Rest).

% elim(+Element, +Lista, -ListaMinusElement) elim(Elem, [Elem | Rest], Rest). elim(Elem, [Prim | Rest], [Prim | L]) :- elim(Elem, Rest, L).

88 CAPITOLUL 5

% rel(+X, +Y) - verifica daca X si Y respecta relatia de ordine rel rel(X, Y) :- X =< Y.

% ordonata(+Lista) - verifica daca Lista este sortata dupa relatia rel(X, Y) ordonata([ _ ]). ordonata([Prim, Secund | Rest]) :- rel(Prim, Secund), ordonata([Secund | Rest]).

Se observ c sortarea se face prin generarea permutrilor elementelor din list i verificarea dac o permutare generat este o secven sortat. Componenta generatoare este predicatul permut(Lista, ListaSortata) i componenta de testare este predicatul ordonata(Lista). Dei implementarea este simpl, exploatnd facilitile nedeterministe ale limbajului Prolog, ea este foarte ineficient.

5.2 Metoda de sortare prin inserie Sortarea prin inserie a unei liste de elemente L = [H | T] se poate exprima recursiv astfel: se sorteaz mai nti lista T n TS i apoi se insereaz elementul H n lista TS, acolo unde i este locul conform relaiei de ordine rel(X, Y). % isort1(+Lista, -ListaSortata) - sortare prin insertie, varianta 1 isort1([], []) :- !. isort1([H | T], LS) :- isort1(T, TS), insereaza(H, TS, LS).

% rel(+X, +Y) - verifica daca X si Y respecta relatia de ordine rel(X, Y) :- X =< Y.

% insereaza(+Element, +Lista, -ListaPlusElement) - % insereaza Element in Lista sortata astfel incat % ListaPlusElement sa ramana sortata insereaza(Elem, [], [Elem]). insereaza(Elem, [Prim | Rest], [Elem, Prim | Rest]) :- rel(Elem, Prim), !. insereaza(Elem, [Prim | Rest], [Prim | L]) :- not(rel(Elem, Prim)), insereaza(Elem, Rest, L). Predicatul cut folosit n definirea predicatului insereaza este un cut verde. Se poate rescrie predicatul insereaza folosind un cut rou astfel:

insereaza(Elem, [], [Elem]). insereaza(Elem, [Prim | Rest], [Elem, Prim | Rest]) :- rel(Elem, Prim), !. insereaza(Elem, [Prim | Rest], [Prim | L]) :- insereaza(Elem, Rest, L).

SORTARE I CUTARE 89

A doua variant de sortare prin inserie este urmtoarea: Lista poate fi privit la un moment dat ca L' = PS::PN, unde PS este partea sortat i PN = [X | T] este partea nesortat. Se ia primul element X din PN i se insereaz n PS. Algoritmul pornete cu PS = [] i PN = L, i se oprete cnd PN = [], n acel moment PS fiind chiar lista sortat. Se observa c PS are rol de acumulator, rezultatul final fiind ntors n al treilea parametru (construcia rezultatului se face pe apelul recursiv). % isort2(+Lista, -ListaSortata) - sortare prin insertie, varianta 2 isort2(L, LS) :- isort2( [], L, LS). isort2(PS, [], PS). isort2(PS, [X | T], LS) :- insereaza(X, PS, PS1), isort2(PS1, T, LS).

5.3 Metoda de sortare rapid Sortarea rapid (quicksort) a unei liste de elemente L se definete recursiv astfel:

1. Elimin un element Pivot din lista L i obine Rest = L - Pivot. 2. mparte lista Rest n dou liste: ListaInf, cu toate elementele din Rest

inferioare elementului Pivot i ListaSup cu toate lementele din Rest superioare elementului Pivot.

3. Sorteaz ListaInf i obine ListaInfSort. 4. Sorteaz ListaSup i obine ListaSupSort. 5. Concateneaz listele ListaInfSort, lista format din Pivot, ListaSupSort

i obine ListaSortat.

Predicatul quicksort(Lista, ListaSortat), definit mai jos, implementeaz acest algoritm. Elementul Pivot este considerat, n implementarea urmtoare, primul element al listei Lista, iar mprirea listei n ListaInf i ListaSup, n funcie de elementul pivot se face cu ajutorul predicatului scindeaz(Element, Lista, ListaInf, ListaSup). % quicksort(+Lista, -ListaSortata) - sortare prin metoda sortarii rapide quicksort([], []). quicksort([Pivot | Rest], ListaSortata) :- scindeaza(Pivot, Rest, L1, L2), quicksort(L1, L1Sortata), quicksort(L2, L2Sortata), conc(L1Sortata, [Pivot | L2Sortata], ListaSortata).

% conc(+L1, +L2, -L) - concateneaza listele L1 si L2 in lista L conc([], L, L). conc([Prim | Rest], L, [Prim | Rest1]) :- conc(Rest, L, Rest1).

90 CAPITOLUL 5

% scindeaza(+Element, +Lista, -ListaInf, -ListaSup) - % imparte Lista n ListaInf (cu elemente inferioare lui Element) % si ListaSup (cu elemente superioare lui Element) % in functie de relatia rel(X, Y) scindeaza(Elem, [], [], []). scindeaza(Elem, [Prim | Rest], [Prim | L1], L2) :- not(rel(Elem, Prim)), !, scindeaza(Elem, Rest, L1, L2). scindeaza(Elem, [Prim | Rest], L1, [Prim | L2]) :- rel(Elem, Prim), scindeaza(Elem, Rest, L1, L2).

S testm acum implementrile metodelor de sortare prezentate i s comparm rezultatele lor cu rezultatul produs de predicatul sort, care este predefinit n SWI-Prolog:

% testarea metodelor de sortare test(F) :- L = [2, 2, 4, 6, 9, 8, 1, 3, 5, 7, 0], P =.. [F, L, S], call(P), write(P), nl. test :- test(isort1), test(isort2), test(quicksort), test(sort). Testarea va decurge astfel:

?- test. isort1([2,2,4,6,9,8,1,3,5,7,0], [0,1,2,2,3,4,5,6,7,8,9]) isort2([2,2,4,6,9,8,1,3,5,7,0], [0,1,2,2,3,4,5,6,7,8,9]) quicksort([2,2,4,6,9,8,1,3,5,7,0], [0,1,2,2,3,4,5,6,7,8,9]) sort([2,2,4,6,9,8,1,3,5,7,0], [0,1,2,2,3,4,5,6,7,8,9])

5.4 Arbori binari Considerm urmtoarea reprezentare n Prolog a arborilor binari:

1) arborele vid este codificat cu nil; 2) un arbore nevid este codificat cu arb(Cheie, SubarboreStang,

SubarboreDrept). Traversarea unui arbore binar, cu afiarea cheilor din noduri, se

implementeaz n Prolog foarte uor folosind facilitile recursive ale limbajului. Predicatul rsd(Arbore) realizeaz afiarea cheilor din Arbore n ordinea rdcin-stnga-dreapta.

% rsd(+Arbore) - parcurge arborele binar Arbore % n ordinea radacina stanga dreapta, afisand cheile arborelui rsd(nil). rsd(arb(Radacina, SubarboreStang, SubarboreDrept)) :- write(Radacina), write(' '),

SORTARE I CUTARE 91

rsd(SubarboreStang), rsd(SubarboreDrept).

Dac se consider cazul arborilor binari de cutare (cu chei ntregi), se pot defini trei predicate: caut(Cheie, Arbore), de cutare a unei chei n arbore, care reuete dac cheia este n arbore i eueaz n caz contrar; inser(Cheie, Arbore, ArboreRez), de inserare a unei chei n arbore, cu argumentele Cheie i Arbore instaniate i argumentul ArboreRez sintetizat de program; i elim(Cheie, Arbore, ArboreRez), care terge o cheie dintr-un arbore. % caut(+Cheie, +Arbore) - reuseste daca Cheie este in % arborele binar de cautare Arbore, esueaza in caz contrar caut(Cheie, arb(Cheie, _ , _ )) :- !. caut(Cheie, arb(Radacina, ArbStg, _)) :- Cheie < Radacina, caut(Cheie, ArbStg). caut(Cheie, arb(Radacina, _ , ArbDr)) :- Cheie > Radacina, caut(Cheie, ArbDr).

Prima clauz a predicatului caut reuete dac cheia este n arbore. Pentru a impiedica o posibil resatisfacere, deci gsirea unei alte apariii a cheii de cutare n arbore, s-a introdus n acest caz predicatul cut. Dac se dorete, de exemplu, afiarea tuturor apariiilor cheii de cutare n arbore, se va elimina acest cut i predicatul caut va avea attea soluii cte apariii ale cheii de cutare exist n arbore.

% inser(+Cheie, +Arbore, -ArboreRez) - insereaza Cheie in % arborele binar de cautare Arbore si produce ArboreRez inser(Cheie, nil, arb(Cheie, nil, nil)). inser(Cheie, arb(Cheie, ArbStg, ArbDr), arb(Cheie, ArbStg, ArbDr)):-!. inser(Cheie, arb(Radacina, ArbStg, ArbDr), arb(Radacina, ArbStg1, ArbDr)) :- Cheie < Radacina, !, inser(Cheie, ArbStg, ArbStg1). inser(Cheie, arb(Radacina, ArbStg, ArbDr), arb(Radacina, ArbStg, ArbDr1)) :- Cheie > Radacina, inser(Cheie, ArbDr, ArbDr1).

Predicatul de inserare a unei chei ntr-un arbore de cutare, inser, utilizeaz n definiie un cut verde pentru creterea eficienei. Se poate elimina condiia Cheie >>>> Radacina, din cea de a treia regul a predicatului inser, caz n care predicatul cut se transform ntr-un cut rou. Programul Prolog urmtor folosete definiiile predicatelor caut i inser pentru a implementa mai multe operaii de prelucrare a arborilor binari de cutare.

Eliminarea unei chei dintr-un arbore binar de cutare se face dup algoritmul standard:

92 CAPITOLUL 5

% elim(+Cheie,+Arb,-ArbNou) elimina Cheie din Arb % cu rezultat in ArbNou elim(Cheie, nil, nil). elim(Cheie, arb(Cheie, nil, nil), nil). elim(Cheie, arb(Cheie, ArbStg, nil), ArbStg). elim(Cheie, arb(Cheie, nil, ArbDr), ArbDr). elim(Cheie, arb(Cheie, ArbStg, ArbDr), arb(Cheie1, Stg1, ArbDr)) :- drept(ArbStg, Cheie1, Stg1),!. elim(Cheie, arb(Cheie1, ArbStg, ArbDr), arb(Cheie1, ArbStg1, ArbDr1)) :- (Cheie < Cheie1, !, elim(Cheie, ArbStg, ArbStg1), ArbDr1=ArbDr) ; elim(Cheie, ArbDr, ArbDr1), ArbStg1=ArbStg.

% drept(+Arb,-Cheie,-SuccDr) - intoarce cel mai din dreapta nod % din arborele Arb. drept(arb(Cheie, ArbStg, nil), Cheie, ArbStg). drept(arb(Cheie, ArbStg, ArbDr), Cheie1, arb(Cheie, ArbStg, ArbDr1)) :- drept(ArbDr, Cheie1, ArbDr1).

Se poate defini un meniu de prelucrare arborilor binari de cutare care s permit execuia operaiilor definite anterior, la cerere.

meniu(Arb):- nl, write('1. Sfarsit'), nl, write('2. Creeaza arbore'), nl, write('3. Insereaza o cheie'), nl, write('4. Cauta o cheie'), nl, write('5. Sterge o cheie'), nl, write('6. Afiseaza arbore'), nl, read(Opt), Opt \= 1, !, actiune(Opt, Arb, ArbNou), meniu(ArbNou). meniu( _ ) :- write('Sfarsit'), nl.

actiune(2, Arb, ArbNou) :- creare(Arb, ArbNou). actiune(3, Arb, ArbNou) :- write('Introduceti cheia: '), read(Cheie), inser(Cheie, Arb, ArbNou). actiune(4, Arb, Arb) :- write('Introduceti cheia: '), read(Cheie), (caut(Cheie, Arb), write('Cheia a fost gasita'); write('Cheia nu este in arbore')), nl. actiune(5, Arb, ArbNou) :- write('Introduceti cheia: '), read(Cheie), elim(Cheie, Arb, ArbNou).

SORTARE I CUTARE 93

actiune(6, Arb, Arb) :- write(' In ce ordine? '), read(Ordine), afisare(Arb, Ordine).

creare(Arb, ArbNou) :- write('Introduceti o cheie, 0 pentru terminare: '), read(Cheie), Cheie \= 0, !, inser(Cheie, Arb, A), creare(A, ArbNou). creare(Arb, Arb).

% afisare(Arbore, Ordine) - afiseaza cheile arborelui binar Arbore, % parcurgand arborele in ordinea specificata de Ordine: rsd, srd, sdr afisare(nil, _ ). afisare(arb(Radacina, SubarboreStang, SubarboreDrept), Ordine) :- (Ordine = rsd, write(Radacina), write(' '); true), afisare( SubarboreStang, Ordine), (Ordine = srd, write(Radacina), write(' '); true), afisare( SubarboreDrept, Ordine), (Ordine = sdr, write(Radacina), write(' '); true).

Afiarea arborilor cu ajutorul predicatului afisare(Arbore, Ordine) se poate face n trei moduri diferite, n funcie de valoarea argumentului Ordine: rsd (rdcin-stnga-dreapta), srd (stnga-rdcin-dreapta) i sdr (stnga-dreapta-rdcin). Se observ utilizarea operatorului de disjuncie a scopurilor, cu ajutorul cruia se exprim cele trei modaliti de parcurgere a arborelui. Afiarea repetat a meniului de aciuni este fcut de predicatul meniu(Arb) prin apelul recursiv al acestuia, ct timp nu s-a selectat aciunea Sfarsit. Predicatul are argumentul Arb instaniat. Acesta poate fi iniial arborele vid i este actualizat de apelul recursiv la noua valoare ArbNou, care depinde de aciunea selectat. n funcie de aciunea selectat n NrActiune i de arborele dat Arb, predicatul actiune(NrActiune, Arb, ArbNou) decide care prelucrri sunt necesare pentru a obine arborele rezultat ArbNou.

S vedem acum un predicat de sortare a listelor, care utilizeaz arbori binari de cutare. Predicatul binsort(Lista, ListaSortata) sorteaz lista Lista n lista ListaSortata. El construiete un arbore binar de cutare prin inserarea succesiv a elementelor din Lista cu ajutorul predicatului inser prezentat anterior. ListaSortata se obine prin parcurgerea n ordine a arborelui obinut.

% binsort(+Lista, -ListaSortata) binsort(L, LSort) :- constr_arb(L, Tree, nil), write('Arborele este: '), nl, write(Tree), nl, parc_ord(Tree, LSort, []).

% constr_arb - construieste un arbore binar de cautare

94 CAPITOLUL 5

constr_arb([], Acc, Acc) :- !. constr_arb([K | Rest], Sol, Acc) :- inser(K, Acc, NoulAcc), constr_arb(Rest, Sol, NoulAcc).

% parc_ord - parcurge in ordine un arbore binar, % construind lista cheilor sale parc_ord(nil, Acc, Acc) :- !. parc_ord(arb(Cheie, Stang, Drept), L, Acc) :- parc_ord(Drept, L1, Acc), parc_ord(Stang, L, [Cheie | L1]).

5.5 Exerciii propuse EP1. Care este complexitatea timp a algoritmului de sortare prin metoda generare i testare, prezentat n Seciunea 5.1 ?

EP2. Comentai asupra complexitii timp a unei implementari Prolog a algoritmului de cutare binar a unei chei ntr-o list sortat cresctor.

EP3. Scriei predicatul ssort(-L,+LS) care sorteaz lista L n lista LS conform metodei de sortare prin selecie. La un moment dat lista este L' = PS::PN, unde PS este partea sortat i PN partea nesortat. Se extrage n mod repetat din PN elementul X de valoare minim i se adaug la sfritul listei PS. Algoritmul ncepe cu PS = [] i PN = L, i se termin cnd PN = [], n acel moment PS fiind chiar lista sortat LS. Pentru eliminarea unui element dintr-o list i concatenarea a dou liste trebuie s mai scriei dou predicate: elim i append. Pentru a evita folosirea lui append se poate extrage maximul din PN la fiecare pas i insera naintea lui SP.

EP4. S se scrie un program Prolog care realizeaz sortarea prin interclasare.

EP5. O concordan este o list de cuvinte care apar ntr-un text, lista sortat n ordine alfabetic mpreun cu numrul de apariii ale fiecrui cuvnt n text. S se scrie un program care genereaz o concordan pornind de la un text dat. S se propun o reprezentare pentru text i o reprezentare pentru concordan.

EP6. S se scrie un predicat care elimin o cheie dintr-un arbore binar de cutare.

EP7. S se rescrie predicatul meniu(Arb), nlocuind definiia recursiv a acestuia cu o definiie care utilizeaz predicatul repeat.

EP8. S se scrie un predicat Prolog care verific egalitatea a doi arbori binari, adic dac au aceleai chei.

EP9. S se scrie un predicat Prolog care verific egalitatea structural a doi arbori binari, adic dac au aceleai numr de chei i arat la fel.

SORTARE I CUTARE 95

EP10. S se defineasc o structur Prolog care s reprezinte un arbore multici. S se scrie un predicat Prolog pentru afiarea unui astfel de arbore.

EP11. S se scrie un predicat Prolog care verific egalitatea a doi arbori multici.