Ce știm că nu știm despre algoritmi? (II)

Mihai Șerban
Senior Software Developer @ Accesa

Partea I a articolului este disponibilă aici.

Informaticienii și-au dat seama rapid că unele probleme sunt dificil de rezolvat, indiferent de progresele tehnologice ale puterii de calcul. În analiza algoritmilor, notația Big O a devenit cel mai utilizat standard de măsurare a complexității și a fost introdusă în anii '70 de Donald Knuth, autorul celebrei cărți: The Art of Computer Programming. În general, notația Big O măsoară scenariul cel mai pesimist pentru modul în care crește timpul de execuție sau consumul de memorie în funcție de dimensiunea datelor de intrare. De exemplu, complexitatea algoritmului GCD este O(log(min(a, b)). Prin comparație, căutarea într-o arie cu n elemente are o complexitate O(n), deoarece numărul de pași - în cel mai rău caz - crește proporțional cu dimensiunea tabloului. Cu toate acestea, extragerea unui element din arie are o complexitate de O(1), presupunând că știm indicele elementului pe care îl căutăm. Programele "Hello world" au o complexitate constantă O(1), iar algoritmii Divide et Impera pot reduce complexitatea lineară O(n) la o complexitate logaritmică O(log n), deoarece nu toate subproblemele vor fi evaluate.

Algoritmii cu complexitate pătratică în timp (O(n²)) pot fi uneori optimizați cu algoritmi mai buni sau cu structuri de date mai adecvate. Ori de câte ori vedeți o structură imbricată, acordați o atenție deosebită mărimii lui n și cercetați ce puteți face pentru a o îmbunătăți: micșorați n, schimbați algoritmul, adăugați limite la intrare etc., deoarece timpul de execuție poate crește destul de repede. Dacă următorul test se execută în ~2 minute pentru n = 100 000, pentru n = 1 000 000 000 se va executa de 10^² = 100 de ori mai lent, însemnând > 3 ore, ceea ce este inacceptabil pentru majoritatea aplicațiilor. Totuși, după cum veți vedea mai târziu, nu algoritmii polinomiali sunt cei care ne țin treji noaptea, doar cei exponențiali.

Structuri imbricate, care rulează în aproximativ două minute pe un laptop obișnuit:

@Test
public void testNestedLoops(){
    int n = 100_000;
    Random random = new Random();
    int z = 0;
    for (int i = 0; i < n; i++){
        for (int j=0; j<n; j++){
            z = random.nextInt();
        }
    }
    System.out.println(
       String. valueOf(z));
}

Teoria complexității computaționale ne spune ce structuri de date să folosim pentru cerințele de business, dacă dorim să obținem cea mai bună performanță. Suntem datori să evaluăm și să înțelegem modul în care utilizatorii consumă datele și care sunt cele mai frecvente cazuri de utilizare. De exemplu, să presupunem că utilizatorii dumneavoastră caută date foarte des, că dimensiunea datelor este mare și că trebuie să se facă rapid căutarea, în timp ce există mai puține constrângeri privind inserția sau că datele nu se schimbă atât de des. În acest caz, ați putea utiliza un arbore de căutare binar în loc de o matrice sau o listă conectată, deoarece complexitatea căutării și a inserției sunt ambele O(log n) proporționale cu înălțimea celor trei. În situația în care arborele este dezechilibrat (poate avea o înălțime de n), complexitatea, în cel mai rău caz, poate fi tot O(n). De aceea, trebuie să ne asigurăm că echilibrăm arborele, ceea ce implică operațiuni suplimentare, prin urmare extra timp, pentru a reconstrui subarbori atunci când este necesar. Desigur, "legăturile" sunt referințe la obiecte sau spații de memorie, astfel încât aceste structuri de date consumă mai multă memorie de stocare decât o matrice.

Fig. 7 Arbori de căutare echilibrați vs. neechilibrați

Indiferent de structurile de date pe care le alegem sau de hardware-ul de care dispunem, unii algoritmi sunt pur și simplu prea dificili pentru a fi calculați într-un timp rezonabil.

Clasificare: Determinist vs. nondeterminist

