Blog infoarena

Sedinte Infoarena

Cosmin
Cosmin Negruseri
03 noiembrie 2007

A inceput de ceva vreme anul scolar si ne-am hotartat sa ne organizam si sa punem osul la treaba. Astfel recent cei din echipa infoarena am avut doua sedinte in care am pus tara la cale.

Pentru ca siteul infoarena nu ar fi nimic fara comunitatea utilizatorilor ei, ne-am decis sa va informam despre discutiile si deciziile luate:

Au aparut cateva schimbari in echipa, astfel Andrei Grigorean si Adrian Airinei devin consilieri. Eu am devenit consilier (din consilier emeritus, ce insemna consilier fara activitate). Adrian Vladu a devenit consilier emeritus.

S-a discutat despre concursul preONI 2008 pe care il va coordona Mircea. Formatul va fi acelasi ca si anul trecut cu patru runde si finala "onsite". Va incepe in luna noiembrie. Cristi va cauta sponsori.

S-au definit mai clar rolurile membrilor, astfel eu ma voi ocupa de blog. De forum, calendar si coordonarea concursurilor inafara de preOni se va ocupa Andrei. Silviu va fi responsabil de sectiunea cu articole ajutat de Catalin Tiseanu, si pe langa asta va fi implicat in cautarea de sponsori. Cristi se ocupa de comunitate, de newsletters si de implementarea comentariilor pentru blog. Adrian Diaconu si Daniel vor avea grija de arhiva de probleme. Valentin va munci pe partea proiectelor noi in comunitatea infoarena de la Implica-te . Leo se ocupa de partea de gestiune a banilor si va continua sa se ocupe ca si pana acum de evaluator. Iar Adrian Airinei va lucra pe partea de organizare a concursurilor.

Mircea si Leo au adus in discutie lucrul la infoarena 3.0 care presupune o rescriere a siteului. Deocamdata suntem in faza de discutii, iar Mircea si Leo ne vor arata la urmatoarea sedinta un design doc pentru a putea evalua mai bine ce avantaje si dezavantaje sunt in lucrul la un nou site.

Va reamintesc ca avem proiecte interesante la sectiunea implica-te , unde ajutorul vostru e binevenit.

 Comentarii (0)

Ginfo a murit

Cosmin
Cosmin Negruseri
01 noiembrie 2007

Mihai Scortaru, redactorul sef al Ginfo , a anutat ca revista isi intrerupe aparitia.

Pacat.

 Comentarii (2)

Categorii:

Interviu Catalin Francu

wickedman
Cristian Strat
31 octombrie 2007

Cosmin a publicat pe blog-ul infoarena un interviu cu nimeni altul decat Catalin Francu.

Catalin este cunoscut in lumea celor pasionati de informatica prin cartea "Psihologia concursurilor de informatica", o carte plina de probleme frumoase si deschizatoare de drumuri la vremea ei, si prin "lista lu' Francu", o lista de discutii pe email, unde cativa dintre cei ce au ajuns apoi olimpici internationali la informatica ai Romaniei rezolvau si discutau probleme.

In lumea lingvistilor este cunoscut prin proiectul dexonline . Acesta [...] contine intreg Dictionarul Explicativ al limbii romane si alte dictionare. In timpul liceului, Catalin a luat o medalie de argint la IOI, iar in timpul facultatii s-a clasat pe locul 7 la etapa finala a concursului ACM ICPC cu echipa reprezentanta a MIT. De asemenea a facut parte din comisia stiintifica a Olimpiadei de Informatica a Europei Centrale din 2000 care s-a desfasurat la Cluj. Dupa terminarea facultatii Catalin a lucrat patru ani ca programator la Google inc.

Citeste interviul acum:

 Comentarii ()

Categorii: stiri

Interviu cu Catalin Francu - partea a doua

Cosmin
Cosmin Negruseri
31 octombrie 2007

In aceasta a doua parte a interviului, Catalin ne povesteste despre MIT, dexOnline, Nilatac, Google si alte lucruri foarte interesante. Daca ati ratat prima parte a interviului, citi-o aici .

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

Pentru ca MIT-ul a fost singura universitate care m-a acceptat (privind in urma, am avut un noroc fenomenal). La Politehnica din Bucuresti am facut trei ani de zile si au fost cursuri dupa care m-am dat in vant (de exemplu, cel de Structuri de Date si Algoritmi sau cel de Limbaje Formale si Translatoare). Totusi, erau mult prea multe alte cursuri care nu aveau ce cauta in programa obligatorie si pur si simplu am zis ca nu mai vreau sa invat lucruri inutile.

Care au fost cursurile tale preferate in facultate? Ne poti face si o descriere pe scurt?

