analiza algoritmilor

Proiectarea algoritmilor Cornelia Novac Ududec

Complexitatea unei probleme Un algoritm rezolv o problem. Adesea pentru a rezolva o aceeai problem putem folosi mai muli algoritmi, poate cu complexiti diferite. Exist cel puin 30 de metode de a sorta un ir de valori, de exemplu! Putem vorbi deci de complexitatea unui algoritm, dar i de complexitatea unei probleme. Complexitatea unei probleme este complexitatea celui mai ``rapid'' algoritm care o poate rezolva. Complexitatea unei probleme este deci o limit inferioar a eficacitii cu care putem rezolva o problem: orice algoritm care va rezolva acea problem va fi mai complex dect complexitatea problemei.

n general este extrem de dificil de evaluat complexitatea unei probleme, pentru c rareori putem demonstra c un algoritm este cel mai bun posibil. Tabloul arat cam aa:

limita inferioara complexitatea cel mai bun dovedita problemei algoritm cunoscut ---------|------------------?----------------------|---------------- f g

Cu alte cuvinte, putem spune: ``problema asta nu se poate face mai repede de f, i noi tim s-o rezolvm n g''. Dar care este complexitatea real, i care este algoritmul care rezolv problema optim, asta foarte rar se poate spune.

Pentru o problem att de banal ca nmulirea a dou numere, considernd numerele scrise n baza 2, iar mrimea lor numrul total de bii n, complexitatea celui mai bun algoritm de nmulire cunoscut este de O(n log n log log n), dar limita inferioar dovedit este de n. Sau pentru nmulirea a dou matrici de n*n elemente: se gsesc ncontinuu algoritmi din ce n ce mai buni (asimptotic vorbind), dar limita inferioar de n2 este nc departe de cel mai bun (i foarte sofisticat algoritm), care este aproximativ O(n2,3) (comparai cu algoritmul ``naiv'' imediat, care este O(n3)).

Clasa P. Alte clase deterministe Unele probleme se pot rezolva, altele nu. De exemplu, o problem notorie, a crei imposibilitate este riguros demonstrat n anii '30 de ctre matematicianul englez Alan Turing, este de a decide dac un program se va opri vreodat pentru o anumit instan a datelor de intrare.

Pe de alt parte, chiar ntre problemele care pot fi rezolvate, teoreticienii trag o linie imaginar ntre problemele care au rezolvri ``rezonabil'' de rapide, i restul problemelor, care se numesc ``intratabile''.

n mod arbitrar, dar nu ne-justificabil, o problem se numete ``intratabil'' dac complexitatea ei este exponenial n mrimea datelor de intrare. (Nu uitai, este vorba de complexitate ``worst-case'' asimptotic.) O problem este ``tratabil'' dac putem scrie complexitatea ei sub forma unui polinom, de un grad orict de mare.

1


Mulimea tuturor problemelor de decizie (adic a problemelor la care rspunsul este da sau nu) cu complexitate polinomial se noteaz cu P (de la polinom). De exemplu, problema de a gsi dac o valoare se afl ntr-un vector este n clasa P; algoritmul exhibat mai sus este un algoritm n timp linear (O(n)) pentru a rspunde la aceast ntrebare.

Un exemplu de problem cu complexitate exponenial (ne-polinomial)? Iat unul: dac se d o formul logic peste numerele reale, cu cuantificatori existeniali ( ) i universali ( ), care folosete numai operaii de adunare, comparaii cu < i conectori logici ( ), este formula adevrat? Un exemplu de formul adevrat:

,..,,

Decizia se poate face numai ntr-un timp exponenial n lungimea formulei (pentru anumite instane), dar demonstraia nu este de loc simpl.