Înainte de a analiza și mai profund diferitele tipuri de algoritmi, merită să menționăm distincția dintre algoritmii deterministici și nondeterministici, precum și dintre cei exacți sau aproximativi. Algoritmii deterministici produc întotdeauna același rezultat atunci când li se prezintă același input. Algoritmii nondeterministici nu o fac. Mașinile Turing sunt deterministe și, prin urmare, toate computerele noastre sunt la fel. Ce se întâmplă dacă dorim să construim un cazinou online? Atunci când cărțile pe care algoritmul de poker le oferă jucătorilor sunt predeterminate, suntem condamnați la eșec. Dacă se întâmplă să fiți programator Java și v-ați gândit instant la infamul java.util.Random(), navigați în ape periculoase. Pentru a simula un comportament nondeterminist pe mașinile Turing, se folosesc generatoare de numere pseudo-aleatorii, numite simplu PRNG-uri. Aceste generatoare folosesc un număr (seed) ca sursă și o ecuație pentru a genera numere în serie pornind de la "seed". Utilizarea aceluiași seed produce aceeași secvență și, în cele din urmă, secvența se repetă, de unde și termenul "pseudo". Java Random() utilizează un generator congruent liniar, cu o ecuație care arată astfel:

Fig. 8 Ecuația generatorului congruent liniar

După cum puteți vedea, ecuația folosește operatorul modulo, care garantează repetarea după cel mult m numere, deci m trebuie să fie destul de mare și, în general, se alege un număr prim, deoarece numerele prime nu au tendința de a avea o mulțime de divizori și, ca atare, sunt o alegere bună pentru un generator de numere bazat pe operatorul modulo. M utilizat în clasa noastră java Random() este câmpul mască, un număr prim special (număr prim Mersenne, după matematicianul francez care le-a studiat), care este mai mic decât 1 dintr-o putere a lui 2, ceea ce îl face ușor de reprezentat și utilizat în operații pe bit, mai rapide. Nu-i așa că vă place când știința se întâlnește cu programarea?

JDK 1.17 java.util. Clasa java.util.Random:

private static final long mask = (1L << 48) - 1;

Dacă țineți socoteala, ați observat deja că numerele prime sunt peste tot în informatică. "Seedul" pentru clasa java.util.Random() este calculat folosind timpul sistemului, după cum putem vedea dacă aruncăm o privire mai atentă.

JDK 1.17 surse:

public Random() {
    this(seedUniquifier() ^ System.nanoTime());
}

"Unificatorul" de seed este doar un număr mare, care este actualizat la fiecare invocare a constructorului:

Algoritmii care utilizează PRNG-uri sunt încă determiniști, dar pot genera numere care, din punct de vedere statistic, au proprietăți similare cu cele ale numerelor cu adevărat aleatorii.

Dacă doriți să implementați o aplicație corectă de poker online, aveți nevoie de aleatoriu real , care este greu de obținut. S-ar putea să doriți să utilizați API-ul random.org sau, dacă aveți succes și serviciile externe vor fi prea costisitoare, ați putea să vă bazați pe un hardware care generează numere aleatorii folosind zgomotul termic al circuitelor sau, chiar mai bine, efectele mecanicii cuantice ale particulelor mici, care sunt cele mai aleatorii lucruri pe care le cunoaștem în prezent. Cu toate acestea, dacă aplicația devine extrem de populară, s-ar putea să constatați că generarea cu adevărat aleatorie a numerelor este destul de lentă. Singura soluție ar putea fi combinarea unei surse cu adevărat aleatorii cu un generator pseudo aleatoriu, care utilizează ca seed numerele generate aleatoriu. În plus, RNG-urile adevărate prezintă, de obicei, asimetrii care fac ca rezultatele lor să nu fie uniform aleatorii și, de asemenea, trebuie să aplicați o funcție hash pe numerele generate aleatoriu. Algoritmii utilizați în prezent pentru calcularea unei funcții hash denumite colectiv SHA-2 folosesc cifrare în bloc, care sunt, de asemenea, algoritmi deterministici ale căror rezultate par aleatorii. Cifrul de bloc este creat cu grijă pentru a amesteca, roti și deplasa biții de la intrare pentru a produce un rezultat suficient de "aleatoriu" încât să fie imposibil de inversat operațiunea, iar în interiorul blocurilor se află, după cum ați intui, numere prime. Funcțiile hash sunt acum folosite peste tot.

