Cvičení z Algoritmů a datových struktur II v ZS 15/16 (pondělí 15:40, S7)

Vedu cvičení k přednášce ADS II Martina Mareše, které se koná v pondělí od 15:40 v S7. Pokud máte nějaký dotaz, pište na vesely (zavináč) iuuk.mff.cuni.cz, případně se zeptejte po cvičení.

Chcete-li konzultaci, ozvěte se mi emailem. Jelikož o zkouškovém nemám pevný rozvrh, napište své časové možnosti a zkusíme udělat nějaký průnik.

Zápočet je nutno dořešit do konce března.

Co jsme dělali

5. 10. Opakování ADS I (zejména trií) formou příkladů, z části zkouškových.
12. 10. Vyhledávání v textu: opakování algoritmu Knuth–Morris–Pratt (konstrukce zpětné funkce) a procvičování jeho použití:
  • Příklad, na němž je naivní algoritmus pomalý, i když nic nenajde.
  • Jak poznat, že je jeden řetězec rotací druhého?
  • Jak najít nejdelší vlastní suffix slova, který je zároveň prefixem?
  • A jak poznat, jestli je řetězec periodický?
  • Hledání jehly jako vybrané podposloupnosti v textu (bonusový příklad, zatím nedokončeno).
19. 10. Vyhledávání v textu: opakování algoritmu Aho-Corasick a procvičování jeho použití/úprav:
  • 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).
  • Počet dvojic (pozice, výskyt jehly) může být pro víc jehel až kvadratický.
  • Počítání frekvencí výskytů slov v textu.
  • Hledání jehly jako vybrané podposloupnosti v textu a počítání výskytů.
26. 10. Ještě jednou řetězce:
  • Pěstované stromy aneb trochu nečekané použití vyhledání řetězce na grafový problém.
  • Hledání nejčastějšího podřetězce délky K (řešení v průměrně lineárním čase pomocí hashování).
  • Hledání nejdelšího společného podřetězce dvou řetězců (triviální řešení, kvadratické řešení pomocí KMP a řešení průměrně v O(n log n)).
  • Zmínka o suffixových stromech.
2. 11. Opakování základních pojmů z toků v sítích a jejich použití:
  • jak přidat k tokům kapacity do vrcholů,
  • jak hledat v grafu hranově nebo vrcholově disjunktní cesty mezi dvěma vrcholy,
  • rozmístění co největšího počtu dominových kostek 2x1 na děravou šachovnici (převod na hledání největšího párování v bipartitním grafu pomocí toků),
  • nejmenší vrcholové pokrytí v bipartitním grafu (bude dokončeno příště).