De la MIT, mi-a placut in mod deosebit cursul de Securitatea Calculatoarelor si Retelelor, care a trecut prin subiecte ca one-way functions, chei publice/private, cookie-uri, spyware, virusi, semnaturi digitale, certificate si multe altele.

Ce cursuri ti-au fost folositoare in viata de programator?

Eu sunt de parere ca practica intr-o companie este foarte deosebita de teoria invatata in scoala. Am luat cursuri de criptografie, algoritmi de aproximare, procese stocastice, probabilitati, limbaje formale si niciunul nu mi-a folosit in mod direct. Mi-ar fi folosit daca as fi scris un client de ssh sau un sistem de modelare financiara, dar nu am avut ocazia sa aplic atat de direct lucrurile invatate la un curs. Indirect, insa, toate mi-au fost folositoare pentru ca m-au invatat concepte noi si, cand m-am izbit de o problema noua, a fost mai usor sa o reduc la ceva cunoscut. De exemplu, nu-mi mai amintesc toti algoritmii studiati la cursul de criptografie, dar mi-au ramas notiuni fundamentale de algebra modulara si teoria numerelor, de care m-am tot izbit in practica.

De cati ani esti in USA?

Din 1999.

Te simti ca acasa aici?

Cred ca oriunde traiesti mai mult de o luna - doua devine acasa.

De ce ti se face dor?

In primii ani petrecuti in America, mi-era dor de Romania. Acum, pe langa asta, cand sunt in Romania mi-e dor de locurile si de prietenii de aici. Cu alte cuvinte, din cauza ca am trait si sunt legat de doua locuri, oriunde m-as duce mi-e dor de ceva. :)

Te vei mai intoarce vreodata in Romania?

Categoric! Ne-am straduit foarte mult sa ne intretinem relatiile personale din Romania.

Ce e dexOnline?

Pentru oameni, este un dictionar explicativ roman online. Pentru mine, este cea mai mare realizare profesionala a mea.

Cum ai inceput cu acest proiect?

In vara lui 2001, am adus cu mine din Romania un dictionar explicativ (DEX). Pe de alta parte, foloseam intens Webster, dictionarul explicativ englez online. M-am gandit ca ar fi cazul sa existe si o pagina similara pentru limba romana.

La acea vreme, eu nu aveam practic nici una din cunostintele necesare. Stiam putin HTML si aveam o idee despre ce inseamna o pagina dinamica, dar cam atat. Restul, PHP, Apache HTTP, MySQL, CSS, template-uri Smarty si altele le-am invatat cu timpul.

Cat timp crezi ca ai petrecut scriind cod pentru proiect?

Mi-e greu sa fac o estimare. Lucrez de sase ani si am avut saptamani in care n-am facut nimic, saptamani in care am scris cod 30-40 de ore pe saptamana si saptamani in care m-am ocupat de treburi care tin de DEX online, dar nu de programare (de exemplu, introducerea sau moderarea de definitii). Nici numarul de linii de cod nu este o masura buna, pentru ca am aruncat mai mult decat am folosit (de exemplu, prima versiune a serverului era scrisa in Perl).

Care este cel mai frumos moment legat de dexOnline pe care l-ai trait?

Cred ca a fost in 2004, cand echipa a terminat de introdus DEX-ul. Era doar un inceput (20% din numarul de definitii si mult mai putine functii pentru cautare decat azi), dar am simtit cu totii o satisfactie enorma pentru ca am muncit mult si pentru ca toata lumea ne credea nebuni. Astazi avem mult mai multe definitii, DEX online stie sa flexioneze cuvinte, de curand am adaugat si cautarea full-text si realizarile astea pot umbri putin acel prim pas. Dar fara el n-am fi ajuns unde suntem azi.

Spune-ne alt proiect interesant la care ai lucrat.

