Blog infoarena

Interviu cu Mihai Patrascu - partea a doua

Cosmin
Cosmin Negruseri
19 octombrie 2007

Acum zece zile am publicat prima parte a interviului cu Mihai Patrascu . A venit timpul sa publicam si partea a doua. In ea Mihai ne vorbeste de olimpiade, de modul lui de lucru si de interese in afara programarii:

Cum ai recomanda cuiva sa se antreneze pentru concursuri sau sa se pregateasca pentru cercetare?

Cred ca cel mai eficient e sa ajungi sa programezi suficient de bine, si apoi sa te concentrezi pe gandirea teoretica la probleme. De prin clasa a 10a nu programam decat cateva zile inainte de olimpiada sa-mi intru in mana. Restul doar ma gandeam dar nu implementam (economiseste mult timp la pregatire).

Din cauza asta nu am fost niciodata un programator prea rapid... In plus capacitatea mea de debug este aproape nula, asa ca preferam sa scriu foarte incet si fara buguri. N-as avea niciodata sanse la un concurs ca ACM sau top coder :)

Care e secretul reusitei la concursuri sau in cercetare? caracteristicile native, educatia profunda, munca depusa?

Clar ca fara inteligenta nu se poate :), dar toti oamenii care ajung sa faca ceva la olimpiade sunt foarte inteligenti. Cred ca ce face diferenta la un nivel inalt e atitudinea personala. In mod constant erau oameni in lot pe care ii consideram mai destepti decat mine, dar eu eram mai hotarat sa castig, lucram mai mult cand trebuia sa lucrez, ma relaxam mai mult cand trebuia sa ma relaxez etc. Nici ceilalti concurenti, nici comisia nu sunt cu un cap mai sus ca tine -- daca tu ai incredere ca esti tare, atunci chiar esti mai tare.

Cum abordezi o problema, ai o reteta standard (generalizare, simplificare, trecerea prin o lista de tehnici) sau ai cate un "aha" moment?

Nu, simt ca intotdeauna imi vin idei dubioase si fara explicatie. Problemele la care ma prindeam cel mai greu erau chestii clasice ca flux, cuplaj, etc -- pana sa ma gandesc ca de fapt poate se foloseste ceva standard imi lua ceva timp.

Cum se compune o problema de olimpiada?

Foarte greu... Am un dispret pentru problemele bazate pe materie avansata. Ne trebuie probleme noi, cu o rezolvare elementara, nu bazate pe ceva care inveti la facultate. Problemele trebuie sa fie cu adevarat concurs de perspicacitate, si ar trebui sa fie la fel de grele pentru un concurent din liceu si pentru un prof care studiaza algoritmi de 50 de ani... Din pacate, e greu de gasit astfel de probleme, si nu am propus prea multe probleme.

De ce nu ai continuat cu concursurile de programare in timpul facultatii?

Concursurile mi se par prin definitie ceva pentru liceu. La nivelul ala inca inveti, si e bine ca ceva sa te motiveze sa inveti, in timp ce iti ascuti inteligenta in domeniu. La facultate stii mai multe, si pot sa faci alte chestii mai important pentru tine si pentru omenire... Poti sa te angajezi, sa lucrezi in cercetare, etc. Poti sa-ti faci un renume la inceput cu IOI, dar pana la urma succesul in viata depinde de alte chestii.

Asta gandeam inca din liceu, asa ca mi-a fost usor sa renunt. In treacat fie spus, am fost de 2 ori la ACM din inertie, o data cu Craiova, si o data la MIT. Amandoua esecuri lamentabile :) Cu echipa din Craiova problema era ca nimeni nu programa suficient de repede (in frunte cu mine). Cu MIT problema a fost interactiunea mea cu autoritatea :) -- am iesit primul la concursul individual, dar echipa s-a format din locurile 2,3,4 la decizia profilor coordonatori.
Razbunarea mea a fost ca anul ala MIT-ul nu s-a calificat la regionala ;)

La ce alte proiecte software ai lucrat?

Singurul proiect mai mare care l-am facut a fost evaluatorul pentru olimpiade (nu stiu daca se mai foloseste, dar s-a folosit la BOI la Iasi si la cateva nationale). Restul totul au fost programe mici pt olimpiade. Si cand am lucrat pentru companii, am lucrat pe directii de cercetare unde nu trebuie decat programe mici prototip care sa testeze o idee.

