[Z] 2012-01-19

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.

[Z] 2012-01-19

Příspěvekod seby » 19. 1. 2012 11:37

Dnes byly opět příklady z cvičení, ovšem s bonusem:
1) TAUT
2) Složitost problému nalezení nejkratší cesty v grafu se zápornými hranami.
3) Navrhněte algoritmus pro nalezení minimálního VP pro les. DOKAŽTE SPRÁVNOST ALGORITMU.
seby
Matfyz(ák|ačka) level I
 
Příspěvky: 42
Registrován: 31. 1. 2008 15:40
Typ studia: Informatika Mgr.
Login do SIS: 25972507

Re: [Z] 2012-01-19

Příspěvekod srlok » 19. 1. 2012 19:31

Ten důkaz správnosti algoritmu si teda ze zadání nepamatuji a ani jsem ho tam nějak extra neměl a na zápočet to stačilo.
srlok
Matfyz(ák|ačka) level I
 
Příspěvky: 12
Registrován: 20. 6. 2010 14:46
Typ studia: Informatika Bc.

Re: [Z] 2012-01-19

Příspěvekod seby » 27. 1. 2012 12:45

V zadání to nebylo, ale říkal to ústně, ale asi na to teda podle tvých slov nehleděl.
seby
Matfyz(ák|ačka) level I
 
Příspěvky: 42
Registrován: 31. 1. 2008 15:40
Typ studia: Informatika Mgr.
Login do SIS: 25972507


Zpět na TIN062 Složitost I

Kdo je online

Uživatelé procházející toto fórum: Žádní registrovaní uživatelé a 1 návštěvník

cron