Am scris un motor de anti-sah pe care l-am botezat "Nilatac" (nu prea creativ, dar e prea tarziu sa-l mai redenumesc). Anti-sahul este o varianta de sah in care captura este obligatorie, iar scopul este sa iti pierzi toate piesele (inclusiv regele, care nu are un statut special). Voiam sa scriu un program de sah care sa stea conectat la FICS (http://freechess.org) si mi-am ales varianta asta, anti-sah, pentru ca era mai simplu de implementat: nu exista sah, nu exista rocada, iar regele poate fi capturat. Spre surprinderea mea, am descoperit ca varianta nu este lipsita de complexitate si frumusete. Jucatorii de varf spun chiar ca anti-sahul se poate masura cu sahul in complexitate.

Am lucrat la Nilatac din 2001 pana prin 2005 si la inceput singurul algoritm pe care il stiam era alpha-beta. Am scris un program cu acest algoritm, l-am conectat la FICS foarte sigur pe mine si... surpriza: multi jucatori umani il bateau frecvent, iar calculatoarele nici nu discutau cu el. Asa am fost silit sa invat multe alte tehnici, de la carti de deschideri pana la tabele de finaluri si de la o reprezentare mai eficienta a tablei de joc (rotated bitboards) pana la un algoritm complet nou de cautare a arborelui de joc, (Proof Number Search).

O particularitate interesanta este ca arborele de joc pentru anti-sah este mai mic decat cel pentru sah, din cauza ca initiativa este foarte importanta si o greseala poate duce la pierderea fortata a jocului (cel care a gresit o data poate fi obligat sa captureze piesa dupa piesa pana pierde partida). Din aceasta cauza, lumea spera ca jocul poate fi rezolvat complet. Dupa mutarea 1. e3, se pare ca negrul nu are un raspuns care sa echilibreze partida. Mi-am adus si eu o mica contributie, rezolvand cateva linii din deschidere, iar acum codul si cartea de deschideri sunt disponibile pe internet.

Cum ai ajuns la Google?

Am fost acceptat ca intern in 2001, la recomandarea fratelui meu si a advisorului meu de la MIT. in 2002 m-am angajat propriu-zis, dupa ce am absolvit facultatea.

Cum a fost viata de programator la Google? Ce iti placea cel mai mult?

Disciplina programarii era extraordinara. Cu totii stim ca e bine ca, atunci cand dai peste un bug in cod, nu e bine sa-l ignori. Fie il repari, fie il raportezi autorului, fie cel putin introduci un raport in bugzilla. Dar la Google lucrul asta chiar se intampla :) Cand scrii o functie noua, care poate fi folositoare si altor echipe, nu pui codul in modulul echipei tale, pe care celelalte echipe nu il folosesc, ci in modulul comun. Lucrul asta cere mai mult timp, pentru ca trebuie sa compilezi si sa rulezi teste suplimentare, dar este atitudinea corecta si Google o incurajeaza.

In general, mi-a placut filozofia lor de a face lucrurile bine din prima, chiar daca dureaza mai mult. Fiecare linie de cod trebuie vazuta de cel putin inca o persoana in afara de autor. Asta ridica probleme cum ar fi ca, dupa ce termini de scris o bucata de cod si i-o trimiti unui coleg ca sa ti-o revizuiasca, dureaza cateva ore pana primesti raspunsul si trebuie sa-ti gasesti altceva disjunct la care sa lucrezi pana atunci. Dar beneficiile sunt mari, pentru ca multe buguri sunt gasite inca inainte de a fi adaugate la repository.

De ce ai plecat?

Am vrut sa am o perioada mai lunga in care sa ma pot ocupa cu norma intreaga de DEX online si de alte proiecte personale (programare, dar si din alte domenii).

De ce programare si nu cercetare?

Probabil tot Google e raspunsul. :) M-ar fi atras un Ph.D. si o cariera academica, dar mi-a fost imposibil sa dau cu piciorul ocaziei de a lucra la Google.

Cum e organizat mediul in care lucrezi? Ce configuratie de calculator? Ce sistem de operare, ide, etc.?

Ca sistem de operare, am pornit cu RedHat in 1999 si am continuat pe aceeasi linie (azi rulez Fedora). M-am tot gandit sa incerc si alte distributii, dar viata parca e prea scurta ca sa o pierzi instaland sisteme de operare... Un IDE nu folosesc, pentru ca nu exista unul bun pentru dezvoltare de pagini de web. As vrea ceva cu suport pentru PHP, HTML, CSS, MySQL, Javascript si, desi am incercat Eclipse si IntelliJ, niciunul nu pare sa se potriveasca. Asa ca am ramas tot in stadiul de terminal text + emacs si nu pot sa zic ca imi lipseste ceva.

Poate un lucru amuzant e ca n-am avut niciodata un CD sau DVD de instalare pentru Fedora. intotdeauna am creat un CD minim de boot, dupa care instalarea propriu-zisa am facut-o prin retea.

Ce calitati are un programator bun?

Lucrurile astea le-am invatat si eu de-abia dupa ce am iesit din scoala si am inceput sa lucrez la Google. Descoperi ca una este programarea de olimpiada sau o tema de facultate, unde practic lucrezi ca un hamster intr-un acvariu, si cu totul altceva este lucrul intr-o echipa. Bunaoara, un principiu de baza la Google era ca, daca cineva vine si te intreaba ceva, trebuie sa-ti faci timp sa-i raspunzi, chiar daca si tu ai proiectele si termenele tale. Este mai bine sa aveti amandoi un randament de 80-90% decat sa ai tu un randament de 100% si colegul tau sa nu stie ce are de facut.

