Algoritmy a datové struktury 2 – cvičení

Podmínky pro získání zápočtu

Pravidelně budu zadávat domácí úkoly. Občas můžu zadat bonusový úkol.

Na zápočet je třeba získat alespoň dvě třetiny počtu bodů ze standardních úloh (bonusové se počítají jen do vašeho skóre).

Co se probralo

2. 10.: Opakování ADS 1, různé úlohy (cvičení před první přednáškou). Úlohy (PDF)

9. 10.: Algoritmus KMP. Úlohy (PDF)

16. 10.: Aho-Corasick, Rabin-Karp. Úlohy (PDF)

23. 10.: Toky v sítích, Ford-Fulkersonův algoritmus, bipartitní párování. Úlohy (PDF)

30. 10.: Toky v sítích, Dinicův algoritmus. Úlohy (PDF)

6. 11.: Nenavazovali jsme na přednášku, místo standardního cvičení jsem pověděl něco o Fourierově transformaci (tady jsou slajdy, které jsem promítal).

Pro zájemce jsem nachystal nějaké úlohy: Zadání (PDF)

Doporučení: 3blue1brown má několik pěkných videí o Fourierově transformaci. První video série je tohle.

13. 11.: Toky v sítích, Goldbergův algoritmus. Úlohy (PDF)

20. 11.: Diskrétní Fourierova transformace a algoritmus FFT. Místo mě cvičení připravil a vedl Pavel Veselý. Úlohy (PDF)

27. 11.: Úvod do hradlových sítí. Úlohy (PDF)

4. 12.: Pokračování hradlových sítí, něco ke konvexnímu obalu v rovině. Úlohy (PDF)

11. 12.: Geometrické algoritmy. Úlohy (PDF)

18. 12.: Úvod do studia těžkých problémů, převody mezi problémy. Úlohy (PDF)

8. 1.: Povídal jsem o problému P vs. NP. K úlohám (PDF) jsme se nedostali.

Na cviku jsem řekl (minimálně) jednu hloupost: že $\mathcal{P}^{SAT} = \mathcal{NP}^{SAT}$. Pokud $\mathcal{P} = \mathcal{NP}$, tak to samozřejmě platí, ale rozbije to několik aktuálních hypotéz (např. polynomiální hierarchii). Pokud vás zajímá, o kterých orákulech $A, B$ platí $\mathcal{NP}^A = \mathcal{P}^A$ a $\mathcal{NP}^B \neq \mathcal{P}^B$, můžete si přečíst tyhle zápisky.

Pokud vás cokoli během cvika zaujalo, můžete mi napsat a já vám zkusím doporučit další zdroje (případně předměty na MFF) k tématu.

Domácí úkoly

Odevzdávejte buď na papíře před začátkem cvičení, nebo v TXT/PDF na e-mail mk-hw@seznam.cz nejpozději ve 23:00 den před cvičením.

