Cat e complexitatea ca timp a Ciurului lui Erastotene? Motivati raspunsul.

Update: E interesant ca nu stim complexitatea unui algoritm pe care il invatam in clasa a 5-a. Ne gandim mai intai ca algoritmul trebuie sa fie mai rapid decat , pentru ca facem n pasi si fiecare pas e mai eficient decat o parcurgere a celor n numere. Daca ne uitam mai atent, numerele sunt parcurse pe sarite si numarul de operatii e . Sirul este convergent, astfel deducem ca ciurul lui eratostene are complexitatea mai mica decat . Nu am folosit faptul ca in algoritm noi vom marca doar pornind de la valori prime, sarind peste multe valori, astfel numarul de operatii al algoritmului e unde pk e cel mai mare numar prim mai mic decat n. Sirul e convergent dupa cum putem citi aici . Astfel complexitatea algoritmului Ciurul lui Erstotene este .

Am o alta intrebare pentru voi: Stiti cat e complexitatea algoritmului lui Euclid?

Cautam de ceva vreme bloguri interesante legate de programare, si am dat la un moment dat peste blogs.msdn.com si peste studentclub.ro. Primele sunt bloguri ale unor angajati Microsoft si urmatoarele sunt bloguri ale unor studenti romani, membrii de organizatii studentesti asociate Microsoft.

Pe ambele platforme apar destul de des stiri despre noile si fascinantele tehnologii M$. Pe blogs.msdn.com sunt si multe posturi interesante si inteleg ca, din cand in cand, oamenii trebuie sa isi promoveze tehnologiile si chestiile la care muncesc. Ceea ce nu inteleg este promovarea aceluiasi gen de subiecte propagandistice de catre studenti. Cei care sunt interesati de asemenea chestii, oricum le pot lua direct de la sursa. Nu inteleg inca aceasta entuziasmare la tot ce e nou, si mi se pare o incercare nereusita de a parea la fel de cool ca fratii lor mai mari care lucreaza la M$.

Nu toate blogurile, sau toate posturile de pe studentclub sunt rele, dar multe care le-am vazut m-au lasat cu o impresie proasta. Exista si posturi foarte bune cum ar fi acesta in care doi frati povestesc experienta lor la internship la Microsoft, din vara aceasta. Daca va uitati atent ii vedeti in poza pe Mircea Pasoi si pe Tiberiu Florea , care au fost si ei la internship la M$ peste vara.

Problema a fost rezolvata de Mihai Patrascu, Radu Cebanu, Adrian Vladu, Marius Buzea, Marius Andrei, Adrian Carcu, Giurgea Mihnea, Liviu Ciortea, Adrian Sandor, Razvan Alecsandrescu, Igor Naverniouk si Csaba Patcas.

La prima vedere pare nerezolvabila, dar de fapt are o solutie destul de simpla. Ea se bazeaza pe faptul ca multimea ZxZ e numarabila. Putem verifica in fiecare secunda T cate o coordonata X0 + Y * T, parcurgand perechile (X0, Y) in spirala. Vom ajunge la un T1 pentru care teroristul este la locatia X0 + Y * T1. Inca nu am rezolvat problema, pentru ca pot exista mai multe perechi de numere pentru care teroristul sa fie la locatia X0 + Y * T1 in momentul T1. Prin faptul ca am gasit pozitia teroristului la un moment fixat T1, am redus problema la una noua determinata de parametrii X0', Y' in care in care nu il stim pe Y dar X0' = X0 + Y * T1. Aceasta subproblema se poate rezolva usor.

Alta problema cu teroristi ce mie imi place foarte mult este Lesbulan , ca dovada am si propus-o la concursul Bursele Agora.

Probleme cu tema similara sunt si Soarecele si pisica (medie ca dificultate, de pe Lista lu' Francu), Tom & Jerry (grea, nu a facut-o nimeni din cate stiu eu cand a propus-o Mugurel la lot) si tunnels (foarte grea, nu a facut-o nici o echipa in finala ACM ICPC 2006), smuggler (de pe rec.puzzles.org cu solutie). Daca sunteti curiosi de rezolvari, putem sa le discutam pe forum.

Un prieten imi zicea recent ca pun prea multe referinte la Google in posturi, si ar trebui sa adaug referinte la Microsoft ca blogul sa fie mai obiectiv (el lucreaza pentru M$).

Pentru a mai echilibra scorul, am pus videoul de mai jos cu o demonstratie impresionanta a unei aplicatii Microsoft. Demonstratia a avut loc tot la TED talks. Cred ca visul oricarui programator este sa lucreze la un astfel de proiect revolutionar.

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.

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

Pacat.

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:

• Partea 1
• Partea a 2-a

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!

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 :).

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.