La fel, este important sa comunici cu restul echipei, sa stii la ce lucreaza ceilalti si ceilalti sa stie la ce lucrezi tu, nu neaparat la nivel de ora sau zi, dar cel putin la nivel de saptamana. Este important ca toata lumea care lucreaza la un proiect sa adopte acelasi stil de formatare a codului. Un programator bun trebuie sa poata citi codul altuia si sa incerce sa-si faca codul cat mai inteligibil de catre altii (graba nu este un motiv sa nu adaugi comentarii acolo unde codul nu este evident).

Desigur, si calitatile individuale sunt importante. Trebuie sa fii ordonat ca sa-ti poti citi propriul cod dupa cativa ani. si asta cere efort, pentru ca peste cativa ani practic vei fi o cu totul alta persoana si de regula una mai inceata la minte. :) Trebuie sa nu-ti fie frica de un limbaj nou, dar nici sa nu extragi doar strictul necesar din el. Bunaoara, multa vreme dupa ce am invatat Java, m-am ferit sa folosesc mecanismul de exceptii. Cu timpul, le-am inteles avantajele si am invatat sa le folosesc pentru a face codul mai frumos si mai robust. De asemenea, trebuie sa ai rabdarea sa te gandesti de doua ori inainte sa implementezi o data.

Care sunt siteurile tale preferate?

Ca tot romanul, citesc stirile din sport in fiecare zi :) Pentru asta, ma duc la http://onlinesport.ro. Citesc stirile pe http://hotnews.ro si pe http://news.google.com. Evident, de cautat caut cu Google, probabil de vreo suta de ori pe zi, dar asta nu punem la socoteala, e ca si cum ai scrie in CV ca stii sa scrii si sa citesti. Daca am nedumeriri despre Fedora si caut pe Google, de cele mai multe ori ajung la http://fedoraforum.org, care are mereu raspunsurile
potrivite. Pentru generalitati, cel mai des folosesc Wikipedia, un site in fata caruia DEX online pur si simplu paleste.

Ce programe iti fac viata mai usoara?

M-am gandit destul de mult la intrebarea asta si am ajuns la concluzia ca nu prea mai sunt programe care sa imi faca viata mai usoara. Exista website-uri fara care m-as simti legat de maini, cum ar fi http://maps.google.com cand vreau sa merg undeva. Dar ca software instalat pe calculator, nu cred ca imi trebuie mai mult decat un sistem standard, de genul Linux + Firefox + OpenOffice.

Ce hobbyuri ai inafara programarii?

Imi place muzica corala (mi-am si petrecut catva timp culegand niste partituri corale cu un software specializat, numit Lilypond). imi place si sahul, desi ma deprima ca joc mai prost decat in liceu, fiindca am mai putin timp liber. si imi plac jocurile pe calculator (desi asta e o afirmatie foarte generala, pentru ca evident sunt jocuri care imi plac si jocuri care nu imi plac).

Ce va urma?

Restul vietii mele :) E o intrebare foarte generala, dar intamplarea face ca vine la un moment bun. Am luat decizia ca 2007 este ultimul an in care mai lucrez la DEX online. De anul viitor vreau sa incep ceva nou, tot legat de programare, si sunt in cautare de idei.

Vrei sa lasi un mesaj cititorilor blogului?

Cred ca noi toti cei pasionati de informatica avem un noroc formidabil. Este una din cele mai palpitante meserii si cine are putina rabdare si disciplina poate produce multe lucruri folositoare si/sau distractive. Asa este si infoarena.ro: este un site cu un continut valoros si cu o comunitate pe masura.

Daca ne gandim la cate lucruri ne ofera internetul si informatica de-a gata, cred ca e bine sa incercam sa si oferim ceva inapoi. Sunt convins ca toti utilizatorii infoarena au mici proiecte personale (in engleza sunt numite atat de distractiv "pet projects") si i-as incuraja pe toti sa le ofere restului lumii ca software liber.
<br>
Multumim pentru interviu!

 Comentarii (2)

Categorii: interviu

Primul cutremur trait in California

Cosmin
Cosmin Negruseri
31 octombrie 2007

Tocmai am simtit un cutremur, a durat vreo 30 de secunde si mi-a zgaltait putin biroul (5.6 grade magnitudine). Am avut senzatii contrastante, pe de o parte ma gandeam ca este primul meu cutremur in CA dupa ce am auzit mult despre ele, si pe cealalta ca ghiozdanul cu chestii de prim ajutor mi-e acasa. Urmatorul gand in minte mi-a fost faptul ca sistemele Google sunt failsafe si daca s-ar strica cateva harddiskuri tot nu ar fi probleme.

