Zkouska - Cepek - 21.1.2011

Pokračování přednášky TIN060 Algoritmy a datové struktury I
Dr.Eddy
Matfyz(ák|ačka) level I
Příspěvky: 6
Registrován: 8. 2. 2010 17:03
Typ studia: Informatika Bc.

Zkouska - Cepek - 21.1.2011

Příspěvek od Dr.Eddy »

1. Nakreslete graf a tabulku zpetne a vystupni funkce podle algoritmu Aho-Corasickova pro slova strom, stroj, postroj, trojka.
2. 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.
3. 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.
Odpovědět

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