• Úkol 1: Definujme Fibonacciho slova takto: $F_0 = a$, $F_1 = b$, $F_{n+2} = F_nF_{n+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?
  Pozor, že $a$ a $b$ v zadání figurují jako proměnné, tedy například ve slově CDCBBCBDC je nejdelší Fibonacciho podslovo CBBCB.
  
  (10 bodů) Deadline: 23. 10.
• Úkol 2: Zjistěte, který řetězec délky $k$ se v textu $S$ vyskytuje nejčastěji. Cílíme na lineární střední hodnotu délky běhu (vůči velikosti vstupu).
  
  (10 bodů) Deadline: 30. 10. Deadline posunut na 6. 11.
• Úkol 3: 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 neorientovaného grafu pomocí toků v sítích.
  Snažte se použít jen $\mathcal{O}(n)$ sítí s $\mathcal{O}(m)$ hranami ($n$ značí počet vrcholů, $m$ počet hran).
  
  Jak postup upravit pro vrcholovou souvislost (nejmenší počet vrcholů, které musíme odebrat pro nesouvislost, případně $n$ pro úplný graf $K_n$)? Zde můžete použít více než $\mathcal{O}(n)$ sítí, ale snažte se o asymptoticky méně než $\mathcal{O}(n^2)$ pro grafy s vrcholovou souvislostí $o(n)$, tj. pro grafy s nízkou vrcholovou souvislostí.
  
  (10 bodů) Deadline: 6. 11.
• Úkol 4: Tentokrát dva úkoly: Zadání (PDF).
  
  (12 bodů) Deadline až 4. 12.
• Úkol 5 (BONUSOVÝ): Spočtěte Fourierův obraz vektoru $(1, i, -1, -i, 1, i, -1, -i, \dots)$ délky $n$ dělitelné $4$ (kde $i=\sqrt{-1}$). Kromě samotného výsledku (který vyjde hezky) je potřeba sepsat i zdůvodnění/výpočty.
  
  (5 bodů) Deadline: 4. 12.
  
  Pro zájemce jsem sepsal vzorové řešení (PDF). Soubor obsahuje dva možné přístupy k řešení úlohy, a navíc nějaké doplňující povídání k DFT.
• Úkol 6: Dokažte, že $n$-bitový OR nelze spočítat v menší než logaritmické hloubce.
  
  (10 bodů) Deadline: 11. 12.
• Úkol 7: Ukažte, jak v logaritmické hloubce otestovat, zda je $n$-bitové číslo dělitelné sedmi.
  
  (10 bodů) Deadline: 18. 12.
• Úkol 8 (BONUSOVÝ): Sestrojte hradlovou síť polylogaritmické hloubky, která dostane matici sousednosti neorientovaného grafu a rozhodne, zda je graf souvislý.
  
  (10 bodů) Deadline: 18. 12.
• Úkol 9: Navrhněte algoritmus pro výpočet obsahu (potenciálně nekonvexního) mnohoúhelníku. Vrcholy jsou zadané v pořadí, jak následují na obvodu.
  
  (10 bodů) Deadline: 8. 1.
• Úkol 10: Rozhodovací problém "$k$ skupin" řeší následující otázku. Mějme $n$ lidí, kteří jsou aktivní v $m$ společenských skupinách. Instance "$k$ skupin" dostane seznam těchto $n$ lidí, seznam jejich $m$ skupin (pro každou skupinu seznam jejích členů) a parametr $k$. Ptáme se, zda existuje $k$ (nebo méně) skupin takových, že každý z $n$ lidí je alespoň v jedné z nich.
  
  Příklad: Seznam lidí bude "Anna, Bedřich, Cyril, Dagmar", a ti jsou aktivní ve skupinách
  • Fotbalisti: Bedřich, Dagmar
  • Klavíristi: Anna, Dagmar
  • Malíři: Anna, Bedřich, Cyril
  Parametr $k$ je nastaven na $2$. Tady je odpověď "ano", protože stačí vzít skupiny "Fotbalisti" a "Malíři". Kdyby chyběla skupina Malíři, odpověď by byla "ne" už jen proto, že Cyril není v žádné skupině.
  
  Váš úkol: Ukažte, že problém SAT z přednášky lze polynomiálně převést na problém $k$ skupin.
  
  (10 bodů) Deadline: 8. 1.
• Úkol 11 (BONUSOVÝ): Vzpomeňme, že booleovských funkcí $n$ proměnných je celkem $2^{2^n}$. Taky jsme viděli, že každou booleovskou funkci jde řešit lineárně hlubokou hradlovou sítí s exponenciálně mnoha hradly.
  
  Ukažte, že polynomiální množství hradel nestačí. Přesněji, dokažte, že pro žádné $k$ neplatí, že každá $n$-vstupová booleovská funkce lze spočítat obvodem s $\mathcal{O}(n^k)$ hradly.
  (To speciálně implikuje existenci konkrétních booleovských funkcí, pro které $\mathcal{O}(n^k)$ hradel nestačí. Můžete taky rozmyslet, že nemusíme končit u polynomů. Lze to dokázat i pro rychleji rostoucí funkce.)
  
  (10 bodů) Deadline: 8. 1.
• Úkol 12 (BONUSOVÝ): Převeďte problém Klika na SAT (přímo, bez odvolání na Cookovu větu).
  Hint: hledejte očíslovanou kliku - tj. uspořádanou $k$-tici vrcholů, které tvoří kliku.
  
  (10 bodů) Deadline: kdy chcete zápočet
• Úkol 13 (BONUSOVÝ): Sestrojte hradlovou síť, která pro zadané dvojkové číslo $x_{n-1}\ldots x_0$ spočítá dolní celou část z jeho dvojkového logaritmu, tj. $\lfloor \log_2 x \rfloor$.
  
  (10 bodů) Deadline: kdy chcete zápočet

Bodové výsledky: Tabulka bodů

Užitečné odkazy

Stránka přednášky.

Knížka Průvodce labyrintem algoritmů, která pokrývá (nejen) sylabus předmětu.

Archiv úloh Korespondenčního semináře z programování.

Soutěžní programování: Codeforces, Spoj, HackerRank, CodeChef.

Zábavné kódící úlohy: Project Euler.