Ce mai, "Living on the edge!" in fata calculatorului :).

 Comentarii (6)

Problema saptamanii

Cosmin
Cosmin Negruseri
30 octombrie 2007

Dupa feedbackul pozitiv de la primele doua probleme, m-am decis sa postez cate o problema draguta cam la doua saptamani.

Problema curenta: Un terorist se afla pe o axa infinita la pozitia X0 in momentul T = 0. La fiecare secunda teroristul se muta la dreapta cu Y unitati (Y poate fi si negativ). X0 si Y sunt numere intregi fixate pe care noi nu le stim. La fiecare secunda putem verifica exact o coordonata de pe axa si vom afla daca teroristul e sau nu acolo. Se cere determinarea unei modalitati de a il descoperi pe terorist si de a ii putea prezice pozitiile urmatoare.

Pentru intrebari referitoare la enunt folositi sectiunea de comentarii. Solutiile complete trimiteti-mi-le ca mesaj privat.

 Comentarii (7)

Categorii: potw probleme

Putina istorie ACM ICPC SEERC

Cosmin
Cosmin Negruseri
29 octombrie 2007

Alt titlu la care m-am gandit pentru acest post este "In cate moduri poti sa propui niste probleme busite".
In fiecare an sunt probleme cu problemele de la regionala ACM la care participa studentii romani, iar anul asta s-a vazut mai clar din rezultate si nu din studierea testelor. Va ziceam intr-un post anterior ca un set de probleme bune este unul in care fiecare problema e rezolvata de cel putin o echipa, dar nici o echipa nu rezolva toate problemele. Anul asta sapte echipe au rezolvat toate problemele, una reusind sa le rezolve in doua ore si patru minute, cand timpul total al concursului e de cinci ore.

Putina istorie a problemelor bushite de-a lungul timpului:

In 2002 problema Sly Number implica rezolvarea unui sistem de ecuatii liniare modulare. Un concurent a testat cu backtracking testele comisiei si nici unul nu ii dadea rezultatul asteptat. In timpul concursului, o echipa a rezolvat problema respectiva, facand probabil aceiasi greseala ca si solutia comisiei.

In 2004 la problema City Game, se cerea determinarea dreptunghiului de arie maxima ce contine doar caracterul F pe o matrice ce contine caractere de F si R. Intre teste era unul care specifica o matrice de 100 de randuri si 100 de coloane, dar avea doar 98 de randuri. Daca aveai norocul ca partea de citire din program sa fie implementata ca si cea a comisieri, puteai rezolva problema ... Multe echipe s-au blocat in problema asta clasica, incercand sa isi gaseasca bugul de implementare care era de fapt in testele comisiei. De asemenea in acelasi an s-a propus problema Alibaba despre care am dubii mari ca ar exista vreo solutie de complexitate mai buna decat O(n^2) desi limita de timp din concurs facea ca o asemenea solutie sa obtina mesajul Time Limit Exceeded. Testele la Alibaba sunt foarte misto, cateva teste mici ce merg cu programare dinamica in O(n^2) si doua teste mari la care merge lejer greedy.

In 2005 s-a propus rezolvarea unui puzzle Sudoku, dar toate testele puteau fi rezolvate punand o cifra in locuri fortate, pentru nici un test nu trebuia facut backtracking. Astfel echipele care fac solutia buna au un dezavantaj fata de echipele care nu isi dau seama ca exista cazuri pe care solutia lor nu merge. Problema Adventurous Driving avea ca limita in enunt n <= 100 iar in teste era un n = 1000. Autorul problemei era mandru de ea, pentru ca doar o echipa a rezolvat-o in timpul concursului.

In 2006 problema Shortest Pair of Paths cerea determinarea a doua drumuri minime disjuncte de la sursa la destinatie. Problema este clasica si se rezolva cu flux maxim de cost minim, dar testele au facut ca o solutie ce gaseste de doua ori un drum folosind algoritmul lui Dijkstra sa mearga. Din nou echipele care au stiut ca problema e mai complicata au pierdut timp implementand solutia mai grea. Alta problema bushita a fost Sherloc Holmes care era un knapsack 2d, dar nu prea incapea in memorie pentru ca n si m erau 10000. Dupa concurs s-a vazut ca testele contineau n si m-ul maxim 300.

Acestea nu sunt singurele exemple.

