Atenţie! Aceasta este o versiune veche a paginii, scrisă la 2007-10-09 07:42:10.
Revizia anterioară   Revizia următoare  

Interviu cu Mihai Patrascu - partea intai

Cosmin
Cosmin Negruseri
09 octombrie 2007

Am avut ocazia sa il reintalnesc acum vreo doua luni pe Mihai Patrascu dupa ce ultima data cand il vazusem a fost la Olimpiada Nationala de Informatica din Bacau in 2001. Era venit in Bay Area la un internship la centrul de cercetare IBM Almaden. I-am propus atunci sa facem un interviu pentru viitorul blog de pe infoarena.

Mihai Patrascu are printre cele mai bune rezultate la olimpiadele internationale la informatica dintre romani. A luat premiul I la Olimpiada nationala de informatica din clasa a 4a (ca concurent la a 5a) pana intr-a 12a. La olimpiada internationala la de informatica a luat doua medalii de aur si una de argint (in 2001 a fost locul doi la internationala). La Concursul Europei Centrale de Informatica a luat un aur si un argint, iar la Balcaniada de informatica un argint. In 2005 a luat premiul Outstanding Male Undergraduate Award pe Statele Unite si Canada. Are chiar si o pagina pe wikipedia

Interviul va fi impartit in doua parti. In aceasta parte Mihai discuta despre MIT, despre cercetare si despre olimpiade:

Cum ai inceput cu informatica?

In clasa a 2a, am decis sa ma duc la Palatul Copiilor si sa studiez electronica. Din pacate, cursul de electronica se umpluse, dar mai erau locuri la cursul de programare...

Ai avut pe cineva care te-a ghidat? Un mentor, o persoana de la care ai invatat?

Nu, practic niciodata. La mai sus-mentionatul curs de programare am invatat sa programez in Basic timp de cateva luni, si am fost captivat. Dar cu asta s-au sfarsit cursurile de programare care le-am luat. Am invatat Pascal dintr-o carte intr-a 4a, C din alta carte (in engleza) intr-a 6a, apoi pentru pregatire mai serioasa la olimpiada am citit GInfo, probleme de pe la concursuri, Knuth si CLR. In liceu am fost la profilul de mate-fizica.

Prin facultate a continuat cam la fel. Dupa 1 an la MIT m-am mutat in departamentul de matematica (ca protest pentru departamentul de CS care nu ma lasa in pace), asa ca n-am luat nici pana azi nici un curs de programare. Am luat multe cursuri de algoritmi, evident. Dar n-au avut niciodata legatura cu cercetarea mea :) Probabil mi-am ales domeniul de lucru dupa aceleasi criterii: un domeniu unde nu se facuse progres de peste 15 ani, si ca atare nu mai existau nici profi nici cursuri predate in mod curent...

De ce MIT si nu alte universitati din state sau din Romania?

Am facut un an la poli in Craiova, dar era o atmosfera trista. Practic lumea nu era acolo decat ca sa ia o diploma, si, partea cu adevarat trista, diploma aia nici nu prea conta...

In State, doar MIT-ul m-a acceptat :) Simplu.

Cum a fost procesul de admitere? Cat de mult conteaza o medalie la olimpiada internationala?

Pana acum cativa ani, la MIT studentii internationali erau practic 100% cu medalii la diverse discipline, si clar asta era criteriul de baza. Multe alte universitati (gen Harvard si restul de Ivy League) cautau oameni cu un profil diferit, care sa ajunga politicieni, manageri etc. In perioada aia era faimoasa bariera culturala intre studentii de la MIT si cei de la Harvard.

In zilele noastre a aparut o oarecare convergenta. Internationalii de la MIT sunt mult mai "normali" si doar putini mai au medalii, in timp ce celelalte universitati au inceput sa aprecieze mai mult oamenii cu medalii.

La MIT au fost multe proteste (spre exemplu, Leiserson s-a plans mult) si speram sa revenim la admisia mai elitista (decanul de admisii a fost concediat recent, pe alte motive, si anul asta vom vedea ce face noul decan).

Cum e viata unui roman la MIT, sunt romanii sau strainii in general priviti ca outsideri?

La MIT e foarte greu sa gasesti americani... Toti "americanii" sunt de fapt la prima generatie, fiind imigrati recent impreuna cu parintii. Asta se datoreaza educatiei la nivel de liceu in State, care orienteaza lumea spre stiinte sociale, avocatura etc. Persoanele care stiu teorema lui Pitagora la liceu sunt "buni la matematica", iar cei care Doamne-fereste iau un curs de trigonometrie sunt "geeks".

