# Zkouška 22.12.2021 Mareš

<{ForumPost(poster="davidzeman", timestamp=2021-12-23 09:12:52)}>
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.
<{/ForumPost}>