# Zkouška - 13.12.2019 Hubička

<{ForumPost(poster="spidoosho", timestamp=2019-12-15 16:16:22)}>
1. Popsat Goldbergův algoritmus, správnost + časová složitost \[10 bodů]  
  
2. Navrhněte hradlovou síť, která porovná dvě n-bitová čísla. (log n) \[5 bodů]  
  
3. Navrhněte algoritmus, který pokruje šachovnici s dírami dominem (2x1), aby žádné domino nečouhalo ze šachovnice nebo z děr. (průvodce 329/4) \[5 bodů]  
  
(BONUS) 4. Navrhněte dynamickou datovou strukturu, která po změne jednotlivých znaků v textu řekne, jestli obsahuje jehlu.
<{/ForumPost}>

<{ForumPost(poster="ZabudolSomHeslo", timestamp=2019-12-15 17:55:39)}>
1. Popísať Dinica - algoritmus, čas, pamäť, stačila mu intuícia  
2. Je existencia nezávislej množiny na grafe s vrcholmi maximálneho stupňa 2 P ? Je existencia nezávislej množiny na grafe s vrcholmi maximálneho stupňa 4 NP ?  
3. Nájsť v texte najdlhšie fibonacciho slovo  
  
Bonusovku som ani nečítal, možno by mohol niekto doplniť.
<{/ForumPost}>

<{ForumPost(poster="Remi", timestamp=2019-12-15 19:03:52)}>
Bonusovka byla pro obě skupiny zhruba stejná.
<{/ForumPost}>