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
existuje řetězec
a číslo
tak, že
(tedy řetězec
opakovaný
-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ť
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
3. Rekurzia je pomalá
. 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ť
, kde K sa rovná sume poľa.
4. Neriešil som. TBH ani nepozrel, pretože mi to nebolo potrebné
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 [latex]\alpha[/latex] existuje řetězec [latex]\beta[/latex] a číslo [latex]k > 1[/latex] tak, že [latex]\alpha = \beta^k[/latex] (tedy řetězec [latex]\beta[/latex] opakovaný [latex]k[/latex]-krát. [5]
3. Vymyslete pseudopolynomiální algoritmus pro [i]“problém tří loupežníků”[/i]: Je dána posloupnost přirozených čísel, lze ji rozdělit na 3 části se stejným součtem? [5]
4. [b]Bonus:[/b] 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ť [latex]\Theta (n \log n)[/latex]
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 [latex]n\bmod(n-len) \equiv 0[/latex]
3. Rekurzia je pomalá [latex]\mathcal{O}(3^N)[/latex]. 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ť [latex]\mathcal{O}(N*K^2)[/latex], kde K sa rovná sume poľa.
4. Neriešil som. TBH ani nepozrel, pretože mi to nebolo potrebné