# Zkouška 15.2.2021 - Hubička

<{ForumPost(poster="ERRORCEK", timestamp=2021-02-15 14:20:15)}>
1. Algoritmus FFT, důkaz zprávnosti a časová složitost. \[10]  
2. Jak zjistit, jestli je zadaný řetězec periodický? Tedy zda pro daný řetězec $\alpha$ existuje řetězec $\beta$ a číslo $k > 1$ tak, že $\alpha = \beta^k$ (tedy řetězec $\beta$ opakovaný $k$-krát. \[5]  
3. Vymyslete pseudopolynomiální algoritmus pro *“problém tří loupežníků”*: Je dána posloupnost přirozených čísel, lze ji rozdělit na 3 části se stejným součtem? \[5]  
4. **Bonus:** Navrhněte hradlovou sít’, která počítá tranzitivní uzávěr orientovaného grafu. (Na vstupu je matice sousednosti, na výstupu matice taková, že na pozici (i,j) je jednička právě tehdy, když v grafu existuje orientovaná cesta z vrcholu i do vrcholu j).  
  
Idea riešení:  
1. Viď průvodce najmä od str. 398, zíde sa vedieť aj prečo a ako funguje to spájanie. Časová by mala byť $\Theta (n \log n)$  
2. Viac spôsobov. Zdvojiť vstup a nájsť periódu. KMP na to funguje dobre. Alebo predpočítať si najdlhší vlastný prefix, ktorý je aj suffix KMPčkom a potom len spraviť či $n\bmod(n-len) \equiv 0$  
3. Rekurzia je pomalá  $\mathcal{O}(3^N)$. To sa dá zlepšiť dynamický programovaním, pamätať si hodnoty už spočítané (napr. v mape), čím sa výrazne redukuje počet volaní rekurzie. Taktiež je to prevoditeľné na problém batohu (teda 2 batohov, 3. je implicitne). Výsledná by mala byť $\mathcal{O}(N*K^2)$, kde K sa rovná sume poľa.  
4. Neriešil som. TBH ani nepozrel, pretože mi to nebolo potrebné
<{/ForumPost}>