Sa organizezi un concurs cu multe probleme, la un nivel inalt este foarte greu. Putine regionale reusesc asta. Printre ele sunt ECNA, o regionala din Canada, NEERC, una din Rusia, CEPC, regionala Europei Centrale. Acestea au probleme de calitate, de dificultate mare, cu explicatii de solutii scrise, cu o echipa de organizatori care contin studenti care au fost concurenti. Nu e de mirare ca aceste regionale au aproape in fiecare an o echipa in primele cinci din lume.

Si la TopCoder se intampla ca un concurs sa fie bushit, desi ei isi bazeaza afacerea lor pe asta. Dar pentru a evita greselile, care, avand in vedere ca organizeaza mai mult de un concurs pe saptamana, ar fi normal sa se intample, acestia au o metodologie foarte bine pusa la punct. Fiecare problema este rezolvata de inca trei oameni, altii decat autorul, care isi dau cu parerea atat asupra problemei cat si asupra testelor alese. Un al patrulea om are grija ca textul sa nu aiba ambiguitati. Autorul trebuie sa faca enuntul, testele si un validator pentru teste.

Concursul ACM este un eveniment important care se desfasoara o data pe an, si el ar trebui organizat cu grija, astfel incat concurentii sa nu plece cu impresia ca au fost luati in bataie de joc. Ce trebuie facut pentru corectarea problemelor din trecut ar fi intinerirea comisiei stiintifice, scrierea unui validator de teste, si implementarea a mai multor solutii pentru fiecare problema. Nu pare foarte greu, dar se pare ca nu se invata nimic din esecurile anterioare.

Puteti citi si postul lui Florin Manea, antrenor al echipelor universitatii Bucuresti, despre regionala ACM aici

 Comentarii (6)

Categorii: concursuri

Demouri tari de la SIGGRAPH

Cosmin
Cosmin Negruseri
28 octombrie 2007

Pol Catalin mi-a aratat un demo de la SIGGRAPH 2007 . Demonstratia este impresionanta, si ne arata cum, cu un algoritm simplu, putem obtine o calitate foarte buna cand redimensionam imagini. Algoritmul functioneaza bine chiar daca imaginea finala e mai mare decat cea initiala.

M-am uitat pe la alte paperuri si demouri de la SIGGRAPH si am dat peste plasma pong, un joculet foarte misto care mi-a adus aminte de vremurile din liceu cand pierdeam ore in sir implementand diversi algoritmi ce generau plasme sau focuri.

Puteti vedea mai jos cele doua demouri, primul e de cinci minute, iar al doilea de doua. Enjoy!

Update Gasiti aici lucrarea care descrie algoritmul folosit.

 Comentarii (2)

Categorii: video

Interviu cu Catalin Francu - partea intai

Cosmin
Cosmin Negruseri
26 octombrie 2007

Odata cu angajarea mea la Google am avut ocazia sa cunosc multi fosti olimpici, pe care ii stiam doar dupa nume, vazandu-i in Ginfo sau in listele cu premii la diverse concursuri. Unul dintre acesti olimpici este Catalin Francu , caruia, la o cina in San Francisco, i-am smuls promisiunea ca va raspunde la cateva intrebari pentru ce avea sa fie blogul infoarena. Acum va voi prezenta prima parte a interviului, dupa o scurta prezentare a lui Catalin.
Catalin este cunoscut in lumea celor pasionati de informatica prin cartea "Psihologia concursurilor de programare", o carte plina de probleme frumoase si deschizatoare de drumuri la vremea ei, si prin "lista lu' Francu", o lista de discutii pe email, unde cativa dintre cei ce au ajuns apoi olimpici internationali la informatica ai Romaniei rezolvau si discutau probleme. Iar in lumea lingvistilor este cunoscut prin proiectul dexonline . Acesta este un wiki (inovator pentru 2001, cand Catalin a inceput proiectul) care contine intreg Dictionarul Explicativ al limbii romane si alte dictionare. In timpul liceului, Catalin a luat o medalie de argint la olimpiada internationala de informatica, iar in timpul facultatii s-a clasat pe locul 7 la etapa finala a concursului ACM ICPC cu echipa reprezentanta a MIT. De asemenea a facut parte din comisia stiintifica a Olimpiadei de Informatica a Europei Centrale din 2000 care s-a desfasurat la Cluj. Dupa terminarea facultatii Catalin a lucrat patru ani ca programator la Google inc.

In aceasta prima parte a interviului, Cata ne vorbeste de olimpiade, de cartea "Psihologia concursurilor de programare" si despre "Lista lu' Francu".

Cum ai inceput cu informatica?