(Ca o curiozitate: exist i probleme cu o complexitate ``ne-elementar'', care este mai mare dect complexitatea oricrei probleme exponeniale. O astfel de problem este cea de decizie a adevrului unei formule n teoria numit S1S, sau ``teoria monadic a succesorilor de ordinul 2''. Nu v lsai intimidai de terminologie: aceasta este practic o teorie logic peste numerele naturale, n care avem voie s scriem formule cu cuantificatori i conectori logici, ca mai sus, dar avem i dreptul s cuantificm peste mulimi. Complexitatea deciziei unei formule logice ntr-o astfel de teorie este mai mare dect pentru orice k natural!) {

k

n..22

Clasa NP. Algoritmi nedeterminiti. NP-completitudine Algoritmii cu care suntem obinuii s lucrm zi de zi sunt determiniti. Asta nseamn c la un moment dat evoluia algoritmului este unic determinat, i ca instruciunea care urmeaz s se execute este unic precizat n fiecare moment. Am vzut ns c limbajul pe care l-am folosit ne permite scrierea unor algoritmi care au mai multe posibiliti la un moment dat; construcia if din limbajul cu grzi permite evaluarea oricrei instruciuni care are garda adevrat.

Acest tip de algoritmi este surprinztor de bogat n consecine cu valoare teoretic. Aceti algoritmi nu sunt direct aplicabili, ns studiul lor d natere unor concepte foarte importante.

Surprinztoare este i definiia corectitudinii unui astfel de algoritm. Un algoritm nedeterminist este corect dac exist o posibilitate de executare a sa care gsete rspunsul corect. Pe msur ce un algoritm nedeterminist se execut, la anumii pai se confrunt cu alegeri nedeterministe. Ei bine, dac la fiecare pas exist o alegere, care fcut s duc la gsirea soluiei, atunci algoritmul este numit corect.

2


Astfel, un algoritm nedeterminist care caut ieirea dintr-un labirint ar arta cam aa:

do not iesire(pozitie_curenta) -> if not perete(nord(pozitie_curenta)) -> pozitie_curenta := nord(pozitie_curenta) [] not perete(est(pozitie_curenta)) -> pozitie_curenta := est(pozitie_curenta) [] not perete(sud(pozitie_curenta)) -> pozitie_curenta := sud(pozitie_curenta) [] not perete(vest(pozitie_curenta)) -> pozitie_curenta := vest(pozitie_curenta) fi od

Pe scurt algoritmul se comport astfel: dac la nord nu e perete mergi ncolo, sau, poate, dac la sud e liber, mergi ncolo, sau la est, sau la vest. n care dintre direcii, nu se precizeaz (este ne-determinat). Este clar c dac exist o ieire la care se poate ajunge, exist i o suit de aplicri ale acestor reguli care duce la ieire.

Utilitatea practic a unui astfel de algoritm nu este imediat aparent: n definitiv pare s nu spun nimic util: soluia este fie spre sud, fie spre nord, fie spre este, fie spre vest. Ei i? Este clar c aceti algoritmi nu sunt direct implementabili pe un calculator real.

n realitate existena un astfel de algoritm deja nseamn destul de mult. nseamn n primul rnd c problema se poate rezolva algoritmic; v reamintesc c exist probleme care nu se pot rezolva deloc.

n al doilea rnd, se poate arta c fiecare algoritm nedeterminist se poate transforma ntr-unul determinist ntr-un mod automat. Deci de ndat ce tim s rezolvm o problem ntr-un mod nedeterminist, putem s o rezolvm i determinist! Transformarea este relativ simpl: ncercm s mergem pe toate drumurile posibile n paralel, pe fiecare cte un pas. (O astfel de tehnic aplicat n cazul labirintului se transform n ceea ce se cheam ``flood fill'': evoluez radial de la poziia de plecare n toate direciile).

Clasa tuturor problemelor care se pot rezolva cu algoritmi nedeterminiti ntr-un timp polinomial se noteaz cu NP (Nedeterminist Polinomial). Este clar c orice problem care se afl n P se afl i n NP, pentru c algoritmii determiniti sunt doar un caz extrem al celor determiniti: n fiecare moment au o singur alegere posibil.

Din pcate transformarea ntr-un algoritm determinist se face pierznd din eficien. n general un algoritm care opereaz n timp nedeterminist polinomial (NP) poate fi transformat cu uurin ntr-un algoritm care merge n timp exponenial (EXP). Avem deci o incluziune de mulimi ntre problemele de decizie: P NP EXP. Partea cea mai interesant este urmtoarea: tim cu certitudine c P EXP. ns nu avem nici o idee despre relaia de egalitate ntre NP i P sau ntre NP i EXP. Nu exist nici o demonstraie care s infirme c problemele din NP au algoritmi eficieni, determinist

3


polinomiali! Problema P=NP este cea mai important problem din teoria calculatoarelor, pentru c de soluionarea ei se leag o grmad de consecine importante.

Problema aceasta este extrem de important pentru ntreaga matematic, pentru c nsi demonstrarea teoremelor este un proces care ncearc s verifice algoritmic o formul logic (cum am vzut mai sus de pild); teoremele la care exist demonstraii ``scurte'' pot fi asimilate cu problemele din mulimea NP (la fiecare pas dintr-o demonstraie putem aplica mai multe metode de inferen, n mod nedeterminist; un algoritm trebuie s ghiceasc niruirea de metode aplicate pentru demonstrarea enunului); dac orice problem din NP este i n P, atunci putem automatiza o mare parte din demonstrarea de teoreme n mod eficient!

Problema P=NP este foarte important pentru criptografie: decriptarea este o problem din NP (cel care tie cheia tie un algoritm determinist polinomial de decriptare, dar cel care nu o tie are n faa o problem pe care nedeterminist o poate rezolva n timp polinomial). Dac s-ar demonstra c P=NP acest lucru ar avea consecine extrem de importante, iar CIA si KGB ar fi ntr-o situaie destul de proast, pentru c toate schemele lor de criptare ar putea fi sparte n timp polinomial (asta nu nseamn neaprat foarte repede, dar oricum, mult mai repede dect timp exponenial)!

Mai mult, n 1971 Cook a demonstrat c exist o problem special n NP (adic pentru care se poate da un algoritm eficient nedeterminist), numit problema satisfiabilitii (notat cu SAT). Problema este foarte simpl: dac se d o formul boolean care cuprinde mai multe variabile, poate fi formula fcut adevrat dnd anumite valori variabilelor? De pild formula:

devine adevrat pentru x1=adevrat i x2 arbitrar. SAT este foarte important, pentru c Cook a demonstrat c dac SAT poate fi rezolvat n P (adic folosind un algoritm determinist polinomial), atunci orice problem din NP poate fi rezolvat n timp polinomial! Problema satisfiabilitii este cumva ``cea mai grea problem'' din NP, pentru c rezolvarea oricrei alte probleme din NP se poate face ``mai repede'' dect a ei. Din cauza asta SAT se numete o problem NP-complet.

De la Cook ncoace s-au mai descoperit cteva sute de probleme NP-complete. Unele probleme care se ivesc foarte adesea n practic s-au dovedit NP-complete! Acesta este un alt motiv pentru care clasa att de abstract NP a problemelor cu algoritmi nedeterminiti este att de important: foarte multe probleme practice au algoritmi polinomiali nedeterminiti, dar cei mai buni algoritmi determiniti iau un timp exponenial!

4


Iat cteva exemple de probleme NP-complete:

Problema comis-voiajorului (turneu Hamiltonian de cost minim): dndu-se o reea de orae, o reea de drumuri ntre orae i o lungime k, exist un traseu de cost mai mic dect k trecnd prin fiecare ora o singur dat i revenind la punctul de plecare?

Dndu-se o mulime de numere naturale, se poate mpri n dou mulimi de numere de sume egale2?

``Clica'': dndu-se un graf G i un numr k, are G un subgraf complet cu k vrfuri (adic o mulime de k vrfuri unite fiecare cu fiecare)?

``Acoperire'': dndu-se un graf G i un numr k, pot alege k vrfuri n aa fel nct toate muchiile din G au un capt ales?

O cantitate enorm de efort i ingeniozitate a fost risipit pentru a ncerca s se demonstreze c P=NP sau opusul acestei afirmaii, dar nici un rezultat concret nu a fost obinut. Credina cvasi-unanim este c P NP, dar numai matematica poate oferi vreo certitudine...

Din cauz c foarte multe probleme practice sunt n NP, i c aparent nu putem avea algoritmi determiniti eficace pentru ele, cercettorii i-au ndreptat atenia asupra unor clase noi de algoritmi, care vor face obiectul seciunilor urmtoare.

Algoritmi aproximativi n seciunile care urmeaz folosim tot timpul premiza nedemonstrat c P NP. Dac P=NP, atunci problemele pe care ne batem capul s le rezolvm prin metode ciudate pot fi de fapt rezolvate exact i eficient, aa c restul articolului cade i nu se mai ridic.

Optim i aproximare Foarte multe probleme de optimizare se dovedesc a fi NP-complete3: probleme n care vrem s calculm maximumul sau minimumul a ceva. Bine, dar dac de fapt m mulumesc s obin o valoare care nu este chiar optim, dar este ``suficient de aproape''? Poate n acest caz complexitatea problemei poate fi redus, i sunt n stare s scriu un algoritm eficient... (polinomial). Avem deci de a face cu un compromis:

solutie optima; solutie sub-optima: algoritm NP sau algoritm polinomial algoritm exponential

ntr-adevr, aceast metod se bucur de un oarecare succes, dar nu de unul general. Algoritmii care rezolv o problem de optimizare n sperana unui rezultat sub-optimal se numesc ``algoritmi aproximativi''.

5


Exist o sumedenie de rezultate n ceea ce privete problemele de optimizare i aproximrile lor. Se demonstreaz c unele probleme pot fi foarte bine aproximate (putem obine soluii ct dorim de aproape de optim n timp polinomial), altele pot fi aproximate numai n anumite limite (de exemplu putem obine soluii de 2 ori mai slabe, dar deloc mai bune), sau altele nu pot fi aproximate deloc (n ipoteza c PNP).

Teoria algoritmilor aproximativi este relativ recent (dei ideea exist de mult vreme), iar unele rezultate sunt extrem de complicate. Ne vom mulumi s dm nite exemple pentru a ilustra algoritmi aproximativi n aciune, i tipul de rezultate care se pot obine.

Vom ilustra dou rezultate diferite din teoria algoritmilor aproximativi: algoritmi de aproximare relativ, algoritmi de aproximare absolut a soluiei (lmurim terminologia imediat).

S notm o instan a unei probleme cu I. Fie OPT(I) valoarea soluiei optime pentru acea instan (care exist, dar pe care nu tim s-o calculm eficient), i fie A(I) valoarea calculat de algoritmul nostru aproximativ. Numim aproximaia absolut dac exist un numr K, independent de instana I, care are proprietatea c |OPT(I) - A(I)| < K.

Numim aproximaia relativ dac exist un R (numit ``performan'') astfel ca pentru orice instan I avem (A(I) / OPT(I)) < R (dac problema caut un maximum, atunci fracia din definiie trebuie inversat).

Algoritmi Monte Carlo O tehnic foarte spectaculoas pentru rezolvarea problemelor este cea a folosiri numerelor aleatoare. Practic algoritmii aleatori sunt identici cu cei obinuii, dar folosesc n plus o nou instruciune, care s-ar putea chema ``d cu banul''. Aceast instruciune genereaz un bit arbitrar ca valoare.

n mod paradoxal, incertitudinea ne poate oferi mai mult putere...

La ce se folosete aleatorismul? S ne amintim c n general complexitatea unei probleme este definit lund n considerare cea mai defavorabil instan. De exemplu, pentru problema comis voiajorului, faptul c aceast problem este NP-complet nu nseamn c nu putem rezolva nici o instan a ei, ci c exist instane pentru care algoritmii cunoscui nu au prea multe anse s termine n curnd.

Acest lucru este adevrat i pentru alte clase de algoritmi; de pild algoritmul quicksort are pentru majoritatea vectorilor de intrare o comportare O(n log n). Dac ns datele de intrare sunt prost distribuite, atunci quicksort poate face n2 comparaii. Pentru n=100 asta nseamn de 10 ori mai mult! Numrul de instane pentru care quicksort este slab este mult mai mic dect numrul de instane pentru care merge bine. Ce te faci ns dac ntr-un anumit context lui quicksort i se dau numai date rele? (Datele preluate din msurtori

6


reale sunt foarte rar complet uniform distribuite). O soluie paradoxal const n a amesteca aleator vectorul nainte de a-l sorta.

Complexitatea medie (average case) a lui quicksort este O(n log n). Complexitatea n cazul cel mai ru (worst case) este O(n2). Dac datele vin distribuite cu probabilitate mare n zona ``rea'', atunci amestecndu-le putem transforma instane care pic n zona ``worst-case'' n instane de tip ``average-case''. Firete, asta nu nseamn ca nu putem avea ghinion, i ca amestecarea s produc tot o instan ``rea'', dar probabilitatea ca acest lucru s se ntmple este foarte mic, pentru c quicksort are puine instane rele5.

Acesta este un caz de folosire a aleatorului pentru a mbunti performana medie a unui algoritm.

Cteodat ctigul este i mai mare, pentru c putem rezolva probleme NP-complete foarte rapid folosind aleatorismul. De obicei avem ns un pre de pltit. Cnd folosim algoritmi din clasa prezentat mai jos, putem risca s nu primim rspunsul corect.

Algoritmi Las Vegas Evoluia unui algoritm care folosete numere aleatoare nu mai depinde numai de datele de intrare, ci i de numerele aleatoare pe care le genereaz. Dac are ``noroc'' algoritmul poate termina repede i bine; dac d prost cu zarul, ar putea eventual chiar trage o concluzie greit. (n cazul quicksort de mai sus rspunsul este ntotdeauna corect, dar cteodat vine mai greu. Aceasta este diferena dintre algoritmii Monte Carlo, mereu coreci, i cei Las Vegas, care pot uneori, rar, grei.)

Vom defini acum algoritmii probabiliti pentru probleme de decizie (inei minte, la care rspunsul este Da sau Nu). Majoritatea problemelor pot fi exprimate n forma unor probleme de decizie, deci simplificarea nu este prea drastic.

Exist dou clase de algoritmi probabiliti, dar ne vom concentra atenia numai asupra uneia dintre ele, pentru care vom da i dou exemple simple i spectaculoase. Vom defini totodat clasa problemelor care pot fi rezolvate probabilist n timp polinomial, numit RP (Random Polinomial).

Observai c dac indicm de la nceput care sunt numerele aleatoare care vor fi generate, evoluia algoritmului este perfect precizat.

Definiie: O problem de decizie este n RP dac exist un algoritm aleator A care ruleaz ntr-un timp polinomial n lungimea instanei (nc pentru un c oarecare), i care are urmtoarele proprieti:

Dac rspunsul la o instan I este ``Da'', atunci cu o probabilitate mai mare de 1/2 algoritmul va rspunde ``Da''.

7


Dac rspunsul la o instan I este ``Nu'', atunci cu probabilitate 1 algoritmul va rspunde ``Nu''.

De cine este dat ``probabilitatea'' de mai sus? De numrul de iruri aleatoare. Cnd rulm un algoritm aleator pentru o instan I avem la dispoziie 2nc iruri aleatoare de bii; pentru unele dintre ele algoritmul rspunde ``Da'', pentru celelalte rspunde ``Nu''. Ceea ce facem este s numrm pentru cte iruri algoritmul ar rspunde ``da'' i s facem raportul cu 2nc. Aceasta este probabilitatea ca algoritmul s rspund ``da''. Opusul ei este probabilitatea s rspund ``nu''.

O tehnic foarte simpl de amplificare poate crete nedefinit aceast probabilitate: dac executm algoritmul de 2 ori pe aceleai date de intrare, probabilitatea de a grei pentru rspunsuri ``nu'' rmne 0. Pe de alt parte, ajunge ca algoritmul s rspund mcar odat ``da'' pentru a ti c rspunsul este ``da'' cu siguran! Din cauza asta, dac probabilitatea de eroare este p pentru algoritm, executnd de k ori probabilitatea coboar la pk (nu uitai ca p este subunitar, ba chiar sub 1/2). Aceast metod se numete ``boost'' n englez, i face dintr-un algoritm probabilist slab ca discriminare o scul extrem de puternic!

Pentru a scdea probabilitatea de eroare a unui algoritm care poate grei cu probabilitatea p pn sub o limit dorit siguranta, se procedeaz astfel:

raspuns, probabilitate = nu, 1 do (raspuns = nu) and (probabilitate > siguranta) -> raspuns, probabilitate := executa(algoritm), probabilitate * p od

Iat un exemplu i o aplicaie al algoritmilor aproximativi.

Rdcinile unui polinom Fie un polinom de mai multe variabile, x1, x2, ... xn. Acest polinom poate fi descris printr-o formul aritmetic, de pild: (x1 + 1) (x2 + 1) ... (xn + 1). ntrebarea este: este acest polinom identic nul sau nu?

Desigur, o posibilitate este de a ``expanda'' acest polinom n form canonic (sum de produse), i de a compara fiecare coeficient cu 0. Dar n general aceast operaie poate lua un timp exponenial! (De exemplu polinomul anterior genereaz 2n termeni!).

Soluia este s ne bazm pe dou proprieti elementare ale polinoamelor:

Un polinom identic nul este 0 pentru orice combinaie de valori a variabilelor; Un polinom ne-nul are ``puine'' rdcini ntr-un corp6.

De aici rezult c:

Dac polinomul este nul, atunci evaluarea lui n orice punct va da 0;

8


Dac polinomul este ne-nul, atunci probabilitatea de a obine valoarea 0 ntr-un punct (v1, v2, ... vn) ales arbitrar din Sn este < d/|S|.

Pentru polinomul de mai sus gradul este n, i putem alege pentru K de exemplu Zp, unde p este un numr prim relativ mare n raport cu n (de dou ori mai mare ajunge!).

Alegnd arbitrar numerele v1, v2, ..., vn n Zp i evalund q(v1, v2, ..., vn) mod p, putem imediat afirma cu probabilitate mare > 1 - n/p despre q dac este nul sau nu! Observai c evaluarea polinomului nu este prea costisitoare, putndu-se face n timp polinomial n lungimea expresiei care descrie polinomul.

Folosind metoda de ``boost'' putem crete rapid sigurana noastr despre rezultatul algoritmului.

Izomorfismul arborilor Iat i o aplicaie imediat a acestei proprieti.

Se dau doi arbori, cu rdcina precizat. Sunt aceti doi arbori ``izomorfi'' (identici prin re-ordonarea fiilor)? Aceast problem este surprinztor de dificil pentru un algoritm determinist (am impresia chiar c este NP-complet). Iat ns o soluie aproape imediat: construim pentru fiecare arbore cte un polinom care nu depinde de ordinea fiilor unui nod, n aa fel nct dac i numai dac arborii sunt izomorfi polinoamele sunt egale. Apoi pur i simplu testm ca mai sus dac polinomul diferen este nul.

O metod de a asocia recursiv un polinom unui arbore este de pild urmtoarea: fiecrui nod i asociem o variabil xk, unde k este nlimea nodului (distana pn la cea mai deprtat frunz). Frunzele vor avea toate asociate variabila x0. Apoi asociem nodului v de nlime k cu fii v1, ... vl polinomul fv = (xk - fv1) (xk - fv2) ... (xk - fvl). Se arat uor c polinoamele sunt egale pentru arbori izomorfi, bazndu-ne pe unicitatea descompunerii n factori a unui polinom. Gradul polinomului asociat unui nod este egal cu suma gradelor fiilor, care la rndul ei este egal cu numrul de frunze care se afl sub acel nod (cum se demonstreaz imediat prin inducie dup nlime). i asta-i tot!

Pentru a ncheia seciunea, s observm c singurul algoritm eficient cunoscut pentru a verifica primalitatea unui numr este tot probabilist7! Pentru c numerele prime mari stau la baza criptografiei cu cheie public n sistemul RSA (probabil cel mai rspndit la ora actual), iat c unele dintre cele mai importante aplicaii se bazeaz indirect pe algoritmi probabiliti. Nimeni nu va putea obiecta asupra utilitii lor!

Algoritmi on-line Adesea trebuie luate decizii cu informaii incomplete. Un caz particular este luarea de decizii pe msur ce datele devin disponibile. Deciziile afecteaz viitorul, dar sunt luate

9


fr a avea cunotine despre datele viitoare. Sa vedem n aciune un exemplu foarte simplu:

Problema schiorului Se pune problema: ce este mai bine: s nchiriezi sau s cumperi schiuri? (Vom presupune c preul schiurilor este constant de-a lungul timpului, ca s simplificm problema). Dilema const din faptul c n fiecare sezon, nu tii dac te vei mai duce odat. Dac le cumperi i nu te mai duci, ai dat banii degeaba. Dac le tot nchiriezi i te duci des, s-ar putea s le plteti de mai multe ori. Totui, trebuie s iei o decizie. Pe care?

Exist un rspuns foarte simplu, care promite nu c d rezultatul cel mai ieftin n orice circumstan, ci doar c nu vei cheltui de dou ori mai mult dect n cazul n care ai face decizia perfect (decizia perfect este cea care tie precis dac te vei mai duce, i de cte ori; ea nu este accesibil dect ``post-factum'', deci este pur teoretic).

Algoritmul este: nchiriezi schiuri pn ai dat pe chirie costul schiurilor. Dup aceea dac mai vrei s mergi le cumperi. Voi demonstra rapid c n felul sta orice s-ar ntmpla nu pierzi mai mult de jumate din banii pe care i-ai fi cheltuit n cazul ideal.

Avem 3 posibiliti:

1. Te opreti nainte de a le cumpra: n cazul sta ai jucat perfect, pentru c ai schiat i nu puteai iei mai ieftin nicicum;

2. Te opreti imediat dup ce le-ai cumprat. n cazul sta ai dat de dou ori preul (odat pe nchirieri, i odat pe cumprare), dar ai schiat ct ai fi putut schia dnd numai odat preul (mai ieftin de odat nu puteai iei);

3. Te opreti mai trziu: n cazul sta cel mai ieftin era tot s le cumperi din prima zi, deci iar ai cheltuit dublu.

Orice alt schem foloseti pentru a decide cumprarea, exist un scenariu n care poi cheltui mai mult de dublu fa de optim.

Algoritmii on-line apar foarte natural ntr-o mulime de situaii: de exemplu n reele de calculatoare, algoritmii care decid traseul unui pachet cu informaii sunt algoritmi on-line; dac decid trasee proaste, reeaua poate deveni supra-aglomerat n viitor; astfel de algoritmi nu au idee despre cererile viitoare, aa c acioneaz cu informaie incomplet.

Un alt exemplu este n sistemele de operare: algoritmii dup care cache-urile (sau sistemele de memorie virtual) aleg paginile care trebuie nlocuite. Alegerea aceasta nu poate fi optim n absena informaiilor despre viitoarele cereri. Cu toate acestea, anumite alegeri sunt mai bune dect altele.

Un al treilea exemplu, tot din contextul sistemelor de operare, este al algoritmilor de planificare, care trebuie s stabileasc n ce moment se execut fiecare proces pe un

10


calculator (paralel). Acolo unde minutul de rulare cost o grmad de bani, deciziile trebuie s risipeasc ct mai puin timp. ns job-uri pentru prelucrare sosesc dinamic, aa c algoritmii trebuie s fac fa unui mediu n continu schimbare.

Algoritmii on-line sunt n general analizai comparndu-i cu algoritmii off-line, care ar avea nainte de a face deciziile informaii perfecte despre toate cererile viitoare. Este clar c informaia aceasta este un mare avantaj, aa c n general algoritmii on-line au performane mult mai proaste dect cei corespunztori off-line.

Cercetrile n acest domeniu sunt doar la nceput; se exploreaz i variante de algoritmi hibrizi on/off-line, n care algoritmul are o idee despre viitor, dar nu neaprat o vedere complet. Asta nu face ntotdeauna sarcina algoritmului mai simpl, pentru c adesea problema cu informaie complet este NP-complet...

Rezumat n acest articol relev succint o mulime de probleme fascinante. Iat recapitulate sumar conceptele eseniale ntlnite:

Orice algoritm se exprim folosind un set de operaiuni elementare; Un algoritm poate rezolva o instan a unei probleme dintr-o clas ntreag; Complexitatea algoritmilor este o funcie de mrimea instanei i msoar

operaiile efectuate pentru a rezolva cel mai nefavorabil caz; Complexitatea se exprim concis prin ordinul de mrime al funciei complexitate

spre infinit; Invarianii sunt o metod foarte util pentru a demonstra corectitudinea unui

algoritm; Complexitatea unei probleme este complexitatea celui mai rapid algoritm care o

poate rezolva; Exist probleme care au nevoie de un timp exponenial (n mrimea problemei)

sau chiar mai mult pentru a fi rezolvate; exist probleme care nu se pot rezolva deloc cu algoritmi;

Clasa problemelor care au algoritmi nedeterminiti polinomiali include foarte multe probleme practice; nimeni nu tie cum s rezolve aceste probleme n mod eficient;

Clasa problemelor NP-complete este un set de probleme care se rezolv toate la fel de repede; un algoritm care ar rezolva deterministic polinomial una din ele ar cauza rezolvarea tuturor problemelor din NP rapid;

Algoritmii aproximativi ncearc s gseasc mai repede soluii sub-optimale la probleme grele;

Algoritmii aleatori folosesc aleatorismul pentru a fora comportarea unor probleme mai curnd ca n cazul mediu dect ca n cazul cel mai ru;

Algoritmii probabiliti gsesc soluiile cu mare probabilitate, dar nu ntotdeauna, ns o fac repede;

11


Algoritmii on-line trebuie s ia decizii nainte de a avea toate informaiile disponibile;

Multe domenii practice beneficiaz masiv de noile tehnici, cea mai notabil fiind criptografia.

Footnotes ... 1

Mai exact . ... egale2

Problema este ntr-adevr NP-complet, dac socotim ca mrime de intrare lungimea tuturor numerelor n bii; altfel exist un algoritm de programare dinamic de complexitate S n, unde S este suma numerelor, iar n este numrul de numere. Observai ns c S este exponenial n lungimea numerelor.

... NP-complete3 Cititorul atent va observa c noiunea de NP-completitudine a fost definit numai pentru probleme de decizie: cu rspuns Da/Nu, pe cnd problemele de optimizare au n general un rspuns numeric; cititorul poate ns s fie linitit, pentru c putem re-formula o problem de optimizare ca o problem de decizie: n loc de ``care este drumul minim?'', ntrebm ``nu-i aa c exist un drum mai scurt de 100?''.

... grafuri4 O cuplare este un set de muchii care nu are vrfuri comune, iar o cuplare maximal este una care are un numr maxim de muchii.

... rele5 Numrul de instane rele poate fi estimat din distribuia variabilei aleatoare complexitate, i este ntr-adevr mic.

... corp6 Aceasta este Teorema Lipton-Schwartz-Zippel: fie SKo submulime a unui corp K, iar q( x ) un polinom de n variabile de grad d cu coeficieni n K. Atunci ecuaia q( x ) =0 are cel mult d |S|n-1 soluii n S.

... probabilist7 Aa se genereaz numere prime: se genereaz un numr aleator i se verific primalitatea cu un astfel de algoritm.

12

Complexitatea unei problemeClasa P. Alte clase deterministeClasa NP. Algoritmi nedeterminiti. NP-completitudineAlgoritmi aproximativiOptim i aproximare

Algoritmi Monte CarloAlgoritmi Las VegasRdcinile unui polinomIzomorfismul arborilor

Algoritmi on-lineProblema schiorului

RezumatFootnotes

analiza algoritmilor

Documents