Pátá série třicátého osmého ročníku KSP

Celý leták v PDF.

Komentáře k úlohám

Teoretická úloha38-5-S Hešování řetězců (Zadání) (Řešení)

Úkol 5: Izomorfismus – více dětí

Jedna z oblíbených hešovacích funkcí spočítala heš rodiče z kódů synů x1, …, xk jako:

kde h je náhodná hešovací funkce do Zp, kterou jsme dostali v zadání.

Ačkoliv by výše popsaná hešovací funkce fungovala, tak dokázat to o ní se nikomu nepovedlo. Nabízí se totiž velmi jednoduchý (avšak falešný) důkaz jak omezit pravděpodobnost kolize:

Uvažme dva vrcholy s kódy synů x1, …, xk a y1, …, yℓ:

Zafixujeme-li x1, …, xk a y1, …, yℓ-1, tak nám to dáva jednu hodnotu, do které se h(yℓ) musí strefit, aby nastala kolize. A protože je h dokonale náhodná, tak pravděpodobnost kolize je 1/p.

Nicméně tohle nefunguje. Problém je, že jednotlivé xi a yi nejsou nezávislé, a tím, že jsme zafixovali část z nich, jsme už mohli předurčit hodnotu h(yℓ). Např. když levý podstrom je třívrcholová cesta a pravý dvouvrcholová, tak při výpočtu heše levé cesty h(h(0)) jsme už použili hodnotu heše pravé h(0). Obecně se jednotlivé podstromy mohou složitě překrývat, a proto není možné v důkazu používat nezávislost.

Daniel Skýpala