of 65
1
I. ANALIZA ALGORITMILOR
PRELIMINARII Abu Ja`far Mohammed ibn Musa al-Khowarizmi (autor persan, sec.
VIII-IX), a scris o carte de matematic cunoscut n traducere latin c Algorithmi de numero indorum, iar apoi c Liber algorithmi, unde algorithm provine de la al-Khowarizmi, ceea ce literal nseamn din oraul Khowarizm. n prezent, acest ora se numete Khiva i se afl n Uzbechistan. Att al-Khowarizmi, ct i ali matematicieni din Evul Mediu, nelegeau prin algoritm o regul pe baza creia se efectuau calcule aritmetice. Astfel, n timpul lui Adam Riese (sec. XVI), algoritmii foloseau
la: dublri, njumtiri, nmuliri de numere. Ali algoritmi apar n lucrrile lui Stifer (Arithmetica integra, Nrnberg, 1544) i Cardano (Ars magna sive de reguli algebraicis, Nrnberg, 1545). Chiar i Leibniz vorbete de algoritmi de nmulire. Termenul a rmas totui mult vreme cu o ntrebuinare destul de restrns, chiar i n domeniul matematicii.
Kronecker (n 1886) i Dedekind (n 1888) semneaz actul de natere al teoriei funciilor recursive. Conceptul de recursivitate devine indisolubil legat de cel de algoritm. Dar abia n deceniile al treilea i al patrulea ale secolului nostru, teoria recursivitii i algoritmilor ncepe s se constituie ca atare, prin lucrrile lui Skolem, Ackermann, Sudan, Gdel, Church, Kleene, Turing, Peter i alii.
1. ALGORITMI
Un algoritm const ntr-o procedur de calcul bine definit care, ntr-o succesiune finit de pai, transform o mulime de valori (date de intrare) ntr-o alt mulime de valori (date de ieire sau rezultatul prelucrrii).
Un algoritm constituie un mijloc de rezolvare a problemelor de calcul
bine definite. Un enun corect al unei astfel de probleme descrie, n termeni generali, relaia intrare/ieire corespunztoare algoritmului problemei.
Conceptele de funcie calculabil i algoritm formeaz obiectele principale de studiu n teoria calculabilitii. Ele apar n diferite domenii ale informaticii i matematicii sub diverse grade de abstractizare.
Dezvoltarea unor tiine implic, printre altele, construirea unor algoritmi care s rezolve o gam ct mai variat de probleme.
Noiunea de algoritm se ntlnete nc din clasele elementare relativ la cele patru operaii fundamentale aplicate numerelor naturale reprezentate n baza zece. Mai trziu, se studiaz algoritmul lui Euclid i algoritmi cu privire la rezolvarea unei ecuaii, determinarea inversei unei matrice nesingulare etc.
2
Exemplu 1.1:
S descriem un algoritm de nmulire a dou numere naturale x, y numit nmulirea La Russe.
P1. Se consider un tablou bidimensional cu dou coloane. Pe prima linie se afl x n prima coloan i y n a doua coloan.
P2. Numrul din prima coloan se mparte la 2 (mprire ntreag), iar cel din a doua coloan se nmulete cu 2.
P3. Pasul P2 se repet pn cnd n prima coloan se obine numrul natural 1.
P4. Se vor elimina liniile care conin n prima coloan un numr par. P5. Se vor nsuma numerele naturale din coloana a doua care corespund
liniilor rmase.
Suma obinut reprezint produsul xy. Fie numerele x = 245 i y = 37. Conform algoritmului descris se obine:
Liniile marcate cu (**) se consider eliminate. Asupra algoritmului descris se pun o serie de ntrebri. a) Condiia de oprire Rspunsul algoritmului const n furnizarea produsului xy. Ultima linie
din ciclu este cea care conine 1 n prima coloan. Odat cu ieirea din ciclu, algoritmul se ncheie.
b) Corectitudinea Algoritmul calculeaz corect produsul celor dou numere naturale. Se
observ c dac marcm cu 1 liniile rmase i cu 0 pe cele eliminate, se
DENMULIT NMULITOR
245 37
122** 74**
61 148
30** 296**
15 592
7 1184
3 2368
1 4736
xy 9065
3
obine numrul x scris n ordine invers n binar (245[10]= 11110101[2]). De altfel acest algoritm calculeaz produsul n binar a dou numere naturale.
c) Durata execuiei (viteza de execuie) Acest algoritm are aceeai vitez de execuie ca i algoritmul standard
de nmulire a dou numere naturale (efectund nmulirea n binar). Exist i ali algoritmi cu o vitez mai mare care calculeaz un astfel de produs.
d) Dimensiunea spaiului de memorie alocat etc. Teoria mulimilor constituie un instrument de descriere simpl i precis
a conceptului de funcie. Construirea unui model matematic pentru un astfel de concept este relativ uor de realizat fiindc avem de-a face cu un proces static. Descrierea conceptului de algoritm este mai dificil deoarece construirea unui model matematic pentru un astfel de concept presupune un
proces dinamic.
Au existat diveri matematicieni ca: E. Post, K. Gdel, A.M. Turing, A. Church etc. care, n mod independent, au dat cte o descriere a noiunii de algoritm.
Clasa tuturor algoritmilor, independent de modul de reprezentare a lor,
posed unele trsturi generale. Pentru un algoritm trebuie precizat:
a) domeniul algoritmului;
b) descrierea propriu-zis a algoritmului. Domeniul algoritmului este o mulime cel mult numrabil de elemente
asupra crora acioneaz algoritmul respectiv n care se includ i rezultatele finale.
Descrierea propriu-zis a algoritmului const n instruciuni care se execut asupra elementelor de intrare prezente n domeniul algoritmului. Fiecare din aceste instruciuni pune n eviden un numr finit de operaii elementare.
Iata descrierea algoritmului La Russe : RUSSE(A, B)
1. arrays X, Y {iniializare}
2. X[1] A; Y[1] B
3. i 1 {se construiesc cele dou coloane} 4. while X[i] > 1 do
5. X[i+1] X[i] div 2 {div reprezint mprirea ntreag}
6. Y[i+1] Y[i]+Y[i]
7. i i+1 8. {adun numerele Y[i] corespunztoare numerelor X[i] impare}
9. prod 0
4
10. while i > 0 do
11. if X[i] este impar
12. then prod prod+Y[i]
13. i i-1 14. return prod
Aciunea unui algoritm este subordonat: a) unor reguli de operare asociate;
b) agentului de calcul.
Regulile de operare asociate unui algoritm solicit fiecrei instruciuni s indice locaiile unde se afl datele de intrare ct i pe cele n care se depun rezultatele intermediare i finale.
Agentul de calcul poate fi uman, mecanic, electronic etc. i are rolul de a executa instruciunile prezente n algoritm.
O problem rezolvabil algoritmic (problem pentru care exist algoritm care s o rezolve) o gndim ca o funcie P total definit pe mulimea tuturor datelor de intrare sau informaiilor iniiale DI (cel mult numrabil), cu valori n mulimea datelor (informaiilor) finale DF (cel mult numrabil). O instan a unei astfel de probleme const ntr-un element dat xDI care satisface condiiile impuse de enunul problemei i este capabil s conduc la o soluie a acesteia. Dac P(x) (exist) i P(x) = y, se spune c y este soluia problemei P pentru intrarea x. n caz contrar, se spune c P nu are soluie pentru intrarea x.
n vederea prelucrrii pe calculator, un astfel de algoritm este transpus ntr-un program scris ntr-un limbaj de programare. Acest program
evalueaz o funcie natural. Dac domeniul de definiie al funciei constituie intrarea pentru programul respectiv, atunci valorile funciei sunt de fapt rezultatele programului.
Exemplul 1.2.
S considerm problema identificrii unei chei numerice date ntr-un tablou numeric unidimensional.
Datele de intrare sau intrarea algoritmului: dimensiunea n a tabloului,
tabloul numeric X = (x[1],..., x[n]) i valoarea numeric y (cheia); Datele de ieire sau ieirea algoritmului: poziia acelui element din
tablou care coincide cu cheia dat y sau un mesaj de neidentificare n cazul n care aceast cheie nu coincide cu nici un element din tablou.
O instan a problemei propuse const ntr-un tablou numeric dat, fie el X = (-11,121,1,0,7,-48) de dimensiune 6 i o cheie numeric, fie ea y = 7.
5
Conform acestei instane algoritmul va furniza ca rezultat faptul c elementul x[5] coincide cu cheia dat (soluie a problemei).
Un algoritm este corect dac pentru orice instan a sa el se ncheie cu o ieire corect care este soluie a problemei de calcul rezolvat prin algoritmul respectiv. Unii algoritmi, dei sunt incoreci n sensul c nu conduc la nici o soluie n timp finit sau conduc la soluii eronate, ei pot fi utili att timp ct erorile produse de ei pot fi controlate.
Comportarea aceluiai algoritm poate fi diferit n funcie de datele de intrare. De aceea se impune o mare atenie asupra acestora din urm. O variabil prezent n intrarea unui algoritm poate identifica un tablou sau un obiect al unei date compuse i va fi tratat ca un pointer la elementele tabloului, respectiv la cmpurile (atributele) obiectului corespunztor.
Modul n care se definete dimensiunea datelor de intrare depinde de problema de calcul analizat. Ea poate fi exprimat prin:
a) numrul de elemente cuprinse n datele de intrare (de exemplu, dimensiunea unui tablou de numere ntregi);
b) numrul total de bii din reprezentarea binar a datelor de intrare (vezi algoritmul de nmulire a dou numere mari ntregi);
c) dou numere naturale (de exemplu, pentru reprezentarea unui graf se solicit numrul de vrfuri i numrul de muchii ale sale);
d) valoarea numeric a intrrii ( pentru algoritmi numerici, de exemplu algoritmul La Russe).
Pentru fiecare algoritm care rezolv o anumit problem P este necesar a se preciza modul de exprimare a dimensiunii datelor de intrare.
Dac exist un algoritm care rezolv problema P nu nseamn c el este unic.
De exemplu, exist algoritmi ca: QuickSort (sortare rapid), MergeSort (sortare prin fuziune), TreeSort (sortare prin arbori), sortare prin selecie i inserie etc. care sunt utilizai n acelai scop.
Prin urmare, apare necesitatea alegerii unui algoritm din clasa de
algoritmi care rezolv problema P care s corespund unor cerine. Algoritmul depinde de aplicaie, implementare, mediu, frecvena utilizrii etc. Compararea algoritmilor este un proces subtil care are n vedere mai
multe aspecte. n continuare, vom cuta s analizm cteva din aceste aspecte care joac un rol important n elaborarea unui algoritm.
2. COMPLEXITATEA CALCULULUI
Teoria complexitii constituie un domeniu foarte important al teoriei algoritmilor care investigheaz rezolvabilitatea individual a problemelor sub anumite restricii de resurse.
6
Teoria complexitii calculului cuprinde: 1) Un studiu analitic al complexitii unor clase de probleme n raport cu
diverse tipuri concrete de maini matematice care le rezolv; 2) Un studiu calitativ al complexitii algoritmilor care rezolv astfel de
probleme.
Mai precis, complexitatea calculului se bazeaz pe legturile existente ntre problemele rezolvabile algoritmic i resursele de calcul.
nainte de a trece la analiza unui algoritm, trebuie s se cunoasc o tehnologie de implementare a acestuia care va include un model pentru
resursele sale i costurile corespunztoare. Aadar, resursele de calcul sunt introduse prin definirea unui model de calcul care, de regul, reprezint o main. n acest sens pot fi utilizate: maini Turing de diverse tipuri, maini cu acces aleatoriu (random-acces machine, RAM), circuite booleene etc. Resursele tipice sunt: timp, spaiu, benzi, capete de citire/scriere, nivele ntr-un circuit etc.
Pentru tratarea celor dou elemente fundamentale, problem i main, considerm trei nivele abstracte n complexitatea calculului.
a) Un nivel nalt care pune n eviden complexitatea abstract a calculului, cunoscut sub numele de teoria Blum de complexitate a calculului, care este independent att de problem ct i de main. O astfel de teorie este construit pe o enumerare efectiv a tuturor funciilor parial recursive, o enumerare a aa numitelor funcii cost-msur i dou axiome de baz (axiomele lui Blum).
b) Un nivel mediu care pune n eviden complexitatea structural, independent de problem dar dependent de main. Scopul unei astfel de complexiti este de a studia capabilitatea unor modele de calcul concrete pentru resurse sau combinaii de resurse, independent de problema propus.
c) Un nivel inferior ce indic o complexitate concret care depinde att de main ct i de problem. Scopul su este de a detecta o bun evaluare, cu un cost pe ct posibil minim, folosind o resurs (sau combinaii de resurse) ntr-un model precizat pentru rezolvarea problemei.
n general, dificultatea unei probleme P se poate msura prin resursele de calcul limitate asociate algoritmului secvenial care o rezolv. Aceste resurse sunt timpul i spaiul de memorie necesare pentru execuia algoritmului respectiv. O astfel de msur se poate evalua n diverse moduri. n termenii mainii Turing, ca model de calcul, complexitatea temporal este stabilit de numrul de deplasri necesare realizrii calculului respectiv, iar pentru un computer digital, de numrul de ciclri ale mainii sau timpul real solicitat de main pentru acel calcul. n ceea ce privete complexitatea spaial, pentru maina Turing, ea const n numrul
7
de celule (ptrate) ale benzii folosite n calcul, iar pentru computer, n numrul de bytes utilizai.
Prin urmare, ideea de complexitate a unui algoritm poate fi privit sub dou aspecte:
a) static, prin structura sa.
b) dinamic, prin durata execuiei sale. Complexitatea spaial se exprim prin dimensiunea spaiului de
memorie necesar algoritmului, independent de comportarea pe care o are el
pe parcursul execuiei. Complexitatea temporal se exprim prin timpul necesar execuiei sale.
Axiomele lui Blum, de exemplu, pun n eviden msuri de complexitate dinamic cu consecine ca: teorema corelrii msurilor, teorema accelerrii, teorema lacunei etc.
Exist numeroase probleme de optimizare n reele de transport, informatic, electronic, logistica construciilor, teoria comunicaiilor (n codurile corectoare de erori), criptografie etc. Pentru algoritmii de rezolvare
a acestor probleme este obligatoriu un studiu al complexitii lor. Complexitatea algoritmilor relativ la coduri, reprezentarea compact a mesajelor n vederea transmiterii lor prin diverse canale, permite o analiz asupra eficacitii metodelor de codificare/decodificare. Relativ la criptografie, studiul complexitii implic elaborarea unor tehnici care s permit cifrarea mesajelor sub o form care s le asigure, pe ct posibil, inviolabilitatea.
Analiza unui algoritm conduce la stabilirea eficienei sale i implic, n principal, ideea de complexitate pentru c ea prevede resursele solicitate de algoritmul respectiv. Stabilirea complexitii unui algoritm este necesar, pe de o parte, datorit faptului c muli algoritmi sunt eliminai de practic deoarece necesit un timp de execuie i un spaiu de memorie foarte mari, iar pe de alt parte, se caut algoritmi ct mai performani n vederea rezolvrii cu calculatorul a unor probleme destul de complexe impuse de practic. Un calculator, orict de performant ar fi, este n esen un automat finit, deci el are posibiliti limitate. Performana unui algoritm se stabilete conform unui criteriu care, de cele mai multe ori, l constituie timpul de
execuie al algoritmului respectiv. Avnd n vedere faptul c pentru seturi de date de intrare diferite acelai
algoritm folosete timpi de execuie diferii este necesar a lua n consideraie:
timpul n cazul cel mai favorabil (durata minim pentru execuia algoritmului);
8
timpul mediu (raportul dintre suma timpilor necesari pentru toate seturile de date posibile i numrul acestor seturi);
timpul n cazul cel mai defavorabil (durata maxim pentru execuia algoritmului).
Acesta din urm ofer o margine superioar a timpului de execuie pentru toate intrrile de o dimensiune fix i reprezint situaia cea mai indicat pentru cutarea de informaii ntr-o baz de date.
S considerm implementarea unui algoritm oarecare care s primeasc intrri de dimensiuni diferite. La o intrare de dimensiune n vom asocia o msur f(n) de folosire a resurselor sale care, de regul, trebuie s se minimizeze. n mod normal, f(n) va reprezenta timpul solicitat de algoritm
pentru intrarea de dimensiune n n cazul cel mai defavorabil sau mediu (la
alegerea noastr). Exist o serie de factori care complic mai mult sau mai puin calculul exact al lui f(n).
De exemplu:
a) Timpul solicitat pentru execuia unei instruciuni individuale dintr-un program, cu aceeai instan i pe aceeai main, poate varia.
b) Poate exista o mare variaie de folosire a resurselor pentru intrri de o anume dimensiune constant n.
c) Cazul cel mai defavorabil poate fi mai rar ntlnit n practic, iar cazul mediu s fie nereprezentativ.
d) Unii algoritmi se pot executa mai bine pe anumite clase de intrri. n acest sens se impun cteva sugestii, cum ar fi:
- Identificarea operaiilor abstracte folosite de algoritm. Pentru a obine o maximizare a independenei de main este necesar o analiz a acestor operaii abstracte, pentru c resursele solicitate de o mare parte din ele vor fi neimportante. Unele din ele sunt utilizate o singur dat la iniializare.
- Un algoritm, n general, posed cel puin un ciclu. Acesta trebuie identificat pentru c instruciunile din interiorul su se execut mult mai des i ele vor juca un rol important n analiza timpului de execuie a algoritmului. Prin contorizarea acestor instruciuni se determin o margine superioar corespunztoare pentru valoarea timpului de execuie n cazul cel mai defavorabil i, dac este posibil, o configurare a cazului mediu. Aceast limit superioar este necesar pentru c, n mod practic, nu poate fi gsit o valoare exact a timpului de execuie n cazul cel mai defavorabil.
- Timpul necesar unui algoritm pentru rezolvarea unei probleme cu o
instan dat, reprezint numrul operaiilor elementare (primitive) efectuate de algoritm pentru acea instan. Se accept o astfel de interpretare deoarece se presupune c execuia unei astfel de operaii se
9
produce ntr-un timp constant i nu depinde de mrimea operanzilor i nici de timpul de memorare a rezultatului. De aceea resursa timp asociat se analizeaz independent de sistemul de calcul pe care se implementeaz algoritmul respectiv.
- Dei progresele tehnologice actuale fac ca necesarul de memorie s treac pe un plan secund, exist totui situaii n care spaiul de memorie utilizat este folosit ca argument n stabilirea unor limite inferioare pentru
timpul de execuie. - Viteza de calcul ce caracterizeaz actuala generaie de calculatoare are
drept consecin faptul c problema timpului de execuie se pune, n general, pentru valori foarte mari ale dimensiunii intrrii. Aceasta conduce la ideea unei analize a termenului dominant (cel care tinde cel mai repede la
infinit) din formula de exprimare a numrului de operaii elementare executate de ctre algoritm.
Dimensiunea informaiilor prelucrate n majoritatea problemelor pe care le ntlnim n practic nu rmne constant.
Pentru a nelege noiunea de procedeu mecanic de calcul au fost propuse numeroase modele de calcul formal. Conform celebrei teze a lui
Church - tot ceea ce este intuitiv calculabil cu ajutorul unui algoritm este
calculabil indiferent de modelul formal de calcul - aceste modele sunt
echivalente. n mod clasic, n teoria complexitii, se consider drept model maina Turing care prezint dublul avantaj de a constitui un model de program pentru calculator, dar i un cronometru pentru timpul de execuie al su. Conform acestui model, complexitatea unui algoritm A, pentru orice dimensiune n a intrrii, este o funcie f(n) ce exprim timpul maxim de execuie a algoritmului.
n descrierea algoritmilor, cel mai convenabil model este modelul RAM
avnd n vedere i cele mai importante clase de complexitate studiate (timp i spaiu polinomial).
Exist cteva funcii tipice de exprimare a timpului de execuie a unui algoritm. Putem obine, n mod obinuit, o astfel de funcie printr-o relaie de recuren.
Cel mai adesea se va ntlni funcia de forma f(n) = cg (n) + tm unde c > 0 este o constant, n reprezint dimensiunea
intrrii, iar tm este un termen mic care este semnificativ doar pentru valori mici ale lui n sau pentru algoritmi sofisticai.
Funcia g(n) poate fi: constant (algoritmul se execut n timp constant); log n (algoritmul se execut n timp log); nm (m = 0, 1, 2)(algoritmul se execut n timp polinomial);
10
Cazuri particulare:
a) n (algoritmul se execut n timp liniar); b) nlog n (algoritmul se execut n timp liniar log); c) n2 (algoritmul se execut n timp ptratic); d) n3 (algoritmul se execut n timp cubic); n! (algoritmul se execut n timp factorial); kn (k > 1, constant) (algoritmul se execut n timp exponenial). Exemplul 2.1.
S considerm un algoritm care efectueaz operaii de punere/extragere a unei date de 32 bii efectuate pe o stiv cu elemente ntregi. Astfel de operaii vor necesita un timp constant. Un algoritm care se execut ntr-un timp constant mic se zice c este perfect.
Exemplul 2.2.
S presupunem un algoritm a crui intrare const dintr-un ir de n caractere. El poate prelucra intrarea sa caracter cu caracter, solicitnd
acelai timp pentru fiecare astfel de caracter. n acest caz, f(n) = n. Un astfel de algoritm care se execut n timp liniar se zice c este excelent.
Exemplul 2.3.
Un algoritm poate cicla direct intrarea sa format din numere ntregi sub forma
f(n) = n + f(n - 1).
Iternd aceast relaie se obine f(n) = n + f(n - 1) = n + ((n-1) + f(n - 2)) =.....
= n + (n - 1) + (n - 2) + .... + 2 + f(1) = n2/2 + n/2 + k, unde k este o
constant. Pentru un n suficient de mare, k i n/2 sunt mici fa de n2. Un astfel de algoritm se execut ntr-un timp ptratic.
Un algoritm care solicit o prelucrare a celor n2 perechi de caractere ce corespund unei intrri care const dintr-un ir de n caractere, solicit tot un timp ptratic de execuie.
Pentru intrri de dimensiuni mari algoritmii care se execut n timp ptratic vor evolua mai lent.
Exemplul 2.4.
Un algoritm poate prelucra, la fiecare pas, jumtate din intrarea sa. Aadar,
f(n) = f(n/2) + 1
(cu aproximare n cazul n care n nu este o putere natural a lui 2). Fie n = 2x. Atunci, f(n) = f(2x) = 1 + f(2x-1) = 1 + (1 + f(2x-2)) = ... = x +
f(20) = x + k, unde k este o constant.
11
n acest caz, f(2x) este aproximativ x, iar f(n) este aproximativ log2n. Un
astfel de algoritm se execut n timp log. Aceti algoritmi au o cretere foarte lent i sunt foarte buni n practic.
Este foarte cunoscut algoritmul Divide et Impera folosit n Quicksort, Mergesort etc. Pentru acest algoritm, f(n) = n + 2f(n/2).
Pentru n = 2x, folosind un mic artificiu, se obine: f(2x)/2x = 2x/2x + 2*f(2x/2)/2x = 1 + f(2x-1)/2x-1 = 1 + (1 + f(2x-2)/2x-2) =
...= x + f(20)/20 =
= x+k, unde k este o constant. Rezult c f(2x) = 2x(x + k) = 2xx + tm. Prin urmare, f(n) = nlog2n + tm.
n concluzie, algoritmul respectiv se execut n timp liniar log. Exemplul 2.5.
S presupunem c intrarea unui algoritm const ntr-o mulime de n numere ntregi. Se cere s se gseasc o submulime a acestei mulimi cu proprietatea c suma elementelor sale este nul.
Printr-o cercetare exhaustiv, n cazul cel mai defavorabil, se vor verifica toate cele 2n submulimi posibile. Un astfel de algoritm se va executa ntr-un timp exponenial.
Exemplul 2.6.
Un algoritm, prin care se cere obinerea tuturor anagramelor corespunztoare unui cuvnt format din n caractere la intrare, se va executa ntr-un timp factorial, pentru c exist n! astfel de posibiliti.
Funcia n! crete aproximativ cu aceeai vitez ca nn, dar mai repede dect 2n.
n 1964, Cobham a introdus clasa P a problemelor rezolvabile
algoritmic n timp polinomial, adic o problem ce se rezolv printr-un algoritm A care pentru orice numr natural n, funcia sa de complexitate este mrginit superior de un polinom cunoscut p(n) n variabila n, adic f(n) kp(n), unde k este o constant nenul. n aceast clas se ntlnesc aa numitele probleme facile. Se mai spune despre un algoritm de complexitate polinomial c reprezint rezultatul unei cunoateri detaliate a problemei pe care o rezolv.
Despre un algoritm care nu este de complexitate polinomial se zice c se comport exponenial. n aceeai clas a algoritmilor exponeniali sunt ncadrai i algoritmii de complexitate nlog n dei nu corespund n sensul strict matematic al noiunii respective. Avnd n vedere viteza de cretere sau ordinul de cretere a timpului de execuie n raport cu n a funciilor exponeniale fa de cele polinomiale, n general, algoritmii exponeniali sunt inutilizabili n practic. Despre un algoritm de
12
complexitate exponenial se spune c este o variant a unei enumerri totale a cilor de identificare a soluiilor problemei respective.
Exist unii algoritmi cu comportare exponenial care, pentru valori relativ mici ale lui n, sunt mai eficieni dect cei alternativi cu comportare polinomial. De asemenea, unii algoritmi exponeniali se comport acceptabil pentru unele probleme particulare (vezi metoda simplex de
rezolvare a problemelor de programare liniar). n general, despre o problem pentru care s-a dovedit c nu exist un
algoritm de complexitate polinomial pentru rezolvarea ei, adic nu este tractabil, se spune c este intractabil. Dificultatea unei astfel de probleme trebuie remarcat prin faptul c
timpul necesar pentru gsirea unei soluii este de ordin exponenial, adic funcia nu se poate exprima printr-o expresie care s poat fi mrginit superior de un polinom n variabila n.
Dac se are n vedere ca model, maina de calcul n paralel (capabil de a efectua simultan un numr relativ mare de calcule independente), clasa problemelor dificile (cele care nu sunt facile) se poate mpri n dou subclase:
a) subclasa problemelor pentru care nu exist algoritmi nedeterminiti de complexitate polinomial pentru rezolvarea lor;
b) subclasa problemelor pentru care exist algoritmi nedeterminiti de complexitate polinomial pentru rezolvarea lor (NP).
Trebuie observat faptul c majoritatea problemelor care par a fi dificile admit algoritmi nedeterminiti de complexitate polinomial pentru rezolvarea lor. Noiunea de algoritm determinist trebuie neleas n sensul c structura sa nu permite o alegere ntre mai multe ci posibile n vederea obinerii rezultatului dorit. Conceptul de algoritm nedeterminist trebuie neles n sensul c el se poate afla n mai multe stri independente care nu se pot alege dup anumite criterii i nici genera aleator. Un algoritm se numete nedeterminist polinomial dac complexitatea calculelor, efectuate pe orice cale a arborelui ce descrie ramificrile procesului de cutare a soluiei, este polinomial.
Avnd n vedere aceste interpretri, conceptul de algoritm determinist polinomial este evident.
Clasa problemelor dificile n sensul cel mai tare este format din acele probleme pentru care s-a demonstrat c nu exist algoritmi pentru rezolvarea lor (de exemplu, problema a zecea a lui Hilbert cu privire la
rezolvabilitatea n numere ntregi a ecuaiilor polinomiale).
13
3. COMPLEXITATE ASIMPTOTIC O simpl caracterizare a eficienei unui algoritm const n viteza de
cretere a timpului su de execuie care ofer posibilitatea de a compara performanele relative ale unor algoritmi alternativi.
n general, este destul de dificil de a determina expresia exact ce definete timpul de execuie al unui algoritm n funcie de dimensiunea problemei, de aceea se stabilesc anumite limite ntre care el poate varia.
Complexitatea se exprim n funcie de aceast dimensiune. Cnd datele de intrare au dimensiuni suficient de mari, astfel nct
numai viteza de cretere a timpului de execuie s fie relevant, vom studia eficiena asimptotic a algoritmilor. Mai exact, se va urmri viteza de execuie a mai multor algoritmi cu acelai obiectiv, sau, altfel zis, viteza de cretere a funciilor a cror expresie reprezint timpul de execuie a unor astfel de algoritmi. n practic exist un interes deosebit asupra modului de cretere a timpului de execuie a unui algoritm o dat cu creterea dimensiunii datelor de intrare pn la cazul limit n care aceast dimensiune crete la infinit. Se folosete, n acest sens, conceptul de timp asimptotic de execuie a unui algoritm. Pentru exprimarea unui astfel de timp se va folosi un limbaj riguros care cuprinde urmtoarele simboluri asimptotice: , O , o , , . Se vor folosi funcii al cror domeniu de definiie l reprezint mulimea numerelor naturale N. Notaia se poate extinde, n unele situaii, la domeniul numerelor reale sau restrnge la o submulime a mulimii numerelor naturale.
Fie mulimea funciilor nenegative care au ca domeniul de definiie mulimea numerelor naturale N = {0, 1, 2, ....}.
Fie funciile f(n), g(n) ngnf , .
3.1. - notaia
Definiia 3.1.1. f (n) = (g(n)) (n ) dac exist constantele c1 > 0,
c2 > 0 i Nn 0 , astfel nct ngcnfngcnn 210 0, . Notaia n indic, o dat n plus, faptul c relaia asimptotic are loc
pentru valori suficient de mari ale lui n. ntr-o scriere asimptotic, chiar dac nu este prezent aceast notaie cu scopul de a simplifica scrierea, ea este subneleas.
Din punct de vedere matematic este corect a folosi notaia
ngnf , pentru c nfng /exist constantele c1 > 0, c2 > 0 i Nn 0 , astfel nct ngcnfngcnn 210 0, .
14
c2g(n)
f(n)
c1g(n)
n
n literatura de specialitate, se folosete, printr-un abuz de utilizare a semnului de egalitate, notaia f (n) = (g(n)) (n ). Se accept ambele notaii i pentru celelalte simboluri care vor urma. Se spune despre funciile f(n) i g(n) c au aproape aceeai vitez de cretere avnd n vedere constantele pozitive multiplicative c1, c2 sau c ele sunt funcii egale pn la un factor constant. Vom spune c funcia g(n) constituie o margine asimptotic tare sau strns (inferioar i superioar) pentru funcia f(n).
Din definiia mulimii (g(n)) se observ c este necesar ca elementele sale s fie funcii nenegative pentru valori ale lui n suficient de mari. O funcie asimptotic pozitiv este strict pozitiv pentru orice valoare a lui n
suficient de mare ( 0nn ).
n mod intuitiv, pe baza definiiei simbolului , ntr-o expresie polinomial ce reprezint timpul de execuie a unui algoritm se ia n calcul doar termenul dominant (de ordin maxim) i se neglijeaz toi termenii de ordin inferior ct i coeficientul termenului dominant.
Fie f(n)= (3/7)n2- 4n. Pentru a arta c f(n)= (n2) trebuie s determinm constantele pozitive n0, c1, c2 astfel nct
22221 4730 ncnnnc . Pentru 73,1 2 cn se observ c are loc inegalitatea 2
47
3 cn , iar pentru
351,1 1 cn are loc
inegalitatea 14
73 c
n . n concluzie, exist constantele
73,
351
21 cc i n0 = 10 astfel nct s aib loc dubla inegalitate,
adic f(n) = (n2). Adesea, dac i se d constantei c1 o valoare ceva mai mic dect coeficientul termenului dominant, iar lui c2 o valoare puin mai mare dect acelai coeficient, definiia simbolului ar putea fi ndeplinit.
n0
f(n) = (g(n))
15
Coeficientul termenului dominant poate fi ignorat pentru c el ar modifica cele dou constante c1 i c2 doar cu un factor constant.
S observm c aceste constante, pentru o aceeai funcie, nu sunt unice i ele depind de funcia respectiv.
Prin relaia ncgnf 0 , se nelege c funcia f (n) are ordinul de cretere al funciei g(n) pentru valori ale lui n suficient de mari, pn la un anumit factor constant c. Logaritmnd aceast relaie, se obine
ngcnf loglog 1 (c1 = log c, este o constant). Logaritmnd i relaia nfngc 0 , se obine nfngc loglog2 (c2= logc este o constant). Se observ c f (n) = (g(n)) (n ) dac i numai dac exist o constant c astfel nct pentru un n suficient de mare, log(f(n)) i log(g(n)) s difere prin cel mult o astfel de constant multiplicativ.
Se spune c implementarea unui algoritm se execut n timp log, respectiv n timp liniar, dac funcia sa de complexitate f(n) este din (log(n)), respectiv (n).
3.2. O - notaia
Definiia 3.2.1 f (n) = O(g(n)) (n ) dac c > 0, Nn 0 astfel
nct ngcnfnn 0,0 . Printr-o astfel de notaie se pune n eviden faptul c funcia f(n) crete
strict mai lent sau cel mult la fel ca funcia g(n). Se mai spune c funcia g(n) domin funcia f(n) sau c funcia f(n) este
dominat de funcia g(n)). Cu alte cuvinte, prin notaia f(n) = O(g(n)) (n ) nelegem faptul c un multiplu constant al lui g(n) constituie o margine asimptotic superioar a lui f(n). Aadar
Nncnfng 0
,0/
astfel nct 0,0 nnngnf .
cg(n)
f(n)
n0 n
f(n) = (g(n))
16
n literatura de specialitate exist o distincie clar ntre o margine asimptotic superioar i o margine asimptotic tare (strns) pe care o ofer . Notaia O ofer o margine asimptotic superioar care nu este neaprat o margine asimptotic tare.
Exemplul 3.2.1.
5n2 = O(n2) constituie o margine asimptotic superioar tare. 5n = O(n2) este o margine asimptotic superioar. Din faptul c f(n) = (g(n)) rezult c f(n) = O(g(n)) pentru c notaia
este mai puternic dect notaia O, adic (g(n)) O(g(n)). O funcie liniar f(n) = an + b = (n) (a > 0). n schimb, folosind notaia
O, este adevrat i relaia f(n) = O(n2). ntr-adevr trebuie s determinm cele dou constante strict pozitive n0 i c astfel nct s aib loc relaia
0oricepentru2
0 nncnban . Dac dreapta intersecteaz parabola
trebuie ca ecuaia ataat s aib rdcini reale. De aceea, vom considera expresia a2 + 4bc de forma (a + 2b)2. Printr-un calcul elementar se observ
c pentru orice 10 nn i 0 cbac relaia este adevrat. Dac dreapta nu intersecteaz parabola, relaia cerut este evident adevrat.
Printr-o afirmaie de genul timpul de execuie al unui algoritm A este O(nk) se nelege c timpul de execuie n cazul cel mai defavorabil (exprimat printr-o funcie de n) este O(nk), adic oricare ar fi datele de intrare de dimensiune n, pentru fiecare valoare a lui n, timpul de execuie respectiv este O(nk), unde k este o constant ntreag.
Propoziia 3.2.1. O condiie suficient ca o funcie g(n) s dea o comportare asimptotic de tip O pentru o funcie f(n), adic f(n) = O(g(n)),
este s existe o constant Nn 0 astfel nct pentru orice 0nn s fie
ndeplinite urmtoarele condiii: a) g(n) > 0;
b) ngnf
n lim s existe i s fie finit.
Demonstraie: Fie ngnf
l n lim . Aceasta nseamn c
0,0 n astfel nct
0, nnlng
nf . Adic
17
lng
nfll
ng
nf .Alegnd
0,11 nnlng
nf . Exist dou constante pozitive
1, 010 lnn astfel nct ngnnfngnn *0,0,0
10 .
Aadar f(n) = O(g(n)). Aceast condiie nu este i necesar. Justificai aceast afirmaie printr-
un contraexemplu.
Exemplul 3.2.2. Fie funciile ngnf , definite prin relaiile f(n) = 10n i g(n) = n2. Dac calculm f(n) i g(n) pentru 1 n 9 se obine: f(1) = 10, g(1) = 1; f(2) = 20, g(2) = 4; f(3) = 30, g(3) = 9; f(4) = 40, g(4) = 16 ,, f(9) = 90, g(9) = 81. Pentru n 10 se observ c n2 10n, adic 0 f(n) g(n).
3.3. - notaia Definiia 3.3.1 f(n) = (g(n)) (n) dac g(n) = O(f(n)) (n).
Nncnfng 0,0 astfel nct 0,0 nnncgnf .
f(n)
c(n)
n
n studiul algoritmilor, simbolul este util pentru a pune n eviden un timp minim posibil de execuie. Aadar simbolul este util n precizarea unei margini asimptotice inferioare nu neaprat tare.
Exerciiu 3.3.1:
Artai c nfnfgngnf .
n0
f(n) = (g(n))
18
n practic se demonstreaz existena marginilor asimptotice tari pornind de la margini asimptotice superioare i inferioare i nu invers.
3.4. o - notaia
Definiia 3.4.1 f(n) = o (g(n)) (n) dac Nnc 0,0 astfel
nct nn0, are loc relaia 0 f(n) < cg(n). Prin urmare,
00 ,0caastfel,0 nnncgnfNncnfng Prin notaia o vom semnala o margine asimptotic superioar care nu este o margine asimptotic superioar tare.
Exemplul 3.4.1.
10n = o(n2), iar 10n2 o(n2). Conform definiiei simbolului o putem spune c f(n) = o (g(n)) (n)
dac ngnf
n lim exist i este egal cu 0.
O astfel de notaie exprim faptul c funcia f(n) crete strict mai lent dect funcia g(n) pentru valori ale lui n suficient de mari.
S observm, de exemplu, c sin(n) = o(n) implic sin(n) = O(n), dar sin(n) = O(1) nu implic sin(n) = o(1) . Ce putei afirma n acest sens ?
Propoziia 3.4.2. O condiie necesar i suficient ca
1caeste0lim nfnfn
3.5. - notaia
Definiia 3.5.1. f(n) = (g(n)) (n) dac Nnc 0,0 astfel
nct nn0, are loc relaia f(n) > cg(n) 0. Simbolul se raporteaz la ntr-un mod asemntor lui o fa de O. Aadar,
00 ,0caastfel,0 nnncgnfNncnfng Se observ c f(n) = (g(n)) dac i numai dac g(n) = o(f(n)).
Aadar desemneaz o margine asimptotic inferioar care nu este o margine asimptotic inferioar tare.
Exemplul 3.5.1.
n2 = (n), iar n2 (n2).
19
Se observ c f(n) = (g(n)) implic
ng
nfnlim (dac limita
exist). 3.6. ~ - notaia Definiia 3.6.1.
f(n) ~ g(n)(n ) dac exist
1lim ng
nfn .
Propoziia 3.6.1. O condiie necesar i suficient ca f(n) ~ g(n) (n) este ca
f(n) = g(n) (1+o(1)).
Demonstraie:
Dac f(n) ~ g(n) atunci
1lim ng
nfn implic
01lim1limlim
ng
nf
ng
nf
ng
ngnfnnn
Aadar (f(n)- g(n))/ g(n) =o(1), adic f(n)= g(n) (1+o(1)). Reciproc se demonstreaz asemntor.
Propoziia 3.6.2. Dac f(n)~ g(n) (n), atunci f(n)=O(g(n))(n). Demonstraie: exerciiu!
4. Compararea asimptotic a funciilor Multe dintre proprietile relaiilor dintre numerele reale se aplic i
la compararea asimptotic a funciilor. Pentru cele ce urmeaz vom presupune c f(n) i g(n)sunt asimptotic pozitive.
Tranzitivitate :
))(()( ngnf i ))(()( nhng implic ))(()( nhnf ,
))(()( ngnf i ))(()( nhng implic ))(()( nhnf ,
))(()( ngnf i ))(()( nhng implic ))(()( nhnf ,
))(()( ngnf i ))(()( nhng implic ))(()( nhnf ,
)(()( ngnf i ))(()( nhng implic ))(()( nhnf .
Reflexivitate:
)),(()( nfnf
)),(()( nfnf
)),(()( nfnf
20
Simetrie:
)),(()( nfnf dac i numai dac )).(()( nfng
Antisimetrie:
)),(()( nfnf dac i numai dac )).(()( nfng
)),(()( nfnf dac i numai dac )).(()( nfng Deoarece aceste proprieti sunt valide pentru notaii asimptotice, se
poate trasa o analogie ntre compararea asimptotic a dou funcii f i g i compararea asimptotic a dou numere reale a i b:
))(()( nfnf ,ba
))(()( nfnf ,ba
))(()( nfnf ,ba
))(()( nfnf ,ba
))(()( nfnf .ba O proprietate a numerelor reale, totui, nu se transpune la notaii
asimptotice:
Trihotomia: pentru orice dou numere reale a i b exact una dintre urmtoarele relaii este adevrat: a < b, a = b, a > b.
Dei orice dou numere reale pot fi comparate, nu toate funciile sunt asimptotic comparabile. Cu alte cuvinte, pentru dou funcii f(n) i g(n) , se
poate ntmpla s nu aib loc nici ))(()( ngnf , nici
))(()( ngnf . De exemplu, funciile n i n1+sin n nu pot fi comparate utiliznd notaii asimptotice, deoarece valoarea exponentului n n1+sin n oscileaz ntre 0 i 2, lund toate valorile intermediare.
EXERCIII: Exemplul 3.1.1.
(n + 1)3 = (n3) (1)
(5 + ( 2n)0.5)0.5 = (n0.25) (2)
(1+7/n)n = (1) (3)
Exemplul 3.4.2. n4 = o(n7 )
(1)
21
5log n = o(n0.03)
(2)
sin n = o(n)
(3)
5.2 n0.5 = o(n/8 + 9 sin n)
(4)
Exemplul 1.3.9.
n4 + 3n3 - 2 ~ n4
(1)
(5n + 1)2 ~ 25n2
(2)
53
1763
25
n
nn ~ 2n2
(3)
4n + 8log n + 78 ~ 4n
(4)
sin 1/n ~ 1/n
(5)
n + sin n ~ n
(6)
5. RELAII RECURENTE Cel mai important ctig al exprimrii recursive este faptul c ea este
natural i compact, fr s ascund esena algoritmului prin detaliile de implementare. Pe de alt parte, apelurile recursive trebuie folosite cu discernmnt, deoarece solicit i ele resursele calculatorului (timp i memorie). Analiza unui algoritm recursiv implic rezolvarea unui sistem de recurente. Vom vedea n continuare cum pot fi rezolvate astfel de recurente.
Cnd un algoritm conine o apelare recursiv la el nsui, timpul su de execuie poate fi descris adesea printr-o recuren. O recuren este o ecuaie sau o inegalitate care descrie ntregul timp de execuie al unei probleme de dimensiune n cu ajutorul timpilor de execuie pentru date de intrare de dimensiuni mici. Putem, apoi, folosi instrumente matematice
pentru a rezolva problema de recuren i pentru a obine margini ale performanei algoritmului.
O recuren pentru timpul de execuie al unui algoritm de tipul divide i stpnete se bazeaz pe cele trei etape definite n descrierea metodei. La
22
fel ca pn acum, vom nota cu T(n) timpul de execuie al unei probleme de dimensiune n. Dac dimensiunea problemei este suficient de mic, de
exemplu n c pentru o anumit constant c, soluia direct ia un timp constant de execuie, pe care l vom nota cu (1). S presupunem c divizm problema n a subprobleme, fiecare dintre acestea avnd dimensiunea de 1/b din dimensiunea problemei originale. Dac D(n) este timpul necesar pentru a divide problema n suprobleme, iar C(n) este timpul
necesar pentru a combina soluiile subproblemelor n soluia problemei originale, obinem recurena
cnnCnD
b
naT
cnn
nT,
,
5.1 Metoda master
Metoda master furnizeaz o reet pentru rezolvarea recurenelor de forma
T(n)= aT(n/b)+ f(n)
(5.1)
unde a 1 i b>1sunt constante, iar f(n) este o funcie asimptotic pozitiv. Metoda master pretinde memorarea a trei cazuri, dar apoi soluia multor recurene se poate determina destul de uor, de multe ori fr creion i hrtie.
Recurena (1.4.1) descrie timpul de execuie al unui algoritm care mparte o problem de dimensiune n n a subprobleme, fiecare de dimensiune b/n, unde a i b sunt constante pozitive. Cele a subprobleme sunt rezolvate recursiv, fiecare n timp T(n/b). Costul divizrii problemei i al combinrii rezultatelor subproblemelor este descris de funcia f(n) (Adic, utiliznd notaia f(n)=D(n) + C(n)). Din punctul de vedere al corectitudinii tehnice, recurena nu este, de fapt, bine definit, deoarece n/b ar putea s nu fie ntreg. nlocuirea fiecruia dintre cei a termeni T(n/b) fie
cu bnT fie cu bnT nu afecteaz, totui, comportamentul asimptotic al recurenei. n mod normal, ne va conveni, de aceea, s omitem funciile parte ntreag inferioar i superioar cnd scriem recurene divide i stpnete de aceast form.
23
Teorema master
Metoda master depinde de urmtoarea teorem.
Teorema 5.1.1. (teorema master) Fie a 1 i b>1 constante, fie f(n) o funcie i fie T(n) definit pe ntregii nenegativi prin recuren
T(n)= aT(n/b) + f(n)
unde interpretm n/b fie ca bn fie ca bn . Atunci T(n) poate fi delimitat asimptotic dup cum urmeaz.
1. Dac abnnf log pentru o anumit constant >0, atunci abnnT log .
2. Dac abnnf log , atunci nnnT ab lglog . 3. Dac abnnf log , pentru o anumit constant >0 i
dac ncfbnaf pentru o anumit constant c 1i toi n suficient de mari, atunci nfnT .
nainte de a aplica teorema master la cteva exemple, s ne oprim puin ca s nelegem ce spune. n fiecare dintre cele trei cazuri, comparm funcia f(n) cu funcia nlogb
a. Intuitiv, soluia recurenei este determinat de cea mai mare dintre cele dou funcii. Dac funcia nlog b
a este mai mare, ca
n cazul 1, atunci soluia este abnnT log . Dac funcia f(n) este mai mare, ca n cazul 3, atunci soluia este nfnT . Dac cele dou funcii sunt de acelai ordin de mrime, ca n cazul 2, nmulim cu un factor logaritmic, iar soluia este
nnfnnnT ab lglglog . Dincolo de aceast intuiie, exist nite detalii tehnice care trebuie
nelese. n primul caz, f(n) trebuie nu numai s fie mai mic dect nlogb
a, trebuie
s fie polinomial mai mic. Adic f(n) trebuie s fie asimptotic mai mic
dect nlogba cu un factor n pentru o anumit constant >0. n al treilea
caz, f(n) trebuie nu numai s fie mai mare dect nlogba, trebuie s fie
polinomial mai mare i, n plus, s verifice condiia de regularitate
ncfbnaf . Aceast condiie este satisfcut de majoritatea funciilor polinomial mrginite pe care le vom ntlni.
24
Este important de realizat c cele trei cazuri nu acoper toate posibilitile pentru f(n).
Exist un gol ntre cazurile 1 i 2 cnd f(n) este mai mic dect nlog ba dar
nu polinomial mai mic. Analog exist un gol ntre cazurile 2 i 3 cnd f(n) este mai mare dect nlog b
a dar nu polinomial mai mare. Dac funcia f(n) cade ntr-unul dintre aceste goluri, sau cnd condiia de regularitate din cazul 3 nu este verificat, metoda master nu poate fi utilizat pentru a rezolva recurena.
Exemplu 5.1.1.
T(n) = 9T(n/3) + n.
Pentru aceast recuren, avem a = 9, b = 3, f(n) = n i astfel nlog ba=
T(n)= nlog 39=(n2).
Deoarece f(n)= (nlog 39-), unde = 1, putem s aplicm cazul 1 al
teoremei master i s considerm c soluia este T(n)= (n2).
Exemplu 5.1.2.
T(n)=T(2n/3) + 1.
Pentru aceast recuren, avem a=1, b= 3/2, f(n)=1 i nlogba= nlog 3/21= n0
=1. Cazul 2 este cel care se aplic deoarece f(n)= (nlog ba)= (1) i astfel
soluia recurenei este
T(n)= (lg n).
Exemplu 5.1.3.
T(n) = 3T(n/4) + nlgn,
Pentru aceast recuren, avem a=3, b=4, f(n)= nlgn i nlogba=nlog34
=(n0,793). Deoarece f(n)=(nlog 43+), unde 0.2, cazul 3 se aplic dac
putem arta c pentru f(n) este verificat condiia de regularitate. Pentru n suficient de mare,
af(n/b)=3(n/4)lg (n/4) (3/4)nlgn = cf(n) pentru c = 3/4.
n consecin, din cazul 3, soluia recurenei este T(n)= (nlgn).
Exemplu 5.1.4. Metoda master nu se aplic recurenei
T(n)= 2T(n/2) + nlgn,
chiar dac are forma potrivit: a=2, b=2, f(n)= nlgn i nlogba = n. Se pare
c ar trebui s se aplice cazul 3, deoarece f(n)= nlgn este asimptotic mai mare dect nlogb
a = n, dar nu polinomial mai mare. Raportul f(n)/nlogba =
(nlgn)/n este asimptotic mai mic dect n pentru orice constant pozitiv . n consecin, recurena cade n golul dintre cazurile 2 i 3.
25
5.2. Metoda ecuaiilor caracteristice 5.2.1. Recurene liniare omogene Exist tehnici care pot fi folosite aproape automat pentru a rezolva
anumite clase de recurene. Vom considera recurene liniare omogene, de forma
a0tn + a1tn-1 + + aktn-k = 0 (5.2.1)
unde ti sunt valorile pe care le cutm, iar coeficienii ai sunt constante. Vom cuta soluii de forma
tn = xn
unde x este o constanta (deocamdat necunoscut). ncercm aceasta soluie n (5.2.1) i obinem
a0xn + a1x
n-1 + ... + akxn-k = 0.
Soluiile acestei ecuaii sunt fie soluia triviala x = 0, care nu ne intereseaz, fie soluiile ecuaiei
a0xk + a1x
k-1 + ... + ak = 0
care este ecuaia caracteristica a recurenei (1.4.2). Presupunnd deocamdat ca cele k rdcini r1, r2, ..., rk ale acestei
ecuaii caracteristice sunt distincte, orice combinaie liniar
k
i
niin rct
1
este o soluie a recurenei (5.2.1), unde constantele c1, c2, ..., ck sunt determinate de condiiile iniiale. Este remarcabil c (1.4.2) are numai soluii de aceasta form.
Exemplu 5.2.1. Recurena care definete irul lui Fibonacci:
tn = tn-1 + tn-2 n 2 iar t0 = 0, t1 = 1. Putem s rescriem aceast recurena sub forma tn - tn-1 -
tn-2 = 0 care are ecuaia caracteristica x2 - x - 1 = 0 cu rdcinile r1,2 = (15 )/2. Soluia generala are forma
nn
n rcrct 2211
Impunnd condiiile iniiale, obinem c1+c2 = 0, n = 0
r1c1 + r2c2 = 1, n = 1
de unde determinm
26
c1,2 = 1/5
Deci, nnn rrt 2151 . Observam c r1 = = (1+5)/2, r2 = - -1 i obinem tn = 1/5(
n - (-)-n) Putem s artm acum c timpul pentru algoritmul care determin irul
Fibonacci este n (n). Se poate arta c, daca r este o rdcina de multiplicitate m a ecuaiei
caracteristice, atunci
tn = rn, tn = nr
n, tn = n2rn, ..., tn = n
m-1rn
sunt soluii pentru (1.4.2). Soluia general pentru o astfel de recuren este atunci o combinaie liniar a acestor termeni i a termenilor provenii de la celelalte rdcini ale ecuaiei caracteristice. Din nou, sunt de determinat exact k constante din condiiile iniiale.
Exemplu 5.2.2. Fie recurena tn = 5tn-1 - 8tn-2 + 4tn-3 iar t0 = 0, t1 = 1, t2 = 2. Ecuaia
caracteristica
x3 - 5x2 + 8x - 4 = 0
are rdcinile 1 (de multiplicitate 1) i 2 (de multiplicitate 2). Soluia generala este:
tn = c11n + c22
n + c3n2n
Din condiiile iniiale, obinem c1 = -2, c2 = 2, c3 = -1/2.
5.2.2. Recurene liniare neomogene Consideram acum recurene de urmtoarea form mai general
a0tn + a1tn-1 + ... + aktn-k = bnp(n) (5.2.2)
unde b este o constant, iar p(n) este un polinom n n de grad d. Ideea generala este c, prin manipulri convenabile, s reducem un astfel de caz la o form omogen.
Exemplu 5.2.3.
De exemplu, o astfel de recurena poate fi: tn - 2tn-1 = 3
n
In acest caz, b = 3 si p(n) = 1, un polinom de grad 0. O simpla
manipulare ne permite s reducem acest exemplu la forma (1.4.2). nmulim recurena cu 3, obinnd 3tn - 6tn-1 = 3
n+1 . nlocuind pe n cu n+1 n
recurena iniial, avem tn+1 - 2tn = 3n+1. In fine, scdem aceste doua ecuaii
i obinem tn+1 - 5tn + 6tn-1 = 0. Am obinut o recurena omogena pe care o putem rezolva ca n
seciunea precedent. Ecuaia caracteristic este: x2 - 5x + 6 = 0
27
adic (x-2)(x-3) = 0. Intuitiv, observm c factorul (x-2) corespunde parii stngi a recurenei
iniiale, n timp ce factorul (x-3) a aprut ca rezultat al manipulrilor efectuate, pentru a scpa de partea dreapt.
Generaliznd acest procedeu, se poate arta c, pentru a rezolva (1.4.3), este suficient s lum urmtoarea ecuaie caracteristic:
(a0xk + a1x
k-1 + + ak)(x-b)d+1 = 0
Odat ce s-a obinut aceast ecuaie, se procedeaz ca in cazul omogen.
5.2.3. Schimbarea variabilei
Uneori, printr-o schimbare de variabil, putem rezolva recurene mult mai complicate. n exemplele care urmeaz, vom nota cu T(n) termenul general al recurenei i cu tk termenul noii recurene obinute printr-o schimbare de variabil. Presupunem pentru nceput ca n este o putere a lui 2.
Exemplu 5.2.4.
Fie recurena T(n) = 4T(n/2) + n, n > 1 n care nlocuim pe n cu 2k, notm tk = T(2
k) = T(n) i obinem tk = 4tk-1 + 2k. Ecuaia caracteristic a
acestei recurene liniare este (x-4)(x-2) = 0 cu ri deci,
tk = c14k + c22
k.
nlocuim la loc pe k cu lg n i obinem T(n) = c1n2 + c2n
Rezult c T(n) O(n2 | n este o putere a lui 2).
EXERCIII:
28
II. PROIECTAREA ALGORITMILOR
PRELIMINARII
1. TEHNICA DIVIDE ET IMPERA. n aceast seciune vom examina o abordare numit divide i
stpnete. Vom utiliza aceast abordare pentru a construi un algoritm de sortare. Unul din avantajele algoritmilor de tipul divide i stpnete este acela c timpul lor de execuie este adesea uor de determinat folosind tehnici date mai sus.
Muli algoritmi au o structur recursiv: pentru a rezolva o problem dat, acetia sunt apelai o dat sau de mai multe ori pentru a rezolva subproblemele apropiate. Aceti algoritmi folosesc de obicei o abordare de tipul divide i stpnete: ei rup problema de rezolvat n mai multe probleme similare problemei iniiale, dar de dimensiune mai mic, le rezolv n mod recursiv i apoi le combin pentru a crea o soluie a problemei iniiale.
Paradigma divide i stpnete implic trei pai la fiecare nivel de recursivitate:
Divide problema ntr-un numr de subprobleme.
Stpnete subproblemele prin rezolvarea acestora n mod recursiv. Dac dimensiunile acestora sunt suficient de mici, rezolv subproblemele n mod uzual, nerecursiv.
Combin soluiile tuturor subproblemelor n soluia final pentru problema iniial.
1.1. Sortarea prin interclasare.
Algoritmul de sortare prin interclasare urmeaz ndeaproape paradigma divide i stpnete. Intuitiv acesta opereaz astfel:
Divide: mparte irul de n elemente care urmeaz a fi sortat in dou subiruri de cte n/2 elemente.
Stppnete: Sorteaz recursiv cele dou subiruri utiliznd sortarea prin interclasare.
Combin: Interclaseaz cele dou subiruri sortate pentru a produce rezultatul final.
S observm c recursivitatea se oprete cnd irul de sortat are lungimea 1,caz n care nu mai avem nimic de fcut, deoarece orice ir de lungime 1 este deja sortat.
29
Operaia principal a algoritmului de sortare prin interclasare este interclasarea a dou iruri sortate, n pasul denumit mai sus combin. Pentru aceasta vom utiliza o procedur auxiliar MERGE(A,p,q,r), unde A este vector, i p,q,r sunt indici ai vectorului, astfel nct p q < r. Procedura presupune c subvectorii A[p..q] i A[q+1..r] sunt sortai. Ea interclaseaz pentru a forma un subvector sortat care nlocuiete subvectorul curent A[p..r].
Dei vom lsa pseudocodul pentru aceast procedur ca exerciiu, este uor de imaginat o procedur de tip MERGE al crei timp de execuie este de ordinul (n), n care n = r p + 1 este numrul elementelor interclasate. Revenind la exemplul nostru cu crile de joc, s presupunem c avem dou pachete de cri de joc aezate pe mas cu faa n sus. Fiecare dintre aceste dou pachete de cri este sortat, cartea cu valoarea cea mai mic fiind deasupra. Dorim s amestecm cele dou pachete ntr-un singur pachet sortat, care s rmn aezat pe mas cu faa n jos. Pasul principal este acela de a selecta cartea cu valoarea cea mai mic dintre cele dou aflate deasupra pachetelor (fapt care va face ca o nou carte s fie deasupra pachetului respectiv) i de a o pune cu faa n jos pe locul n care se va forma pachetul sortat final. Repetm acest procedeu pn cnd unul din pachete nu este iepuizat. n aceast faz, este suficient s lum pachetul rmas i s-l punem pe pachetul deja sortat, ntorcnd toate crile cu faa n jos. Din punctul de vedere al timpului de execuie, fiecare pas de baz dureaz un timp constant, deoarece comparm de fiecare dat doar dou cri. Deoarece avem de fcut cel mult n astfel de operaii elementare, timpul de execuie pentru procedura MERGE este (n).
MERGE- SORT (A, p, r)
1. if p r 2. then q [(p + r)/2] 3. MERGE-SORT (A, p, q)
4. MERGE-SORT (A, q+1, r)
5. MERGE (A, p, q, r)
Acum putem utiliza procedura MERGE ca subrutin pentru algoritmul de sortare prin interclasare.
Procedura MERGE- SORT (A, p, r) sorteaz elementele din
subvectorul Ap,..r. Dac p r, subvectorul are cel mult un element i este, prin urmare, deja sortat. Astfel pasul de divizare este prezent aici prin
simplul calcul al unui indice q care mparte Ap..r n doi subvectori
Ap..q, coninnd n/2 elemente i Aq+1..r coninnd n/2 elemente.
30
Pentru a sorta ntregul ir A = A1, A2,..An, vom apela procedura
MERGE-SORT (A, 1, lungime A ), unde din nou , lungime A = n. Dac analizm modul de operare al procedurii, de jos n sus, cnd n este o putere a lui 2, algoritmul const din interclasarea perechilor de iruri de lungime 1, pentru a forma iruri sortate de lungime 2, interclasarea acestora n iruri sortate de lungime 4, i aa mai departe, pn cnd dou iruri sortate de lungime n/2 sunt interclasate pentru a forma irul sortat de dimensiune n. Figura 2.1 ilustreaz acest proces.
ir ordonat
Fig. 1.1. Modul de operare al sortrii prin interclasare asupra vectorului A= . Lungimile irurilor sortate, n curs de interclasare,
cresc pe msur ce algoritmul avanseaz de jos n sus.
1.1.1 Analiza algoritmilor de tipul divide i stpnete Cnd un algoritm conine un apel recursiv la el nsui, timpul su de
execuie poate fi, adesea, descris printr-o relaie de recuren sau mai simplu, recuren, care descrie ntregul timp de execuie al unei probleme de dimensiune n cu ajutorul timpilor de execuie pentru date de intrare de dimensiuni mai mici. Putem, apoi, folosi instrumente matematice pentru a
rezolva problema de recuren i pentru a obine margini ale performanei algoritmului.
O recuren pentru timpul de execuie al unui algoritm de tipul divide i stpnete se bazeaz pe cele trei etape definite n descrierea metodei. La
1 2 2 3 4 5 6
6
2 4 5 6 1 2 3 6
2 5 4 6 1 3 2 6 6
1 3 2 6 5 2 4 6
31
fel ca pn acum, vom nota cu T(n) timpul de execuie al unei probleme de dimensiune n. Dac dimensiunea problemei este suficient de mic, de
exemplu n c pentru o anumit constant c, soluia direct ia un timp constant de execuie, pe care l vom nota cu (1). S presupunem c divizm problema n a subprobleme, fiecare dintre acestea avnd dimensiunea de b ori mai mic dect dimensiunea problemei originale. Dac D(n) este timpul necesar pentru a divide problema n suprobleme, iar C(n) este timpul necesar pentru a combina soluiile subproblemelor n soluia problemei originale, obinem recurena
1.1.2. Analiza sortrii prin interclasare Dei algoritmul MERGE-SORT funcioneaz corect i cnd numrul
de elemente nu este par, analiza bazat pe recuren se simplific dac presupunem c dimensiunea problemei originale este o putere a lui 2. Fiecare pas de mprire genereaz deci dou subiruri avnd dimensiunea exact n/2. n continuare vom vedea c aceast presupunere nu afecteaz ordinul de cretere a recurenei.
Pentru a determina recurena pentru T(n), timpul de execuie al sortrii prin interclasare a n numere, n cazul cel mai defavorabil, vom raiona n felul urmtor. Sortarea prin interclasare a unui singur element are
nevoie de un timp constant. Cnd avem n1 elemente, vom descompune timpul de execuie dup cum urmeaz:
Divide: La acest pas, se calculeaz doar mijlocul subvectorului, calcul
care are nevoie de un timp constant de execuie. Astfel, D(n) = (1). Stpnete: Rezolvm recursiv dou probleme fiecare de dimensiune
n/2,care contribuie cu 2T(n/2) la timpul de execuie. Combin: Am observat, deja c procedura MERGE pentru un
subvector cu n elemente consum (n) timp de execuie, deci C(n)= (n).
Cnd adunm funciile D(n) i C(n) pentru analiza sortrii prin
interclasare, adunm o funcie cu timpul de execuie (1). Aceast sum
este o funcie linear n raport cu n, adic are timpul de execuie (n). Adugnd aceasta la termenul 2T(n/2) de la pasul stpnete, obinem timpul de execuie T(n) in cazul cel mai defavorabil pentru sortarea prin interclasare:
cnnCnDbnaT
cnnT
),()()/(
),1()(
32
Se poate arta c T(n) este (nlgn) unde lgn reprezint log2n. Pentru numere suficient de mari, sortarea prin interclasare, are timpul de execuie
(nlgn).
2. TEHNICA GREEDY
Algoritmii greedy (greedy = lacom) sunt n general simpli i sunt folosii pentru rezolvarea problemelor de optimizare, cum ar fi: s se gseasc cea mai bun ordine de executare a unor lucrri pe calculator, s se gseasc cel mai scurt drum ntr-un graf etc. Algoritmii aplicai problemelor de optimizare sunt compui dintr-o secven de pai, la fiecare pas existnd mai multe alegeri posibile Un algoritm greedy va alege la
fiecare moment de timp soluia ce pare a fi cea mai bun la momentul respectiv. Deci este vorba despre o alegere optim, fcut local, cu sperana c ea va conduce la un optim global. Acest capitol trateaz probleme de optimizare ce pot fi rezolvate cu ajutorul algoritmilor greedy.
Algoritmii greedy conduc n multe cazuri la soluii optime, dar nu ntotdeauna.
2.1. O problem de selectare a activitilor Primul exemplu pe care l vom considera este o problem de repartizare
a unei resurse mai multor activiti care concureaz pentru a obine resursa respectiv. Vom vedea ca un algoritm de tip greedy reprezint o metod simpl i elegant pentru selectarea unei mulimi maximale de activiti mutual compatibile.
S presupunem c dispunem de o mulime S = 1,2,..., n de n activiti care doresc sa foloseasc o aceeai resurs (de exemplu o sal de lectur). Aceast resurs poate fi folosita de o singur activitate la un anumit moment de timp. Fiecare activitate i are un timp de pornire si i un timp de
oprire fi, unde si fi . Dac este selecionat activitatea i, ea se desfoar pe durata intervalului [si, fi). Spunem c activitile i i j sunt compatibile dac intervalele [si, fi) i [sj, fj) nu se intersecteaz (adic i i j sunt
compatibile dac si fj sau sj fi). Problema selectrii activitilor const din selectarea unei mulimi maximale de activiti mutual compatibile.
Un algoritm greedy pentru aceast problem este descris de urmtoarea procedur, prezentat n pseudocod. Vom presupune c activitile (adic datele de intrare) sunt ordonate cresctor dup timpul de terminare:
1),()2/(2
1),1()(
nnnT
nnT
33
f1 f2 ... fn (2.1) n caz contrar aceast ordonare poate fi fcut n timp O(nlgn).
Algoritmul de mai jos presupune c datele de intrare s i f sunt reprezentate ca vectori.
SELECTOR-ACTIVITI-GREEDY (s, f)
1: n lungime[s]
2: A {1}
3: j 1
4: for i 2 to n do
5: if si fj then
6: A A U {i}
7: j i 8: returneaz A
Operaiile realizate de algoritm pot fi vizualizate n figura 2.1. n mulimea A se introduc activitile selectate. Variabila j identific ultima activitate introdus n A. Deoarece activitile sunt considerate n ordinea nedescresctoare a timpilor lor de terminare, fj, va reprezenta ntotdeauna timpul maxim de terminare a oricrei activiti din A. Aceasta nseamn c
fj = max{fk : A} (2.2) n liniile 2-3 din algoritm se selecteaz activitatea 1, se iniializeaz A
astfel nct s nu conin dect aceast activitate, iar variabila j ia ca valoare aceast activitate. n continuare liniile 4-7 consider pe rnd fiecare activitate i i o adaug mulimii A dac este compatibil cu toate celelalte activiti deja selectate. Pentru a vedea dac activitatea i este compatibil cu toate celelalte activiti existente la momentul curent n A, este suficient, conform formulei (2.2), s fie ndeplinit condiia din linia 5 adic momentul de pornire si, s nu fie mai devreme dect momentul de oprire fj, al activitii cel mai recent adugate mulimii A. Dac activitatea i este compatibil, atunci n liniile 6-7 ea este adugat mulimii A, iar variabila j este actualizat. Procedura SELECTOR-ACTIVITI-GREEDY este
foarte eficient. Ea poate planifica o mulime S de n activiti n (n), presupunnd c activitile au fost deja ordonate dup timpul lor de terminare. Activitatea aleas de procedura SELECTOR-ACTIVITI-GREEDY este ntotdeauna cea cu primul timp de terminare care poate fi
planificat legal. Activitatea astfel selectat este o alegere "greedy" (lacom) n sensul c, intuitiv, ea las posibilitatea celorlalte activiti rmase pentru a fi planificate. Cu alte cuvinte, alegerea greedy maximizeaz cantitatea de timp neplanificat rmas.
34
i s
i
f
i
1 1 4
2 3 5
3 0 6
4 5 7
5 3 8
6 5 9
7 6 1
0
8 8 1
1
9 8 1
2
1
0
2 1
3
1
1
1
2
1
4
Figura 2.1. Operaiile algoritmului SELECTOR-ACTIVITI-GREEDY asupra celor 11 activiti date n stnga. Fiecare linie a figurii corespunde unei iteraii din ciclul pentru din liniile 4-7. Activitile care au fost selectate pentru a fi incluse n mulimea A sunt haurate, iar activitatea curent i este nehaurat. Dac timpul de pornire si, al activitii i este mai mic dect timpul de terminare al activitii j (sgeata dintre ele este spre
timp
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14
1
1
1
1
1
1
1
1
1
1
1
4 8
8
8
4
4
4
4
4
4
4
8
11
11
10
9
8
7
6
5
4
3
2
35
stnga), activitatea este ignorat, n caz contrar (sgeata este ndreptat spre dreapta), activitatea este acceptat i este adugat mulimii A.
2.1.1. Demonstrarea corectitudinii algoritmului greedy
Algoritmii de tip greedy nu furnizeaz ntotdeauna soluiile optime. Cu toate acestea, algoritmul SELECTOR-ACTIVITI-GREEDY determin ntotdeauna o soluie optim pentru o instan a problemei selectrii activitilor.
Teorema 2.1. Algoritmul SELECTOR-ACTIVITI-GREEDY furnizeaz soluii de dimensiune maxim pentru problema selectrii activitilor.
Demonstraie. Fie S = {1,2,..., n} mulimea activitilor care trebuie planificate. Deoarece presupunem c activitile sunt ordonate dup timpul de terminare, activitatea 1 se va termina cel mai devreme. Vrem s artm c exist o soluie optim care ncepe cu activitatea 1, conform unei alegeri greedy.
S presupunem c A S este o soluie optim pentru o instan dat a problemei selectrii activitilor. Vom ordona activitile din A dup timpul de terminare. Mai presupunem c prima activitate din A este activitatea k.
Dac k = 1, planificarea mulimii A ncepe cu o alegere greedy. Dac k 1 vrem s artm c exist o alt soluie optim B a lui S care ncepe conform
alegerii greedy, cu activitatea l. Fie B =A - {k} U {l}. Deoarece f1 fk, activitile din B sunt distincte, i cum B are acelai numr de activiti ca i A, B este de asemenea optim. Deci B este o soluie optim pentru S, care conine alegerea greedy a activitii 1. Am artat astfel c exist ntotdeauna o planificare optim care ncepe cu o alegere greedy.
Mai mult, o dat ce este fcut alegerea greedy a activitii 1, problema se reduce la determinarea soluiei optime pentru problema selectrii acelor activiti din S care sunt compatibile cu activitatea 1. Aceasta nseamn c dac A este o soluie optim pentru problema iniial, atunci A' = A -{1} este o soluie optim pentru problema selectrii activitilor
S' = {i S, si f1}. De ce? Dac am putea gsi o soluie B' pentru S' cu mai multe activiti dect A', adugarea activitii 1 la B' va conduce la o soluie B a lui S cu mai multe activiti dect A, contrazicndu-se astfel optimalitatea mulimii A. n acest mod, dup ce este fcut fiecare alegere greedy, ceea ce rmne este o problem de optimizare de aceeai form ca problema iniial. Prin inducie dup numrul de alegeri fcute, se arat c realiznd o alegere greedy la fiecare pas, se obine o soluie optim.
36
2.2. Coduri Huffman
Codurile Huffman reprezint o tehnic foarte utilizat i eficient pentru compactarea datelor; n funcie de caracteristicile fiierului care trebuie comprimat, spaiul economisit este ntre 20% i 90%. Algoritmul greedy pentru realizarea acestei codificri utilizeaz un tabel cu frecvenele de apariie ale fiecrui caracter. Ideea este de a utiliza o modalitate optim pentru reprezentarea fiecrui caracter sub forma unui ir binar.
Sa presupunem c avem un fiier ce conine 100.000 de caractere, pe care dorim s l memorm ntr-o form compactat. Frecvenele de apariie ale caracterelor n text sunt date de figura 2.2: exist doar ase caractere diferite i fiecare dintre ele apare de 45.000 de ori.
a b c d e f
Frecvena(n mii) 4
5 13 12 16 9 5
Cuvnt codificat; lungime fix 0
00 001 010 011 100 101
Cuvnt codificat; lungime
variabil 0 101 100 111 1101 1100
Figura 2.2. O problem de codificare a caracterelor. Un fiier de
100.000 de caractere conine doar caracterele a-f, cu frecvenele indicate. Dac fiecrui caracter i este asociat un cuvnt de cod pe 3 bii, fiierul codificat va avea 300.000 de bii. Folosind codificarea cu lungime variabil, fiierul codificat va ocupa doar 224.000 de bii.
Exista mai multe modaliti de reprezentare a unui astfel de fiier. Vom considera problema proiectrii unui cod binar al caracterelor (pe scurt cod) astfel nct fiecare caracter este reprezentat printr-un i binar unic. Dac utilizm un cod de lungime fix, avem nevoie de 3 bii pentru a reprezenta
ase caractere: a=000,b=001, ...,f=101. Aceast metod necesit 300.000 de bii pentru a codifica tot fiierul. Se pune problema dac se poate face o compactare i mai bun.
O codificare cu lungime variabil poate mbunti semnificativ performanele, atribuind caracterelor cu frecvene mai mari cuvinte de cod mai scurte iar celor cu frecvene mai reduse cuvinte de cod mai lungi. Figura 2.3(b) prezint o astfel de codificare; irul 0 avnd lungimea de 1
bit reprezint caracterul a in timp ce irul 1100 de lungime 4 reprezint
caracterul f. Aceast codificare necesit (45 1 + 13 3 4-12 3 + 16 3 + 9 4 + 5 4) 1.000 = 224.000 bii pentru a reprezenta un fiier i
37
economisete aproximativ 25% din spaiu. Vom vedea c aceasta este de fapt o codificare-caracter optim pentru acest fiier.
Figura 2.3. Arborii corespunztori schemelor de codificare din figura 2.2. Fiecare frunz este etichetat cu un caracter i cu frecvena de apariie a acestuia. Fiecare nod intern este etichetat cu suma ponderilor frunzelor
din subarborele aferent. (a) Arborele corespunztor codificrii de lungime
fix a=000,...,f=101. (b) Arborele asociat codificrii prefix optime
a=0,b=101,...,f=1100.
2.2.1. Coduri prefix
Vom considera n continuare doar codificrile n care nici un cuvnt de cod nu este prefixul altui cuvnt. Astfel de codificri se numesc codificri prefix. Se poate arta c o compresie optim a datelor, realizat prin codificarea caracterelor, poate fi realizat i prin codificarea prefix, deci considerarea codificrii prefix nu scade din generalitate.
Codificarea prefix este util deoarece simplific att codificarea (deci compactarea) ct i decodificarea. Codificarea este ntotdeauna simpl pentru orice codificare binar a caracterelor; se concateneaz cuvintele de cod reprezentnd fiecare caracter al fiierului. De exemplu, prin codificarea prefix avnd lungime variabila din figura 17.3, putem codifica un fiier de
3 caractere abc astfel: 0101100=0101100, unde semnul "" reprezint operaia de concatenare.
Decodificarea este de asemenea relativ simpl pentru codurile prefix. Cum nici un cuvnt de cod nu este prefixul altuia. nceputul oricrui fiier codificat, nu este ambiguu. Putem deci sa identificm cuvntul iniial de cod, s l ''traducem'' in caracterul original, s-l ndeprtm din fiierul codificat i s repetm procesul pentru fiierul codificat rmas. n exemplul
100
14
0
140
86
28 58
e:9 f:5 d:16 c:12 b:13 a:45
1 0
1
0
0
1
1 1 0 0
0
100
55
1 0
a:45
25
b:13 c:12
1 0 30
d:16
1 0
14
e:9 f:5
1 0
(b) (a)
38
nostru, irul 001011101 se translateaz automat n 001011101, secven
care se decodific n aabe. Procesul de decodificare necesit o reprezentare convenabil a
codificrii prefix astfel nct cuvntul iniial de cod sa poat fi uor identificat. O astfel de reprezentare poate fi dat de un arbore binar ale crui frunze sunt caracterele date. Interpretm un cuvnt de cod binar pentru un caracter ca fiind drumul de la rdcina pn la caracterul respectiv, unde 0 reprezint "mergi la fiul stng" iar 1 ''mergi la fiul drept". n figura 3 sunt prezentai arborii pentru cele dou codificri ale exemplului nostru. Observai c acetia nu sunt arbori binari de cutare. deoarece frunzele nu trebuie s fie ordonate, iar nodurile interne nu conin chei pentru caractere.
O codificare optim pentru un fiier este ntotdeauna reprezentat printr-un arbore binar complet, n care fiecare vrf care nu este frunz are doi fii.
Codificarea cu lungime fix din exemplul de mai sus nu este optim deoarece arborele asociat, prezentat n figura 3(a), nu este un arbore binar
complet: exist dou cuvinte de cod care ncep cu 10..., dar nici unul care s nceap cu 11.... Conform celor de mai sus ne putem restrnge atenia numai asupra arborilor binari complei, deci dac C este alfabetul din care fac parte caracterele, atunci arborele pentru o codificare prefix optim are exact |C| frunze, una pentru fiecare liter din alfabet, i exact |C| - 1 noduri interne.
Dndu-se un arbore T, corespunztor unei codificri prefix, este foarte simplu s calculm numrul de bii necesari pentru a codifica un fiier. Pentru fiecare caracter c din alfabet, fie f(c) frecvena lui c n fiier i s notm cu dT(c) adncimea frunzei n arbore (adic nivelul pe care se afl). S observm c dT(c) reprezint de asemenea cuvntul de cod pentru caracterul c. Numrul de bii necesari pentru a codifica un fiier este
( ) ( ) ( )Tc C
B T f c d c
Vom numi acest numr costul arborelui r.
2.2.2. Construcia unui cod Huffman Huffman a inventat un algoritm greedy care construiete o codificare
prefix optim numit codul Huffman. Algoritmul construiete arborele corespunztor codificrii optime, ntr-o manier "bottom-up". Se ncepe cu o mulime de | C| frunze i se realizeaz o secven de | C | -1 operaii de interclasare pentru a crea arborele final.
39
n algoritmul care urmeaz, vom presupune c C este o mulime de n
caractere i fiecare caracter c C este un obiect avnd o frecven dat f[c]. Va fi folosit o coad de prioriti pentru a identifica cele dou obiecte cu frecvena cea mai redus care vor fuziona. Rezultatul interclasrii celor dou obiecte este un nou obiect a crui frecven este suma frecvenelor celor dou obiecte care au fost interclasate.
HUFFMAN (C)
1: n |C|
2: Q C
3: pentru i l, n 1 execut
4: z ALOC-NOD()
5: x stnga[z} EXTRAGE+MIN(Q)
6: y dreapta[z] EXTRAGE-MIN(Q)
7: f z fx+f y 8: INSEREAZ (Q,3)
9: returneaz EXTRAGE-MIN(Q)
Pentru exemplul nostru, algoritmul lui Huffman lucreaz ca n figura 2.3. Deoarece exist 6 litere n alfabet, dimensiunea iniial a cozii este n = 6, iar pentru a construi arborele sunt necesari 5 pai de interclasare. Arborele final reprezint codificarea prefix optim. Codificarea unei litere este secvena etichetelor nodurilor ce formeaz drumul de la rdcin la liter.
n linia 2 coada de prioriti Q este iniializat cu caracterele din C. Ciclul for din liniile 3-8 extrage n mod repetat dou noduri x i y cu cea mai mic frecven din coad, i le nlocuiete n coad cu un nou nod z, reprezentnd fuziunea lor. Frecvena lui z este calculat n linia 7 ca fiind suma frecvenelor lui x i y. Nodul z are pe x ca fiu stng i pe y ca fiu drept. (Aceast ordine este arbitrar; interschimbarea fiilor stng i drept ai oricrui nod conduce la o codificare diferit, dar de acelai cost.) Dup n - 1 fuzionri, unicul nod rmas n coad, rdcina arborelui de codificare, este returnat n linia 9.
2.2.3. Corectitudinea algoritmului lui Huffman
Pentru a demonstra c algoritmul de tip greedy al lui Huffman este corect, vom arta c problema determinrii unei codificri prefix optime implic alegeri greedy i are o substructur optim. Urmtoarea lem se refer la proprietatea alegerii greedy.
Lema 2.1. Fie C un alfabet n care fiecare caracter c C are frecvena f [c]. Fie x i y dou caractere din C avnd cele mai mici frecvene. Atunci
40
exist o codificare prefix optim pentru C n care cuvintele de cod pentru x i y au aceeai lungime i difer doar pe ultimul bit.
Demonstraie. Ideea demonstraiei este de a lua arborele T reprezentnd o codificare prefix optim i a-l modifica pentru a realiza un arbore reprezentnd o alt codificare prefix optim. n noul arbore, caracterele x i y vor apare ca frunze cu acelai tat i se vor afla pe nivelul maxim n arbore. Dac putem realiza acest lucru, atunci cuvintele lor de cod vor avea aceeai lungime i vor diferi doar pe ultimul bit.
Fie b i c dou caractere reprezentnd noduri terminale (frunze) situate pe nivelul maxim al arborelui T. Fr a restrnge generalitatea, vom
presupune c fb f[c] i f[x f[y. Cum f[x i f[y sunt frunzele cu
frecvenele cele mai sczute, in aceast ordine, iar fb i f[c] sunt deci
frecvene arbitrare, n ordine, avem f[x f[b] i f[y f[c. Dup cum se vede in figura 2.5, vom schimba n T poziiile lui b i x pentru a produce arborele T', iar apoi vom schimba n T' poziiile lui c i y pentru a obine arborele T". Conform ecuaiei (17.3), diferena costurilor lui T i T' este
( ) ( ) ( ) ( ) ( ) ( )
[ ] ( ) [ ] ( ) [ ] ( ) [ ] ( )
[ ] ( ) [ ] ( ) [ ] ( ) [ ] ( )
( [ ] [ ])( ( ) ( )) 0,
T T
c C c C
T T T T
T T T T
T T
B T B T f c d c f c d c
f x d x f b d b f x d x f b d b
f x d x f b d b f x d b f b d x
f b f x d b d x
deoarece att f[b] - f[x] i [ ]Td b - [ ]Td x sunt nenegative. Mai precis,
f[b] - f[x] este nenegativ deoarece x este frunz avnd frecvena minim
iar [ ]Td b - [ ]Td x este nenegativ pentru c b este o frunz aflat pe nivelul
maxim n T. n mod analog, deoarece interschimbarea lui y cu c nu mrete
costul, diferena B(T) B(T") este nenegativ. Astfel B(T) B(T"), ceea ce implic B(T") = B(T). Aadar T" este un arbore optim n care x i y apar ca noduri terminale frai, i se afl pe nivelul maxim, ceea ce trebuia demonstrat.
41
f:5 e:9 c:12 b:13 d:16 a:45 (a)
f:5 e:9 c:12 b:13
d:16 a:45 (c)
25 14
1 0 1 0
c:12 b:13 d:16 a:45 (b)
f:5 e:9
14
1 0
c:12 b:13
25
1 0
30
1 0
d:16 14
1 0
f:5 e:9
a:45 (d)
c:12 b:13
25
1 0
30
1 0
d:16 14
1 0
f:5 e:9
55 a:45
1 0
(e)
c:12 b:13
25
1 0
30
1 0
d:16 14
1 0
f:5 e:9
55
1 0
1 0
a:45 (f)
Din lema 2.1 se deduce faptul ca procesul de construcie a unui arbore optim prin fuzionri poate, fr a restrnge generalitatea. s nceap cu o alegere greedy a interclasrii acelor dou caractere cu cea mai redus frecven. De ce este aceasta o alegere greedy? Putem interpreta costul unei singure interclasri ca fiind suma frecvenelor celor dou obiecte care fuzioneaz. La fiecare pas, dintre toate interclasrile posibile, algoritmul HUFFMAN o alege pe aceea care determin costul minim.
42
Figura 2.4 Paii algoritmului Huffman pentru frecvenele date n figura 17.3. Fiecare parte ilustreaz coninutul cozii ordonate cresctor dup frecven. La fiecare pas, cei doi arbori cu cele mai sczute frecvene fuzioneaz. Frunzele figureaz ca dreptunghiuri ce conin un caracter i frecvena sa. Nodurile interne figureaz ca cercuri ce conin suma frecvenelor fiilor lor. O muchie care leag un nod intern cu fiii ei este etichetat cu 0 dac este o muchie ctre un fiu stng, respectiv cu 1 dac este ctre fiul drept. Cuvntul de cod pentru o liter este secvena etichetelor de pe muchiile care leag rdcina de frunza asociat caracterului respectiv. (a) Mulimea iniial de n=6 noduri, unul pentru fiecare liter. (b)-(e) Etape intermediare. (f) Arborele final.
Lema 2.2. Fie T un arbore binar complet reprezentnd o codificare
prefix optim peste un alfabet C, unde frecvena f[c] este definit pentru
fiecare caracter c C. Considerm dou caractere x i y oarecare care apar ca noduri terminale frai n T, i fie z tatl lor. Atunci, considernd z ca un
caracter avnd frecvena f[z = f[x + f[y], arborele T' = T - {x,y} reprezint o codificare prefix optim pentru alfabetul C' = C -{x,y} {z}.
Demonstraie. Vom arta mai nti c B(T), costul arborelui T, poate fi exprimat n funcie de costul B(T') al arborelui T' considernd costurile
componente din ecuaia (17.3). Pentru fiecare c C - {x,y}, avem [ ]Td c =
[ ]Td c , i f[c] [ ]td c = fc] [ ]td c . Cum [ ]Td x = [ ]Td y = [ ]Td z + 1, avem
[ ] ( ) [ ] ( ) [ ] [ ]) ( ) 1) [ ] ( ) ( [ ] [ ]),T T T Tf x d x f y d y f x f y d z f z d z f x f y
de unde deducem c
( ) ( ) [ ] [ ] .B T B T f x f y
43
Dac T' reprezint o codificare prefix care nu este optim pentru alfabetul C', atunci exist un arbore T" ale crui frunze sunt caractere n C' astfel nct B(T") < B(T'). Cum z este tratat ca un caracter n C', el va apare
ca frunz n T". Dac adugm x i y ca fiind fiii lui z in T", atunci vom
obine o codificare prefix pentru C avnd costul B(T") + f[x + f[y] < B(T), ceea ce intr n contradicie cu optimalitatea lui T. Deci T' trebuie s fie optim pentru alfabetul C'.
Figura 2.5 O ilustrare a pasului cheie din demonstraia lemei 2.1. n arborele optim T, b i c sunt dou dintre frunzele aflate pe cel mai de jos nivel n arbore; aceste noduri se consider frai. x i y sunt dou frunze pe care algoritmul Huffman le interclaseaz primele; ele apar n poziii arbitrare n T. Frunzele b i x sunt interschimbate pentru a obine arborele T'. Apoi, frunzele c i y sunt interschimbate pentru a obine arborele T". Cum cele dou interschimbri nu mresc costul, arborele rezultat T" este de asemenea un arbore optim.
2.3. Arbori pariali de cost minim Fie G = un graf neorientat conex, unde V este mulimea
vrfurilor si M este mulimea muchiilor. Fiecare muchie are un cost nenegativ (sau o lungime nenegativ). Problema este sa gsim o
submulime A M, astfel nct toate vrfurile din V sa rmn conectate atunci cnd sunt folosite doar muchii din A, iar suma lungimilor muchiilor
din A sa fie cat mai mica. Cutam deci o submulime A de cost total minim. Aceasta problema se mai numete si problema conectrii oraelor cu cost minim, avnd numeroase aplicaii.
Graful parial este un arbore si este numit arborele parial de cost minim al grafului G (minimal spanning tree). Un graf poate avea mai
muli arbori pariali de cost minim si acest lucru se poate verifica pe un exemplu.
Vom prezenta doi algoritmi greedy care determina arborele parial de cost minim al unui graf. In terminologia metodei greedy, vom spune ca o
mulime de muchii este o soluie, daca constituie un arbore parial al
x
y
y x
T T/
b
y
c x
T//
@
' b
c
y x
44
grafului G, si este fezabila, daca nu conine cicluri. O mulime fezabil de muchii este promitoare, daca poate fi completata pentru a forma soluia optima. O muchie atinge o mulime data de vrfuri, daca exact un capt al muchiei este in mulime. Urmtoarea proprietate va fi folosita pentru a demonstra corectitudinea celor doi algoritmi.
Proprietatea 2.1 Fie G = un graf neorientat conex in care fiecare
muchie are un cost nenegativ. Fie W V o submulime stricta a vrfurilor
lui G si fie A M o mulime promitoare de muchii, astfel nct nici o muchie din A nu atinge W. Fie m muchia de cost minim care atinge W.
Atunci, A {m} este promitoare. Demonstraie: Fie B un arbore parial de cost minim al lui G, astfel
nct A B (adic, muchiile din A sunt coninute in arborele B). Un astfel
de B trebuie sa existe, deoarece A este promitoare. Daca m B, nu mai
rmne nimic de demonstrat. Presupunem ca m B. Adugndu-l pe m la B, obinem exact un ciclu (Exercitiul3.2). In acest ciclu, deoarece m atinge W, trebuie sa mai existe cel puin o muchie m' care atinge si ea pe W (altfel, ciclul nu se nchide). Eliminndu-l pe m', ciclul dispare si obinem un nou arbore parial B' al lui G. Costul lui m este mai mic sau egal cu costul lui m', deci costul total al lui B' este mai mic sau egal cu costul total al lui B.
De aceea, B' este si el un arbore parial de cost minim al lui G, care include
pe m. Observam ca A B' deoarece muchia m', care atinge W, nu poate fi
in A. Deci, A {m} este promitoare.
Mulimea iniiala a candidailor este M. Cei doi algoritmi greedy aleg muchiile una cate una intr-o anumita ordine, aceasta ordine fiind specifica
fiecrui algoritm.
2.3.1. Algoritmul lui Kruskal
Arborele parial de cost minim poate fi construit muchie, cu muchie, dup urmtoarea metoda a lui Kruskal (1956): se alege nti muchia de cost minim, iar apoi se adaug repetat muchia de cost minim nealeas anterior si care nu formeaz cu precedentele un ciclu. Alegem astfel #V1 muchii. Este uor de dedus ca obinem in final un arbore. Este ns acesta chiar arborele parial de cost minim cutat?
nainte de a rspunde la ntrebare, sa consideram, de exemplu, graful din Figura 2.6(a). Ordonam cresctor (in funcie de cost) muchiile grafului: {1, 2}, {2, 3}, {4, 5}, {6, 7}, {1, 4}, {2, 5}, {4, 7}, {3, 5}, {2, 4}, {3, 6},
{5, 7}, {5, 6} si apoi aplicam algoritmul. Structura componentelor conexe
este ilustrata, pentru fiecare pas, in Figura 2.7.
45
Figura 2.6 Un graf si arborele su parial de cost minim.
Figura 2.7 Algoritmul lui Kruskal aplicat grafului din Figura 2.6(a)
Mulimea A este iniial vida i se completeaz pe parcurs cu muchii acceptate (care nu formeaz un ciclu cu muchiile deja existente in A). In final, mulimea A va conine muchiile {1, 2}, {2, 3}, {4, 5}, {6, 7}, {1, 4}, {4, 7}. La fiecare pas, graful parial formeaz o pdure de componente conexe, obinut din pdurea precedenta unind dou
Pasul Muchia
considerata
Componentele conexe ale
subgrafului
iniializare {1}, {2}, {3}, {4}, {5}, {6}, {7} 1 {1, 2} {1, 2}, {3}, {4}, {5}, {6}, {7}
2 {2, 3} {1, 2, 3}, {4}, {5}, {6}, {7}
3 {4, 5} {1, 2, 3}, {4, 5}, {6}, {7}
4 {6, 7} {1, 2, 3}, {4, 5}, {6, 7}
5 {1, 4} {1, 2, 3, 4, 5}, {6, 7}
6 {2, 5} respinsa (formeaz ciclu) 7 {4, 7} {1, 2, 3, 4, 5, 6, 7}
46
componente. Fiecare component conex este la rndul ei un arbore parial de cost minim pentru vrfurile pe care le conecteaz. Iniial, fiecare vrf formeaz o componenta conexa. La sfrit, vom avea o singur component conex, care este arborele parial de cost minim cutat (Figura 2.6(b)).
Ceea ce am observat n acest caz particular este valabil i pentru cazul general, din Proprietatea 2.1 rezultnd:
Proprietatea 2.2 n algoritmul lui Kruskal, la fiecare pas, graful parial formeaz o pdure de componente conexe, n care fiecare component conex este la rndul ei un arbore parial de cost minim pentru vrfurile pe care le conecteaz. In final, se obine arborele parial de cost minim al grafului G.
Pentru a implementa algoritmul, trebuie s putem manipula submulimile formate din vrfurile componentelor conexe. Folosim pentru aceasta o
structur de mulimi disjuncte si procedurile de tip find si merge (Vezi disciplina Structuri de date i algoritmi). In acest caz, este preferabil s reprezentam graful ca o list de muchii cu costul asociat lor, astfel nct s putem ordona aceast list n funcie de cost. Iat algoritmul:
KRUSCAL(G = )
1. {iniializare} 2. sorteaz M cresctor in funcie de cost
3. n #V
4. A {va conine muchiile arborelui parial de cost minim} 5. {iniializeaz n mulimi disjuncte coninnd fiecare cate un element din V}
{bucla greedy}
repeat
{u, v} muchia de cost minim care nc nu a fost considerata
ucomp find(u)
vcomp find(v)
if ucomp vcomp then merge(ucomp, vcomp)
A A {{u, v}} until #A = n-1
return A
47
Pentru un graf cu n vrfuri si m muchii, presupunnd ca se folosesc
procedurile find3 si merge3, numrul de operaii pentru cazul cel
