Základní informace

• Cvičící: Petr Kučera <>, místnost S304
• Termín: Pondělí 10:40 -- 12:10 S6

Podmínky zápočtu

Na každém cvičení zadám domácí úkol. Termín odevzdání bude vždy do začátku dalšího cvičení. K udělení zápočtu bude nutné úspěšně vyřešit alespoň polovinu celkového počtu bodů (za každý úkol bude bod).

Domácí úkoly

1. cvičení (7. října 2013)

Uvažte naivní algoritmus na nalezení vzoru P délky m v textu T délky n, který pracuje v čase $O(mn)$. Popište příklad textu T vzoru P, který vyžaduje čas $\Omega(mn)$, a to i v případě, že se vzor P v textu T vůbec nevyskytuje.

2. cvičení (14. října 2013)

Popište, jak upravit Rabin-Karpův algoritmus pro vyhledávání zadané čtvercové matice P typu $m\times m$ v matici T typu $n\times n$.

3. cvičení (21. října 2013)

Popište co nejefektivnější algoritmus, který z dopředné, zpětné a výstupní funkce vyhledávacího automatu Aho-Corrasickové zkonstruuje konečný automat s pouze přechodovou funkcí a přijímajícími stavy.

4. cvičení (4. listopadu 2013)

Je dán graf $G=(V,E)$ a dva vrcholy $a,b\in V$. Popište, jak pomocí toků v sítích nalézt maximální počet po dvou hranově disjunktních cest, které vedou v G z a do b.

5. cvičení (11. listopadu 2013)

Ukažte, že Dinicův algoritmus pracuje v čase $O(mn)$ na síti s jednotkovými kapacitami (m zde označuje počet hran a n označuje počet vrcholů).

6. cvičení (18. listopadu 2013)

Máme množinu továren $t_1, \dots, t_p$ a množinu obchodů $o_1, \dots, o_q$, všichni vyrábějí a prodávají jeden druh zboží. Přitom továrna $t_i$ ho za jednotku času vyrobí $a_i$ kusů a obchod $o_j$ spotřebuje $b_j$ kusů. Máme daný bipartitní graf, který udává, ze které továrny lze vozit zboží do kterého obchodu. Dají se požadavky obchodníků splnit? Pokud ano, jak zjistit, které výrobky se mají přepravovat kam?

7. cvičení (25. listopadu 2013)

Popište komparátorovou síť pro výpočet maxima a minima, tj. jde o síť, která na výstupu na nejlevější pozici bude mít minimum a na nejpravější pozici maximum vstupních čísel. Síť by měla být co nejmělčí, ideálně s hloubkou $O(\log_2n)$, kde $n$ je počet čísel na vstupu.

8. cvičení (2. prosince 2013)

Je zadáno $n$ sečen kruhu se středem $s$. Tyto sečny jsou zadány souřadnicemi koncových bodů. Zajímá nás, kolik dvojic těchto sečen se uvnitř kruhu protíná. Popište algoritmus, který tento počet určí v čase $O(n\log n)$.

9. cvičení (9. prosince 2013)

Popište lineární algoritmus, který spočítá obsah konvexního mnohoúhelníku, pokud jsou na vstupu body zadané v pořadí, v jakém jsou na obvodu.