Hubička 17. 6. 2026

Zadání:

1. Popíšte hešovanie a ako vieme riešiť kolízie prvkov. Popíšte časovú zložitosť operácii Find() a Insert(). [10]

2. Definujte (2,4) strom a dokážte logaritmickú hlbku. [5]

3. V bludisku sú 2 roboty, ktorým vieme dávať inštrukcie iba naraz. Keď jeden narazí na stenu, proste stojí. Popíšte algoritmus ako oboch robotov dostať ku východu. (Alebo niečo také, proste stačilo mu že BFS, s tým že do fronty ukladáme pozície oboch robotov) [5]

4. Popíšte algoritmus na identifikáciu cyklov so záporným súčtom v orientovanom ohodnotenom grafe. [5]

5. Bonus: Orientovaný graf je polosúvislý ak medzi každými 2 vrcholmi vedie cesta aspoň jedným smerom. Popíšte efektívny algoritmus na zistenie či je graf polosúvislý.

PS: Asi najviac chill skúška na akej som bol. Pán Hubička bol celý čas milý a usmiaty. Myslel som že skúška bude viac ústna, ale bola skôr písomná. Keď ste mali niečo vypracované, len ste sa prihlásili, on prišiel za vami, prečítal si to a hneď vám navrhol známku, alebo povedal že ešte máte niečo opraviť alebo dorobiť. Odpovede nemuseli byť nejako extra podrobné, ani dôkaz nejako extra rigorózny, stačilo že máte šajnu o čo sa jedná. Čas bol prakticky neobmedzený.