Evident suntem toÅ£i diferiÅ£i ca ÅŸi oameni (un fapt excelent), ÅŸi fiecare a avut  motivaÅ£ia sa în a ajunge olimpic È™i în a alege informatica.

Antreprenorii sunt o specie complexă care are nevoie de multe calități pt supraviețuire, nu neapărat aliniate cu calitățile unui informatician de olimpiadă.

Adaug È™i eu niÈ™te poveÈ™ti personale la problemă, anume 2 motive pentru care cred că aÈ™ fi un antreprenor catastrofal, dar  care m-au dus spre succes la olimpiadele de info.


1. Aș fi un antreprenor catastrofal fiindcă îmi place puritatea şi rigurozitatea

De-asta am ajuns la info È™i nu la fizică,care de asmenea mă pasiona mult.ÃŽn fizică,  legile naturii nu sunt scrise într-o carte numită " The C Programming Language ", ci trebe să le aflăm prin niÅŸte experimente destul de impure ( imprecise ÅŸi pline de aproximări). Cum mai adăugăm câteva zerouri la masă, energie sau viteză, hopa, apar niÅŸte legi noi complet diferite pe noi care nu le-am fi putut bănui  Ã®nainte (fiindcă în  cu  experimentele vechi   legile noi afectau rezultatul cu maxim zece la minus 20  sau  cevanemăsurabil  pe-acolo). Devine un pic enervant jocul ăsta : adică cine plm ese crede natura asta să se joace cu aÅŸa cu noi?

Informatica e o ÅŸtiinţă pur intelectuală, poate cea mai mare realizare a intelectului homo sapiens. E destul de remarcabil, zic eu că putem porni de la niÅŸte porÅ£i logice care fac and /or/ not ÅŸi putem ajunge la kernelul de Linux, la compilatoare È™i la la programe de flux maxim scrise în C. Care programe în C fac fix ceea ce ar trebui să facă, dacă rulează  pe un sistem corect construit corect de la bază la vârf.

Pe mine m-a fascinat aspectul ăsta de abstractizare  recursivă e ÅŸi de  construcÅ£ie din ce în ce mai complexă deasupra unor construcÅ£ii anterioare făcute tot de noi. Totul pe bază solidă, adică niÅŸte porÅ£i logice elementar definite, pe care am tot compus chestii mai măreÈ›e. La modul intelectual , chiar nu contează dacă o poartă logică se defectează È™i dacă compilatorul are buguri. La nivel abstract al fiecare  nivel al construcÈ›iei noastre  merge  ÅŸi respectă regulile nivelului de mai jos, deci este o realizare corectă care rezolvă ceva bine definit Chiar dacă un È™urubel e È™ubred È™i o poartă logică explodează, astfel de detalii nu sunt interesante. Ansamblul tot  a realizat ce ne-am propus în mod abstract. È™i e o realizare  la fel de admirabilă.

Informatica e un joc abstract fără limite în care putem construi orice ne ţine.
Există întradevăr  limite (spre exemplu, flux maxim în O(n) probabil chiar nu e posibil).
Aceste limite mă pasionează la vârsta asta, pentru că sunt cât de mult ne putem apropia  de a identifica o lege a naturii demonstrabilă matematic . ÃŽn fond, dacă chiar nu există algoritm de flux maxim liniar, asta nu e ceva stip**at în definiÈ›ia limbajului C sau în modul în care ne-am decis noi să construim calculatoare. E un fapt fundamental despre biÅ£i, informaÅ£ie, ÅŸi cum se poate raÅ£iona cu informaÅ£ia asta în mod algoritmi- - aÈ™ zice chiar o lege a naturii, care e demonstrabilă formal matematic fiindcă toată construcÈ›ia noÈ›iunii de algoritm în informatică e una pur intelectuală bazată pe 4 porÅ£i logice.
 

2. Un alt motiv pentru care aÅŸ fi un antreprenor catastrofal dar am ajuns la olimpiada de info e că sunt un tip antisocial care vrea să fe lăsat să încerce È™i să facă chestii singur. Deasta n-am ajuns la mate, care mi s-a părut fie prea strictcă fie prea socială. O demonstraÈ›ie nu are valoare pe hârtie. Pot să mă gândesc mult la fiecare pas È™i să mă asigur cât de cât că e corectă, să încerc să o  simplific să evit calculele, etc. Dar valoarea demonstraÈ›iei este una socială: o explic cuiva care e interesat de problemă ÅŸi nu găsise o demonstraÅ£ie, încerc să conving că ceva e adevărat. pentru a-l lămuri È™i convinge. O demonstraÈ›ie  e o formă de comunicare O demonstaÅ£ie care stă pe foaie nu are niciun sens. Ca atare, matematică nu poÅ£ii face de capul tău ( sau e prea nasol).
La informatică, un algoritm scris în C are un sens ÅŸi o semnificaÅ£ie. Calculatorul e dispus la orice oră să-mi urmărească algoritmul È™i să-mi spună ce afiÈ™ează  Procesul de codare e foarte interactiv È™i , cu buguri, teste, nervi, reveniri, etc. Nu are aspectul one-way de "mă gândesc È™i apoi scriu o demonstraÈ›ie pe foaie".

