Cvičení z Algoritmů a datových struktur II v ZS 14/15 (úterý 15:40)

Vedu cvičení k přednášce ADS II Ondřeje Čepka v úterý od 15:40 v S10. Pokud jste zmateni, proběhla změna cvičícího z Dušana Knopa na mě. 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

7. 10. Cvičil Dušan Knop: Vyhledávání v textu: opakování algoritmu Knuth–Morris–Pratt a trií (písmenkových stromů). 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ý. Je jeden řetězec rotací druhého? (A možná ještě něco.)
14. 10. Vyhledávání v textu: opakování algoritmu Aho-Corasick. Vyhledávací automat, který v každém stavu (vrcholu trie) má uloženu množinu všech jehel (vyhledávaných slov), která jsou suffixem tohoto stavu, může být asymptoticky větší než délka všech jehel dohromady. Jak toto opravit? Počítání frekvencí výskytů jehel a zjišťování, je-li řetězec periodický.
První série úkolů do 4.11.
21. 10. Vyhledávání v textu: Rabin-Karpův algoritmus pro jedno hledané slovo a jaká je pro něj vhodná hešovací funkce. Toky v sítích: příklad malé sítě, kde Ford-Fulkersonův algoritmus potřebuje velmi mnoho hledání zlepšujících cest, jak hledat v grafu hranově nebo vrcholově disjunktní cesty mezi dvěma vrcholy a jak přidat k tokům kapacity do vrcholů. 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.
4. 11. Cvičil Tomáš Gavenčiak: Toky v sítích: síť, kde Ford-Fulkersonův algoritmus nedoběhne, opakování Dinicova algoritmu a hledání blokujícího toku. Sítě s více zdroji a stoky, dopravní problém (rozvoz chlebů z továren do obchodů tak, abychom splnili požadavky obchodů) a problém s projekty. O důkazech pomocí potenciálové metody (přičítání jedničky k binárnímu číslu).
11. 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, 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 25.11.
18. 11. Diskrétní Fourierova transformace jako lineární zobrazení, její matice a převádění vektorů (včetně převodu kanonické báze vektorového prostoru nad komplexními čísly).
25. 11. Diskrétní Fourierova transformace reálného vektoru je antisymetrická (čísla na symetrických pozicích jsou komplexně sdružená) a naopak. Aplikace DFT: aproximace funkce na intervalu (navzorkované v n bodech) pomocí sinů a cosinů.
2. 12. 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.
9. 12. Hradlové sítě: logické funkce se dvěma (nebo i více) 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ů a dělitelnost třemi pomocí hradlové sítě.
16. 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 tříbarevnosti grafu na SAT. Pseudopolynomiální algoritmus na batoh (polynomiální pro vstup kódovaný v jedničkové soustavě).
6. 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 9.12.14 (posunul jsem termín do dalšího cvičení). 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