Indecidabilitate și intractabilitate

Continuând seria de posturi de cultură generală pentru programatori(am mai zis că nu sună bine în română), o să încerc să alunec puțin dinspre tehnic înspre filosofic.

Este de bun simț să admitem că știința progresează, dovadă că în fiecare război se găsesc noi mijloace de ucide oameni(dacă ne gândim bine, și calculatoarele au fost construite tot cu ocazia războiului). Cu toate că progresează, în secolul 20 s-a ajuns la concluzia că știința nu ne va putea da niciodată toate răspunsurile.

O expresie filosofică a acestui adevăr o aduce Blaga, afirmând că nu putem trece, cu ajutorul cunoașterii, de limita impusă de Marele Anonim. O abordare mai pragmatică și recunoscută de lumea științifică vine de la Kurt Gödel, care prin 1931, arată nu numai că sistemul nostru de axiome este incomplet, ci și că nu avem cum să construim unul complet.

Ce înseamnă acest lucru? Păi axiomele sunt niște adevăruri pe care se bazează toate cunoștințele noastre. Pornind de la aceste axiome ca fundație, începem să construim: cărămidă cu cărămidă, găsim noi teoreme, dar la un moment dat vrem să punem undeva o cărămidă și nu putem, pentru că acolo lipsește fundația, și fără fundație nu putem construi. Nici o problemă, s-ar zice, mai punem fundație(aka acceptăm noi axiome), dar la un moment dat iar ajungem într-un punct unde nu putem construi. Gödel a demonstrat că în afară de sistemele triviale, oricâtă fundație am avea, tot nu vom putea construi orice. La un moment dat, se va enunța o teoremă, despre care nu vom putea ști dacă e adevărată sau nu, oricât ne-am strădui.

Revenind la calculatoarele noastre, nu știu câți și-au pus întrebarea ”Ce se poate calcula?” sau ”La ce întrebări ne poate răspunde calculatorul?”. Din mulțimea de întrebări posibile, nu o să le alegem pe cele de genul ”what is the answer to life the universe and everything”… asta e ușoară, răspunsul e 42(întrebați pe google dacă nu mă credeți). Ne vom lega de acum încolo de întrebările la care se poate răspunde cu DA sau nu, numite și probleme de decizie. Exemple de astfel de întrebări sunt ”Este 25 mai mare ca 20?”sau ”Se poate găsi un drum pe harta României, care să treacă prin fiecare oraș o singură dată?” sau încă ”Dacă rulăm algoritmul ăsta, o să se termine vreodată?”.

Evident, pentru întrebări de genul primeia, răspunsul se găsește imediat. Sărim deocamdată peste a doua, și ne uităm la cea de-a 3-a. Ca să o exprimăm mai precis, vrem să scriem un program care să analizeze un alt program, și să ne spună dacă se termină, sau buclează la infinit. Tot prin anii ’30, Alan Turing a demonstrat că un astfel de program nu se poate scrie. Spunem deci, că această problemă este indecidabilă. Desigur, putem să rulăm efectiv programul care se cere analizat, iar dacă se termină am câștigat: putem răspunde cu certitudine DA. Dacă în schimb după 10 minute sau după 10 luni, programul tot rulează, nu avem de unde ști dacă face calcule utile și la un moment dat va ajunge la rezultat, sau s-a împotmolit într-o buclă infinită.

Dacă ne întoarcem la a doua întrebare, care pentru cunoscători se numește problema ciclului Hamiltonian, observăm că putem găsi o soluție: încercăm fiecare drum posibil în parte, iar la un moment dat, fie am epuizat toate drumurile, fie am găsit un drum cu proprietatea cerută. Deși această abordare va da până la urmă un răspuns la întrebare, avem de încercat o groază de variante. Mai rău, pentru cei ce au citit postul anterior din această categorie, putem spune că algoritmul are o complexitate exponențială, adică să zicem că avem un calculator suficient de rapid care să rezolve problema pentru un anumit număr de orașe în timp rezonabil, dacă mai introducem chiar și un număr foarte mic de orașe în ecuație, nu se va mai găsi răspuns într-un timp acceptabil.

Partea cu adevărat proastă la problema de mai sus este că nici până în zilele noastre nu s-a găsit vreo abordare mai bună, care să rezolve problema în timp polinomial. Singurul lucru care mai salvează cât de cât situația este faptul că dacă cineva găsește din întâmplare un drum, putem verifica destul de repede(în timp polinomial) dacă soluția este corectă sau nu. De fapt, foarte multe probleme cu care ne întâlnim în practică au proprietatea de a li se putea verifica soluția în timp polinomial. Vom nota această clasă de probleme cu NP. Desigur, în această clasă de probleme intră și cele simple, care se pot rezolva în timp polinomial, a căror clasă o notăm cu P, deci avem P \subseteq NP.

