Algoritmus FFT, důkaz zprávnosti a časová složitost. [10]
Jak zjistit, jestli je zadaný řetězec periodický? Tedy zda pro daný řetězec {: alt="\alpha" type="image/"} existuje řetězec {: alt="\beta" type="image/"} a číslo {: alt="k > 1" type="image/"} tak, že {: alt="\alpha = \beta^k" type="image/"} (tedy řetězec {: alt="\beta" type="image/"} opakovaný {: alt="k" type="image/"}-krát. [5]
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]
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í:
Viď průvodce najmä od str. 398, zíde sa vedieť aj prečo a ako funguje to spájanie. Časová by mala byť {: alt="\Theta (n \log n)" type="image/"}
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 {: alt="n\bmod(n-len) \equiv 0" type="image/"}
Rekurzia je pomalá {: alt="\mathcal{O}(3^N)" type="image/"}. 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ť {: alt="\mathcal{O}(N*K^2)" type="image/"}, kde K sa rovná sume poľa.
Neriešil som. TBH ani nepozrel, pretože mi to nebolo potrebné