[1. Care-i problema cu hashingul?]

Mişto problema! Soluţia  nu e deloc evidentă şi eu nu mai auzisem de problemă, dar până la urmă e foarte simplă (un hashtable ca să trasăm o muchie între valori x şi x+/-1, urmat de componente conexe).

M-a rugat Cosmin să-mi dau cu părerea dacă există soluţie în timp liniar fără hashing. Probabil că nu, fiindcă fără hashing nu știm să facem în O(n) nici element distinctness (ai n întregi; se repetă vreunul?). De fapt asta e problemă majoră în teorie.

Dar hai să profit de ocazie să discut un pic filosofic.

1. Care-i problema cu hashingul?
E un algoritm simplu care chiar merge bine. La companiile mari ale momentului, ai de lucrat cu date foarte mari și aproape că nu există cod fără hashing la problemele din industrie. Deci mi se pare aproape obligatoriu să fie întrebări de hashing la interviu.

Ca să ilustrez cu o poveste Am fost la bere cu niște ingineri de la Google NY și după 3-4 beri s-au apucat să mă întrebe de puzzles cu hashing, zicând că ei vor să facă toate întrebările de interviuri despre hashing, fiindcă citez "e singura chestie de la algoritmi fundamentali care chiar e esențială".

Eu la AT&T n-am păreri așa drastice, fiindcă sunt în research și nu intervievez ingineri Dar la ce lucrez zilele ăştea chiar e hashing, şi e esenţial în practică

Teoria și cât de rapid merg algoritmii
Eu în liceu eram foarte confuz la capitolul "cât de mari sunt întregii", în ce complexitate merge radix sort, etc. Mi-aș fi dorit o explicaţie pe îndelete, și o să încerc acuma să dau o astfel de explicaţie, fiindcă văd că sunt oameni cu întrebări similare în comentarii.

În particular vreau să explic de ce radix sort nu e O(n) şi calcularea unui hash chiar e O(1), nu timp proporţional cu numărul de biţi.

Despre teorie: Dacă nu se pogoară Duhul Sfânt să ne dea o teorie aprobată de sus, teoria o definim noi matematic după cum ni se scoală, și n-are valoare decât în măsura în care scoate rezultate utile despre realitate. Matematic să poate defini orice, inclusiv o teorie fizică fără gravitație, doar că n-o să prezică chestiile care le vedem în experimente (ignorăm pe moment experimente despre cum acţionează gravitația pe Coyote și Roadrunner).

De la teoria algoritmilor vrem să aflăm care algoritmi sunt mai rapizi când îi codăm în C, și aproximativ cam cât de rapid e un algoritm relativ la un altul. Ca să obținem o astfel de teorie, trebe să admitem următorul fapt. Codul ăsta:

Cod:

int add(int a, int b)
{
    return(a+b);
}

... rulează mult mai repede decât să facem adunarea bit cu bit cu un for de la 1 la 32. Nu e greu să definești o teorie simplă care înglobează această proprietate:

Teoria spune că ai date de intrare pe un anume tip int, care nu știi fix câți biți are. Mărimea e o variabilă, nu o constantă, și nu se poate ignora în running time; notaţia încetăţenită pt nr. de biţi per int este "w" (vine de la machine Word). Teoria spune că operațiile din limbaj pe astfel de ints rulează în O(1), nu în O(w).

Mie personal mi se pare o presupunere rezonabilă. Limbajul C e foarte popular când ne doare de eficiență și orice proiectant de procesoare îl ia în seamă. Deci probabil orice procesor comercial are instrucțiuni care fac acele operațiile fundamentale din C, gen adunare, xor, etc. Deci o teorie care măsoară numărul de operații în C aproape măsoară numărul de cicluri de procesor, care e o măsură corectă pt timpul de rulare. Empiric se constată că modul ăsta de a defini complexitatea are corelații utile cu timpul de rulare măsurat pe multe calculatoare reale, cel puțin dacă nu iei complexitatea prea în serios (dacă îmbunătățeși un algoritm de la 7n operații la 5n operații, nu-mi e clar că ai îmbunătățit timpul de rulare;fix de-asta teoreticienii sunt mai mândrii când obțin îmbunătățiri asimptotice, nu doar de constantă).

