Vladan Majerech - NTIN061 Algoritmy a datové struktury II

Last Modified: 17.10.2025

Valid HTML 4.01 Strict ... vlastně už jen HTML, ale jaký obrázek?

Index

odkazy , cvičení 1, cvičení 2, cvičení 3

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í).

Cvičení 2

Věnovali jsme se vyhledávání v textu. Nejprve jsme si chvíli povídali o vyhledávání na internetu, tedy jak velmi zhruba funguje příprava podkladů pro vyhledávání na internetu a jak zhruba může být dotaz vyhodnocován. Pak jsem zmínil možnost obráceného přístupu, tedy předzpracování sena, což umožňuje následné efektivní vyhledávání libovolných předem neznámých jehel (Suffix trees ... předzpracování se dá udělat v čase $O(n)$ a vyžaduje $O(n)$ prostoru (s multiplikativní konstantou řekněme 20)).

Následně jsme se věnovali vyhledávání jehly(el) v seně metodou, kdy předzpracujeme jehlu(y).

Na obou cvičeních jsem zmínil algoritmus s plovoucí hašovací funkcí (Robin Karp), který umí s velikou pravděpodobností vyloučit pozice, kde se jehla určitě nenachází, s tím, že pozici, kde se jehla nachází nikdy nevyloučí. Existuje i xorovací, shiftovací hashovací funkce, jejíž výpočet i aktualizace bude mít lepší multiplikativní konstantu než standardní modulo polynomiální funkce. (Pomocí "zobrist hashing" triku se každému písmenku přiřadí náhodné např. 128 bitové číslo, toto číslo se rotuje podle toho na které pozici se daný znak vyskytuje. Není to polynom o základu $2^k$, vyhledem k cyklickému doplnění bitů nízkých řádů a výsledný hash získáme xorem mezivýsledků. Posunutí slova se projeví rotací hashe celého slova, takže je akualizace v $O(1)$. (Pro jehly delší než počet bitů Zobrist hashingu povedu přehození písmen vzdálených tento počet ke stejnému hashi, což by neměl být případ polynomů.)

Následně jsme Knut-Moris-Prat algoritmus víceméně odbyli, víc jsem se věnovali Aho-Corrasick algoritmus, jež je jeho zobecněním a zjednodušení datové struktury pro cestu místo stromu, kde stačí pole čísel je implementační detail. Věnovali jsme se tedy Aho-Corrasic algoritmu, a předvedli jsme si jej na příkladě.

U AC algoritmu jsme se nevěnovali důkazům, toho, že postupujeme správně, nicméně jsme všechny jednotlivé kroky zdůvodnili. Implicitně jsme dokázali složitost vyhledávání i složitost vybudování fail podpůrných pointerů. Co se týče hlášení nalezených jehel, využil jsem příležitost k odbočce k funkcionálně persistentní datové struktuře srůstajících seznamů. Nezmiňoval jsem se o tom, co to je částečná a plná persistence.

Na konci hodiny jsme odbočili k datové struktuře (písmenkový strom) Trie. Řekli jsme si o možnosti reprezentace hran trie ve slovníku, ale i o tradičních metodách pole odkazů. Naznačil jsem snížování prostorové náročnosti při reprezentaci statické množiny pomocí eliminace vrcholů stupně 1 i pomocí reprezentace ofsetů do jednoho pole s překrývajícími se intervaly hodnot (s nepřekrývajícími se nenilovými odkazy), rozmysleli jsme si, jak musíme modifikovat vyhledávání, abychom se nezacyklili a lokalizovali jen slova z množiny.

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 z druhého cvičení 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ě.