Sunt multe lucruri pe care nu le știm despre algoritmii nondeterministici, deoarece încă încercăm să îi înțelegem pe cei determiniști. Din fericire, toate computerele noastre sunt acum deterministe (cu excepția computerelor cuantice). Pentru o mulțime de aplicații practice, pot fi utilizați algoritmi PRNG, cu avantajele vitezei, costului și ușurinței de integrare. Aceste aplicații includ algoritmi și tehnici de aproximare, testarea software-ului, algoritmi de explorare vs. exploatare etc. Pentru unele aplicații, cum ar fi criptografia, PRNG-urile nu sunt considerate adecvate, în ciuda eforturilor continue de a crea generatoare de numere pseudo aleatorii sigure din punct de vedere criptografic.

Clasificare: Algoritmi exacți, aproximativi, euristici și probabilistici

Majoritatea algoritmilor cu care lucrăm în activitatea noastră zilnică pot fi rezolvați în timp polinomial: căutarea unui element în baza de date, sortarea unei liste de elemente, efectuarea unei tranzacții de plată, regăsirea tuturor restaurantelor din zona dumneavoastră. Această clasă de probleme se numește P. O definiție mai formală a lui P este ansamblul tuturor problemelor de decizie care pot fi rezolvate de o mașină Turing deterministă în timp polinomial. Unele dintre aceste probleme sunt într-adevăr dificile, deoarece gradul polinomialului poate fi mare sau dimensiunea datelor de intrare poate fi mare și, de obicei, le putem optimiza folosind metode ale teoriei grafurilor, cum ar fi arborii binari ordonați. Dar, în general, putem găsi soluția optimă pentru acestea. Dacă calculăm soluția optimă, algoritmul se numește "exact".

Cu toate acestea, pentru unele probleme, un algoritm exact nu este fezabil, pentru că nu se cunoaște niciun algoritm care să găsească soluția optimă într-un timp rezonabil. Unele probleme din P se încadrează în această categorie, însă, de obicei, este vorba de probleme pentru care algoritmii exacți cunoscuți au o complexitate peste cea polinomială: exponențială sau factorială, ambele dincolo de ceea ce "mașinile noastre Turing" existente pot calcula într-un timp rezonabil chiar și pentru dimensiuni moderate ale datelor de intrare. Deoarece aceasta este o problemă pe care încă trebuie să o rezolvăm, abordarea este de a găsi algoritmi polinomiali, care pot calcula soluții aproximative sau soluții "decente" cu ajutorul euristicii bazate pe intuiție sau care funcționează în natură. Dat fiind că toate aceste probleme pot fi rezolvate prin forță brută, dar timpul de execuție sau resursele de calcul sunt impracticabile, le numim probleme intratabile. A nu se confunda cu problemele nerezolvabile, cum ar fi problema opririi.

O distincție importantă între abordările euristice și cele de aproximare este aceea că un algoritm de aproximare este demonstrabil la o distanță cunoscută față de soluția optimă, exprimată de regulă în procente, în timp ce pentru abordarea euristică nu avem o măsură a cât de bun este algoritmul și îl folosim pentru că funcționează. Este adevărat că nu sună a "știință" informatică, dar așa este.

Algoritmii probabilistici, numiți și algoritmi randomizați, sunt utilizați atât în tehnicile de aproximare, cât și în cele euristice. Folosim algoritmi probabilistici pentru că sunt simpli și pentru că eșantioane mari de date aleatorii sau date generate conform unei distribuții de probabilitate care reprezintă datele se pot apropia asimptotic de soluția optimă, dacă se execută suficiente calcule simple. De obicei, PRNG-urile sunt potrivite pentru această sarcină, astfel încât nu este nevoie de generatoare aleatorii adevărate.

Algoritmi Monte Carlo

