98

alexpetrescu
Petrescu Alexandru
22 decembrie 2020

Doresc să vă împărtaşesc un nou succes al comunităţii informatice din România. Vara aceasta unul dintre membrii săi a obtinut cea mai mare nota all-times pentru lucrarea sa de licenţă la Universitatea Oxford. Vă propun să ne bucuram cu ţotii de acest eveniment şi să ne hrănim cu invăţăturile acestei lucrări.

De ce e atât de wow!

Ca să inţelegem mai bine ce inseamna această notă de 98 din 100, am selectat câteva informaţii bine-cunoscute românilor studenţi la informatică în Oxford:

  • Lucrarea de licenţă este un proiect la care lucrezi cu un profesor specializat în domeniul tău de interes. Rezultatul este, practic, un fişier pdf constând în cel mult 10 000 de cuvinte.
  • O lucrare excelentă primeşte în jur de 70 din 100 de puncte.
  • Notele de peste 80 sunt rezervate lucrărilor demne de publicat într-un jurnal sau la o conferinta, sub forma unui paper.
  • Convenţiile de examinare recomandă ca în jur de 5% dintre lucrări să primeasca o nota în intervalul 80-90.
  • Cea mai mare nota cunoscută nouă este obţinută anul trecut tot de către un român, lucrare cotată cu 91 de puncte.

Despre ce e vorba in proiectul de 98

Domeniul se numeşte 'Computational Social Choice', şi este stiinţa ce studiaza dintr-o perspectiva algoritmică orice conţine cuvintele alegători şi candidaţi. În general, un alegător are preferinţe, pe care cel mai des şi le exprima ordonând candidaţii dupa valoarea lor în ochii lui. De exemplu, într-o alegere pentru cea mai bună fetiţă Powerpuff, alegătoarea Bessie ordonează candidaţii astfel: Blossom > Bubbles > Buttercup. Date fiind preferinţele alegatorilor, se pune problema determinării câstigătorilor (unul sau mai mulţi!) într-un mod cât mai echitabil. Cuvântul echitabil este intenţionat vag, deoarece explicitarea lui în diverse modaliţăti dă naştere diverselor sisteme concrete de votare pe care le folosim (e.g. sistemul cu două tururi folosit pentru alegerile prezidenţiale).

L-am rugat pe Andrei1998Andrei Constantinescu Andrei1998 să facă un rezumat al detaliilor algoritmice ale proiectului său.

Îi dau cuvantul:

Cu toate că domeniul isi are originile in politică şi economie, ceea ce poate frapa este caracterul izbitor algoritmic al problemelor de interes. Nu voi intra foarte adânc in amănuntele de Social Choice ale proiectului, dar cred că ar fi interesant pentru comunitate să explic în ce masură cunoştinţele din liceu ajută mai departe în cercetare. Iata câteva exemple de tehnici de la concursurile de algoritmică pe care le-am folosit pentru a obţine complexităţile îmbunătăţite din lucrare:

  • Tehnica "Parametric Search", care a apărut în scena programării competiţionale o dată cu problema Aliens de la IOI 2016. Tehnica a mai fost folosită ulterior în problema Popcorn, iar membrii comunităţii au găsit soluţii alternative mai simple ce o folosesc în probleme propuse în trecut: Padurari şi Flooow.
  • Optimizarea "O(nk^2) devine O(nk)", care a apărut în România o dată cu problemele Arbkset, Lianyu şi Cli. Aceasta este o rafinare a mai cunoscutei "O(n^3) devine O(n^2)", folosită în probleme precum: Politic, Purification şi Tricolor. Dacă nu aţi auzit de acest smen, puteţi citi o superba explicaţie începând cu pagina 22 de aici (problema Barricades).
  • În afara programei de olimpiadă: Algoritmul Simplex. Cu toate acestea, problema Echilibrare admite o soluţie inedită, alternativă, folosind această tehnică; pentru majoritatea elevilor, Simplex nu e mai mult decât un "black-box". Aside: Având în vedere soluţia oficială a problemei, ce putem înţelege, sau intui, din acestea? Există strânse legături între problemele de flux întâlnite la olimpiada, forma lor matriceala şi problemele lor duale de optimizare. Nu nu, nu o să explic ce am vrut să zic cu asta - să vă provoc şi pe voi puţin!

