# zkouška 25.1 - Hric

<{ForumPost(poster="Schiroo", timestamp=2007-01-28 22:37:36)}>
**Písemná část:**  
4 příklady, 75min., každý příklad za 5bodů, na ústní potřeba 12/20.  
  
Zadání (přibližné):  
1, Vytvořte vyhledávací stroj Aho-Corrasick pro vzorky {dar, radar, hrad, hlad, hra }  
2, Odhadněte počet nasycených převedení v Goldbergově algoritmu. Dokažte.  
3, Vynásobte polynomy (x*x - x + 2)*( 2x - 1 ) pomocí FFT.  
4, a,Popište algoritmus RSA, popište postup, jak najít inverzní prvek. Dokažte správnost RSA  
   b, Kolik různých klíčů můžu dostat pro p = 11 a q = 4?  
**  
Ústní:**  
1 otázka, s důkazem, zdálo se mi, že je zadával podle toho, jak kdo napsal písemku. Kdo chce jedničku, měl by prý umět i složitější důkazy.  
  
Otázky:  
Dokažte neexistenci aproximačního algoritmu pro obecný problém obchodního cestujícího   
Aproximační algoritmus pro vrcholové pokrytí  
Nalezení konvexního obalu  
Třídící sítě  
Převoditelnost problémů, co jsou to NP úplné problémy...  
  
...a další, odcházel jsem mezi prvními, víc nevím  
  
Já jsem dostal obecného obch.cest, řekl jsem mu, co je ob. problém obch. cest., že bych to asi měl převést na NP úplnou úlohu nebo úlohu se složistostí 2^n a že nevím jak :oops: . Z písemné 18/20, výsledek za 2.Ptal se i na chyby v písemce, jestli vím, jak bych to měl opravit.
<{/ForumPost}>

<{ForumPost(poster="Petaa", timestamp=2007-02-07 13:44:28)}>
Jsem ponekud zmaten... :/ Tam by prece q a p mela byt nejaka prvocisla, aby to byla RSA sifra, ne? A q=4 prvocislo neni. :( Jak by se to pocitalo??
<{/ForumPost}>

<{ForumPost(poster="Anonymous", timestamp=2007-02-07 20:33:53)}>
ak si dobre spominam tak tam malo byt 3.
<{/ForumPost}>