# Zkouška 22. 1. 2019 - Čepek

<{ForumPost(poster="I30T4", timestamp=2019-01-22 13:30:27)}>
1) sestavte automat AC pro hledání zadaných jehel  
2)Dokažte, že Batoh(věci, váhy, kapacita, cíl) je NP-úplný (použijte problémy probírané na přednášce)  
3)pomocí algoritmu na hledání maximálního toku (ten nepopisujte ani nevysvětlujte) najděte (hranovou) souvislost grafu v polynomiálním čase. Dokažte správnost a časovou složitost.
<{/ForumPost}>