Articles

Cum am ajuns aici? Povestea algoritmilor.

Până de curând, algoritmii au fost un domeniu al informaticienilor. Dar acum, ei au intrat în viața noastră și au devenit omniprezenți. Algoritmul nu mai este un cuvânt străin. Comerțul algoritmic, prejudecata algoritmică, algoritmul Facebook, chiar și războiul algoritmic – toți acești termeni au devenit parte din vocabularul nostru în ultimii ani. Unii merg atât de departe încât susțin că trăim într-o nouă eră: era algoritmului. Dar algoritmii nu sunt chiar atât de noi. Îi folosim, cu bună știință sau nu, de sute și mii de ani. Algoritmii sunt doar descrieri specifice ale unor acțiuni pas cu pas care trebuie să se întâmple pentru a obține un anumit rezultat. Ele sunt unul dintre cele mai comune instrumente de partajare a cunoștințelor.

Practic, orice proces de a învăța pe cineva cum să facă ceva folosește algoritmi.

Câteva aspecte ale algoritmilor s-au schimbat însă în ultimele câteva decenii. În special, introducerea computerelor înseamnă că mulți algoritmi din ziua de azi sunt dramatic mai complecși decât ne-am fi putut imagina vreodată în trecut. Cum au evoluat algoritmii pentru a fi astăzi mult mai sofisticați decât erau în trecut? Haideți să aruncăm o scurtă privire asupra istoriei lor.

Algoritmi care ghidează acțiunile umane

Stampilă emisă la 6 septembrie 1983, în Uniunea Sovietică, cu ocazia comemorării a 1200 de ani de la nașterea (aproximativă) a lui al-Khwārizmī; via Wikimedia Commons

Termenul algoritm derivă de la numele lui Muhammad ibn Mūsā al’Khwārizmī, un matematician persan din secolul al IX-lea. Numele său latinizat, Algoritmi, însemna „sistemul numeric zecimal” și a fost folosit în acest sens timp de secole. Noțiunea modernă de algoritm a apărut în limba engleză în secolul al XIX-lea și a devenit mai frecvent utilizată începând cu anii 1950, declanșată de apariția primelor computere disponibile în comerț.

Cu mult înainte ca algoritmii să primească numele lor modern, totuși, ei erau creați și utilizați în mod obișnuit.

Primii algoritmi au fost surprinși pe hârtie în Grecia Antică. Savanți precum Nicomachus din Gerasa sau Euclid creau atunci elementele de bază ale matematicii moderne. Pentru a ușura înțelegerea și aplicabilitatea ideilor lor, ei au exprimat multe dintre ele sub forma unor acțiuni pas cu pas.

Nicomachus din Gerasa a introdus Sita lui Eratostene. Sita este folosită până în prezent de studenții care învață să scrie coduri informatice eficiente. Ea a ajutat la simplificarea procesului de identificare a numerelor prime. Numerele prime sunt numere naturale, mai mari decât unu, care nu pot fi formate prin înmulțirea a două numere naturale mai mici. De exemplu, patru nu este un număr prim, deoarece poate fi format prin înmulțirea a doi cu doi. Cinci, în schimb, este un număr prim, deoarece niciun număr natural mai mic decât cinci nu poate fi înmulțit pentru a forma cinci. Deși nu este prea greu de identificat primele câteva numere prime (de exemplu, 2, 3, 5, 7, 11, 13, 17, 19, 23 și 29), găsirea numerelor prime mari necesită mult timp. Iar numerele prime mari sunt esențiale în criptografie. Sita lui Eratostene oferă instrucțiuni pas cu pas pentru eliminarea rapidă a tuturor numerelor care nu sunt prime dintr-un set definit de numere (de exemplu, între 1 și 10.000) până când rămân doar numere prime. În prezent, sunt disponibili numeroși algoritmi care simplifică sarcina de a identifica astfel de numere. Sita lui Eratostene a dat startul unei întregi familii de algoritmi care au același scop și care devin din ce în ce mai buni (mai rapizi sau care necesită mai puțini pași) în detectarea numerelor prime.

Sita lui Eratosthenes de SKopp la Wikipedia germană