Ai vreo metoda dupa care iti imparti timpul sau lucrezi cand si cum ai chef?

Eu profit de libertatea din cercetare pana la punctul unde enervez pe toata lumea :) Daca n-am chef sa fac nimic saptamana asta, nu fac nimic saptamana asta. Ma duc la munte, citesc ceva, nu conteaza. Cand lumea munceste la o lucrare (care implica finalizat tot felul de detalii si scrisul propriu-zis), eu de obicei fac misto de ei :) De obicei nu reusesc nici macar sa scriu pe hartie niste calcule.

Dar daca am o idee de rezolvare in cap si vreau sa scriu o lucrare pentru o conferinta, am o reteta standard. Cu 2-3 zile inainte de deadline, imi iau periuta de dinti, 10-15 sticle de Pepsi Diet, cateva kg de prajituri, si ma duc in birou. Si acolo petrec cele 2-3 zile lucrand (am determinat ca rata optima de somn in birou e cam 2h pe zi). Adrenalina e foarte interesanta.

Citesti bloguri/frecventezi forumuri? Spune-ne cateva exemple.

Chiar am si eu un blog la http://infoweekly.blogspot.com/, in care discut probleme de cercetare in algoritmi. Cred ca unele chestii ar putea fi interesante pentru studentii la olimpiade in ani mai mari, care vor sa se decida ce vor sa faca in viitor. Pot sa vada cateva probleme si sa vada daca ii tenteaza teoria.

De citit, citesc cateva bloguri din teorie, dar nu cu prea multa pasiune (doar ca e util sa te tii la curent). La forumuri nu particip.

Ce interese, hobbyuri, pasiuni care nu sunt legate de programare ai?

A, multe... Desi intotdeauna stau rau cu timpul, asa ca fac mai putine decat as vrea. Imi place foarte mult sa calatoresc, si acum pot sa fac asta cu toate conferintele la care ma duc (am ajuns in 28 de tari pana acum). Imi place sa vorbesc cu lumea, sa descopar culturi noi, si imi place sa citesc mult despre istorie.

Periodic descopar pasiuni pt un nou sport. In liceu mergeam pe munte si jucam badmington, apoi am facut alergari (era o vreme cand alergam 16km pe seara), am jucat rugby (in Divizia 3 din State), mai recent climbing si sailing.

Pe ce te concentrezi acum?

Anul asta voi termina doctoratul... Trebuie sa scriu o teza si sa aplic pentru joburi (in pricipal, o sa aplic pentru joburi de prof la universitati). Asta ia destul de mult timp. In rest, mai lucrez la cercetare, si mai calatoresc.

Cum tii pasul cu cercetarea curenta? Sunt conferintele importante si discutiile cu ceilalti cercetatori (comunitatea din care faci parte), sau e deajuns sa citesti research paperurile ce apar?

Sunt cateva conferinte importante la care ma duc intotdeauna. Problema e ca nu pot sa stau intr-o sala si sa ascult o prezentare (lipsa de concentrare). Asa ca in timpul conferintei ma intalnesc cu prieteni vechi care de asemenea nu vor sa fie prezenti, si mergem la bere sa mai discutam probleme. Ca sa aflu ce se intampla citesc lucrari pe Net.

Cum te vezi in 5-10 ani?

Sper ca cu un job :) Planul este sa lucrez in continuare in domeniu si sa mai rezolv cateva probleme importante. Apoi as vrea sa incerc si sa fondez o companie cu o idee trasnet. Avem multe rezultate valoroase in teorie, care nu se aplica pentru ca lumea nu se gandeste suficient la impactul mai larg si nu gaseste aplicatiile bune. Daca imi vine vreo idee buna la capitolul asta nu voi ezita sa incerc o companie, in paralel cu jobul de prof.

Vrei sa le transmiti ceva celor ce acum incep cu viata competitionala?

E sansa voastra sa aratati lumii ce tari sunteti, si sa deveniti si mai tari pe parcurs. E un drum bun in viata.

Ii multumim lui Mihai pentru un interviu foarte interesant.

 Comentarii (4)

Categorii: concursuri interviu

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 (concurand la clasa 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 sa stai cuminte si sa 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 extazul 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(n\ lg^2 n), si s-au prins cativa oameni. Apoi m-am mai gandit la problema, am gasit o rezolvare in O(n\ lg 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^{3/4}), 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 (3)

Categorii: interviu
Vezi pagina: 12  (12 rezultate)