Cau,
mohl by sem nekdo napsat, co bylo dnes na zkousce? Neco stejneho jako v predchozich letech, nebo neco noveho?
Diky, Mana.
Co bylo dnes na zkousce [15.1.2009]
Re: Co bylo dnes na zkousce [15.1.2009]
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.
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.
- twoflower
- Supermatfyz(ák|ačka)
- Příspěvky: 445
- Registrován: 22. 9. 2004 21:07
- Typ studia: Informatika Ph.D.
- Kontaktovat uživatele:
Re: Co bylo dnes na zkousce [15.1.2009]
Všechny tyhle příklady jsou z minulých let.ondrisko píše:Ahoj, boli nové príklady, takže podraz.