Algoritmy a datové struktury II

Cvičení k přednášce Algoritmy a datové struktury II [NTIN061].

Požadavky na zápočet

Co jsme dělali

4. 10. 2017
Naivní algoritmus hledání textu je pomalý. Vyhledávání textu jako podposloupnosti, Longest common substring a příbuzné problémy.
11. 10. 2017
Algoritmus KMP a konstrukce vyhledávácího automatu. Jak poznat jestli je jedno slovo rotací druhého nebo jestli je slovo periodické.
18. 10. 2017
Algoritmus Aho-Corasicková a konstrukce vyhledávácího automatu. Proč nemůžeme hlásit výskyty průchodem zpětných hran ani je mít přepočítané jako množiny u každého stavu. Frekvence výskytů hledaných slov.
25. 10. 2017
Toky v sítích, Ford-Fulkersonův algoritmus a jeho chování na jednotkových, celočíselných a racionálních kapacitách. Hranově a vrcholově disjunktní cesty. Věže na vykousané šachovnici.
1. 11. 2017
Dinicův algoritmus a jeho složitost na jednotkových kapacitách. Poslanecké kluby a assignment problem.
15. 11. 2017
Hradlové sítě, s omezeným i binárním počtem vstupů hradel. Sčítání pomocí hradlových sítí. Komparátorové sítě.
22. 11. 2017
Zatřizování s použitím komparátorů a komparátor jako hradlová síť. Proč konvexní obal potřebuje $\Omega (n \log n)$ času a počítání obsahu konvexního mnohoúhelníka.
29. 11. 2017
Komplexní čísla, $n$-té odmocniny jedničky a rychlá Fourierova transformace. Výsledek FFT aplikované na vektory $(0, \ldots, 0)$ a $(x, \ldots, x)$. Souvislosti se spojitou Fourierovou transformací, zpracováním zvuku a obrazu.
6. 12. 2017
Pokračování FFT. Výsledek FFT aplikované na vektory $(1, \omega_n^{j}, \omega_n^{2j}, \ldots, \omega_n^{(n-1)j})$. Inverz FFT.
13. 12. 2017
Třídy P a NP. Zoo NP-úplných problémů. SAT a 3-SAT. Nezávislá množina, klika a vrcholové pokrytí. Loupežníci, batoh a součet podmnožiny. Barvení grafů.
20. 12. 2017
Opakování minulého cvičení.
3. 1. 2018
Hamiltonovské kružnice a cesty (orientované i neorientované) a převody mezi nimi. Získání řešení z rozhodovacích verzí problémů. Problémy jdou řešit na jednodušších podtřídách (např. nezávislá množina ve stromu).
10. 1. 2018
Obchodní cestující (TSP) a jeho NP-úplnost. Aproximační algoritmy. Neaproximovatelnost TSP a 2-aproximace jeho metrické varianty. 2-aproximace vrcholového pokrytí.

Domácí úkoly

Úkoly odevzdávejte buď osobně před začátkem cvičení nebo pomocí emailu. Pokud je to alespoň trochu možné, neodevzdávejte prosím přes mail naskenované ruční řešení (ideálně sázejte v $\LaTeX \text{u}$).

1. Rotace slova (do 11.10.) 5b.
Napište algoritmus, který na vstupu dostane řetězec $S$ a číslo $k$. Na výstupu algoritmu chceme řetězec rotovaný o $k$ pozic (řetězec na pozici $k$ rozřízneme a přilepíme začátek za konec). Algoritmus by měl běžet v čase $O(|S|)$. Zároveň můžete využít jen pole, ve kterém je vstupní řetězec zapsán a $O(1)$ pomocné paměti.
2. Suffixy a prefixy (do 18.10.) 5b.
Pro slova $A, B$ chceme nalézet nejdelší suffix slova $A$, který je zároveň prefixem slova $B$.
3. Speciální výskyty (do 25.10) 4b.
Vymyslete algoritmy, které dostanou na vstupu slova $J_1, \ldots ,J_k$ a text $S$. Výstupem algoritmu pak je pro každou pozici,
  • index pozice a nejdelší slovo, které na ní končí,
  • index pozice a nejkratší slovo, které na ní končí,
  • index pozice a nejdelší slovo, které na ní začíná,
  • index pozice a nejkratší slovo, které na ní začíná.
