navigation
hledat
Rozdíly
Zde můžete vidět rozdíly mezi vybranou verzí a aktuální verzí dané stránky.
|
courses:a4m01tal:zkouska-2015-06-04 [2015/06/09 22:49] velekmar |
courses:a4m01tal:zkouska-2015-06-04 [2025/01/03 18:28] (aktuální) |
||
|---|---|---|---|
| Řádek 1: | Řádek 1: | ||
| ===== Zkouška TAL 4. 6. 2015 ===== | ===== Zkouška TAL 4. 6. 2015 ===== | ||
| + | |||
| + | {{ :courses:a4m01tal:tal_15_6_4.jpg?200 |}} | ||
| {{:courses:a4m01tal:zktal04062015.pdf|}} - je tam vše, na co jsem si vzpomněl, kdo tam byl, tak třeba má ofocené zadání. Dřív jsem se k tomu bohužel nedostal | {{:courses:a4m01tal:zktal04062015.pdf|}} - je tam vše, na co jsem si vzpomněl, kdo tam byl, tak třeba má ofocené zadání. Dřív jsem se k tomu bohužel nedostal | ||
| Řádek 6: | Řádek 8: | ||
| Konkrétně např. otázka č. 4, zde platí, že co-NP je podmnožinou R, proto stačí vzít jakoukoliv NPC úlohu. Ta je v R a není v co-NP. Důležité je u těchto úloh si představit Velký knedlík jazyků. | Konkrétně např. otázka č. 4, zde platí, že co-NP je podmnožinou R, proto stačí vzít jakoukoliv NPC úlohu. Ta je v R a není v co-NP. Důležité je u těchto úloh si představit Velký knedlík jazyků. | ||
| - | ~~DISCUSSION~~ | + | Poznámka k příkladu 5), správnost algoritmu. V zadání bylo, zda algoritmus vrátí maximální počet hranově disjunktních cest z bodu u do bodu v. Uvedený algoritmus není správný. Problém je v řádku c., pokud existuje hrana. Jelikož není specifikováno, jaká cesta, může to být cesta o maximálním počtu hran. Viz uvedený obrázek z bodu 1 do bodu 4. Existují maximálně dvě hranově disjunktní cesty (1,3,4) a (1,2,4). Pokud jako první se vybere (1,2,3,4), algoritmus vrátí 1, což je špatně. |
| + | {{:courses:a4m01tal:grafik5.png|}} | ||
| + | |||
| + | ~~DISCUSSION~~ | ||