În acest model, să calculezi un hash e O(1) pt hash functions simple (vezi universal hashing pe  wikipedia). Cel mai simplu universal hashing face doar o îmulţire cu o constantă (un număr mare pe int care e musai să fie impar) urmat un shift. Ceva în genul:

Cod:

#define BITS_PER_HASH 14

int a;
void init_hash(void)
{
   srand(time(NULL));
   a = rand()*2 +1;
}

int hash(int x)
{
  return(((unsigned)a*x) >> (32-BITS_PER_HASH));
}

În această teorie, hash tables sunt algoritmi randomizaţi, iar running time chiar e O(1) pe operaţie (operaţie = insert /delete/lookup); bineînțeles, e vorba de expected running time, fiindcă nu e algoritm deterministic. Sunt multe hash tables și hash functions, care în combinații diverse obţin caracteristici variabile. Spre exemplu, unele combinații au varianță mică în timpul de rulare, etc.

Acuma, care e complexitatea la radix sort? Dacă nu putem ignora w, o să depindă de w. În practică w=32,  dar ce contează? În practică totul e o constantă,  inclusiv n (să zicem un milion), luăm acele constante, le  băgăm în formula de running time, și estimăm cam cât de bine merge algoritmul. Radix sort depinde de cât spațiu ai pt algoritm, fiindcă faci un tabel cu spațiul ăla și indexezi în el ca să distribui valorile. Să notăm spațiul cu S (dacă faci byte cu byte, S=256). Atunci folosești radix S,iar timpul total o să fie fix O(n w/lgS).  Acest timp nu e O(n) decât dacă ai spaţiu de counting sort, în care caz problema devine trivială (nu-ţi trebe nici hashing, faci un vector mare). Dar cât e S? Cât e disponibil în implementarea ta; în realitate S e un #define în cod. Fără presupuneri suplimentare, în teorie putem spune sigur că S>= n, fiindcă spaţiu O(n) e optim (trebe măcar să stocăm inputul). Folosind acest raţionament, timpul de rulare la radix sort e maxim O(nw/lg n), care nu e liniar deloc.

Normal că radix sort rămâne cel mai rapid algoritm de sortare în practică şi e mult mai bun ca quicksort, heapsort şi alţi algoritmi. Dar algoritmii ăştia chiar rulează în nlgn operații, şi dacă băgăm în formule valorile reale de n, w şi S, devine clar că radix sort va merge mai bine. Nu apare nicio surpriză aici; radix sort merge în ceva timp mai mare ca O(n) și mai mic ca O(nlg n), care depinde de w (un parametru necunoscut când ne gândim teoretic).

Totuşi, radix sort nu merge în O(n). Aici teoria chiar ne spune ceva interesant. Anume, ne spune că dacă ai de ales între radix sort şi hashing (care dă O(n) curat), ar trebui să alegi hashing. N-am avut timp să codez dar cred că e corect ce spune teoria aici şi la problema asta hashing chiar merge mai repede (cel puțin dacă implementezi bine). Legat de implementare, e clar că hashing e un pic mai neevident de codat și optimizat; la capitolul implementare e clar care soluție câștigă, și teoria algoritmică nu are nimic de spus despre asta.

Pe toate 5

Să știi că 3-ul din lista ta nu prea seamănă cu cea de la IOI, deși pare. Multă lume a luat-o în direcții foarte greșite la IOI.

În perioada 2-9 iulie va avea loc în Bistriţa a 19a ediţie a Balcaniadei de Informatică. Pentru a asigura un standard cât mai înalt al problemelor de concurs, vă solicităm ajutorul în compunerea problemelor.

PROPUNERI DE PROBLEME:
Vă rugăm să trimiteÅ£i orice propuneri de probleme la adresa de email [email protected] (Mihai PătraÅŸcu).

Problemele trebuie să fie de natură algoritmică, potrivite unui concurs gen BOI. Problemele vor fi evaluate de către Comisia BOI2011 pentru Selecţia Problemelor, care va decide problemele folosite în competiţie.

Autorii problemelor selecţionate pentru BOI vor fi invitaţi să facă parte din Comisia Ştiinţifică a BOI 2011. Ca parte din această comisie, autorii vor fi invitaţi să participe direct la organizarea BOI, prin prezenţa fizică la Bistriţa în timpul concursului (dar prezenţa la Bistriţa nu este obligatorie). Dacă autorul problemei acceptă invitaţia de a se prezenta la Bistriţa în perioada olimpiadei, toate cheltuielile vor fi acoperite din fondurile de organizare.

PROPUNERI PROBLEME:

Vom accepta propuneri de probleme până la data de 1 iunie 2011. Pe măsură ce mulţimea de probleme se conturează mai puternic, scad şansele ca o problemă să fie selectată, aşa că recomandăm autorilor de probleme să trimită propunerile cât mai devreme pentru şanse maxime de a fi selectate.