4. Domino na šachovnici (do 1.11.) 5b.
Mějme šachovnici $r \times s$ se seznamem zakázaných políček. Chceme na povolená políčka rozmístit kostky domina velikosti $1 \times 2$ políčka tak, aby každé povolené políčko bylo pokryto právě jednou kostkou. Kostky je povoleno otáčet.
5. Zaokrouhlování matice (do 15.11.) 5b.
Na vstupu dostaneme matici $A$ nezáporných reálných čísel o velikosti $r \times s$. Vymyslete algoritmus, který zaokrouhlí prvky matice nahoru nebo dolů tak, že zůstanou zachovány všechny řádkové i sloupcové součty, nebo odpoví, že takové zaokrouhlení neexistuje.
6. Porovnání dvou čísel (do 22.11.) 5b.
Sestrojte hradlovou síť hloubky $O(\log n)$, která porovná dvě $n$-bitová čísla $x$ a $y$ a vydá jedničku, pokud $x$ < $y$.
7. Středově symetrická množina (do 29.11.) 5b.
Navrhněte algoritmus, který rozhodne zda je množina bodů v rovině středově symetrická.
8. Fourierovy obrazy (do 6.12.) 6b.
Spočítejte Fourierovy obrazy následujících vektorů (každý za 2b.):
  • $(1,0,1,0, \ldots ,1,0)$,
  • $(\omega_n^0, \omega_n^1, \ldots, \omega_n^{n-1} )$,
  • $(\omega_n^0, \omega_n^2, \ldots, \omega_n^{2n-2} )$ kde $\omega_n = e^{2\pi i / n}$.
9. $k$-barevnost (do 20.12.) 5b.
Převeďte problém $k$-barevnosti na $k$-SAT pro $k \geq 2$. Správné řešení obsahuje popis redukce a důkaz její správnosti!
10. Loupežníci (do 3.1.) 5b.
Máte algoritmus pro rozhodovací verzi loupežníků. Jak naleznete rozdělení mezi loupežníky? Zde se nám jedná o to najít řešení, pokud můžete položit polynomiálně mnoho dotazů rozhodovací verzi loupežníků.
11. Vrcholové pokrytí stromu (do 10.1.) 5b.
Nalezněte polynomiální algoritmus pro nalezení vrcholového pokrytí stromu.

Bonusové domácí úkoly

B1. Palindromický prefix (do 25.10.) 5b.
Najděte nejdelší prefix slova $A$, který je palindromem.
B2. Špatná síť pro Dinicův algoritmus (do 22.11.) 5b.
Najděte síť, na níž Dinicův algoritmus běží v čase $\Omega (n^2 m)$ (tedy asymptoticky v nejhorším možném čase).
B3. Obsah nekonvexního mnohoúhelníka (do 13.12.) 5b.
Navrhněte algoritmus na výpočet obsahu nekonvexního mnohoúhelníka (vrcholy jsou zadané v pořadí na obvodu).

Body

Přezdívky Celkem 1 2 3 4 5 6 7 8 9 10 11 B1 B2 B3
maximum 70 5 5 4 5 5 5 5 6 5 5 5 5 5 5
zápočet 33 3 3 2,4 3 3 3 3 3,6 3 3 3 0 0 0
Dexman 48 5 5 2,5 5 4 4 5 0 0 5 5 5 0 2,5
EM 38 5 4 2 4,5 2,5 2,5 4,5 4 0 0 0 5 1 3
Jerrys 40 5 5 2,5 4,5 3,5 2,5 5 2 2 0 3 3,5 0 1,5
MARTESING 43 5 5 4 5 4 5 5 0 5 0 0 5 0 0

Užitečné odkazy