Vladan Majerech - NTIN061 Algoritmy a datové struktury II

Last Modified: 17.9.2025

Index

odkazy , cvičení 1

Pro získání zápočtu z NTIN061 je potřeba získat (3/5 z možných bodů za domácí úkoly zadávané v průběhu semestru).

Pokud není uvedeno jinak, počet přidělených bodů rychle klesá v případě použití časově neoptimálních algoritmů. Za odevzdání po termínu je jen poloviční počet bodů. Termín bude vždy uveden, je do počátku pátečního cvičení (10:40). Na domácí úkoly letos použijeme owl. Pokud jste ode mne nedostali e-mail s linkem, tak mne kontaktujte.

Odkazy na obdobné stránky

Cvičení či materiály k nim Jana Hrice, moje loňská cvičení.

Cvičení 1

Nahrávka z cvičení je nepoužitelná. Kromě toho, že nic není vidět na tabuli, tak ani není zaznamenaný zvuk.

Na všech proběhlých cvičeních jsme prodávali datové struktury. Vždy zazněly seznamy, vyhledávací stromy, a slovníky. Výjiměčně byly vyhledávací stromy prezentované na prvním cvičení prodejné, poskytovaly jak iterátor Next(), tak Range() použitelný k odhadu velikosti počtu klíčů v určeném intervalu, což jsme mohli požít pro optimalizaci vyhodnocování SQL dotazů (vybereme vlastnost s nejmenším počtem klíčů v intervalu a pro vrácené záznamy filtrujeme dle ostatních podmínek) navíc Find() vracel prvek „nejblíž“ k hledanému klíči, takže vyhledávání intevalů fungovalo i pokud klíč nebyl v množině. Navíc jsme si poradili i s opakujícími se klíči.

Vždy jsme zmínili rozměry složitosti střední hodnota (průměrná přes pravděpodobnosti vstupu) (php attack problém), randomizovaná (průměr pro jeden vstup přes chování náhodného generátoru) a pro datové struktury i amortizovaná (umožňující spočítat celkový čas za průběh algoritmu, ač některá zavolání mohou mít výrazně větší čas než jiná).

Na prvním cvičení jsme stihli propagovat i Disjoint Find Union, Haldy i Trie. Často jsem upozorňoval na v praxi důležitý počet výpadků keší, protože načítání keše je řádově pomalejší než čtení z keše (to silně diskvalifikuje Trie, ale i sofistikovaná řešení konfliktů při hešování).

Na obou cvičeních jsme zmínili vztah Fibonacciho čísel a AVL stromů (vztah mezi hloubkou a velikostí).