Zkouška 3.2.2009 Hric

Pokračování přednášky TIN060 Algoritmy a datové struktury I
Wideman

Zkouška 3.2.2009 Hric

Příspěvek od Wideman »

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.
Odpovědět

Zpět na „TIN061 Algoritmy a datové struktury II“