Vladan Majerech - NTIN061 Algoritmy a datové struktury II

Last Modified: 22.11.2024

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

Index

odkazy, cvičení 1, cvičení 2, cvičení 3, cvičení 4, cvičení 5, cvičení 6, cvičení 7, cvičení 8

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 je do počátku cvičení příslušného dne (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 všech proběhlých cvičeních jsme prodávali datové struktury. Vždy zazněly prioritní fronty, vyhledávací stromy, a slovníky (na druém cvičení byly zmíněny Kálmanovy filtry). Vždy byly první prezentované vyhledávací stromy neprodejné, a bylo potřeba vylepšit reklamní kampaň. Vždy jsme řešili možnosti optimalizace vyhodnocování SQL dotazů.

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

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 (intelisense, na konci druhého cvičení jsme zmínili 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, tuto funkci jsem ale zatloukal. (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)$.)

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ě. Odbočili jsme 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ů. Bavili jsme se o 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.

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ů. Na prvním cvičení jsem zmínil o tom, co to je částečná a plná persistence, a zmínil využití částečné persistence v úloze lokalizace bodů v rovině.

Cvičení 3

Věnovali jsme se algoritmům pro toky v sítích, jak postupnému zvyšování toku (Ford-Fulkerson, Edmons Karp, Dinic) včetně popisu rozhraní DS (například Sleator Tarjan) pro implementaci v $O(mn\log n)$ čase, tak algoritmu začínajícího maximálním pretokem, konvertujícím jej na tok, zachovávajíc maximalitu (Goldberg Tarjan), dospěli jsme k tomu, že by se hodilo pracovat s vrcholy v nejvyšší výšce, ale nedostali jsme se k analýze této varianty. Zatím tedy máme jen složitost $O(mn^2)$.

Cvičení 4

Dokončili jsme analýzu algoritmu zachovávajícího maximalitu (rozdělení na fáze a potenciál víc klesající pro dlouhé fáze). Zmínil jsem algoritmus 3 indů (Malhotra, Pramodh, Maheshwari). Pak jsme začali řešit úlohy na toky v sítích.

Cvičení 5

Řešili jsme úlohy na toky v sítích, na prvním cvičení jsme navíc hledali maximální párování v obecném neorientovaném grafu.

Cvičení 6

Na druhém cvičení jsme hledali maximální párování v obecném neorientovaném grafu. Na obou cvičeních jsme se zabývali datovou strukturou pro efektivní implementaci Dinicova algoritmu.

Cvičení 7

Věnovali jsme se hradlovým sítím, nejprve jsme si ukázali že nejmenší univrzální obvody jsou nand a nor se dvěmi vstupy. Pak jsme se bavili o paralelní technice, kde místo sekvenšního počítání mezivýsledků počítáme funkce na základě neznámých mezivýsledků, kde skládání funkcí nevadí, že neznáme vstupní parametry. Na druhém cvičení se podařilo tuto techniku na zjišťování přijetí vstupního slova konečným automatem naznačit lépe než na cvičení prvním. Pak jsme se věnovali sčítání, a zvláště pak počítání přenosů technikou skládání funkcí. Ke konci hodiny jsme se věnovali implementaci komparátoru a na základě něho pak obvodu pro merge sort. Na obvod pro bitonické třídění nebyl čas.

Cvičení 8

Na začátku cvičení jsme rychle odbyli bitonické třídění a pak jsme se věnovali Petrově větě o postupné transformaci obecného $n-$ úhelníku pomocí uší na jeden bod. Věta slouží jako vhled do duálního světa za Fourierovou transformací, neboť aplikace každého druhu uší odpovídá vynulování jedné z duálních souřadnic. Na konci máme jedinou nenulovou souřadnici, která se celou dobu nezměnila a koresponduje těžišti $n$ úhelníka. Pak jsme se věnovali převodu násobení čísel na násobení polynomů a násobení polynomů na násobení funkčních hodnot a převod ze světa funkčních hodnot do světa polynomů. Naznačil jsem princip Cooley-Tukey algoritmu (když je počet složek mocninou dvojky), inverzní transformaci i možnosti implemantace v modulární aritmetice. Na prvním cvičení zbyl záporný čas na povídání o oplikacích FFT, na druhém cvičení jsem je naznačil před začátkem povídání o násobení.