# Zkouska MJ 14.02.2008

<{ForumPost(poster="dallingerp", timestamp=2008-02-14 16:02:12)}>
1. Je dan orientovany graf G a s, t z V(G). Naleznete max. mnozinu cest z s do t takovou, aby prunik kazdych dvou byl {s, t}  
  
uloha na hledani toku.  
staci kazdy vrchol rozdelit na dva, aby vsechny vstupni hrany mirily do jednoho, vsechny vystupni hrany vychazely z druheho a spojit je hranou (tim se vynuti, aby se kazdym vrcholem proslo max. jednou)  
kazde hrane nastavim kapacitu na 1 a vyhledam max. tok. velikost toku bude odpovidat poctu tech cest. Nejakym prohledavanim se pak najdou ty cesty. Muzou na nich byt nejake cirkulace, ktere je nutne odstranit, ale nemuzou mit spolecne vrcholy.  
  
2. Pro dane retezce a, b zjistete, zda existuje k: R(a, k) = b  
R(a, k) = a\[k:]a\[:k]  
napr. R(abcde, 2) = cdeab  
  
b' = bb  
Knuth-Morris-Prattovym algoritmem hledam a v b'. pokud ho najdu pak k neexistuje, pokud ho najdu tak k existuje a rovna se poradi v b', kde zacina podretezec a  
  
3. Aho-Corasikova  
popis algoritmu a dukaz  
  
4.* Hradlova sit pro transitivni uzaver  
na vstup dostanu matici sousednosti, jako vystup vypadne matice dosazitelnosti  
  
uvedomil jsem si, ze matice sousednosti, je vlastne zobrazeni V->V vrcholu, do kterych je mozne se dostat cestou delky 0-1, takze kdyz tu matici vynasobim samu sebou, bude mi rikat do kterych vrcholu se dostanu po cestach delky 0-2. nejdelsi mozna cesta v grafu muze byt dlouha n vrcholu, takze musim tu matici umocnit na n-tou. to muzu udelat v log(n) nasobeni matic.  
navic ani nepotrebuju vedet jakou ten kterej prvek ma hodnotu, jenom jestli to je, nebo neni nule.  
proto ty matice budu nasobit v Z2  
a'_ij = OR (a_ik AND a_kj) , k od 1 do n.  
ty ANDy muzu pro celou matici pocitat najednou (konstatnni cas), ty ORy stromem. celkem tedy nasobeni stoji O(log(n)).  
celkova casova slozitost O(log^2(n))
<{/ForumPost}>