Vladan Majerech - NTIN061 Algoritmy a datové struktury II
Last Modified: 14.10.2026
Index
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 čtvrteč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
Na nahrávce je přiměřeně rozumný zvukový záznam, a můžete poznat, že jsem něco psal na netabuli.
Prodávali jsme datové struktury. Zazněly haldy, seznamy, spojování tříd ekvivalence, vyhledávací stromy, a slovníky. Vyhledávací stromy byly neprodejné, u hald to bylo na hraně, union-find bylo potřeba vylepšit. Postupně jsme se dostali k užitečnosti vyhledávacích stromů v SQL, museli jsme přidat iterátor Next(), ukázalo se, že by se hodilo umět odhadnout počet prvků v intervalu, k čemuž by se hodil Range() odhadující/určující počet prvků s menším klíčem. Pomocí toho jsme mohli optimalizovat 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, ale případ, kdy klíči na začátku intervalu odpovídá více hodnot by si zasloužil víc pozornosti (dospecifikace Find/modifikace iterátoru).
Zmínili jsme 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 to, že v praxi je důležitý počet výpadků keší, protože načítání keše je řádově pomalejší než čtení z keše jsem upozorňoval jen při modifikaci reprezentace “spojového seznamu„ (silně to diskvalifikuje Trie (o kterém jsme nehovořili), ale i sofistikovaná řešení konfliktů při hešování).
Cvičení 2
Povídali jsme si o vyhledávání. (Hashovaná databáze výsledků řazených dle relevantnce, crowling).
Pak jsme se bavili o vyhledávání v nepředpřipraveném seně a o tom, že se nám budou v budoucnosti určitě hodit i konečné automaty, kvůli regulárním výrazům. Pak jsme se věnovali případu stejně dlouhých jehel, až jsme se konečně dostali k Aho-Corrasic algoritmu na paralelního vyhledávání množiny slov bez omezení na jejich délky.
Bavili jsme se o tom, jak reprezentovat Trie slovníkem, a nakonec jsme měli "Aho-Corrasic kompresi" konečného automatu vyhledávající danou množinu slov (konečný automat by neměl zpětné hrany, ale pro každé písmeno by měl rovnou pokračování do stavu, kam se dostaneme skákáním dokud neposouváme čtecí hlavu). Vytvořili jsme si zadání na kterém jsme si jak budování "Aho-Corrasic" automatu, tak jeho použití vyzkoušeli. Co se týče reprezentace hlášení nálezů, všimli jsme si, že nám přirozeně vznikla funkcionálně persistentní (immutable) struktura pro reprezentaci výsledků odpovídajících jednotlivým "nálezům".
Cvičení 3
Věnovali jsme se algoritmu pro toky v sítích, postupným zvyšováním toku (Ford-Fulkerson, Edmons Karp, Dinic) včetně řešení vrstevnaté sítě jak pomocí algoritmu tří indů (Malhotra, Pramodh, Maheshwari), tak pomocí DS (popisu rozhraní), na nahrávce jsou i stěžejní triky pro jednu z možných implementací (Sleator Tarjan stromy se Splay vyvažováním) pracující v $O(mn\log n)$ čase. Algoritmu začínajícího maximálním pretokem, konvertujícím jej na tok, zachovávajíc maximalitu (Goldberg Tarjan), se buceme věnovat příště.