Algoritmii aleatorii au un rol important în problemele legate de fizică sau în matematică, unde avem de-a face cu formule complexe și cu intrări a căror distribuție de probabilitate este știută. Această clasă de algoritmi este cunoscută sub numele de metodele Monte Carlo, iar prima aplicație practică a fost evaluarea difuziei neutronilor în miezul unei arme nucleare, la Laboratorul Național Los Alamos, în 1946. Abordările deterministe eșuează din cauza volumului de calcul necesar. În 1948, simulările Monte Carlo pentru reacții nucleare erau programate pe ENIAC, primul calculator programabil construit vreodată. Algoritmii Monte Carlo funcționează datorită legii numerelor mari, care afirmă că pe măsură ce efectuăm mai multe încercări aleatorii, pe atât ne apropiem mai mult de valoarea așteptată a unei funcții. Întrucât lucrările privind proiectele de fisiune nucleară erau clasificate, acest proiect de cercetare a fost denumit Monte Carlo, deoarece unchiul lui Stanislaw Ulam, unul dintre cercetătorii implicați în proiect, împrumuta bani de la rude pentru a juca la cazinoul Monte Carlo din Monaco.

Un bun exemplu de funcționare a metodei pentru aproximarea pi, așa cum se vede în imaginea următoare.

Fig. 9 Aproximarea lui pi folosind metoda Monte Carlo

Fig. 10 Formula de aproximare a lui pi folosind metoda Monte Carlo

Permiteți-ne să ilustrăm acest lucru cu un algoritm cu care sunteți cu siguranță obișnuiți.

Criptografia asimetrică

Având acum o scurtă introducere în istoria algoritmilor și câteva moduri în care îi putem clasifica, haideți să facem o legătură între teorie și practică și să punem cap la cap piesele într-unul dintre cei mai utilizați algoritmi din prezent.

În rândurile următoare, vom aborda criptografia asimetrică. Aceasta, cunoscută și sub numele de criptografie cu cheie publică, permite comunicarea securizată între două sau mai multe părți, facilitând simultan decriptarea mesajului doar de către destinatarul său. Este o îmbunătățire majoră față de criptografia cu cheie simetrică, în care secretul - parola, cheia - trebuia să fie partajat între cele două părți, ceea ce însemna că ambele părți puteau decripta mesajele și fiecare dintre ele se putea da drept cealaltă.

Fig. 11 Principiul criptografiei asimetrice

Primul și cel mai cunoscut algoritm de criptografie cu cheie publică este RSA, publicat în '77 de Ron Rivest, Adi Shamir și Leonard Adleman. Acesta este în continuare cel mai utilizat algoritm, deoarece nu a fost încă descifrat. L-ați folosit de multe ori - prin intermediul browserului - ori de câte ori ați trimis date către un site web cu criptare TLS, prin HTTPS. În calitate de programator, ați generat singur câteva chei. Cu Putty, ca în imaginea de mai jos, pentru autentificarea SSH, sau certificate SSL auto-semnate, întrebându-vă cum funcționează și, în primul rând, de ce trebuie să mișcați frenetic mouse-ul peste zona gri.

Fig. 12

Ce se întâmplă aici? Dacă ne permitem să simplificăm puțin, vom genera o cheie publică și o cheie privată. Aceste două chei trebuie să fie legate între ele, astfel încât un mesaj criptat cu cheia publică să poată fi decodat cu cheia privată, dar cheia privată să nu poată fi dedusă din cheia publică. Formula de criptare - decriptare din imaginea de mai jos se bazează pe dificultatea de a găsi numărul d (care este cheia privată), în timp ce se cunosc n și e (cheia publică), deoarece n este un produs a două numere prime, să le numim p și q (n = pq).

Fig. 13 Formula de principiu RSA. M - mesaj, m^e - mesaj criptat, n, e - cheie publică, d - cheie privată