Sistemul de vot pe care îl studiem se numeşte Chamberlin-Courant, şi este destul de uşor de descris. Avem n candidaţi şi m alegatori, fiecare alegător exprimându-şi preferinţele prin liste ordonate de preferinţe. Pentu un k dat, scopul este să alegem un comitet câstigător format din k candidaţi, adica unul de cost minim. Cum calculăm costul? Pentru fiecare alegător număram candidaţii mai bine văzuţi de către el decât toţi aleşii din comitetul de k, şi apoi adunăm la costul total acest număr. De exemplu, dacă primele opţiuni ale tuturor alegătorilor formeaza o mulţime de cel mult k candidaţi, atunci comitetul câstigător va avea cost 0! Din păcate, problema generală este NP-hard, dar nu este totul pierdut, deoarece în alegeri reale preferinţele candidaţilor nu sunt arbitrare, sau "worst-case", aşa cum ne obisnuiesc temerarii comisiilor, ci au destul de multa structură. În ce sens au structură? Depinde - esenţa este să restrângem domeniul de preferinte suficient de puţin încât să putem înca modela alegerile reale, dar şi suficient de mult încât să putem rezolva problema în timp polinomial. Nu zic mai mult să nu plictisesc!

Totuşi, cel mai mare efort pentru mine a fost acela de a prezenta noile rezultate clar şi fără "leap"-uri în raţionament. Am observat în general o oarecare superficialitate când vine vorba de asta - de foarte multe ori într-un salt în raţionament se ascunde o greşeală extrem de subtilă. În sensul ăsta, vă las cu o anecdotă: primul rezultat pe care l-am avut a constat pur şi simplu în a citi un paper vechi de aproximativ 5 ani. Am observat cum autorii prezentau un algoritm polinomial bazat pe programare dinamică pentru o problema pe arbori, dar algoritmul era redactat de aşa natura încât micile greşeli de scriere (cum ar fi un ' uitat aici, un indice dincolo) se aliniau perfect cât sa dea naştere unui algoritm care părea corect. Şi mai interesant, în funcţie de cum corectai typo-urile, fie devenea greşit, dar polinomial, fie corect, dar atunci analiza complexităţii nu mai mergea dusă la capăt (algoritmul devenea exponenţial pe un arbore stea, aşa cum arătăm în paper-ul complet). Ironia este că am fost la un milimetru să zic "mda, are sens, probabil e corect", cum nu înţelegeam încă toate notaţiile şi ideea centrală părea naturala. Totuşi, ceva tot parca nu se lega şi eram încăpăţânat! Fast-forwarding, am găsit un algoritm nou pentru problemă, unde am putut folosi chiar optimizarea menţionată în lista de tehnici de la olimpiade de mai sus.

Două gânduri

Andrei a fost de acord cu mine că nota a fost obţinută după un efort considerabil de a explica cât mai bine cum curg ideile una din alta. Nu era suficient să fie clar, trebuia să şi pară natural şirul logic al ideilor prezentate. După aceasta "dezvăluire a secretului", aş încheia postarea cu un mesaj de încurajare adresat juniorilor, seniorilor şi studenţilor nostri, din partea lui Andrei:

Mi se par sincer prea puţini aceia care îsi doresc o carieră în cercetare, şi sunt uimit de numărul covârsitor al oamenilor, în unele cazuri medaliaţi chiar şi cu aur la olimpiadele internaţionale, care nici nu iau în calcul această variantă. Industria tech nu trebuie văzută ca un life goal după olimpiade - există atât de multe lucruri stimulante intelectual în cercetare şi pe care nu le vei găsi niciodată în industrie, lucruri care pot aduce o satisfacţie extraordinară - de la a învăţa lucruri noi şi până la descoperi o nouă teorie, poate chiar ceva ce poate salva vieţi!

Categorii:
remote content