Cvičení z Algoritmů a datových struktur II v ZS 14/15 (pátek 10:40)

Vedu cvičení k přednášce ADS II Ondřeje Čepka v pátek od 10:40 v S10. Pokud máte nějaký dotaz, pište na vesely+ads2 (zavináč) iuuk.mff.cuni.cz. (piště prosím i to +ads2, abych si mohl emaily třídit).

Zápočet je třeba dořešit do konce sprna (s tím, že nějakou dobu budu pryč a nemohu zaručit rychlé odpovědi).

Co jsme dělali

3. 10. Opakování ADS 1 formou pár vybraných úloh.
10. 10. Vyhledávání v textu: opakování algoritmů Knuth–Morris–Pratt a Aho-Corasick (hlavně konstrukce zpětné funkce, výstupní funkcí se budeme zabývat příště). Proč je naivní algoritmus pomalý, i když nic nenajde? Počet dvojic (pozice, výstkyt slova) může být pro víc jehel až kvadratický. Jak poznat, že je jeden řetězec rotací druhého?
17. 10. Vyhledávání v textu: opakování algoritmu Aho-Corasickové (tentokrát i výstupní funkce). Proč prostá reprezentace výstupní funkce může být asymptoticky větší než celý vyhledávací automat a než velikost jehel (vyhledávaných slov) a jak ji reprezentovat efektivněji. Počítání frekvencí výskytů slov v textu. Úprava vyhledávacího automatu pro velké abecedy (jako např. Unicode). Rabin-Karpův algoritmus pro jedno hledané slovo a jaká je pro něj vhodná hešovací funkce.
První série úkolů do 31.10.
24. 10. Toky v sítích: krátké opakování a příklad sítě s reálnými kapacitami, kde Ford-Fulkersonův algoritmus neskončí a hodnota toku ani nekonverguje k maximální hodnotě (pro špatnou volbu zlepšujících cest), jak přidat k tokům kapacity do vrcholů a jak hledat v grafu hranově nebo vrcholově disjunktní cesty mezi dvěma vrcholy. Hledání největšího párování v bipartitním grafu pomocí toků a aplikace na rozmístění věží na šachovnici s dírami.
31. 10. Toky v sítích: opakování Dinicova algoritmu; toky s více zdroji a více stoky, k toku f a většímu toku g existuje tok h v síti rezerv takový, že g dostaneme zlepšením f podle h; rozvoz chlebů z továren do obchodů tak, abychom splnili požadavky obchodů, a efektivnější implementace Dinicova algoritmu (ale ne asymptoticky).
7. 11. Toky v sítích: opakování Goldbergova algoritmu (metoda preflow-push) včetně implementace některých kroků a analýza O(n3) v případě, že vybíráme nejvyšší vrchol, o potenciálové metodě a amortizované složitost (příklad s přičítáním jedničky k binárnímu číslu), Goldbergův algoritmus na jednotkových sítích a různé počáteční výšky zdroje (nedoděláno).
Druhá série úkolů do 21.11.
14. 11. Dokončení toků v sítích: dva problémy na minimální řez: nejmenší vrcholové pokrytí v bipartitním grafu a realizace projektů za co největší odměnu při pořízení sdílených zdrojů za co nejnižší cenu. Diskrétní Fourierova transformace jako lineární zobrazení, její matice a převádění vektorů (nedokončeno).
21. 11. Diskrétní Fourierova transformace: dokončení převádění vektorů, poznámka o převádění bází, transformace reálného vektoru je antisymetrická (čísla na symetrických pozicích jsou komplexně sdružená) a naopak. Nakonec aplikace toho všeho: aproximace funkce na intervalu (navzorkované v n bodech) pomocí sinů a cosinů.
28. 11. Počty bodů potřebné pro operace násobení, sčítání, mocnina, dělení (jsou-li polynomy dělitelné) a odmocnina (z odmocnitelného polynomu). Rychlá Fourierova transformace rekurzivně, jako hradlová síť a nerekurzivně. Poznámka o Fourierově transformaci nad konečnými tělesy, která jde použít třeba pro násobení dlouhých čísel.
5. 12. Cvičil Martin Böhm:Hradlové sítě: logické funkce se dvěma vstupy a jejich vyjádření jen pomocí AND, OR a NOT a pak jen pomocí NANDu (negace ANDu), XOR za pomoci co nejméně NANDů, dělitelnost třemi pomocí hradlové sítě a porovnání dvou nestejných n-bitových čísel.
12. 12. Složitost: opakování tříd P a NP a polynomiálních redukcí. Příklady redukcí: vrcholové pokrytí z nezávislé množiny, převod SATu na 3-SAT (nahrazování dlouhých klauzulí kratšími) a pseudopolynomiální algoritmus na batoh (polynomiální pro vstup kódovaný v jedničkové soustavě).
19. 12. Složitost: převod tříbarevnosti grafu a nezávislé množiny na SAT a převod 3-SATu na kvadratické nerovnice.
9. 1. Aproximační algoritmy: 2-aproximační kostrový algoritmus na TSP s trojúhelníkovou nerovností, 2-aproximační algoritmus na MAX-SAT a 2-aproximační algoritmus na vrcholové pokrytí. Neexistence konstantně aproximačního algoritmu na TSP bez trojúhelníkové nerovnosti (pokud P se nerovná NP).

