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
- Loňská přednáška Martina Mareše
- Kuchařky a jiné učební texty KSP (hledání v textu, toky v sítích, geometrické algoritmy, ...)