Zkouška 22. 1. 2019 - Čepek

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