Cvičení 8. 12. 2021: Hešování za ideálních podmínek

Nový úkol: není

Staronový úkol: hash_experiment

Řešení cuckoo_hash

Notace:

Na cvičení budeme používat definice univerzality a nezávislosti dle skript, stejně se z nich nejspíš budete učit na zkoušku. Bohužel, v téhle oblasti je terminologie silně zmatená a neustálená.
Rozdíly terminologie mezi přednáškou a skripty:

Př. 1: Modulo ničí univerzalitu

Ukažte, že pokud máme univerzální systém hešovacích funkcí H, pak systém H, kde ke každé fci navíc přidáme modulo m, už nemusí být univerzální.
Trochu formálněji: Dokažte, že pro každé c a m>1 existuje univerzum U a systém H z U do U tak, že H je univerzální, ale H už není c-univerzální.
Hint: Můžou se hodit systémy z minulého cvika.

Př 2.: Rabin-Karp

Odbočka k textovým algoritmům.
Máme dva řetězce, dlouhé seno S a krátkou jehlu J a chceme najít v senu najít všechny výskyty jehly. Označíme si délky |S|=n a |J|=k.
Triviální algoritmus v čase O(nk) prostě zkontroluje každý podřetězec sena délky k znak po znaku, zda to není jehla. Vylepšete triviální algoritmus pomocí hešování tak, abyste dostali v průměru složitost O(n+k+kt), kde t je počet výskytů jehly v seně.
Může pomoct si vzpomenout na ADS2. Taktéž se bude hodit vzpomenout si, jak se dají efektivně hešovat řetězce, viz například skripta (pro změnu), konec sekce 6.1.