Algoritmy a datové struktury II
Cvičení k přednášce Algoritmy a datové struktury II [NTIN061].
Požadavky na zápočet
- Na každém cvičení bude zadán (alespoň) jeden úkol s odevzdáním do začátku příštího cvičení.
- Na zápočet je třeba dosáhnout 60% z celkového počtu bodů.
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