In saptamana 7-11 decembrie, Mihai Patrascu va sustine 2 prezentari (sub forma de cursuri), una la Universitatea Politehnica din Bucuresti (UPB), si una la Universitatea din Bucuresti (UNIBUC). Sunteti invitati sa participati la cele 2 prezentari daca sunteti interesati de subiectele abordate, de alte subiecte conexe, sau pur si simplu pentru a-l vedea pe Mihai la treaba (care sigur va va trezi interesul pentru informatica teoretica in general, si pentru subiectele abordate in cursuri, in particular). Intrarea este libera. Titlurile si rezumatele celor 2 prezentari le gasiti mai jos. Iar in caz ca nu ati auzit de Mihai Patrascu pana acum
, aveti la sfarsitul post-ului si o (foarte) scurta biografie a sa (alternativ, puteti sa-l cautati pe Google
).
1) Talk UPB
Cand: luni, 7 decembrie 2009, ora 18:00
Unde: Facultatea de Automatica si Calculatoare, sala EC 101
Titlu: Funcţii de hash tabulare
Rezumat: Implementarea tabelelor de hash folosind căutare liniară (linear
probing) este mai eficientă decât alte implementări dacă funcţia de
hash este suficient de alteatoare. Din păcate, linear probing se
comportă foarte prost în conjuncţie cu funcţiile de hash bazate pe
înmulţire (cele mai folosite în practică), şi ca atare, acest algoritm
este deseori evitat.
Voi descrie o funcţie de hash foarte simplă, care este la fel de
rapidă ca înmulţirea pe procesoarele actuale, dar se bazează pe
indexarea în tabele precalculate. O analiză matematică ne demonstrează
că această funcţie garantează timp de rulare constant pentru tabelele
de hash.
2) Talk UNIBUC
Cand: vineri, 11 decembrie 2009, ora va fi stabilita in curand
Unde: in cadrul UNIBUC (locatia exacta va fi stabilita in curand)
Titlu: Rezultate negative pentru structuri de date
Rezumat: Cum demonstrăm că anumite rezultate algoritmice sunt imposibil de
obţinut? Spre exemplu, cum demonstrăm că nu există nicio structură de
date cu spațiu liniar care poate suporta range queries în timp
constant? În acest curs, voi descrie o demonstrație completă a acestui
rezultat, trecând prin mai mulți pași simpli, dar interesanți.
Biografie Mihai Patrascu:
Mihai Pătraşcu lucrează în prezent în departamentul de cercetare al
AT&T (în New York). Domeniul lui de cercetare este informatica
teoretică (structuri de date, algoritmi, lower bounds). În trecut, a
efectuat studiile universitare (2006) și doctorale (2008) la MIT,
urmate de un an în laboratorul IBM din San Jose, California.
Mihai a obţinut câteva premii de cercetare, cât şi mai multe medalii
la olimpiadele internaţionale de informatică (în timpul liceului).
Cu exceptia cazurilor in care se specifica altfel, continutul site-ului infoarena