od ondrisko » 15. 1. 2009 23:15
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.
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.