Hubička 22. 5. 2026

Zadání:

Varianta A:

1. Popište Kruskalův algoritmus na hledání nejmenší kostry spolu s důkazem správnosti a časovou složitostí.

2. Definujte topologické uspořádání grafu a popište algoritmus na jeho sestrojení.

3. Vymyslete algoritmus, který vypíše nejdelší (o nejvíce hranách) z nejlevnější cest mezi dvěma vrcholy v neorientovaném grafu s kladnými hodnotami hran.

4. Vymyslete algoritmus, který v posloupnosti najde nejdelší souvislý úsek, ve kterém jsou všechny prvky navzájem různé.

5. Bonus: Fibonacciho soustava: Každé číslo je zapsáno jako posloupnost 0 a 1, kde číslo se rovná součtu Fibonacciho čísel odpovídajících indexům jedniček (odzadu). Zápis čísla nazveme "hezkým", pokud se v něm nikde nenachází dvě jedničky za sebou, také víme, že pro každé číslo existuje jednoznačný "hezký" zápis. Vymyslete algoritmus, který sečte dva "hezké" zápisy a vypíše "hezký" zápis jejich součtu v subkvadratickém čase.