Vă rugăm să folosiţi fişiere text pentru descrierea problemelor şi a soluţiilor. Dacă propunerea dumneavostră necesită mai multe fişiere, vă rugăm să trimiteţi o arhivă în format tgz sau zip.

Pentru o evaluare cât mai obiectivă, Comisia de Selecţie nu va cunoaşte autorii problemelor în timpul evaluării. Ca autor, vă rugăm să nu vă identificaţi în enunţul problemei sau în textul soluţiei.

Urmând exemplul IOI, BOI 2011 va folosi o interfaţă de apeluri de funcţii între codul concurentului şi modulul de evaluare. Ca atare, problemele
propuse pot folosi limite de timp mai mici. Dispar de asemenea multe inconveniente legate de citirea ÅŸi scrierea fiÅŸierelor mari.

VÄ‚ DORIM MULTÄ‚ INSPIRAÅ¢IE ÅžI
VÄ‚ MULÅ¢UMIM ANTICIPAT PENTRU PROBLEMELE PROPUSE!

Comisia de Selecţie a Problemelor, BOI 2011:
Adrian Airinei
Doru Popescu Anastasiu
Marius Andrei
Mugurel Andreica
Filip Buruiană
Paul-Dan Băltescu
Cosmin Gheorghe
Andrei Grigorean
Dana Lica
Cosmin NegruÅŸeri
Andrei Pârvu
Mihai Pătraşcu (șef comisie)
Andrei Puni
Mircea Păşoi
Alexandru Sălcianu
Radu Ștefan
Bogdan Tătăroiu

Chestiile legate de confidenţialitate şi paranoia sunt foarte puternice în cultura corporatistă din state. Trebe să arăţi aşa ceva ca să arăţi că eşti firmă serioasă

Vroiam să menţionez un concurs interesant online despe baze de date, care pare la nivel de studenţi: http://db.csail.mit.edu/sigmod11contest/

Nu am nicio legătură cu concursul şi n-am interacţionat niciodată cu vreunul similar. Ei au definit o problemă legată de baze de date, şi vor un algoritm şi implementare cât mai bune. Sunt convins că între membrii infoarena s-ar putea găsi lejer câştigători.

Motivul principal pt care vreau să anunţ concursul e că e asociat cu SIGMOD, care e o conferinţă de databases cu renume puternic --- unii colegi chiar o consideră cea mai tare din parcare. (Aviz oamenilor pasionaţi de baze de date care caută chestii de adăugat pe CV-uri... În special relevant dacă vreţi phd-uri sau joburi prin state.)

De asemenea, mai e o chestie neobişnuită, anume că cineva chiar specifică o problemă clară în domeniul de DB. Vreau să adaug o poveste de când lucram la research lab la o companie care chiar vinde baze de date pe bani grei (se cheamă cu 3 litere şi sună ca "hai, biem o bere?"). Ideea era că aveam un client cumulţi bani care nu ştiam cine este şi ce puneîn baza de date (secrete comerciale la nivel de vicepresidentss, că doar suntem firme serioase cplm). Doar că nu prea le mergea lor bine db-ul, şi ca să-l îmbunătăţim, ne-au trimis un sample măreţ de 7 queries care mergeau prea lent (cu toate câmpurile denumite "a,b,c" şi penurie de detalii despre datele în care se caută ceva). Evident că a mers genial proiectul :p

Prin contrast, dacă cineva simte un imbold să rezolve o problemă de DB în viaţă, concursul ăsta bine specificat de la SIGMOD pare o mană cerească Mai că-mi vine să mă apuc şi eu, dar e greu cu codingul la o vârstă.

Vreau să anunţ call for problems de la IOI 2011 Tailanda: http://www.ioi2011.or.th/call_for_tasks (Recunosc că anunţul e oarecum din interes personal, fiind membru în ISC.)

Pe scurt, ne trimiteţi probleme mişto şi vă dăm excursie gratis şi mişto în Tailanda. Eu personal am trimis probleme şi la IOI'09 şi IOI'10 şi mi s-a părut foarte mişto experinţa de propunător (n-ai mare brânză de muncă, dar simţi că ai făcut ceva mişto pt olimpiadă şi poţi să vezi ce se întâmplă în interiorul IOI).

