Matfyz Wiki
Nakreslete graf a tabulku zpetne a vystupni funkce podle algoritmu Aho-Corasickova pro slova strom, stroj, postroj, trojka.
Mate mrizku n * n, kde je m cernych bodu a ostatni bile. Navrhnete polynomialni algoritmus, ktery zjisti, jestli existuje prave m cest z cernych bodu do nejakych bilych na okraji mrizky, ktere jsou vrcholove disjunktni. Cerny bod na okraji mrizky potrebuje cestu delky 0. Muzete vyuzit jakykoli algoritmus z prednasky, ale nemusite ho popisovat.
Izomorfismus podgrafu pro grafy G a H je prave tehdy, kdyz existuje v G nejaky indukovany podgraf izomorfni s H. Dokazte, ze tento problem je NP-uplny. Muzete vyuzit znalost NP-uplnych problemu z prednasky.