!<blog/interviu-mihai-patrascu-partea-intai?mip-portrait.jpg!_(big)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':utilizator/mpatrascu _(big)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':http://www.cra.org/Activities/awards/undergrad/2005.patrascu.html _(big)pe Statele Unite si Canada. Are chiar si o pagina pe_ 'wikipedia':http://ro.wikipedia.org/wiki/Mihai_P%C4%83tra%C5%9Fcu_%28informatician%29

'Mihai Patrascu':utilizator/mpatrascu _(big)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':http://www.cra.org/Activities/awards/undergrad/2005.patrascu.html _(big)pe Statele Unite si Canada. Are chiar si o pagina pe_ 'wikipedia':http://ro.wikipedia.org/wiki/Mihai_P%C4%83tra%C5%9Fcu_%28informatician%29

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

**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 <tex>O(nlg^2 n)</tex>, si s-au prins cativa oameni. Apoi m-am mai gandit la problema, am gasit o rezolvare in <tex>O(n lg n)</tex> 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 <tex>O(n^{4/3})</tex>, care l-a publicat la European Symposium on Algorithms. Bineinteles ca asta m-a motivat, si i-am imbunatatit algoritmul la <tex>O(n^{2/3})</tex> -- deci recordul revine la Romania :)

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 <tex>O(n\ lg^2 n)</tex>, si s-au prins cativa oameni. Apoi m-am mai gandit la problema, am gasit o rezolvare in <tex>O(n\ lg n)</tex> 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 <tex>O(n^{3/4})</tex>, care l-a publicat la European Symposium on Algorithms. Bineinteles ca asta m-a motivat, si i-am imbunatatit algoritmul la <tex>O(n^{2/3})</tex> -- 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.

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

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

Cred ca toata lumea stie ca se face in <tex>O(lg\ n)</tex> 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 <tex>O(lg  n)</tex> 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.

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 <tex>O(lg\ n)</tex> 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 :)
h2. _(big)A doua parte din interviu va fi publicata in curand._

'Comentarii':forum/index.php?topic=2164.0

2164