Euclid, celălalt savant menționat mai sus, mult mai cunoscut decât Nicomachus în zilele noastre, a introdus un algoritm pentru identificarea celui mai mare divizor comun a două numere. Din nou, nu întotdeauna o sarcină ușoară, dar esențială în multe situații. Algoritmul lui Euclid a contribuit la facilitarea acestui calcul. De ce este util algoritmul lui Euclid? Imaginați-vă că aveți o cameră cu dimensiunea exactă de 612 pe 2006 centimetri care are nevoie de o nouă podea. Algoritmul lui Euclid vă va ajuta să găsiți dimensiunea celor mai mari dale pătrate care ar acoperi în mod ordonat podeaua. Răspunsul, dat de algoritm, este de 34 cm pe 34 cm, rezultând o dispunere de 18 pe 59 de plăci. Bineînțeles, orice faianțar vă va spune că răspunsul este greșit și că habar nu aveți ce faceți, deoarece algoritmul nu ia în considerare lățimea chitului și nu lasă spațiu pentru acesta. Nu vă temeți: și acest lucru poate fi calculat și poate fi clar exprimat sub forma unui algoritm.

Algoritmi care ghidează acțiunile mașinilor

De-a lungul celor câteva sute de ani care au urmat, au fost creați și surprinși pe hârtie mult mai mulți algoritmi. Aceștia au fost apoi folosiți de indivizi și urmați pas cu pas. Primul algoritm menit să fie executat pe o mașină a fost creat de Ada Lovelace (născută Byron) și publicat în 1843.

Ada Byron, în vârstă de patru ani. În curând, ea va deveni primul programator de calculator din lume. De către artist: Alfred, Comte d’Orsay. Imagine digitală; Somerville College, Oxford – Somerville College, Oxford, Public Domain, https://commons.wikimedia.org/w/index.php?curid=44246375

Ada era un personaj intrigant. S-a născut în 1815, fiind singurul copil legitim al poetului Lord Byron. Ea a dezvoltat mari talente în matematică. Și cum dragostea pentru poezie era în mod clar în genele ei, ea a reușit cumva să dezvolte și să echilibreze atât dragostea pentru știință, cât și pentru poezie. Ada și-a autodefinit modul de gândire ca fiind „știință poetică”. Fiind o matematiciană pricepută, a ajuns să-l cunoască pe Charles Babbage, care este adesea numit „părintele calculatoarelor”, datorită invențiilor sale. Amândoi au dezvoltat o relație de lucru și o prietenie. Ada a fost foarte interesată de unul dintre proiectele lui Charles – Motorul analitic.

O diagramă pentru Motorul analitic. By ArnoldReinhold – Own work, CC BY 4.0, https://commons.wikimedia.org/w/index.php?curid=69497631

Motorul analitic a fost un calculator mecanic – o mașină care automatiza calculele. Motorul analitic a fost cel pentru care a scris primul algoritm. Lucrarea ei era o formulă care arăta cum să configureze Motorul pentru a calcula o anumită secvență complexă de numere, numite numere Bernoulli. Formula este acum recunoscută pe scară largă ca fiind primul algoritm de calculator din istorie.

Ada nu s-a limitat doar la calcule matematice pure. Având în vedere că a trăit în secolul al XIX-lea, ea a fost o adevărată vizionară.

În timp ce mulți dintre contemporanii ei vedeau primele computere mecanice în primul rând ca pe niște dispozitive de numărare, ea se întreba ce este dincolo de efectuarea de calcule. Era curioasă în legătură cu potențialul mai larg al calculatoarelor mecanice ca instrumente de colaborare. Ea spera să vadă computere care să împuternicească oamenii mult mai mult decât prin simpla automatizare a calculelor.

Diagrama lui Lovelace din „nota G”, primul algoritm de calculator publicat, de Ada Lovelace – http://www.sophiararebooks.com/pictures/3544a.jpg, Public Domain, https://commons.wikimedia.org/w/index.php?curid=37285970

Din păcate, construcția Motorului Analitic nu a fost finalizată înainte de moartea lui Ada, astfel că aceasta nu a putut niciodată să își vadă algoritmul în acțiune. Din păcate, Motorul Analitic nu a fost construit nici până în ziua de azi. Un alt proiect al lui Charles Babbage, Difference Engine №2, a fost construit de Muzeul de Știință din Londra abia în 1991. S-a demonstrat că este funcțional, folosind materiale și tehnologii disponibile pentru Charles Babbage. Se pare că Babbage a fost pur și simplu ghinionist când a fost vorba de construirea proiectelor sale. Alte implementări parțiale ale operei lui Charles există în alte părți, dar, din păcate, nu putem rula algoritmul lui Ada Byron pe un Motor Analitic real.

Secolul al XIX-lea a devenit o eră a „algoritmilor încorporați în mașini”.