Informal:
* nu prea e nevoie de probleme supergrele. Lumea de pe comitete e în general hardcore, şi dacă vrem chestii naşpa de buşeală găsim şi noi. E nevoie de probleme deştepte, care să le povestească lumea acasă şi să zică "uite, a fost drăguţă asta"
* cel mai greu e de găsit probleme drăguţe şi inteligente cam la nivel de argint, deci dacă vreţi să maximizaţi şansele ca problema să fie folosită, încercaţi s-o faceţi la nivelul ăsta
* deadlineul e 20 februarie. Evident ne pasă mai mult să avem probleme mişto decât de deadline, dar n-ar fi o idee foarte proastă să vă ţineţi de deadline cât de cât.
* având membru român în ISC, o să fie mai uşor cu bârfa, şi o să aflaţi mai multe detalii ca de obicei (ce părere a avut comisia despre problemă, pe bune; care sunt şansele reale să fie folosită etc)
* BOI'11 o să fie în România, aşa cănu trimiteţi chiar cele mai mişto probleme la IOI. O să fie call for problems şi oricine (minus concurenţii) poate fi în comisie dacă vă interesează. Excursie gratis în Bistriţa poate nu sună chiar la fel de interesant, dar gândiţi-vă la gloria patriei!

Evident anunţul nu se aplică concurenţilor. Mai bine luaţi medalii decât să propuneţi probleme

Uite clasamentul pe țări, adunând punctajele concurenților. Nu știu unde să inserez Canada, fiindcă au avut 8 oameni și nu scrie pe site care sunt Canada 1 sau 2.

România e pe 17 (Canada e sigur în fața Ro, deși nu știu unde).

2821 United States of America
2781 China
2726 Russia
2694 Japan
2683 Poland
2654 Czech Republic
2644 Thailand
2638 Bulgaria
2611 Taiwan
2595 Croatia
2555 Belarus
2548 Iran
2525 Korea
2501 Germany
2498 Singapore
2489 Romania
2475 Latvia
2458 India
2435 Hungary
2427 Turkey
2421 Italy
2402 Slovakia
2384 Indonesia
2362 Lithuania
2361 Brazil
2321 Hong Kong
2289 South Africa
2288 Serbia
2252 Israel
2251 Ukraine
2230 Sweden
2221 Netherlands
2204 Argentina
2199 Egypt
2175 Australia
2165 France
2152 Georgia
2108 Finland
2104 Kazakhstan
2090 New Zealand
1964 Spain
1908 Slovenia
1874 Austria
1872 Macedonia
1870 United Kingdom
1868 Mexico
1863 Bosnia and Herzegovina
1853 Switzerland
1775 Denmark
1738 Armenia
1723 Portugal
1634 Greece
1623 Colombia
1572 Syria
1526 Belgium
1487 Moldova
1470 Estonia
1376 Macao
1215 Luxembourg
1197 Mongolia
1095 Azerbaijan
829 Cuba
694 Turkmenistan
636 Trinidad and Tobago
627 Venezuela
532 United Arab Emirates
499 Cyprus
466 Madagascar
450 Albania
446 Ghana
396 Bangladesh
388 Ireland
386 Tajikistan
386 Sri Lanka
301 Saudi Arabia
300 Libya
168 Nigeria
158 Kuwait

O abordare generală pentru a sorta fără spaţiu suplimentar se găseşte la: http://people.csail.mit.edu/mip/papers/radix/arxiv.pdf

Vezi paginile 2-5 (sunt vreo 3 algoritmi separaţi).

Până la urmă nu e aşa greu, dar nici nu e complet trivial. Ideea e că poţi să economiseşti Θ(n lg n) biţi de spaţiu dacă ai n numere sortate. Spaţiu ăsta e aproape suficient ca să stochezi o permutare, care e fix tot ce-ţi trebuie.

