Algoritmul

Rețeta exactă

Ce este, la urma urmei, un algoritm? În esență, este o rețetă impecabilă: o succesiune finită de pași limpezi, lipsiți de orice urmă de ambiguitate, care primește niște date de intrare, le prelucrează metodic și produce întotdeauna un răspuns corect, oprindu-se garantat după un număr rezonabil de operații. Fiecare pas individual trebuie să fie atât de elementar încât cel care îl execută să-l poată îndeplini mecanic, fără să ceară lămuriri suplimentare și fără să aibă nevoie de vreo fărâmă de intuiție.

Această cerință de precizie absolută este mult mai aspră decât pare la prima vedere. Într-o carte de bucate obișnuită, o indicație precum „amestecă până când compoziția se leagă” sau „rumenește la foc potrivit” este perfect utilă pentru un bucătar uman, care vede consistența sosului și simte mirosul din cuptor. Însă pentru un calculator, o asemenea comandă este de neînțeles: el nu are simțuri, nu are experiență de viață și nu poate ghici ce am vrut să spunem. Un pas de algoritm autentic seamănă mai degrabă cu: „adună numărul din cutia A la numărul din cutia B și pune rezultatul în cutia C”. Procesorul pe care l-am construit în lecțiile trecute nu poate pune întrebări; prin urmare, tot ceea ce îi cerem trebuie descris fără rest, până la ultima virgulă.

Numele de „algoritm” este un omagiu istoric adus marelui savant persan Muhammad ibn Musa al-Khwarizmi, care a trăit la Bagdad în jurul anului 825. Tratatul său despre calculul metodic cu cifre indiene a fost tradus în latină în Evul Mediu, iar numele autorului, pronunțat stângaci în Europa, a dat cuvântul „algoritm”, în timp ce un alt termen din titlul cărții sale — al-jabr — a dat naștere cuvântului „algebră”.

Sortarea prin selecție

Pentru a vedea un algoritm în carne și oase, să luăm o problemă clasică: avem o grămadă de numere amestecate și vrem să le așezăm în ordine crescătoare. Iată o rețetă simplă și intuitivă, în trei pași: parcurge șirul rămas și găsește cel mai mic număr; schimbă-l cu numărul de pe prima poziție liberă; repetă aceeași procedură pornind de la poziția următoare. Această metodă poartă numele de sortare prin selecție.

De ce este aceasta un algoritm autentic? Din trei motive fundamentale: în primul rând, se termină întotdeauna, fiindcă la fiecare pas zona nesortată scade cu exact un element; în al doilea rând, dă garantat rezultatul corect pentru absolut orice șir de numere, indiferent cât de haotic ar fi fost amestecat; în al treilea rând, putem socoti cu precizie matematică, înainte de a rula programul, câți pași va avea de făcut mașina.

Câți pași

Să numărăm efortul: dacă avem n numere, la prima rundă comparăm primul element cu celelalte n−1 numere. La a doua rundă căutăm printre cele n−2 rămase, și tot așa, până când ajungem la ultimul. Adunate, numărul total de comparații este dat de formula n·(n−1)/2 — adică, grosso modo, jumătate din pătratul lui n. Dacă avem 10 numere, facem vreo 45 de comparații; dacă avem 1.000 de numere, facem aproape o jumătate de milion de comparații; iar dacă avem un milion de numere, ajungem la amețitoarea cifră de 500 de miliarde de operații! Acest efort nu depinde de noroc: chiar dacă șirul este deja ordonat, algoritmul va face orbește exact același număr de verificări.

Dar oare putem fi mai isteți? Desigur! Gândiți-vă la principiul „dezbină și cucerește”: în loc să căutăm prin tot mormanul, împărțim șirul în două jumătăți egale, sortăm separat fiecare jumătate, iar la sfârșit le împletim (le interclasăm) parcurgându-le în paralel, de la stânga la dreapta, comparând doar elementele din vârf. Aceasta este sortarea prin interclasare (Merge Sort). Aici reîntâlnim magica înjumătățire binară din prima lecție: un șir de n elemente se poate înjumătăți de cel mult log₂n ori, iar la fiecare nivel de împărțire munca de împletire este proporțională cu n. Volumul total de muncă scade spectaculos la aproximativ n·log₂n comparații.

