Zkouška - 11.12.2019 Hubička - Fórum studentů MFF UK

Zkouška - 11.12.2019 Hubička

3 příspěvky • Stránka 1 z 1

spidoosho: Matfyz(ák|ačka) level I; Příspěvky: 20; Registrován: 27. 5. 2019 19:36; Typ studia: Informatika Bc.

Zkouška - 11.12.2019 Hubička

Příspěvek od spidoosho » 15. 12. 2019 16:10

1. Popsat algoritmus KMP, určit jeho složitost a ukázat jeho korektnost. [10 bodů]

2. V grafu najděte všechny vrcholově disjunktní cesty mezi danými dvěma vrcholy. [5 bodů]

3. Vytvořte co nejmělčí hradlovou síť, která vypočítá dvojkový logaritmus vstupního čísla (tedy vrátí pozici nejlevější jedničky). [5 bodů]

(BONUS) 4. Dokažte, že EXACTLY-3,3-SAT nenÍ NP-uplný. (průvodce 454/6)