La toate capitolele, MIT-ul este mai mult decat deschis... Majoritatea oamenilor sunt foarte inteligenti, si exista o toleranta foarte mare (dupa principiul ca oamenillor destepti li se permite). Cei mai ciudati oameni i-am vazut la MIT.

Cursuri preferate in facultate?

Advanced Data Structures (care l-am si predat un an), Advanced Algorithms, Randomized Algorithms, Geometric Computing, Computer Architecture, Microeconomics, Syntax (in lingvistica, nu programare :p)

De ce cercetare si nu programare?

Cred ca mentalitatea de om de stiinta ma caracterizeaza. Imi doresc foarte mult sa aflu raspunsuri, nu numai sa fac ceva care sa mearga. Ca cercetator pot sa las ceva in urma, ceva cunostiinte noi pentru omenire. Ca programator m-as simti mult mai egoist -- fac ceva ca sa castig eu niste bani.

In plus, programarea mi s-a parut intotdeauna o unealta la ce facem noi, nu un scop in sine. Principalul este sa te gandesti, sa "te prinzi", si apoi poti stai cuminte si programezi ideea. Dar esenta e ideea. Un programator bun e unul care gandeste bine, nu unul care tasteaza repede.

Te-au influentat in vreun fel olimpiadele din liceu?

Foarte mult. Motivul evident e ca mi-au oferit o deschidere -- am vazut locuri noi, oameni noi, probleme mai grele, si apoi din cauza lor am ajuns la MIT. Motivul mai subtil dar mai important e ca olimpiadele au fost locul ideal pentru dezvoltarea spiritului competitiv. In Romania este foarte usor sa ajungi blazat si mediocru. La olimpiade descoperi ca poti sa castigi si poti sa pierzi, iar agonia si exstazul sunt la un pas distanta. Odata ce prinzi gustul luptei, iti vei dori mereu sa faci mai mult in viata, si asta te face un om mai reusit.

Ti-a ramas in minte vreo problema de la concursuri?

Am dat la BOI'03 o problema draguta cu Farey sequence. E exemplul meu favorit despre cum problemele de concursuri pot fi interesante si pentru "oamenii mari". La concurs era suficienta o rezolvare in O(nlg^2 n), si s-au prins cativa oameni. Apoi m-am mai gandit la problema, am gasit o rezolvare in O(n) si am publicat-o la o conferinta de Algorithmic Number Theory, ca amuzament matematic. Oamenilor le-am placut, si recent un tip din Polonia (care a fost si
el la IOI prin 1995) a gasit in algoritm in O(n^{4/3}), care l-a publicat la European Symposium on Algorithms. Bineinteles ca asta m-a motivat, si i-am imbunatatit algoritmul la O(n^{2/3}) -- deci recordul revine la Romania :)

Nu e o problema fundamentala care chiar sa conteze, dar arata cum tipul de rationament de la olimpiada e acelasi ca pentru cercetare.

Cum te antrenai in timpul liceului? Studiai din carti? Rezolvai probleme de pe siteuri cu evaluatoare automate? Discutai probleme cu colegii?

Pe vremea mea nu prea existau siteuri cu evaluare automata. N-am folosit niciodata unul, desi cred ca sunt utile.

Eu in principal citeam carti, GInfo, etc si ma gandeam la probleme. Discutam destul de mult cu ceilalti concurenti, de la care invatam idei interesante. Asta se intampla la lot, pentru ca in Craiova nu era nimeni cu care sa pot sa discut.

Ai vreun algoritm/structura de date preferata?

Partial sums, care este o structura de date foarte clasica si simpla. Problema: ai un array A[1..n], poti sa faci update (A[i] = valoare noua), si queries: raporteaza suma A[1]+..+A[k], pentru k dat.

Cred ca toata lumea stie ca se face in O(lg n) cu binary trees, si ideea e super-utila in multe probleme.

Cand am ajuns la MIT, vroiam sa incep sa lucrez in cercetare si citeam lucrari pe care le gaseam pe Internet sa vad despre ce e vorba. Am citit undeva ca nu s-a putut demonstra ca O(lg  n) e optim la problema asta (spre exemplu, ganditi-va ca pentru a face un dictionar, in loc de binary trees poti sa folosesti hashing, care merge in timp constant). Mi s-ar parut straniu ca nimeni n-a putut demonstra asta, asa ca am scris un paper in care am demonstrat. Mi s-a spus apoi ca asta era "problema nr 1" in data structures din 1989, am fost invitat sa dau talkuri despre solutie, si am primit si un premiu.

Totul a fost accidental, pur si simplu eu nu stiam nimic si am avut o perspectiva total diferita de toata lumea... Dar acum evident sunt foarte atasat de problema asta :)

A doua parte din interviu va fi publicata in curand.

Comentarii

Categorii: interviu