Cred că noi, developerii, am început să uităm importanța algoritmilor care stau la baza fiecărei linii de cod pe care o scriem. Aceștia stau acum ascunși în spatele diverselor frameworkuri și librării pe care le folosim cu automatism prinși în taskurile zilnice, eludându-ne cu succes atenția. În acest articol, voi încerca să vă conving că diferența dintre succesul și eșecul unui proiect, dintre un software excelent și "technical debt" este de cele mai multe ori dată de abilitatea noastră de a clasifica problema din perspectiva algoritmilor, făcând mai întâi un pas în spate, pentru reflecție. Să pornim așadar de la definiție. Ce este un algoritm?
Potrivit Google, un algoritm este "un proces sau un set de reguli care trebuie urmat în calcule sau în alte operațiuni de rezolvare a problemelor, în special de către un computer", iar Wikipedia îl descrie ca "o secvență finită de instrucțiuni riguroase, utilizată de obicei pentru a rezolva o clasă de probleme specifice sau pentru a efectua un calcul". În acest sens, este cunoscut faptul că adunarea a două numere nu este un algoritm, așa cum nu este nici sistemul de operare Ubuntu.
Trebuie să existe ceva la mijloc, care să nu fie comun și care să aibă scop delimitat - ceva ce se poate aplica mai multor situații și pe care îl poți folosi pentru a clasifica și înțelege problemele. La ce algoritmi vă gândiți atunci când cineva vă cere să numiți unul?
Putem să începem cu cei mai vechi algoritmi cunoscuți. Puțini îndrăznesc să se întoarcă în timp înainte de vechile tăblițe de lut babiloniene. Recent decodificate, acestea conțin numere pitagoreice scrise în baza 60 - de acolo avem baza de numărare pentru măsurarea timpului și unghiurile măsurate în grade; anii babilonieni aveau 360 de zile, deoarece Pământul parcurge aproximativ 1 grad în fiecare zi în jurul Soarelui, ușor de numărat în baza 60.
Fig. 1 Tableta babiloniană Plimpton 322 din lut, ~1800 î.Hr., autor necunoscut; Sursă: Plimpton 322 - Wikipedia
Cu toate acestea, numerele și tehnicile de trasare a unui unghi drept greu pot fi numite "algoritmi". De aceea, unii spun că Eratostene, cel care cu ciurul său a descoperit o metodă de găsire a tuturor numerelor prime - până la o anumită limită -, în timp ce măsura circumferința Pământului și era bibliotecar șef la Biblioteca din Alexandria, merită pe deplin titlul de descoperitor al primului algoritm sau chiar de inventator - depinde de care baricadă a dezbaterii despre apariția matematicii ești - prin descoperire sau invenție.
Fig. 2 Sita lui Eratostene, numerele prime până la 100
Personal, prefer să plasez originea algoritmilor în mâna lui Euclid, probabil cea mai influentă figură din istoria matematicii, ca părinte al geometriei, prin lucrarea sa din Elemente, încă a doua cea mai publicată carte după Biblie. Tot în Elemente, o idee care astăzi se numește teorema fundamentală a aritmeticii a dat startul la ceea ce este astăzi teoria numerelor. Aceasta afirmă că fiecare număr întreg are o factorizare primă unică, ceea ce face din numerele prime elementele de bază ale tuturor numerelor.
Teorema fundamentală a aritmeticii
Chiar și pentru grecii antici, numerele prime erau mai mult decât o curiozitate interesantă. Folosind teorema de mai sus, ei ofereau o modalitate eficientă de a simplifica fracțiile, ceea ce era deosebit de util în construcții sau în împărțirea bunurilor. Deoarece era dificil să descompui numitorul și numitorul în factorii săi primi și să efectuezi simplificări în acest mod, Euclid a conceput un algoritm pentru a calcula în mod eficient cel mai mare divizor comun a două numere - funcția gcd. Dacă ați făcut informatică, este posibil ca unul dintre primii algoritmi pe care i-ați implementat să fi fost gcd sau testul de primalitate.
Dacă ne imaginăm un salt rapid în viitor de 2500 de ani, iată cum ar putea arăta algoritmul gcd în java.
public int gcd(int a, int b){
while (a != b){
if (a > b) {
a = a - b;
} else {
b = b - a;
}
return b;
}Se poate la fel de bine afirma că istoria algoritmilor începe cu Muhamad ibn al-Khwārizmī, un matematician persan, care a trăit în Bagdad în secolul al IX-lea. Cuvântul "algoritm" este derivat din numele său, el fiind cel care a introdus în lume sistemul pozițional zecimal, prin cartea sa Despre calculul cu cifre hinduse. Nu pentru această carte îl numim însă părintele algoritmilor, ci pentru o carte care i-a fost cerută de calif, în care trebuia să întocmească o listă de probleme din viața de zi cu zi și metodele de rezolvare a acestora. Cartea includea, printre altele, întrebări despre măsurarea terenurilor, tranzacții comerciale și distribuirea moștenirii în familie. El a decis să înceapă cartea cu o lucrare matematică, care să abstractizeze toate problemele concrete în ceea ce noi numim acum algoritmi. Celebra carte se numește Cartea Compendiu despre calculul prin completare și echilibrare. În arabă, aceasta ar fi "al-Kitāb al-Mukhtașar fī Hisāb al-Jabr wal-Muqābalah", dar versiunea mai scurtă este cunoscută sub numele de al-Jabr, pe care noi o numim acum pur și simplu algebră, după cartea care a stabilit noul domeniu matematic.
Fig. 3 Pagina de titlu a cărții Cartea Compendiu despre calculul prin completare și echilibrare; Sursă: The Compendious Book on Calculation by Completion and Balancing - Wikipedia
Unii susțin că, pentru a avea un algoritm, este nevoie de o mașinărie care să îl execute. Dacă oamenii îl fac manual - sau mental - este doar matematică. Tot acești oameni vor stabili locul de naștere al algoritmilor în 1843, într-o publicație scrisă de Ada Lovelace, pentru a dovedi utilitatea unei mașinării mecanice concepute de Charles Babbage, pe care a numit-o Motorul Analitic. În notele Adei Lovelace despre Sketch of The Analytical Engine Invented by Charles Babbage de Luigi Menabrea, ea a descris modul în care Motorul Analitic putea calcula numerele Bernoulli folosind un algoritm recursiv, care putea funcționa pe o mașinărie care nu a fost construită niciodată. Numerele Bernoulli apar atunci când se calculează orice sumă de puteri ale numerelor naturale. Având o formulă pentru acestea, se simplifică calculul. Ele sunt, de asemenea, legate de numerele prime și oferă o modalitate de a distinge între numerele prime regulate și neregulate. După cum vom vedea și mai târziu, numerele prime sunt prezente peste tot. Puteți citi mai multe despre algoritmul și istoria Adei Lovelace.
Motorul analitic nu a fost construit niciodată, deoarece la acea vreme nu era fezabilă producerea unor componente mecanice la o precizie și o calitate atât de ridicate precum cele necesare, dar au fost construite două motoare diferite (v2), unul de către Muzeul de Știință din Londra în anii '80 și altul în SUA, care se află acum la Intellectual Ventures din Seattle. Mai jos, puteți vedea impresionantul prim motor de diferență construit - o mașină de 8.000 de piese, cântărind aproximativ 5 tone. După cum a intuit Menabrea, în viitor, nu va mai fi nevoie de matematicieni pentru calcule complexe - lucrătorii ar trebui să se descurce. Noi, programatorii, suntem "forța de muncă" care lucrează la aceste mașini și, într-adevăr, nu ne putem numi matematicieni.
Sugestivă este în acest sens previziunea despre motorul analitic a lui Luigi Menabrea (1809-1896), inginer și viitor prim-ministru italian:
Fig. 4 Diagrama unui algoritm pentru Motorul Analitic pentru calculul numerelor Bernoulli, din Sketch of The Analytical Engine Invented by Charles Babbage de Luigi Menabrea, cu note de Ada Lovelace. Pașii descriu modul în care motorul analitic ar calcula B8, pe care ea l-a numit B7 în notația sa. Sursa: Wikimedia Commons
,,O dată ce motorul va fi construit, dificultatea se va reduce la confecționarea cărților, dar cum acestea nu sunt decât traducerea unor formule algebrice, va fi ușor, prin intermediul unei notații simple, să încredințăm executarea lor unui muncitor."
Fig. 5 Motorul de diferențe al Muzeului de Știință din Londra, primul construit după proiectul lui Babbage. Proiectul are aceeași precizie pe toate coloanele, dar în calculul polinoamelor, precizia pe coloanele de ordin superior putea fi mai mică. Sursă: Wikimedia commons
La scurt timp după aceea, Alan Turing a venit și a propus o Mașină Universală Turing, care poate calcula orice, inspirând construcția calculatoarelor electronice programabile. Conform conceptului lui teoretic, Mașina Turing era programul (algoritmul) care împreună cu datele de intrare era trimis Mașinii Universale Turing pentru execuție. Acest lucru a dat o nouă dimensiune programabilității și a definit termeni precum algoritm și computabilitate în termeni matematici. Este fascinant cum Alan Turing a pornit această revoluție a informației ca efect advers, nu ca scop în sine, în timp ce lucra la una dintre problemele milenare din lista lui David Hilbert, aceea a deciziei (în germană Entscheidungsproblem), fiind unul dintre primii care au demonstrat că problema deciziei nu poate fi rezolvată. Pe scurt, a demonstrat că există întrebări despre un sistem la care nu se poate răspunde cu "Da" sau "Nu", chiar dacă se cunosc toate datele (axiomele) sistemului. Prin urmare, mașina lui universală - și matematica prin extensie - are limitări definitive pe care David Hilbert spera să le depășim. Cu toate aceste limitări de natură logică și computațională, dispozitivele pe care le purtăm după noi în buzunar, mici exemple de mașini Turing, sunt fascinante și capabile de atât de multe lucruri. Luând în considerare teorema completitudinii a lui Kurt Gödel, știm acum că, din păcate, matematica nu este nici completă, nici "deductibilă", dar produsul secundar al demonstrației lui Turing, mașina Turing, a dat naștere informaticii - așa cum o cunoaștem astăzi - și erei informaționale care a urmat. Pentru această realizare, Turing este considerat de către mulți dintre noi ca fiind părintele fondator al științei calculatoarelor.
Imediat după aceea, algoritmii au pătruns în fiecare domeniu existent, detectând, căutând, clasificând, modelând, prezicând, raportând și optimizând totul, de la cea mai bună mișcare de șah, la cel mai bun interval de timp pentru culoarea verde a semaforului, până la înțelegerea și convingerea comportamentului uman, demonstrarea de teoreme și prezicerea formei proteinelor pe baza secvenței de aminoacizi. Să vedem cum le putem clasifica pentru a face lumină asupra posibilităților și metodelor oferite de algoritmi.
Vă amintiți de algoritmul Euclid de la începutul articolului? Există o altă modalitate de a rezolva această problemă, pe care sunt sigur că o veți recunoaște instantaneu:
public int rgcd(int a, int b){
if( b == 0) {
return a;
}
return rgcd(b, a % b);
}Este versiunea recursivă a aceluiași algoritm pe care îl puteți vedea mai sus, ceea ce ne aduce la unul dintre modurile în care putem clasifica algoritmii: iterativi și recursivi. În teorie, aceștia sunt ambii valizi, dar, în practică, am putea prefera abordarea iterativă, pentru a salva spațiu de memorie pe stack, cel puțin în Java. Algoritmul de mai sus este un caz special de recursivitate: este recursivă pe coadă, iar în majoritatea limbajelor de programare funcționale de astăzi este optimizat de compilator. Acesta poate fi un motiv bun pentru a utiliza Scala sau Kotlin în loc de Java, dacă intenționați să folosiți recursivitatea. Privind mai atent, existența stackului și a compilatorului în spatele fiecărei funcții din limbajul de programare face ca fiecare funcție recursivă să fie, în principiu, una iterativă. Amintiți-vă că, la bază, se execută pe un model similar unei mașini Turing.
Orice funcție recursivă poate fi exprimată iterativ și viceversa, lucru demonstrat în anii '30. Atunci au fost propuse trei modele computaționale diferite: funcțiile general recursive ale lui Kurt Godel (da, aceeași persoană care a demonstrat că matematica e incompletă), calculul lambda a lui Alonzo Church și mașina Turing a lui Alan Turing. Ulterior s-a arătat că cele trei modele sunt echivalente. Mai simplu spus: ce poate fi exprimat recursiv (Kurt Godel), poate fi exprimat iterativ (Turing), dar și funcțional (Church). Acest fapt este atât de bine-cunoscut încât există multe companii care interzic codul recursiv. Așa că programatorii trebuie, uneori, să convertească codul recursiv în iterativ. Din nefericire pentru ei, nu pot răspunde că "nu se poate", deoarece chiar și managerii știu că "se poate". Mai mult decât atât, programatorii cu un stil imperativ se trezesc adesea cu comentarii la "pull requesturi", precum cel de mai jos, acum când programarea funcțională este pe val.
Fig. 6 Orice poate fi exprimat într-un mod funcțional. Chiar și în Java.
Acum afirmăm că ceva este computabil prin definiție dacă poate fi implementat de o mașină Turing. Nu știm încă dacă orice funcție este computabilă de către aceasta, deoarece nu știm ce este sau ce poate fi o funcție "efectiv computabilă" exceptând definiția lui Turing. Din punct de vedere practic, considerăm că orice funcție care nu implică structuri infinite este computabilă, astfel încât nu puteți folosi acest argument pentru a spune stakeholderului că funcția solicitată de acesta este imposibil de implementat. Există, bineînțeles, probleme care sunt indecidabile, probleme pentru care nu poate exista niciun algoritm pe care să-l putem scrie pentru a le rezolva. Cel mai cunoscut exemplu este problema opririi a lui Alan Turing, care afirmă că nu poate exista un algoritm care să poată determina dacă un algoritm dat sau o mașină Turing și o intrare produc un rezultat sau rulează la nesfârșit. Pentru acest tip de problemă, să presupunem că stakeholderii vă cer să implementați un algoritm de generare de cod care să optimizeze bugetul companiei. În acest caz, ar trebui să începeți cu o "spike" uriaș, pentru a cerceta posibilitățile de generare a unor algoritmi pentru care să negociați această problemă. Pentru o aprofundare a stadiului actual al problemei, verificați teza Church-Turing, cu speranța că, într-o zi, o vom putea transforma într-o teoremă și vom dovedi că noi, programatorii, putem implementa tot ceea ce își doresc stakeholderii noștri, dacă avem la dispoziție suficient timp și resurse.
continuare în numărul următor al revistei.
de Bogdan Maxim
de Nóra Dobre
de Ovidiu Mățan
