Friday, December 4, 2009

Talks

Update: The 2nd talk is happening 6pm-8pm in Amfiteatrul Pompeiu (= amfiteatrul de la etajul 2).

I am giving two talks in Bucharest this coming week:
  • a more practical one at Poly on Monday (December 7) at 6pm in room EC 101 (Fac. Automatică şi Calculatoare)
  • a more theoretical one at UniBuc on Friday (December 11). Room and time to be announced here, but it will be earlier in the afternoon.
Abstracts below. Don't forget to vote on Sunday.

  1. Funcţii de hash tabulare

    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. Rezultate negative pentru structuri de date

    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.

8 comments:

Anonymous said...

Will you give the talks in Romanian?

Mihai said...

I'll try :) But there are many words I can't translate.

Anonymous said...

Perhaps you should give a talk in Romanian on your job hunt. :-)

Anonymous said...

i love you mihai, you are great.

Anonymous said...

The abstracts seem to be a word-for-word translation from English.

Anonymous said...

Looks like Mihai used IBM Model 1 for translating abstracts from English.

Adrian said...

Pui si un link la paper-uri, slide-uri pentru cele 2 prezentari? Multumesc.

Mihai said...

Prezentarea de la UniBuc e bazata pe: http://people.csail.mit.edu/mip/papers/index.html#structures

Prezentarea de la Poli e bazata pe: http://people.csail.mit.edu/mip/papers/index.html#charhash