Fundur með erindi

Fundurinn hefst með veitingum að hefðbundnum hætti frá kl. 16:45.

Að þeim loknum, eða klukkan 17:15, flytur Páll Melsted erindi sem hann nefnir: Slembigangur á Kúkúhakkatöflum.

Kúkúhakkatafla er gagnagrind sem geymir vörpun frá lyklum til staka. Kúkúhakkataflan notar d hakkaföll og tryggir að hvert stak er geymt í einu af þeim d hólfum sem hakkaföllin vísa á fyrir lykil þess. Kúkúhakkatöflur hafa ýmsa kosti fram yfir aðrar gagnagrindur, þá helst stuttan sóknartíma og góða minnisnýtingu. Við innsetningu lykla er vitað að trjáarleitaraðferð tekur fastan væntitíma en verstu tilfelli geta tekið margliðutíma. Allar praktískar útfærslur nota slembigang fyrir innsetningu en fram að þessu voru engin mörk þekkt á keyrslutíma þeirra. Við fjöllum um slembigang á kúkúhakkatöflum og sýnum fram á markliðulogra tímamörk fyrir vænti- og versta tilfellis tíma fyrir innsetningu staka.

Páll Melsted útskrifaðist með BS próf frá stærðfræðiskor Háskóla Íslands veturinn 2003 og stundar doktorsnám í reikniritum, fléttufræði og bestun við Carnegie Mellon University.