Parintii mei au facut parte din primele generatii de la ICI, ceea ce si-a pus amprenta asupra mea si a fratelui meu. Prin clasa a 4-a am vazut prima oara un calculator ZX Spectrum. Mi-au placut mult jocurile, iar cu timpul am inceput sa ma intreb si cum sunt facute si daca as putea face si eu ceva asemanator. in clasa a 8-a, cand s-a pus problema sa-mi aleg un liceu, deja nu mai aveam dubii.

Erau alte discipline de care erai interesat in timpul scolii?

Da... in dictionar, langa definitia pentru "tocilar" este poza mea :) Am invatat multe prostii care acum imi dau seama ca au fost pierdere de vreme, dar unele materii chiar mi-au placut. De felul meu am fost atras de matematica si fizica. Muzica si biologia erau frumoase, dar erau predate foarte prost.

Cum si ce lucrai pentru olimpiade?

Generatia mea (promotia 1996) n-a avut foarte multe resurse la indemana. Circulau colectii de probleme din anii trecuti, dar comunicarea intre olimpici era de baza, pentru ca unul afla de un algoritm interesant si il raspandea. Manualele domnului profesor Sorin Tudor au fost multa vreme "Biblia" mea; de altfel consider ca la vremea lor au fost pur si simplu avangardiste (si nu stiu cati profesori se pricepeau sa predea notiunile pe care le contineau acele manuale).

Ce persoane au avut o influenta in formarea ta?

Parintii si fratele meu Cristi, in primul rand. Mi-amintesc ca eram prin clasa a 2-a, iar Cristi tocmai invata despre scheme logice si se chinuia sa mi le explice si mie. Mie imi placeau romburile cel mai mult, dar altceva n-am inteles. :) La liceu am avut multi profesori buni de informatica, dar in special doamna Rodica Cherciu si domnul Sorin Tudor. Este adevarat ca un profesor poate sa atraga sau sa sperie un elev, dupa cum isi preda materia. Nu in ultimul rand, la loturile de informatica au fost intotdeauna oameni deosebiti (elevi si profesori). in lumea olimpiadelor mi-am cunoscut multi dintre prietenii de astazi.

Mai tii minte probleme frumoase de la olimpiada?

Mi-a placut intotdeauna, pentru simplitatea ei, problema acoperirii tablei cu L-triominouri (Se da o tabla cu dimensiunea de 2^n \ast 2^n din care s-a eliminat un patrat. Se cere ca restul sa se acopere cu L-triominouri). Am pus de multe ori aceasta intrebare la interviuri la Google si putini au stiut sa o rezolve in 10-15 minute. Problema care m-a determinat sa ma apuc serios de studiul algoritmilor este "Se da un arbore neorientat. in fiecare nod se afla un bec. Initial toate becurile sunt stinse. Prin atingerea unui bec, el si toate becurile vecine isi schimba starea. Sa se identifice o ordine de atingere a becurilor astfel incat in final toate becurile sa fie aprinse."

Ce structura de date iti place cel mai mult?

E greu de raspuns la intrebarea asta. E mai important sa stii la ce e buna o structura de date decat sa-ti placa. De exemplu, am cunoscut oameni care nu suporta listele inlantuite si folosesc intotdeauna vectori, chiar si atunci cand au de facut insertii sau concatenari.
Cand folosesti Java si ambele structuri sunt deja implementate, si trebuie numai sa stii de ce tip sa declari variabila, aceasta reticenta este foarte daunatoare.

Pentru simplitatea implementarii, imi plac mult seturile disjuncte cu compresia caii (folosite, de exemplu, in algoritmul lui Kruskal pentru aflarea arborelui partial de cost minim). Analiza teoretica a complexitatii este foarte subtila.

Sunt olimpiadele folositoare?

Este iarba verde? :)

Cum e de partea cealalta a baricadei in concursurile de informatica, cand participi ca organizator?

Avem mai putin timp liber, pentru ca mereu e cate ceva de facut, dar satisfactiile si placerea sunt la fel de mari. Daca vreun student sau un profesor are un ceas liber, prefera sa implementeze o solutie pentru vreuna din probleme. Nu numai pentru ca e bine sa avem mai multe solutii pentru verificare, ci si din acea dorinta, care ne impinge pe toti la concursuri, de a ne masura fortele cu o problema noua.

Cum ti-a venit idea sa scrii "Psihologia Concursurilor de Programare"?

Domnul profesor Sorin Tudor a venit cu ideea sa-mi impartasesc cateva din experientele de la olimpiade. Pentru ca de aici nu aveau cum sa rezulte mai mult de 10-20 de pagini, m-am gandit sa adaug cateva structuri de date pe care le-am folosit destul de frecvent la concursuri si care nu erau discutate in manualele de liceu.

Cum ai ales structura cartii si problemele?

