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
. 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.