Co bylo dnes na zkousce [15.1.2009]

Základní přednáška o teorii složitosti algoritmů. Zhruba první polovina přednášky je věnována studiu složitosti konkrétních algoritmů různých typů (grafové, rozděl a panuj, hladové na matroidech) pracujících v polynomiálním čase. Složitost je zkoumána jak "klasicky" (složitost v nejhorším případě), tak amortizovaně. Druhá polovina přednášky je pak věnována studiu třídy NP, polynomiální převoditelnosti problémů a důkazům NP-úplnosti problémů. Závěr přednášky je věnován tématům souvisejícím se studiem NP-úplnosti: pseudopolynomiálním algoritmům a silné NP-úplnosti, početním úlohám a třídě #P.
Manicka
Matfyz(ák|ačka) level I
Příspěvky: 26
Registrován: 28. 6. 2006 18:20

Co bylo dnes na zkousce [15.1.2009]

Příspěvek od Manicka »

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

Diky, Mana.
ondrisko

Re: Co bylo dnes na zkousce [15.1.2009]

Příspěvek od ondrisko »

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.
ondrisko

oprava

Příspěvek od ondrisko »

oprava v 1. príklade: a) dokážte správnosť, nie zložitosť
Uživatelský avatar
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]

Příspěvek od twoflower »

ondrisko píše:Ahoj, boli nové príklady, takže podraz.
Všechny tyhle příklady jsou z minulých let.
Odpovědět

Zpět na „TIN062 Složitost I“