[Zk] 6.2.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.
Uživatelský avatar
strevlik
Matfyz(ák|ačka) level I
Příspěvky: 49
Registrován: 7. 3. 2006 10:56
Typ studia: Informatika Bc.
Kontaktovat uživatele:

[Zk] 6.2.2009

Příspěvek od strevlik »

Pro vsechny poctare pravdepodobnosti pridavam informaci, ze v patek bylo zadani s profesorem Zweisteinem.
Ceberus
Matfyz(ák|ačka) level I
Příspěvky: 22
Registrován: 28. 10. 2007 23:37
Typ studia: Informatika Mgr.
Bydliště: Petřvald u N.J. / kolej 17.listopadu
Kontaktovat uživatele:

Re: [Zk] 6.2.2009

Příspěvek od Ceberus »

Zkouškové příklady - jak již asi víte - jsou ve studnici vědomostí. Já si je trochu upravil pro své pochopení a vměstnal na 2xA4, s čímž se pěkně zachází v tramvaji. 8) http://uloz.to/x2NYa1ow/mff-slozitost1-priklady-pdf (v tomtéž umístění i .odt verze)

A ještě dodám ústní: já měl matroidy, zaregistroval jsem ještě kachlíkování, převod SAT na kliku, #P a vztah k NP.
Odpovědět

Zpět na „TIN062 Složitost I“