Fórum studentů MFF UK

Cau,
mohl by sem nekdo napsat, co bylo dnes na zkousce? Neco stejneho jako v predchozich letech, nebo neco noveho?

Diky, Mana.

Ahoj, boli nové príklady, takže podraz.

1) Máme mince v hodnotách 1,2,5,10 Kč a sumu x. Navrhnite hladový algoritmus, ktorý z týchto mincí zloží sumu x z čo najmenšieho počtu mincí. a) Dokážte zložitosť Vami navrhnutého algoritmu. b) Nájdite protipríklad (nie nutne len s mincami v zadaní), na ktorom Vami navrhnutý algoritmus zlyhá.

2) Majme k dispozícii čiernu skrinku riešiacu rozhodovaciu verziu HK (hamiltonovská kružnica), tj. pre daný graf G a hodnotu k nám odpovie, či existuje HK dĺžky k v G. Navrhnite polynomiálny algoritmus, ktorý s pomocou čiernej skrinky nájde v grafe G HK minimálnej možnej dĺžky.

3) Majme problém 3R-SAT (splniteľnosť formulí v CNF, kde každá premenná sa vyskytuje najviac trikrát). Dokážte, že 3R-SAT je NP-úplný problém.

Dúfam, že som to nepoplietol. Časom môžem doplniť aj riešenia.

oprava v 1. príklade: a) dokážte správnosť, nie zložitosť

ondrisko píše:Ahoj, boli nové príklady, takže podraz.

Všechny tyhle příklady jsou z minulých let.