Zkouška 22.12.2021 Mareš
Napsal: 23. 12. 2021 09:12
14:00
1. NP-úplnost a NzMna.
2. Nejdelší Fibonacciho podslovo v řetězci nad abecedou {a,b}, kde F1=a, F2=b, Fn+2=FnFn+1.
3. Hradlová síť pro dělitelnost 5.
16:00
1. Goldberg - všechny invarianty a lemmata, jedno dokázat.
2. Je jeden řetězec rotací druhého?
3. Dokázat, že NzMna je NP-úplná i pro grafy s vrcholy stupně <= 4.
1. NP-úplnost a NzMna.
2. Nejdelší Fibonacciho podslovo v řetězci nad abecedou {a,b}, kde F1=a, F2=b, Fn+2=FnFn+1.
3. Hradlová síť pro dělitelnost 5.
16:00
1. Goldberg - všechny invarianty a lemmata, jedno dokázat.
2. Je jeden řetězec rotací druhého?
3. Dokázat, že NzMna je NP-úplná i pro grafy s vrcholy stupně <= 4.