M-am gandit la cateva structuri de date, implementabile in timp de concurs, despre care elevii nu prea aveau de unde citi. Problemele alese fie exemplifica folosirea acestor tipuri de date, fie subliniaza unele alegeri care tin de psihologia fiecarui concurent. De exemplu, am gasit un algoritm greedy care merge pe toate exemplele mele, dar nu il pot demonstra matematic. il implementez sau nu? Sau am gasit un algoritm lent cu care stiu ca nu o sa iau punctaj maxim. il implementez sau caut altul mai bun?

Cat timp ti-a luat sa scrii cartea si cat de usor a fost sa o publici?

Cateva luni, dintr-o vacanta de vara pana prin noiembrie. Publicarea nu a fost o problema, deoarece ideea cartii a venit tocmai de la Sorin Tudor, care avea propria editura. Mai problematica a fost tiparirea, pentru ca la migrarea pe alt calculator si pe alta imprimanta, se dadea peste cap toata paginarea (pe vremea aceea nu auzisem de LaTeX, de PDF, sau in general de altceva in afara de Microsoft Word).

A meritat efortul?

Fara nici un dubiu! A fost una din primele mele slujbe platite, am castigat un ban facand ceea ce imi placea si a rezultat ceva palpabil si -- din cate aud -- folositor.

De ce ai inceput lista lui Francu?

In 1996 am inceput (sau mai degraba am continuat, de unde l-a lasat fratele meu) un mic cerc de informatica. Cu timpul am inceput sa corespondam si prin email. Emailurile au capatat valoare in sine si am creat o lista de discutii dedicata.

Cum a evoluat lista si discutiile de pe lista de-a lungul timpului?

La inceput, trimiteam probleme, asteptam o saptamana si corectam solutiile trimise. Perioada cea mai buna a listei, zic eu, a fost cand am introdus o notiune de "coeficient" (se numea DFCC si se masura in Dexteri). Dincolo de copilaria numelui, m-am straduit sa nascocesc un coeficient care scadea incet cu timpul, pentru a-i incuraja pe abonati sa trimita solutii la fiecare etapa.

De ce a murit?

Plecarea la MIT a fost "inceputul sfarsitului". Aveam mai putin timp liber si o vreme s-a ocupat Cristi Cadar de lista (de altfel, el a propus aproape jumatate din numarul problemelor). Ocazional au mai contribuit si alti "ilustri" ca Rodica Pintea, Valentin Gheorghita, Mihai Badoiu, Irina Dumitrascu, Bogdan Dumitru, Alex Susu...

Un alt motiv a fost ca elevii care au participat initial la cercul de informatica au absolvit liceul, ceea ce mi-a redus mie motivatia de preparator. :) si nu in ultimul rand a fost aparitia altor site-uri, romanesti si internationale, dedicate problemelor de programare, cu evaluatoare automate etc. Ma bucur mult ca infoarena.ro incorporeaza majoritatea problemelor propuse pe lista, pentru ca ne-am gandit mult la ele si ar fi fost pacat sa se piarda.

A doua parte a interviului va fi publicata in curand.

In contextul interviului cu Cata (cum ii zic prietenii), infoarena are doua proiecte unde este nevoie de ajutorul vostru. Unul este transcrierea cartii "Psihologia concursurilor de programare" in format textile. Altul ar fi cel de transformare a problemelor din Lista lu' Francu in formatul infoarena si de adaugarea lor in arhiva (au mai ramas vreo 10 probleme de adaugat). Aveti mai multe detalii aici si aici .

In poza de mai sus apar Cristi Strat , 'maestru' Catalin, eu , iar cenzurati sunt doi ilustrii necunoscuti :), se dau puncte de karma pe forum pentru cine ii identifica pe cei doi.

 Comentarii (8)

Categorii: interviu

TED - talks

Cosmin
Cosmin Negruseri
24 octombrie 2007

TED sunt niste conferinte tinute anual cu o serie de discursuri tinute de diversi oameni destepti despre domeniul lor, care sunt deschizatoare de ochi. In 2006 mi-a placut mult talkul despre economie a lui Hans Rosling. El avea o firma cu un produs ce facea niste grafice interactive, animate pe axa timpului. Dupa ce l-a vazut in actiune, Google i-a cumparat firma :). Anul acesta, Hans a mai avut un talk care a fost la fel de interesant, cu un final neasteptat. Fiecare talk are 20 de minute, daca nu faceti ceva important acum, urmariti-le ca merita:

Myths About the Developing World (2006)

Watch the end of poverty (2007)

 Comentarii (4)

Categorii: video
Vezi pagina: 12345... 272829303132 3334353637383940 (393 rezultate)