h2. Despre ce e vorba in 'proiectul':https://github.com/Andrei1998/bachelors-thesis 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ătorul Marcel ordonează candidaţii astfel: %{color:red}Blossom% > %{color:blue}Bubbles% > %{color:green}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':https://en.wikipedia.org/wiki/Two-round_system folosit pentru alegerile prezidenţiale).
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: %{color:red}Blossom% > %{color:blue}Bubbles% > %{color:green}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':https://en.wikipedia.org/wiki/Two-round_system folosit pentru alegerile prezidenţiale).
L-am rugat pe ==User(user="Andrei1998" type="tiny")== să facă un rezumat al detaliilor algoritmice ale proiectului său:
L-am rugat pe ==User(user="Andrei1998" type="tiny")== să facă un rezumat al detaliilor algoritmice ale proiectului său.
h3. Î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':https://ioinformatics.org/files/ioi2016problem6.pdf de la IOI $2016$. Tehnica a mai fost folosită ulterior în problema 'Popcorn':problema/popcorn, iar membrii comunităţii au găsit soluţii alternative mai simple ce o folosesc în probleme propuse în trecut: 'Padurari':problema/padurari şi 'Flooow':problema/flooow.
* Optimizarea "<tex>O(nk^2)</tex> devine <tex>O(nk)</tex>", care a apărut pentru prima oară în România o dată cu problema 'Cli':problema/cli. Aceasta este o rafinare a mai cunoscutei "<tex>O(n^3)</tex> devine <tex>O(n^2)</tex>", folosită în probleme precum: 'Politic':problema/politic, 'Purification':problema/purification şi 'Tricolor':problema/tricolor. Dacă nu aţi auzit de acest smen, puteţi citi o superba explicaţie începând cu pagina $22$ de 'aici':http://www.lookingforachallengethebook.com/uploads/1/4/5/5/14555448/preview-_looking_for_a_challenge.pdf (problema Barricades).
* În afara programei de olimpiadă: 'Algoritmul Simplex':https://en.wikipedia.org/wiki/Linear_programming. Cu toate acestea, problema 'Echilibrare':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 in 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!
* Optimizarea "<tex>O(nk^2)</tex> devine <tex>O(nk)</tex>", care a apărut în România o dată cu problemele 'Arbkset':problema/arbkset, 'Lianyu':problema/lianyu şi 'Cli':problema/cli. Aceasta este o rafinare a mai cunoscutei "<tex>O(n^3)</tex> devine <tex>O(n^2)</tex>", folosită în probleme precum: 'Politic':problema/politic, 'Purification':problema/purification şi 'Tricolor':problema/tricolor. Dacă nu aţi auzit de acest smen, puteţi citi o superba explicaţie începând cu pagina $22$ de 'aici':http://www.lookingforachallengethebook.com/uploads/1/4/5/5/14555448/preview-_looking_for_a_challenge.pdf (problema Barricades).
* În afara programei de olimpiadă: 'Algoritmul Simplex':https://en.wikipedia.org/wiki/Linear_programming. Cu toate acestea, problema 'Echilibrare':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 "wrost-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!
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':https://arxiv.org/abs/2010.08637}-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.
h2. Ideile pe care voiam să le extragem
Mai întâi, vreau să remarcăm ca aceasta lucrare are ca substrat *algoritmica*, şi arată cât de utile ne pot fi cunoştinţele şi skill-urile dobândite pregătindu-ne pentru olimpiade.
Apoi, ce vreau eu cel mai mult şi mai mult să subliniez este că nota a fost obţinută după un efort uriaş 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! Acestea au fost posibile după ce ani la rând, Andrei a predat informatica, în cele mai diverse contexte, oricui era pasionat. Experienţa sa în acest domeniu, *implicarea sa în comunitate*, au fost factorii principali, din punctul meu de vedere, care au contribuit la succesul său.
h2. Două gânduri
În concluzie, îl las pe Andrei sa transmită un mesaj de încurajare juniorilor, seniorilor şi studenţilor nostri:
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:
bq. 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!