Una dintre problemele mileniului, pentru care se oferă un premiu de 1 milion de dolari, este verificarea dacă e incluziune strictă, sau avem egalitate, între cele două clase de probleme. Partea care stă în calea egalității, e un anumit grup de probleme, numite NP-complete, sau intractabile, de genul celei amintite mai sus, pentru care nu s-a găsit încă un algoritm polinomial, dar nici nu s-a putut demonstra că nu ar exista. Este surprinzător faptul că toate aceste probleme, din domenii atât de diferite, se pot reduce în timp polinomial una la alta. De exemplu, dacă reușim să găsim o soluție în timp polinomial la problema împărțirii unei mulțimi de numere, în două mulțimi cu sume egale(pentru olimpicii la info care cred că au soluția, trebuie să repet că vreau timp polinomial, nu pseudopolinomial), vom putea rezolva în timp polinomial și problema ciclului Hamiltonian amintită mai sus.

Acest fapt remarcabil, posibilitatea reducerii, ne ușurează de multe ori viața în practică. Când întâlnim o problemă la care nu putem găsi soluție în timp polinomial, putem încerca să o reducem la o problemă NP-completă cunoscută, iar dacă reușim reducerea, înseamnă că am întâlnit o problemă cu care informaticienii și matematicienii se confruntă fără succes de decenii, și probabil ar fi cazul să ne petrecem timpul cu ceva mai util, de exemplu să încercăm să dăm o soluție aproximativă, sau să facem un backtracking cât mai optimizat.

Concluzia pe care cititorul ar trebui să o tragă din cele citite mai sus, este că nu orice problemă se poate rezolva cu ajutorul calculatorului, și chiar și pentru cele care se pot rezolva, nu putem găsi tot timpul o rezolvare care să dea soluția în timp acceptabil. Cu toate acestea, putem construi soluții imperfecte, care să ajute utilizatorul, și care să încerce să se apropie cât mai mult de perfecțiune.

Published in: on Februarie 19, 2010 at 16:53  Comments (3)  

Atenție la țepe cu telefonul

Scriu postul acesta pe fugă, fiindcă am de prins un tren, însă consider necesar să avertizez lumea despre persoanele care dau țepe cu telefonul.

M-a sunat un tip, care zicea că e de la Cosmote, și că în urma unei promoții am câștigat o reducere la abonament cu 50%, minute în plus și alte minunății. Yupiii… Pentru a activa acest premiu, trebuie doar să tastez *444* … nu mai stiu ce, apoi un număr de telefon, pe care mi-l dictează el.

Dacă nu v-ați prins deja, ăsta e serviciul pentru a încărca o cartela cu credit, și fiind pe abonament, poți să încarci cu destul de mult… cîteva miloane chiar. Mișto, nu?

Din fericire eu m-am prins, și i-am notat numărul. Îl pun aici, just for fun, în speranța că vreun nebun va da de el și se va apuca să îl hărțuiască: 0769.14.26.21.

Partea și mai faină e că numărul fiind de cartelă, ”glumețul” nostru nu poate fi prins. La relații cu clienții mi-au spus că trebuie să mă duc la un magazin de-al lor, să completez o plângere, ș.a.m.d. Iar eu am un tren de prins.

Tot ce pot să fac este să scriu chestia asta pe blog, în speranța că cineva o va citi, și nu va lua țeapă când va fi sunat(deși cred că cititorii mei sunt mai inteligenți decât ai lor, așa că nu vor fi probleme).

Published in: on Februarie 10, 2010 at 15:06  Lasă un comentariu  

The big O

Fiindcă în viața reală nu prea se mai întâmplă nimic intersant, am decis să scriu o serie de articole legate de calculatoare. Asta și deoarece temele abordate de mine până acum nu se prea potrivesc cu titlul blogului ”Just a coder”. Categoria nou creată se numește ”General knowledge for programmers”(parcă nu ar suna bine în română), și doresc să scriu o serie de post-uri, despre concepte des întâlnite în viața de coder, dar de care lumea se cam sperie. Posturile din această categorie nu se vor exhaustive, nici măcar pe departe. Tot ce doresc să prezint e un skimming prin conceptele abordate, după care cititorul interesat poate da un search pe Google pentru a se documenta corespunzător.

Post-ul de azi se referă la notația asimptotică, numită în engleză ”the big O notation”, și se adresează în special celor care au nedumeriri atunci când aud că un algoritm are complexitatea O(n^2), în timp ce altul are doar O(n \log n).

Complexitatea unui algoritm nu e altceva decât o măsură a numărului de operații pe care algoritmul îl face. Să zicem că avem un algoritm care găsește elementul maxim dintr-un vector oarecare(sau dacă vreți, listă).

Dacă cititorul s-a încumetat să ajungă până aici, probabil îi este familiar conceptul de vector, și știe că pentru a determina elementul maxim, trebuie să inițializeze o valoare cu primul element, apoi să o compare pe rând cu celelalte. Mai concret vorbind, dacă vrem să aflăm care este cel mai înalt elev din clasă, le cerem să intre pe rând pe ușă, punându-l pe primul drept etalon. De fiecare dată când intră cineva mai înalt decât etalonul, elevul mai înalt devine etalon. Evident, ultimul elev rămas drept etalon este cel mai înalt din clasă.

