# Zkouška 3.2.2009 Hric

<{ForumPost(poster="Wideman", timestamp=2009-02-03 13:47:50)}>
Byl to test se čtyřma otázkama, každá za 5b, k postupu na ústní bylo potřeba 13b, čas 80 minut:  
1) bylo zadáno p, q, e, M, mělo se zašifrovat M v RSA, dopočítat d, spočítat, kolik je možných klíčů pro zadané p a q  
2) dokázat, že operátor delta (takovej ten trojúhelník v carry look-ahead) je asociativní a není komutativní  
3) odhadnout počet nenasycených převedení přebytku v Goldbergově algoritmu a dokázat  
4) Dokázat, že problém dvojité nezávislé množiny je NP-úplný. Problém dvojité nezávislé podmnožiny - (G1, G2, k) - v grafu G1 i G2 je nezávislá podmnožina velikosti aspoň k  (hint: převedení problému kliky na problém nezávislé podmnožiny)  
  
Poté u ústní části měl u sebe vytisknutý ten seznam požadavků ke zkoušce a z něj něco namátkou vybíral.
<{/ForumPost}>