Zápočet

Zápočet získáte za zcela správné vyřešení alespoň jedné úlohy z každé série a za zápočtový program či esej.

Budou dvě série domácích úkolů s „měkkým termínem“ (zhruba 14 dní po zadání): pokud řešení série odevzdáte do začátku cvičení v den termínu, stačí jeden úkol z této série (pokud není ono řešení úplně špatně). Jinak je potřeba vyřešit dva úkoly ze série. Úkoly odevzdávejte nejlépe elektronicky (ve formátu PDF, ODT, ... nebo i jen jako text emailu). Obrázky jsou vítány (mohou být i naskenované/nafocené). Můžete mi odevzdávat i papíry s ručně psaným řešení, ale pište prosím čitelně. Nafocený text psaný rukou mi neposílejte.

Na úkolu je velmi důležité dobré vysvětlení (včetně časové a paměťové složitosti, pokud to dává u úkolu smysl) a zdůvodnění. To může být krátké, ale mělo by být přesné, výstižné a dávat smysl, i když čtenář řešení nezná. Přečtěte si ho po sobě. Úkolů bude letos málo, dejte si s nimi proto prosím záležet :-)

Dále je na zápočet potřeba vytvořit zápočtový program či esej. Zápočtový program spočívá v implementaci zvoleného algoritmu či datové struktury. Programovací jazyk neomezuji, ale pokud chcete použít jiný než C, C++, C#, Python, Javu a Pascal, nejprve mi napište. Algoritmus či DS by měly být implementovány v daném jazyce tak, aby snadno mohly být použitelné v jiném programu (např. přes #include v C či C++). Samozřejmostí je rozumné okomentování kódu, které by mělo obsahovat i časovou složitost jednotlivých procedur (stačí stručně). K programu navíc vytvořte 5-10 testovacích sad, které ověří správnost implementace včetně různých speciálních případů. Dodejte mi také prosím program, který spustí algoritmus na datech v zadaném souboru, abych ho mohl otestovat.

Tématem může být implementace těžšího algoritmu či DS z přednášky, případně (lépe) jejich aplikace či úprava na nějaký daný problém. K inspiraci můžete využít nápady od Martina Mareše. Kdybyste chtěli téma mimo přednášku, můžeme se na tom domluvit.

Esej spočívá v nastudování nějakého algoritmu či datové struktury nad rámec přednášky a v sepsání 2-3 stránkového textu, z něhož by mělo být jasné, jak algoritmus či DS funguje a také jak se zhruba dokazuje správnost a časová či paměťová složitost. Technické detaily důkazu nemusí být součástí textu. Na konec textu dejte reference na své zdroje (články, knihy, webové stránky apod.). Příklady témat: suffixový strom, lepší typy hald (nejlépe nějaké jiné než Fibonacciho), test rovinnosti grafu, Karger-Steinův algoritmus pro nejmenší řez, ...

Zvolené téma zápočťáku mi pošlete emailem a vyčkejte na jeho potvrzení. Termín na výběr zadání je 4.12.14. Termín na odevzdání není, ale zápočťáky odešlete prosím do konce výuky v semestru (zápočet je stejně potřeba ke zkoušce, alespoň u Čepka).

Účast na cvičení není povinná, nicméně doporučená.

Tabulka výsledků

Již není vidět.

Zdroje