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

Nový úkol: hash_experiment

• Deadline 3 týdny
• Vzhledem k tomu, že se na přednášce neprobrala většina věcí k úkolu, tak jsme ho chtěli zadat další týden, ale přišli jsme na to až ve chvíli, kdy už byl na pondělní paralelce zadán...
• Pokud ty věci už neznáte nebo si nechcete sami nastudovat ze skript (což stejně doporučuju), počkejte radši až na příští týden.
• Je to hešování, tedy hodně náhody a váš seed může hodně ovlivnit výsledky. Je to tedy výrazně víc máchání rukama než obvykle. O to víc použijte a zopakujte fakta/věty z přednášky (jaké vlastnosti má daná rodina heš. fcí atp.).
• Buď se držte grafů ze zadání, nebo si nastudujte, jak se správně do grafů dává směrodatná odchylka (standard deviation). Ustálený způsob, jak odchylku zobrazovat v grafech je jako error bar. Je naprosto špatně odchylku v grafu zobrazit prostě jen vynesením hodnot odchylky spolu s naměřenými daty! Velmi zjednodušeně, odchylka průměrná vzdálenost naměřených hodnot od průměru všech naměřených hodnot. (Přesněji třeba na české wiki, anglickou wiki tady úplně nedoporučuju, jde zbytečně moc do těch teoretických detailů.) Je tedy určitým způsobem relativní vůči naměřeným hodnotám vizualizovat tyhle dvě věci dohromady, jako absolutní hodnoty, úplně nedává smysl. Můj krátký intuitivní argument je, že svým způsobem mají tyhle dvě veličiny jiné "jednotky".

Řešení matrix_experiment

Notace:

• \(\U\) : univerzum
• \(U = |\U|\)
• \(S \subset \U\) : množina, kterou hešujeme
• \(n = |S| \)
• \(\B\) : kyblíčky/políčka v hešovací tabulce
• \(m = |\B|\)
• \(h, h_1, h_2, \dots\) : všelijaké hešovací fce

• univerzální v přednášce = 1-univerzální ve skriptech
• obecná c-univerzalita se na přednášce nedefinovala, případně jen neformálně jako (c-)přibližná univerzalita
• (pozor, některá literatura 2-univerzalitou myslí 2-nezávislost, viz níže)
• k-nezávislost v přednášce = (k,1)-nezávislost ze skript
• ekvivalent skriptové k-nezávislosti je v rámci přednášky přibližná k-nezávislost, ale nedefinováno formálně
• obecná (k,c)-nezávislost ze skript je stejný případ jako výše a univerzalita

Př. 1: Univerzalita a nezávislost

1. Připomeňte si definici c-univerzality a (k,c)-nezávislosti.
2. Uvažte systém funkcí \(\mathcal{H}_1 = \{h(x) = x\}\), který obsahuje jedinou funkci \(h(x) = x\) (to jest, \(\B = \U\)). Je \(\H_1\) c-univerzální pro nějaké c? Je (k,c)-nezávislý pro nějaká k a c?
3. Dokažte, že systém \(\H_2 = \{h_a(x) = a | a\in\B\}\) všech konstantních funkcí je (1,1)-nezávislý. Též ukažte, že \(\H_2\) není (2,c)-nezávislý ani c-univerzální pro žádné c.
4. Dokažte následující:
   • \(\H\) je (k,c)-nezávislý \(\Rightarrow\) \(\H\) je (k-1,c)-nezávislý (\(k > 1\))
   • \(\H\) je (2,c)-nezávislý \(\Rightarrow\) \(\H\) je c-univerzální

Př. 2: Modulo ničí univerzalitu