Pentru o mână de 8 numere, diferența dintre cele două metode este neînsemnată. Însă pentru o bază de date cu un milion de înregistrări, diferența înseamnă totul: un procesor modern rezolvă sortarea prin interclasare într-o fracțiune de secundă (câteva zeci de milioane de operații), în vreme ce sortarea prin selecție îl ține ocupat timp de minute bune, făcând sute de miliarde de pași pentru a ajunge exact la același rezultat.

Complexitatea

Ritmul în care crește numărul de operații pe măsură ce volumul de date de intrare devine tot mai mare poartă numele de complexitate computațională. În informatică, ignorăm detaliile mărunte și constantele secundare, păstrând doar termenul care dictează explozia efortului: spunem că sortarea prin selecție are o complexitate de ordinul n² (creștere pătratică), în timp ce sortarea prin interclasare are o complexitate de ordinul n·log n.

Renunțarea la constante poate părea o neglijență matematică, dar în realitate este o dovadă de profundă claritate. Oricât de mult am optimiza un algoritm de ordinul n² și oricât de neglijent am programa un algoritm de ordinul n·log n, pentru un volum de date suficient de mare algoritmul n·log n îl va surclasa întotdeauna pe primul fără drept de apel. Nici măcar cumpărarea unui supercomputer de o mie de ori mai puternic nu poate salva un algoritm ineficient: puterea brută a procesorului doar amână puțin momentul în care curba pătratică devine un zid de netrecut. Complexitatea este o trăsătură matematică a ideii în sine, nu a mașinii fizice, și de aceea rămâne adevărată peste secole, indiferent cum evoluează cipurile de siliciu.

Probleme fără un algoritm bun

Până aici, toate sarcinile analizate aveau soluții elegante. Dar informaticienii au descoperit curând o întreagă familie de probleme pentru care știm exact ce avem de făcut, dar pentru care efortul de calcul explodează astronomic. Gândiți-vă la un comis-voiajor care trebuie să viziteze o sută de orașe și caută traseul cel mai scurt. Rețeta brută este banal de simplă: testează pe rând toate rutele posibile și alege-o pe cea mai scurtă! Pașii se pot scrie în trei rânduri de cod. Problema este că numărul traseelor posibile pentru o sută de orașe depășește cu mult numărul tuturor atomilor din universul observabil; niciun calculator din lume, oricât ar rula până la sfârșitul timpului, nu ar putea parcurge această listă.

Pentru asemenea probleme complexe nimeni nu a descoperit încă o scurtătură rapidă și infailibilă — și nimeni nu a reușit să demonstreze că o asemenea scurtătură nu ar putea exista. Această dilemă este cea mai celebră problemă deschisă din informatică și matematică (cunoscută ca problema „P versus NP”). În practică, inginerii se mulțumesc cu metode aproximative, care oferă un răspuns rezonabil de bun într-un timp scurt, fără pretenția perfecțiunii absolute.

Totuși, în toate aceste cazuri dificile există o consolare: știm cu certitudine cum arată pașii teoretici, chiar dacă sunt prea mulți pentru a fi executați. Dar există o barieră mult mai profundă și mai tulburătoare, care nu are nicio legătură cu viteza procesoarelor. Este vorba despre acele sarcini cotidiene pe care orice ființă umană le rezolvă fără niciun efort conștient într-o fracțiune de secundă, dar pentru care nimeni pe lume nu poate așterne o rețetă cu pași clari: cum deosebim un câine de o pisică? Cum recunoaștem scrisul de mână al unui prieten? Cum înțelegem ironia dintr-o frază? Aici nu ne lipsește puterea de calcul; ne lipsește însăși rețeta. În lecția următoare vom încerca să scriem o astfel de rețetă mecanică, doar pentru a vedea unde anume se prăbușește logica clasică și de ce avem nevoie de o paradigmă complet nouă: învățarea automată.