Chiar am implementat algoritmul cam într-o oră (cu ceva concentrare . Dar nu e algoritm de concurs.

Revin cu câteva clarificări... Asta cu cât contează diploma la interviu mi se pare bias statistic. Dacă cineva te-a chemat fizic la interviu, ai trecut de stadiul unde contează diploma. În schimb nu te cheamă nimeni să-ţi zică "Vezi tu, pari cam la fel de bun cu ăla de la Stanford, dar noi avem mai multă încredere în ăla totuşi... Mersi c-ai venit pe la noi ca să-ţi explicăm asta." Încă un bias statistic: locurile unde aplici. Dacă ai făcut Master la MIT ştii (de la prieteni, din anunţuri, de la adviser) de un anumit set de locuri. Dacă ai terminat Poli, ştii de un alt set. Aproape sigur, lista de la Poli nu cuprinde locuri care nu angajează decât oameni cu master sau phd la universităţi top 10. Deci nu e ca şi cum o să simţi vreodată că diploma contează

Dar dacă tot am zis asta, să adaug că în universitățile de top din US sunt oameni de toate calibrele. Imaginați-vă ce înseamnă să fii Admissions Officer la MIT. Primești aplicații de la primii 2-3 oameni din toate liceele din State (mult mai mulți decât poți accepta). Pe care îi iei? Toți au recomandări de la directorul liceului unde scrie că sunt un pic mai deștepți ca Einstein (nu de alta, dar liceele sunt în competiție, și pun un panou mare la intrare cu placement: în ultimii 10 ani, am băgat 3 elevi la Harvard, 2 la MIT...). Spre exemplu, anul trecut zicea MIT că 42% din cei admiși au fost primii la ei în liceu. În condițiile ăștea, vă dați seama că procesul de admitere e foarte aleator.

Legat de timpul liber, în State e foarte puţin în undergrad (lucrezi pe rupte în timpul anului, iar vara te duci să te relaxezi la vreun internship). Dar în PhD mi s-a părut mult mai mult ca în Europa. În Europa PhDs chiar au un regim semiformal: studenţii au zile de "vacanţă", şi îşi ascultă adviserul, care e un fel de şef. În State, scopul unui prof este să "producă" phd students care vor fi angajaţi în locuri supertari. Ori chestia asta nu se poate obţine decât dacă încurajezi studenţii tăi să fie cât mai independenţi. În timpul doctoratului avem un cerc mare de prieteni cu care colindam pe unde vroiam și când vroiam. Într-un an am reușit să fiu "noresident for tax purposes" la Massachusetts, care înseamnă că am stat fizic în stat mai puțin de 180 zile/an

În fine, legat de ce zice Vivi cu prietenii de facultate. Eu n-am stat decât 1 an în România la facultate, dar mi s-a părut mult mai antisocial. Lumea nu prea venea la curs, mulți erau angajați sau la 2 facultăți -- pe scurt, nici nu prea știam cu cine sunt coleg. (Tu stăteai în cămin, unde probabil întâlneai lumea mai direct.) În State, undergrazii chiar sunt destul de sociali, în timpul ăla liber cât există. Gândește-te că nu poți să mergi la un bar să bei (majoritatea au sub 21), deci te întâlnești tot căminul în barul improvizat de la etajul 2

1) În străinătate există universități de toate rangurile și trebuie să conștientizați că există diferențe enorme între ele. Personal cred că Poli este mai bună decât cam orice universitate din U.S. din afara top 20-30. Asta nu arată neapărat cât de bună e Poli, ci cât de mare este gapul între universitățile de top și restul.

2) Având în vedere punctul 1, nu cred că merită să pleci în străinătate decât într-un loc de top. Dacă te gâdești pragmatic la viitor, cred că se menține recomandarea -- când vei vrea să te angajezi după ce ai terminat Poli, ți se va acorda prezumpția de inteligență (poate e cel mai bun din România, dar a stat la el în țară din diverse motive...). Dar dacă ai terminat universitatea X de pe locul 100 ești etichetat ca mediocru din start.

3) Pt angajare, e necesar să fii bun, dar nu e neapărat suficient. Chiar credeți că se poate compara părerea pe care și-o dezvoltă 2-3 oameni după câteva ore de interviu, cu informația pe care anagajatorul o poate obține din foaia matricolă care reflectă 4 ani la MIT? Normal că oricine va avea încredere mai multă în tipul care a terminat bine la MIT, și îi va da jobul mai de sus, oricât de genial ai părea tu la interviu.

4) Presupun că nu s-a schimbat prea mult situația în România de când am fost eu în liceu, deci probabil elevii încă termină liceul frustrați pe viață și antrenați într-o cultură mult prea comercială. Așa că e normal dacă la acest moment nu îți dorești decât să devii un simplu programator, cât mai repede. Dar peste 10 ani, când o să ai și mașină și apartament și bani să te plimbi pe unde vrei, ce-o să mai vrei? Recomand să nu vă faceți prea multe planuri bazate pe prezumpția că nu veți dori niciodată o carieră interesantă. Dacă tot porniți dintr-o postură de lideri (ca olimpici, sunteți mult deasupra studenților medii de la informatică), e bine să v-o păstrați. O să vă bucurați mult de poziția asta mai târziu.

5) Despre poveștile cu nivelul scăzut la facultățile din străinătate... Realitatea este că dacă te bate dumnezeu și iei Fizică I la MIT, o să vezi cum le ia o oră să definească arctangenta. Dar asta nu spune nimic despre nivelul facultății -- în loc de cursul ăla poți să iei și cursuri de doctorat care prezintă descoperiri din ultimul an. Motivul principal pt a merge la MIT e nivelul celor mai buni 10%, nu nivelul celor mai slabi 10%.

