nechodím na prednáškyAlgoritmy a dátové štruktúry prednáška 19
Preber si túto prednášku so svojou AI
Skopíruj pripravený podklad a vlož ho do ChatGPT, Claude alebo inej AI — bude ťa učiť alebo skúšať len z tejto prednášky.
Zhrnutie prednášky
Prednáška nadväzuje na hešovanie a rieši problém, že deterministická hešovacia funkcia má vždy nejaký zlý vstup spôsobujúci lineárny najhorší prípad. Predstavuje sa technika univerzálneho hešovania založená na operácii XOR a náhodne generovanej bitovej tabuľke spolu s dôkazom, že pravdepodobnosť kolízie dvoch rôznych prvkov je najviac 1/m. Ilustruje sa to na príklade Boba a Alice, ktorí pomocou náhodne zvoleného prvočísla a modulárnej aritmetiky s vysokou pravdepodobnosťou overia zhodu dvoch obrovských súborov s minimálnou komunikáciou. Ďalej sa prednáška venuje všeobecnejšie použitiu náhody v algoritmoch: generovaniu rovnomerného výberu z viacerých možností pomocou mince, korektnému náhodnému preusporiadaniu poľa (Fisher-Yatesov algoritmus) oproti chybným naivným prístupom a náhodnému vzorkovaniu z dátového prúdu (reservoir sampling).
- Univerzálne hešovanie a operácia XOR
- Náhodná bitová tabuľka ako základ hešovacej funkcie
- Dôkaz obmedzenia pravdepodobnosti kolízie na 1/m
- Porovnávanie veľkých súborov cez náhodné prvočíslo a modulo
- Zdroje náhody v počítačoch a pseudonáhodné generátory
- Fisher-Yatesov algoritmus na náhodné preusporiadanie poľa
- Chyby naivného miešania poľa náhodnými výmenami
- Reservoir sampling - náhodný výber vzorky z dátového prúdu
Zhrnutie pripravené s pomocou AI z prepisu videa.