Existau o mulțime de astfel de algoritmi, care automatizau tot felul de acțiuni umane. Dacă aveai nevoie de un model complicat pe o bucată de țesătură, Joseph Marie Jacquard, un țesător și comerciant francez, avea o soluție pentru tine: războiul de țesut Jacquard. Acesta a permis producătorilor de țesături să producă modele sofisticate folosind o serie de carduri perforate care instruiau un război de țesut cum să țeasă. În mod similar, primele centrale telefonice foloseau dispozitive mecanice sofisticate pentru a conecta apelurile telefonice. Acestea urmau automat instrucțiuni pas cu pas pentru ca, în cele din urmă, două persoane să vorbească între ele. Aceste mașinării, fie că era vorba de războaie de țesut sau de centrale, au fost revoluționare la vremea lor și sunt încă impresionante până în ziua de azi. Este greu să nu admiri nivelurile de complexitate ale unora dintre aceste mașini. Cu toate acestea, toate aceste dispozitive erau încă pur mecanice. Erau alcătuite din pârghii, întrerupătoare, arbori. Făceau mult zgomot. Și erau foarte departe de ceea ce numim noi calculatoare în zilele noastre.

Algoritmi pe calculatoare de uz general

Nu până în anii 1930 am văzut primele mențiuni despre algoritmi în calculatoare electronice (nemecanice). Alan Turing a fost printre primii oameni de știință care au surprins în mod oficial modul în care indivizii efectuau calcule. Scopul lui Turing a fost acela de a surprinde un proces general, mai degrabă decât unul specific unei anumite sarcini, cum ar fi pentru identificarea numerelor prime sau calcularea celui mai mare divizor comun. Procesul general putea fi apoi utilizat pentru a îndeplini sarcini specifice. Munca conceptuală a lui Turing a dus la dezvoltarea a ceea ce este cunoscut în prezent sub numele de Mașina Turing. Mașina Turing, la rândul său, a dus la apariția calculatoarelor de uz general. Prefixul „scop general” este esențial aici. Spre deosebire de mașinile anterioare, noile calculatoare executau seturi arbitrare de instrucțiuni. Acestea ar putea fi utilizate în scopuri care nu au fost prevăzute nici măcar de creatorii lor. Cu alte cuvinte: Munca lui Turing a dus la dezvoltarea calculatoarelor pe care putem instala și rula aplicații.

Nu există Flappy Bird pe smartphone-ul tău fără conceptul de mașină Turing.

Decenii mai târziu, algoritmii au devenit extrem de sofisticați. Atât de sofisticați, de fapt, încât adesea ne este imposibil să explicăm cum funcționează. În secolul al XX-lea, mulți preferau să se gândească la algoritmii de calculator ca la niște cutii negre. Nu era nevoie să înțelegi cum anume funcționau. Tot ce te interesa erau intrările – ceea ce intra în cutia neagră – și ieșirile – ceea ce ieșea. Această simplificare a fost o alegere. În secolul XXI, pentru unii algoritmi, aceasta nu mai este o alegere: oamenii nu pot explica cu exactitate modul în care algoritmii ajung la anumite ieșiri și, prin urmare, suntem obligați să ne gândim la acești algoritmi ca la niște cutii negre, sau poate magice. Un grup de astfel de algoritmi sunt unii dintre algoritmii de inteligență artificială. Putem explica principiile lor. De exemplu, putem spune că un algoritm folosește o rețea neuronală artificială. Putem, de asemenea, să explicăm cum a fost creată rețeaua și cum a rezultat intrarea cu o anumită ieșire. Ceea ce nu putem explica, însă, este de ce acest rezultat particular a fost ieșirea algoritmului, dincolo de o explicație pur mecanică. Eric L. Loomis, a cărui durată de încarcerare a depins de un algoritm, a încercat să înțeleagă de ce algoritmul COMPAS l-a evaluat ca fiind un infractor cu risc ridicat. A fost pur și simplu imposibil. Sofisticarea algoritmilor este adesea copleșitoare. Și acesta este doar începutul.

Trăim într-o lume în care algoritmii sunt peste tot – nu doar pe hârtie sau în mințile noastre, ci și controlând mașini, calculatoare și roboți.

Ei sunt mici, omniprezenți și – cel puțin în unele cazuri – inexplicabili.

O definiție mai formală a unui algoritm este „o specificație lipsită de ambiguitate a modului de rezolvare a unei clase de probleme” sau „un set de operații de sine stătător, pas cu pas, care trebuie efectuate”

www.oed.com/view/Entry/4959

În octombrie 2018, cel mai mare număr prim cunoscut este 277.232.917- 1, un număr cu 23.249.425 de cifre. Doar pentru a verifica dacă acest singur număr este prim a fost nevoie de șase zile de calcul non-stop pe un computer casnic contemporan. (https://www.mersenne.org/primes/press/M77232917.html)