6) E normal să vă întrebați "ce naiba pot să învețe ăia la facultățile de top?" Probabil că dacă nu treci printr-o astfel de facultate, nu vei înţelege niciodată ce puteai obţine. Ce înveţi din facultățile de top nu e pur și simplu mai multă materie -- cursurile ălea sunt și pe net, deci le poți învăța și stând acasă. Partea importantă e antrenamentul pe care ţi-l faci stând acolo în fiecare zi, motivaţia pe care o capeţi când eşti aproape de alţi oameni super-inteligenţi, şi alte chestii d-ăştea.

Dacă vrei să înveţi materie, MIT e ultimul loc din lume unde să mergi. La cursul de baze de date, în prima oră proful a zis ceva de genul "Multe baze de date comerciale folosesc un limbaj numit SQL. Găsiţi şi voi ceva documentaţie de pe net şi învăţaţi-l pt data viitoare." E la fel la toate cursurile: se studiază principii, nu detalii. Când se duce lumea la job, probabil nici nu ştie să programeze într-un limbaj comercial*, dar nu asta contează -- ştiu să înveţe repede. (*Nu e glumă; până acum vreo 2 ani programarea se preda într-o variantă de LISP.)

Va fi intr-adevar in amfiteatrul de la etajul 2, ora 6pm.

Vineri 4 iulie, la 2pm, continuam seria de intalniri de cercetare cu episodul 3. Topicul probabil "Hash Tables".

Sala este aceeasi (etajul 2, Universitate).

S-a creat un grup de discutii cu oamenii interesati de astfel de lucruri din Bucuresti. Daca sunteti interesati, ar fi bine sa va abonati (numele grupului e CS Bucharest <[email protected]>; sau puteti sa-mi trimiteti mie un email <[email protected]>, si o sa-l trimit si eu mai departe la cineva care stie cum se adauga lumea pe grup ). In curand, probabil ca anunturile si discutiile vor fi exclusiv pe grupul asta, si nu o sa mai bagam spam pe infroarena

Mi s-a spus ca ultimul meu mesaj a fost un pic amenintator, asa ca incerc sa explic mai bine aici. Intalnirile astea de cercetare nu presupun un background, si sunt deschise oricui. De fapt, un scop important este ca participantii sa afle chestii de background interesante, sa incerce sa se gandeaca singuri la probleme, si sa vada daca le place sau nu. Aproape niciun participant nu are cunostiinte peste ce stie un participant bun la olimpiada (dar va capata).

Ce am spus data trecuta e ca intalnirile astea sunt inutile ca pregatire pt olimpiada, fie ea IOI sau ACM. Asta era un sfat ca sa nu va pierdeti timpul, nu fiindca vrem sa va speriem sau sa ne dam smecheri.

Problemele discutate sunt o continuare naturala (si interesanta, speram) a algoritmilor de la olimpiada, dar sunt la un alt nivel. Discutam de algoritmi randomizati, discutam de algoritmi prea avansati pentru a fi implementati in cateva ore (si uneori de algoritmi atat de avansati ca sunt pur teoretici ), discutam mult de analiza (cat de bun e algoritmul de fapt?). Daca veniti, trebuie sa aveti un interes (sau un potential interes) in algoritmi ca un scop in sine, ca "o problema fundamentala a omenirii" . Daca veniti doar cu intrebarea "cum imi foloseste asta la concurs?" o sa plecati dezamagiti.

Asta e tot ce vroiam sa scriu data trecuta, sper ca acuma e mai clar.

[miercuri, 11 iunie, 3:30pm]

Salutari pentru toata lumea!

Florin Manea si cu mine ne gandeam de ceva vreme sa facem niste intalniri pentru lumea interesata sa lucreze la probleme de cercetare (algoritmi si domenii adiacente). Inca nu stim exact cum ar putea merge si cata lume e interesata, dar decat sa ne lungim la discutii filosofice, ne-am zis sa facem o intalnire pilot maine:

Cand: miercuri, 11 iunie, 3:30pm.
Unde: Facultatea de Matematica, Sala 204.

Intalnirea e pentru oamenii care au intentia, sau cred ca ar putea avea intentia, sa se gandeasca la probleme de cercetare. Vom vedea exact cum pot functia intalnirile, dar ideea este sa discutam despre probleme la care se lucreaza in prezent (inclusiv prezentarea unor rezultate recente), si evident sa incercam sa scoatem algoritmi mai buni

Fiindca nu vrem sa va pierdeti timpul, ar trebui sa va avertizam clar ca asta nu e pregatire de olimpiada. Subiectele discutate sunt prea "grele" pentru a fi implementate in 2 ore la un concurs. Am vrea sa rezervam intalnirile pentru oamenii care vor sa se gandeasca la probleme mult mai grele decat cele de la concursuri. (Genul de probleme la care te gandesti 2 luni, si la care s-au mai gandit si multi altii luni sau ani de zile.)