Până acum probabil ne-am dat deja seama că numărul de operații depinde de numărul de elemente din vector, sau de numărul de elevi din clasă, pe care în general îl notăm cu n. Mai exact, operațiile efectuate pentru determinarea maximului sunt comparații, în număr de n-1(deoarece pe primul element nu avem cu cine îl compara). Cu toate acestea, vom zice că algoritmul are complexitatea O(n), și nu O(n-1). În primul rând, acel 1 nu este relevant, pentru că oricum programul va face anumite operații de inițializare, pe care nu trebuie să le luăm în calcul, și în al doilea rând, faptul că îl luăm doar pe n, ne simplifică mult calculele, și ne ajută de multe ori să ”vedem” mai bine problema.

Așa cum multă lume își poate imagina, la apelul unei funcții care face ceva util, se fac anumite operații(punere parametri de apel și adresă de întoarcere pe stivă, inițializare variabile, etc. – dacă aceste operații nu sunt cunoscute, cititorul nu trebuie să își facă griji, deoarece sunt irelevante în acest post -). Vine atunci întrebarea ”de ce aceste operații nu se iau în considerare când măsurăm complexitatea?”. Răspunsul este că această complexitate nu trebuie să ne dea numărul exact de pași efectuați de algoritm, ci ne interesează mai mult cum se modifică acest număr de pași, dacă dimensiunea datelor problemei se modifică.

De exemplu, dacă avem un algoritm cu complexitate O(n), care rulează pentru n=1000, timp de 10 secunde, și îl mărim pe n cu 1, folosind regula de trei simplă, obținem un timp de execuție de 10.01 secunde, care practic nu diferă în mod vizibil de primul. Chiar dacă îl dublăm pe n, vom dubla doar timpul de execuție, la 20 de secunde, care rămâne tot în limitele rezonabile.

Să ne închipuim acum un algoritm de complexitate O(2^n), care rulează tot pentru n=1000 timp de 10 secunde. Dacă îl mărim pe n doar cu 1, cunoscând că 2^{n+1} = 2 \cdot 2^n, ne dăm seama că timpul de execuție se dublează. Dacă îl mărim pe n cu 10 doar, adică de la 1000 la 1010, timpul de execuție va crește de 2^{10} = 1024 ori, adica de la 10 secunde la aproape 3 ore. Timpul este încă rezonabil, dacă lucrăm la o problemă suficient de importantă, cât să merite să așteptăm 3 ore, dar ce ne facem de exemplu dacă ne trece prin cap să dublăm dimensiunea datelor problemei? Astfel de probleme se numesc probleme intractabile, și vom discuta mai multe despre ele într-un post viitor.

Am observat mai sus că pentru calcularea complexității unui algoritm, nu trebuie să ținem cont de constantele aditive care apar, deoarece acestea nu influențează semnificativ numărul de operații, atunci când dimensiunea datelor problemei se modifică. Vestea bună este că ”big O” ne scapă nu doar de constantele aditive, ci și de alte neplăceri.

Să luăm un alt exemplu, calcularea sumei elementelor de deasupra diagonalei principale, a unei matrici. Aceste elemente sunt în număr de 1 + 2 + \ldots (n-1) = \dfrac{n(n-1)}{2}, deci acesta este numărul de adunări pe care îl vom face. Dacă scriem acestă valoare sub formă polinomială, avem \dfrac{1}{2} n^2 - \dfrac{1}{2} n. Ca să trecem la notația asimptotică, trebuie să-l luăm doar pe n la puterea cea mai mare, fără a ”căra” după noi constantele multiplicative, aditive, sau puteri mai mici ale lui n, deoarece pentru valori suficient de mari ale acestuia, doar puterea cea mai mare din polinom va contribui semnificativ la creșterea numărului de operații. Vom obține complexitatea pentru această problemă O(n^2). Denumirea de notație asimptotică vine de la conceptul de asimptotă din matematică, dar n-o să intru în detalii aici.

Ar trebui ca deja să ne fi prins de șmecherie : pentru a calcula complexitatea unui algoritm, putem număra operațiile efectuate, fără a ține cont de detalii, iar acea valoare, deși oarecum aproximativă, ne va da o bună estimare a creșterii numărului de operații, la creșterea dimensiunii datelor problemei.

O ultimă chestiune, pentru a răspunde la o întrebare pe care unii cititori și-ar putea-o pune: ”Cum numărăm operațiile, de ajungem uneori la logaritmi, în formula complexității?”. Pentru a răspunde la această întrebare e necesar să cunoaștem conceptul de arbore binar. Chiar dacă o problemă nu specifică în mod explicit această structură, rezolvarea o poate sugera, prin împărțirea structurii de date în două jumătăți egale, și aplicarea algoritmului pe fiecare jumătate. Astfel, devine necesară parcurgerea unui astfel de arbore de la rădăcină, până la o frunză, ceea ce face ca numărul de operații să fie proporțional cu înălțimea acestuia. Un exercițiu pe care îl las pe seama cititorului care nu a adormit încă, este verificarea sau demonstrarea faptului că înălțimea unui arbore binar echilibrat este de ordinul \log_2 n, unde n este numărul de noduri al arborelui.

Published in: on Februarie 5, 2010 at 01:54  Lasă un comentariu