Cheia privată, d, poate fi calculată din p și q, dar pentru a găsi p și q trebuie să descompunem n în factorii săi primi, ceea ce reprezintă un algoritm de complexitate exponențială, cel puțin în cazul abordării naive. Pentru n-uri suficient de mari, este extrem de nepractic. Valorile actuale ale lui n au 2048 de biți. Se pare că ne-am întors la Euclid, închizând ciclul, discutând în continuare despre numere prime. Dacă ați urmărit discuția până aici, poate v-ați întrebat: "Bine, dar cum găsim numere prime atât de mari precum p și q pentru început? Nu este aceasta o problemă aproape la fel de dificilă?". Și ați avea dreptate. Un lucru care face ca numerele prime să fie speciale este faptul că știm puține lucruri despre distribuția lor. De la Euclid încoace, știm că există o cantitate infinită de numere prime, dar încă nu știm cum să le găsim eficient, cu excepția metodei vechi și bune pe care ați învățat-o în liceu: luați fiecare număr (poate săriți peste cele pare), verificați dacă este prim împărțindu-l la toate numerele prime mai mici decât el însuși (sqrt(n). Dacă nu se împarte exact la niciunul, ați găsit un număr prim. Așadar, găsirea a două numere prime mari este o chestiune anevoioasă. Și, evident, nu le putem folosi pe cele existente, ci avem nevoie de altele noi pentru fiecare pereche de chei publice - private. Acest lucru ne lasă cu o singură opțiune de compromis: să alegem două numere la «întâmplare» și să sperăm că sunt prime. Acum știți suficient despre aleatoriu și calculatoare pentru a înțelege de ce trebuie să mișcăm mouse-ul deasupra zonei gri. Avem nevoie de un seed "aleatoare" pentru un generator de numere pseudo aleatorii folosit pentru a ghici numerele prime pe care le căutăm, p și q. Acest "aleator" sunteți dumneavoastră, dacă se întâmplă să credeți în liberul arbitru. Și chiar dacă nu credeți, mișcarea mâinii este, totuși, mai puțin previzibilă decât ceasul sistemului de operare. "Bănuiala" din ecuație este testul de primalitate Miller-Rabin, care este un algoritm probabilistic eficient și aproximativ. Putem crește probabilitatea ca numărul testat să fie prim prin rularea algoritmului mai mult timp, iar versiunea utilizată în prezent a acestuia a fost descoperită în 1980. Aceasta este încă o metodă complicată, care pare să funcționeze bine. De fapt, ne-am bazat întreaga industrie și securitate pe ea, dar dovada că testul de primordialitate Miller funcționează se bazează pe ipoteza Riemann nedovedită - probabil cea mai faimoasă problemă nerezolvată din matematică - despre care nu am îndeajuns de multe cunoștințe pentru a o explica. Deoarece acest test de primalitate este rapid, putem găsi rapid două numere care ar putea fi prime cu un grad de încredere suficient de ridicat pentru a le folosi în calculul cheilor publice și private.

Cele mai dificile probleme din informatică

Dintre problemele de decizie, unele sunt nesoluționabile, cum ar fi problema opririi menționată mai sus. Alte probleme sunt rezolvabile și cunoaștem algoritmi polinomiali pentru a le rezolva. Clasa acestor probleme se numește P. Există probleme pentru care putem verifica soluțiile destul de ușor (în timp polinomial). Clasa acestor probleme se numește NP. De exemplu, factorizarea numerelor întregi, care stă la baza criptografiei noastre este o problemă NP. Dacă cunoaștem factorii primi, putem verifica rapid dacă aceștia se înmulțesc la rezultat. Se numesc NP, deoarece toate aceste probleme pot fi rezolvate în timp polinomial de către o mașină Turing nedeterministă. Aceasta este o mașină Turing teoretică specială care poate verifica toate ramurile posibile ale unui algoritm, care este același lucru cu a intui soluții. Evident, P ⊂ NP. Există totuși unele probleme de decizie la care putem reduce orice altă problemă NP, probleme "rădăcină" dacă doriți. Acestea se numesc probleme NP-Complete și pot simula sau rezolva orice altă problemă din NP. Cunoaștem destul de multe astfel de probleme și adăugarea câtorva la această clasă vă va aduce faimă. Și mai există probleme dificile, care se numesc Hard. NP-Hard ca și în Bond, James Bond. Ele sunt, cel puțin, la fel de dificile ca NP-Complete, toate problemele din NP putând fi reduse la NP-Hard în timp polinomial. Problemele NP-Complete sunt un subset al NP-Hard, dar unele probleme NP-Hard nu sunt nici măcar în NP sau nu sunt probleme de decizie.

Credem că nicio problemă NP-Hard - sau NP-Complete prin incluziune - nu poate fi rezolvată în timp polinomial, deoarece nu a fost descoperit niciun algoritm care să le rezolve eficient. Cu toate acestea, acest lucru nu a fost încă demonstrat. Aceasta este cea mai dificilă problemă din domeniul informaticii și se numește P ≠ NP. Rezolvarea acesteia vine cu faimă bine-meritată și cu 1 milion de dolari. Dacă P ar fi egal cu NP, o mulțime de probleme pe care le considerăm dificile ar putea fi rezolvate cu un algoritm polinomial (P), ceea ce înseamnă că există modalități mult mai eficiente de a rezolva probleme NP-Complete (și unele NP-Hard).

Cea mai faimoasă problemă NP-Complete este problema vânzătorului ambulant.

Fig. 14

Are o complexitate factorială, astfel încât rezolvarea sa prin forță brută, chiar și în cazul unei dimensiuni modeste a datelor de intrare, este nepractică. De aceea, se utilizează în schimb abordări euristice. Cele mai multe dintre aceste euristici sunt algoritmi aleatorii discutați mai sus. Pentru această problemă, Simulated annealing face o treabă excelentă, însă este imposibil de spus cât este de eficient. O altă abordare euristică poate fi optimizarea în colonii de furnici, din clasa algoritmilor de inteligență a roiului. Mai puțin computaționali și, de asemenea, mai puțin eficienți sunt algoritmii greedy, în care se caută optimi locali pas cu pas.

Teme de gândire sub forma unor probleme NP-Hard:

Lucrați la universitate. Noul an universitar începe în curând și trebuie să repartizați clasele pe intervale orare astfel încât să nu existe conflicte și clasele pentru fiecare grup să fie cât mai apropiate posibil.

V-ați decis sau, cel mai probabil, ați găsit în sfârșit pe cineva cu care să vă căsătoriți și trebuie să vă planificați nunta. Cu toate acestea, știi că unii dintre prietenii tăi nu se plac între ei, iar alții da. Orice masă poate avea un număr configurabil de locuri. Așezați-vă invitații la masă pentru a le maximiza fericirea.

Testați ipoteza celor 6 grade.

Problema rucsacului: sugerați articole de adăugat la un kart sau la o pagină de recomandări, pentru a maximiza potrivirea preferințelor utilizatorului până la o anumită sumă totală.

Algoritmi de învățare automată

Uneori, problemele noastre nu implică decizii, dar trebuie să prezicem, să modelăm sau să înțelegem. Pentru acest tip de probleme, algoritmii de învățare automată sunt alegerea potrivită. S-a dovedit matematic că algoritmii ML sunt aproximatori de funcții universale, deci pot modela orice poate fi exprimat ca o funcție, cu condiția să fie definiți suficienți neuroni. Deep learning este cea mai bună abordare pentru problemele în care avem o mulțime de date, indiferent cât de incomplete, iar rezultatul pare aleatoriu. ML va găsi modelele care duc la rezultat și, uneori, la modele mai bogate decât realitatea (a se vedea "overfitting"). Algoritmii ML nu sunt însă, de sine stătători, capabili să rezolve orice problemă, așa cum se încăpățânează OpenAI să ne demonstreze contrariul cu fiecare nouă lansare de ChatGPT. Uneori avem nevoie doar de o matematică mai bună, așa cum e ilustrat în următorul exemplu, bazat pe o conjectură celebră care spune că numerele n^17 + 9 și (n + 1)^17 sunt prime între ele:

Fig. 15

Există cel puțin un n pentru care ecuația este falsă, iar cel mai mic n care o invalidează este n=84244329252559288932929288197322308900672459420460792433.

Concluzie

Este fascinant cum întregul domeniu IT se bazează pe presupunerea că anumite ipoteze matematice ar putea fi adevărate, în timp ce unii dintre cei mai de succes algoritmi pe care îi cunoaștem se bazează pe euristici pe care încă nu am învățat cum să le măsurăm și nu înțelegem de ce - și uneori nici cum - funcționează. La suprafață, în ciuda înțelegerii limitate pe care o avem asupra fundamentelor științifice ale domeniului, IT-ul pare atât de neproblematic, de concret, de explorat științific, capabil să rezolve orice problemă i-ar putea trece cuiva prin cap - de la explorarea spațiului la salvarea planetei. Sper că cititorii s-au convins că este vorba de o aparență.