Daca sunteti interesati de astfel de intalniri dar nu puteti veni maine, dati-mi un email la [email protected]. Am vrea sa stim cam cata lume e interesata, si nu vrem sa va pierdem la numaratoare

-mip

Un prieten de la MIT a creat urmatoarea problema. Mi-a zis sa-i fac publicitate, cu mesajul "sa vedem cat de tari sunt romanii tai"   Asta ar trebui sa fie motivant

http://www.spoj.pl/problems/SEGMENTS/

Ah, heavy hitters   Chiar la ce lucram azi in drum spre facultate.

Problema e intr-adevar importanta pt baze de date de toate felurile (din cate aud si google). Uite cam ce se poate face:

1. Usor de demonstrat, si complet deterministic [ca la elementul majoritar]: Daca cauti elemente cu densitate mai mare de 1/k, poti sa faci un pass prin date, cu memorie O(k), si la sfarsit sa obtii o lista cu O(k) elemente candidate. Stii ca toate elem de densitate > 1/k apar intre candidati, dar candidatii pot sa aiba si valori mai mici.

2. evident daca faci inca un pass poti sa verifici marimea fiecarui candidat si sa pastrezi chiar heavy hitters reali.

3. Mai interesant (si mai greu), problema se poate si daca ai un stream de date cu +1 si -1 amestecate (adica ai m operatii, fiecare incrementeaza sau decrementeaza countul de la un element, si apoi vrei sa afli elementele de count mai mare de m/k). Iti trebe spatiu O(k lg m), si randomizare. Vezi http://stellar.mit.edu/S/course/6/fa07/6.895/courseMaterial/topics/topic1/lectureNotes/lec4/lec4.pdf

4. Si mai interesant, problema se poate face in diverse norme L_p, care sunt superutile la estmat k-th frequency moments. Frequency moment inseamna (aproximativ) ca ai un stream de additions si deletions la mai multe tabele intr-o baza de date, si vrei sa estimezi marimea joinului intre k dintre ele. Surprinzator chiar poti face asta tinand minte putine informatii (spre exemplu radical din m, pt k=3)...

5. Daca stie cineva sa faca heavy hitters in L_2^2(L_1) [negative type metrics over L1]  sa-mi zica si mie    Problema asta e utila la calculat edit distance cu comunicare putina (avem doua copii putin modificate de la un fisier, pe doua calculatoare in retea, si vrem sa facem sincronizare care sa ne coste in functie de cat de diferite sunt fisierele -- nu vrei sa tranferi tot fisierul de fiecare data).

-mip

Misto carte, Cata! Alaturi de aia a lui Mitrana, au fost cele mai importante pt mine.

Si lista a fost misto o perioada, pana in ultimul an cand singurele mesaje erau injuraturi intre mine si Cristi F... Ah, vremurile bune Tin minte mesajul cand imi sugera sa ma urc pe o cladira inalta de la MIT, si m-am abtinut cu greu sa nu-i zic ceva de mama, in principal fiindca coincidea cu mama lui Cata.

Salutare oameni buni!

Dupa discutii cu unii dintre voi si observarea atenta a universului, reiese clar ca trebuie facut mai mult lobby pt concursurile de informatica. Notiunea de IOI etc trebuie popularizata pt publicul larg, pt angajatori si pt profesorii (in special cei in comitele de admisii la programe de masterat, doctorat etc).

E ceva ce trebui facut cu consecventa, timp indelungat, dar uite cateva chestii care se pot face mai repede si pot ajuta. Sper ca unii dintre voi sa se poate implica.

* exista pagina pe ro.wikipedia cu IOI si olimpicii de acolo (http://ro.wikipedia.org/wiki/Olimpiada_Interna%C5%A3ional%C4%83_de_Informatic%C4%83). Trebuie facuta pagina pt BOI, CEOI si concursurile ACM, cu olimpicii romani. De asemenea, nu ar strica o pagina explicativa pt ONI, desi acolo nu se poate pune o lista cu premiantii, evident...

* ar trebui facuta o pagina pt BOI la en.wikipedia (momentan exista doar la Baltic Olympiad: http://en.wikipedia.org/wiki/BOI)

* uitati-va la pagina asta: http://infoarena.ro/olimpici/. E o tentativa de a strange informatii despre ce s-a intamplat cu olimpicii de la IOI. Din pacate nu stim datele la toata lumea... Cine stie e rugat sa completeze.

S-ar putea extinde pagina si cu medaliatii la alte concursuri, dar (1) nu am datelele, fiindca pe ro.wikipedia nu exista decat IOI;  (2) cred ca e esential ca intai sa completam pagina asta ca o statistica, care apoi pot sa o trimit la profi etc.

Sper ca unii dintre voi sa poata ajuta... Numai bine si ne mai auzim.
-mip