9. 11. Cvičení se nekoná, je děkanský sportovní den.
16. 11. Nejmenší vrcholové pokrytí v bipartitním grafu pomocí minimálního řezu. Opakování Dinicova algoritmu, hledání cesty ve vrstevnaté síti rovnou s čištěním, síť, na které Dinic vykoná co nejvíce fází, a odhad O(m) na hledání blokujícího toku, jsou-li kapacity jednotkové. Také řešení problému s rozvozem čokolády z továren ke spotřebitelům.
23. 11. Toky v sítích: opakování Goldbergova algoritmu (metoda preflow-push) a jeho implementace implementace v případě, že vybíráme nejvyšší vrchol. Časová složitost O(nm) na jednotkových sítích a různé počáteční výšky zdroje.
30. 11. Hradlové sítě: logické (booleovské) funkce se dvěma vstupy a jejich vyjádření jen pomocí AND, OR a NOT a pak jen pomocí NANDu (negace ANDu). Šlo by to ještě pomocí NORu (negace ORu), ale pomocí jiné funkce už ne. Převod logických funkcí s více vstupy na hradlovou síť s hradly AND, OR a NOT. Porovnání dvou N-bitových čísel sítí hloubky O(log N) a proč to nejde podstatně lépe, pokud používáme hradla se dvěma vstupy (nebo konstantně mnoha vstupy). Násobení dvou N-bitových čísel za pomoci převodu sečtení tří čísel na sečtení dvou čísel (nedokončeno).
7. 12. Dokončení hradlových sítí: násobení dvou N-bitových čísel s logaritmickou hloubkou za pomoci převodu sečtení tří čísel na sečtení dvou čísel, zmíněn převod odčítání na scítání (když reprezentujeme záporná čísla dvojkovým doplňkem.
Výpočetní geometrie (v rovině):
  • testování orientace úhlu pomocí determinantu,
  • provázkový algoritmus na konvexní obal na O(NH), kde H je počet bodů na obalu (zmíněno, že tento se použije na vytvoření algoritmu v O(N log H)),
  • přímka obsahující co nejvíce bodů v O(N2 log N),
  • nejdelší vodorovná úsečka v nekonvexním mnohoúhelníku pomocí zametání roviny.
14. 12. Diskrétní Fourierova transformace (DFT) jako lineární zobrazení a matice tohoto zobrazení. Co udává 0-tá a (n/2)-tá složka výsledného vektoru? Převádění vektorů a převod kanonické báze vektorového prostoru nad komplexními čísly (z toho lze vydedukovat, jak vypadá inverzní zobrazení k DFT).
21. 12. DFT reálného vektoru je antisymetrický vektor (čísla na symetrických pozicích jsou komplexně sdružená). Aproximace funkce pomocí sinů a kosinů (stačila by dokonce lineární kombinace sin kx a cos kx pro k od 0 do n/2). Rychlá Fourierova transformace pomocí hradlové sítě hloubky log n, z níž se pak dá odvodit podoba nerekurzivní implementace FFT.
4. 1. Převody rozhodovacích problémů: nezávislá množina na vrcholové pokrytí a obráceně, tříobarvitelnost grafu na splnitelnost formule a splnitelnost formule na kvadratické nerovnice.
Na závěr ještě návrat k rychlé Fourierově transformaci, konkrétně její verze nad konečnými tělesi a hlavní myšlenky rychlého násobení celých čísel pomocí FFT.
11. 1. Opakování NP-úplnosti a o tom, jak se vypořádat s NP-úplnými problémy. Pokračování v převodech problémů: 3D párování na soustavu 0/1 lineárních rovnic a soustava O/1 lineárních rovnic na batoh.

Zápočet

Zápočet je za 100 bodů. Body lze získávat různým způsobem, další způsoby možná časem přibudou. Zápočet je nutno dořešit do konce března.

Úkoly

Na cvičení (většinou) zadám 2-3 úkoly na vymyšlení asymptoticky co nejrychlejšího algoritmu (není-li řečeno jinak). Do řešení byste měli především napsat slovní popis algoritmu spolu se stručným zdůvodněním správnosti (není třeba formální důkaz) a časovou a paměťovou složitostí. Program nebo pseudokód není povinný, může sloužit k lepšímu pochopení (nebo k procvičení programování :-)

Po 14 dnech od zadání jsou úkoly za polovinu uvedených bodů, přesněji do začátku cvičení 14 dnů po zadání (není-li uvedeno jinak). Taky po 14 dnech k nim mohu říct na požádání nápovědu (buď po cvičení, nebo emailem).

Úkoly odevzdávejte nejlépe elektronicky (ve formátu PDF, ODT, ... nebo i jen jako text emailu). Nafocený text psaný rukou mi neposílejte.

Tabulka s úkoly je níže. Po čase (po alespoň týdnu od termínu, tedy po 3 týdnech od zadání) řeknu k některým těžším úkolům řešení (alespoň za 11 bodů).

Zápočtový program

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 mohly být snadno 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.

Před tím, než začnete něco programovat, pošlete mi email s tématem zápočťáku a počkejte na schválení. Témata musejí být různá a může se jednat o implementaci těžšího algoritmu či DS z přednášky, případně (lépe) o jejich aplikaci či o úpravu 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.

Konkrétní bodové ohodnocení zápočtového programu závisí na vybraném tématu, u středně obtížných témat to bude okolo 60 bodů. Také můžete získat nějaké bonusové body za pěkné zpracování (implementaci).

Esej

Esej spočívá v nastudování nějakého algoritmu či datové struktury nad rámec přednášky a v sepsání 2-4 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, ...

Konkrétní bodové ohodnocení závisí na vybraném tématu a na zpracování, podobně jako u zápočťáku. Témata esejí musejí být také různá.

Soutěž CTU Open Contest

Pokud v soutěži CTU Open Contest úspěšně vyřešíte alespoň 3 úlohy, získáte 15 bodů. Za alespoň 5 vyřešených úloh je 20 bodů. (Účast je samozřejmě nepovinná a bodů za úkoly bude celkově o dost víc jak 100, nemluvě o možnosti napsat zápočťák či esej.)

Seznam úkolů

Za plný počet odevzdávejte do 14 dnů od zadání do začátku cvičení (není-li řečeno jinak).
Datum Jméno Body Zadání
12. 10. rýmy 7 Vymyslete algoritmus, který načte slovník a pak umí pro zadaná slova nacházet nejlepší rýmy – tím se myslí slovo ve slovníku, které má se zadaným slovem má co nejdelší společný suffix (a je od něj různé). Pokud je nejlepších rýmů více, vypište libovolný z nich. Časová složitost odpovědi na dotaz by neměla záviset na velikosti slovníku.
Úkoly z tohoto cvičení je možné odevzdávat za plný počet bodů až do 2.11.
podposloupnost 10 Hledáme v textu (seně) jehlu jako vybranou podposloupnost. Navrhněte algoritmus, který vypíše všechny výskyty. Plný počet bodů za řešení se složitostí O(S+JV), kde S je délka sena, J délka jehly a V počet výskytů; menší počet bodů za méně efektivní, ale stále polynomiální řešení. Můžete předpokládat, že všechny znaky jehly jsou navzájem různé.
rotace na místě 12 Daný řetězec S zrotujte na místě o k znaků doprava v čase O(n), n = |S| (nezávisle na k). Na místě zde znamená, že krom samotného řetězce (jako modifikovatelného pole znaků) smíte použít navíc jen O(1) proměnných velikosti O(log s), kde s je velikost textu. Zdůvodněte, že vaše řešení skutečně funguje.
19. 10. zkratky 8 Ukažte, že u algoritmu Aho-Corasicková jsou zkratky potřeba: Předpokládejme, že bychom u každého stavu zkoumali, do jakých všech stavů se lze dostat po zpětných hranách, a sbírali ty koncové. Sestrojte vstup, pro který tím strávíme víc než lineární čas, ačkoliv nenajdeme vůbec žádný výskyt.
Fibonacciho slova 13 Definujme Fibonacciho slova takto: F0=a, F1=b, Fn+2 = FnFn+1, kde a a b jsou libovolná různá písmena. Jak v zadaném řetězci (nad potenciálně velkou abecedou) najít nejdelší Fibonacciho podslovo v lineárním čase?
Hint: Pokud bych stavěl automat pro aktuální Fi , do jakého stavu se můžu dostat při nečekaném písmenku?
Pozor, a a b jsou v této úloze proměnné, tedy např. ve slově CDCBBCBDC je nejdelší Fibonacciho podslovo CBBCB.

K úkolu bylo řečeno řešení.
26. 10. multihodiny 8 Máme dvoje "multihodiny", každé s N nerozlišitelnými ručičkami, jejichž polohy jsou zadané absolutními úhly (můžete předpokládat, že úhly ručiček dostanete seřazené dle absolutních úhlů). Zjistěte, jestli polohu na jedněch hodinách lze dostat pootočením druhých hodin, tedy pootočením všech ručiček o stejný úhel.
Příklad: absolutní úhly na 1. hodinách jsou 10°, 90°, 180° a 190° a na 2. hodinách 0°, 180°, 260° a 350°. Jedny hodiny lze pootočit tak, že získáme ty druhé.
Úkoly z tohoto cvičení je možné odevzdávat za plný počet bodů až do 16.11. do začátku cvičení.
sifra 15 Substituční šifra funguje tak, že zpermutujeme abecedu: například permutací abecedy ABCDE... na DEABC... zašifrujeme slovo BABA na DEDE. Zašifrovaný text je méně srozumitelný, ale například vyzradí, kde v originálu byly stejné znaky a kde různé.
Je dáno seno zašifrované substituční šifrou a (nezašifrovaná) jehla. Najděte všechny možné výskyty jehly v originálním seně (tedy takové pozice v seně, pro něž existuje permutace abecedy, která přeloží jehlu na příslušný kousek sena).
opakování 9 Najděte v řetězci nejdelší opakující se podřetězec (stačí, když se opakuje jednou, opakování se mohou protínat). Např. v řetězci CAUAHOJZDARAHOJCAU je to AHOJ, v řetězci ABCABCABC je to ABCABC.
Na plný počet bodů to můžete udělat i asymptoticky "trochu hůře" než lineárně, ale nepoužívejte suffixový strom (ledaže byste popsali jeho konstrukci).
2. 11. věže 8 Je dána děravá šachovnice o straně délky N. Umístěte na ní co nejvíce věží tak, aby nestály na dírách a žádné dvě se vzájemně neohrožovaly, přičemž dvě věže se ohrožují, když jsou na stejném řádku či sloupci, nezávisle na tom, jestli jsou mezi nimi díry. (Problém stačí převést na hledání maximálního toku.)
Úkoly z tohoto cvičení je možné odevzdávat za plný počet bodů do 23.11. do začátku cvičení (proudloužil jsem termín o týden).
pseudotok 11 Mějme graf, jehož hrany jsou orientované a mají kladné celočíselné kapacity. Pro každý vrchol v je navíc dáno, jaký má být minimální součet toků po vstupních hranách do v a kolik musí maximálně vytékat po výstupních hranách z v. Cílem je najít ohodnocení hran („pseudotok“), které respektuje kapacity a bude splňovat podmínky na každý vrchol, případně ohlásit, že takové ohodnocení neexistuje. (Tok to být nemusí a často ani nebude, jinými slovy nemusí vždy platit Kirchhoffův zákon.)
16. 11. souvislost hranová 8 Hranová souvislost (neorientovaného) grafu je minimální počet hran, které musíme odebrat, aby se stal nesouvislým. Najděte algoritmus na zjištění hranové souvislosti pomocí toků v sítích, přičemž se snažte použít pouze O(n) sítí s O(m) hranami (kde n je počet vrcholů grafu a m je počet hran).
(Úkoly z tohoto cvičení je možné odevzdávat za plný počet bodů do 30.11. do začátku cvičení.)
souvislost vrcholová 7 Jak upravit řešení předchozí úlohy pro vrcholovou souvislost? Vrcholová souvislost je nejmenší počet vrcholů, které musíme z grafu odebrat, aby se stal nesouvislým, případně n pro úplný graf Kn. Můžete použít víc jak O(n) sítí, ale snažte se o asymptoticky méně jako O(n2) sítí alespoň pro určité grafy, například pro grafy s vrcholovou souvislostí o(n), tedy relativně malou.
projekty 15 Mějme zdroje Z1 až Zn a projekty P1 až Pk, přičemž za realizaci projektu Pi dostaneme ri peněz, ale potřebujeme k tomu mít k dispozici množinu zdrojů Si. Každý zdroj Zj nás stojí náklady cj, ale jakmile ho jednou koupíme, můžeme ho použít ve více projektech. Navrhněte algoritmus, který zjistí, které projekty realizovat a jaké zdroje si koupit, aby byl celkový zisk co největší (ziskem je rozdíl odměn za splněné projekty a nákladů na pořízené zdroje).
Hint: Hledejte minimální řez ve vhodném grafu.
23. 11. goldberg 10 Naprogramujte Goldbergův algoritmus s výběrem nejvyššího vrcholu (jak jsme ukazovali na cvičení). Stačí i jen pseudokód, ale podrobný (mj. co a jak se přidává do datových struktur) a jednotlivé kroky okomentujte.
párování 9 Vzpomeňte si, jak jsme převáděli největší párování v bipartitním grafu na maximální tok v jisté síti. Nahlédněte, jak chod Ford-Fulkersonova algoritmu přeložit do řeči párování v původním grafu a získat tak algoritmus na největší párování v bipartitním grafu, který vůbec nepoužívá toky.
30. 11. dělitelnost třemi 10 Sestrojte hradlovou síť logaritmické hloubky, která otestuje, zda je N-bitové binární číslo dělitelné třemi.
zatřídění 10 Navrhněte třídící síť (tj. hradlovou síť s komparátory) s co nejmenší hloubkou, která na vstupu dostane setříděnou posloupnost délky N a číslo, která máte do této posloupnosti zatřídit. Výstupem je tedy N+1 setříděných čísel. Můžete předpokládat, že N+1 je mocnina dvojky.
těžká funkce 14 Ukažte, že nějaké funkce vyžadují hradlové sítě s větším než polynomiálním počtem hradel. Přesněji: dokažte, že pro každé K a dost velké N ("dost velké" může záviset na K) existuje booleovská funkce N proměnných, která se nedá spočítat hradlovou sítí o O(NK) hradlech.
Hint: spočtěte počet funkcí a odhadněte počet hradlových sítí dané velikosti.
7. 12. obal a třídění 9 Výpočet konvexního obalu je alespoň tak těžký jako třídění reálných čísel: Ukažte, že umíte-li vypočítat konvexní obal množiny n bodů v čase T(n), lze třídit n reálných čísel v čase O(T(n)). Jinými slovy vymyslete převod třídění čísel na výpočet konvexního obalu. (Vypočtením konvexního obalu přitom myslíme nejen stanovení, které body na obalu leží, ale i v jakém pořadí. Leží-li tři body na jedné přímce, prostřední z nich nemusí ležet v konvexním obalu, i kdyby v něm oba krajní body byly.)
průnik 11 Na vstupu jsou zadány dva konvexní mnohoúhelníky (jako posloupnosti vrcholů v pořadí dle jejich obalu). Vypočtěte konvexní mnohoúhelník, který vznikne jejich průnikem.
14. 12. DFT převod 1 8 Jak vypadá DFT vektoru (42,-42,42,-42,42,-42, ... ,42,-42) délky n pro n sudé? (Hint: vyjde pěkně.)
Oba úkoly z 14.12. jsou do začátku cvičení 4.1. Oba rovněž můžete odevzdat na papíře, pokud se vám to zdá pohodlnější.
DFT převod 2 8 Jak vypadá DFT vektoru (0,1,0,1,0,1, ... ,0,1) délky n pro n sudé? (Hint: vyjde opět pěkně :-)
21. 12. DFT antisymetrického vektoru 9 Dokažte, že DFT antisymetrického vektoru je reálný vektor. Vektor x je antisymetrický, pokud xj a xn-j jsou komplexně sdružená čísla a x0 je reálné číslo.
Tento úkol je do začátku cvičení 11.1. a také ho můžete odevzdat na papíře.
obdélníky 14 Návrat ke geometrickým algoritmům: Navrhněte algoritmus, který spočítá obsah sjednocení dané množiny osových obdélníků, tedy obdélníků, které mají strany rovnoběžné s x-ovou a y-ovou osou.
Hint: Vzpomeňte si na intervalové stromy (i když úlohu jde možná řešit i bez nich).
Tento úkol je do konce března.
4. 1. kvadratické rovnice 12 Najděte polynomiální převod z 3-SATu (splnitelnosti formulí v CNF, kde klauzule mají maximálně 3 literály) na problém splnitelnosti soustavy kvadratických rovnic (soustava je splnitelná, pokud existuje ohodnocení proměnných reálnými čísly takové, že platí každá rovnice).
Hint: zkuste nejprve převést 3-SAT na kubické rovnice. (Ale možná to lze řešit i jinak.) I za kubické rovnice bude určitá část bodů.
Tento úkol a všechny následující jsou do konce března..
2-SAT 15 Ukažte, jak vyřešit 2-SAT (splnitelnost logických formulí v CNF, jejichž každá klauzule obsahuje nejvýše 2 literály).
násobení čísel min. 10 Domyslete a sepište detaily okolo násobení velkých celých čísel pomocí FFT, jež jsme načali na cviku. Může se hodit podívat se na cvičení na konci kapitoly o Fourierově transformaci ve skriptech. Body přidělím dle kvality zpracování.
11. 1. P-úplnost 7 Jak vypadají P-úplné problémy? Tedy takové, které leží v P a cokoliv z P se na ně dá převést.
nezávislá a malé stupně 9 Dokažte NP-úplnost nalezení nezávislé množiny velikosti alespoň K v grafu, jehož vrcholy mají stupeň omezen čtyřmi. Můžete zkusit převést 3,3-SAT na tento problém.
středová symetrie 8 Jak efektivně zjistit, jestli je zadaná množina bodů středově symetrická?
setřízení 0/1 posloupností 10 Dokažte, že pokud komparátorová síť setřídí každou posloupnost nul a jedniček, tak už setřídí cokoliv.
E3,E3-SAT 15 3-SAT omezíme tak, aby každá klauzule obsahovala právě 3 různé proměnné a každá proměnná se vyskytovala v právě 3 klauzulích. Ukažte, že pro takový problém existuje triviální algoritmus.

Tabulka výsledků

Již není vidět.

Zdroje a odkazy