[Zk] 12.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.

[Zk] 12.2.2009

Příspěvekod Jakobicek » 12. 2. 2009 20:43

Zadaní písemné části standardní
1)Ukázat, že lze nalézt pomocí DFS zadané topologické uspořádání
2)Ukázat, že v binárním stromu existuje hrana po jejímž oddělení zbydou dvě komponenty každá s max (2n+1/3) vrcholy
3)Zednický metr

Ústní je trochu loterie. Já dostal odvodit složitost u UPAS pro SM. Základem bylo napsat algoritmus -zde jsem proškrtával z druhé strany než je ve skritpech, což čepkovi v podstatě nevadilo /asi to možná i funguje/ a říci, že v nejhorším případě je ten proškrtaný seznam geometrická posloupnost - v okamžiku, kdy si todle pamatujete je ten zbytek důkazu relativně snadný a dá se odvodit metodou "doplňování obrázku" ... Dva další kolegové dostali neexistenci UPAS pro TSP a aproximační algo pro TSP s trojúhelníkovou nerovností. Poslední dostal #P. Jenom snad poznamenám, že čepek stačil vyzkoušet tři lidi zatímco vedle zkoušející kučera studenty zkoušel o poznání důkladněji.
Minsk will lead with blade and sword Boo will sort out the details
Jakobicek
Matfyz(ák|ačka) level II
 
Příspěvky: 53
Registrován: 26. 1. 2006 12:42
Bydliště: Praha... VSE/MATFYZ

Re: [Zk] 12.2.2009

Příspěvekod Lado » 12. 2. 2009 21:48

Tiez som bol na danej skuske. Za hodinu a pol som stihol aj zapocet aj skusku - ked som videl tie priklady, tak som velebil Cepka za to, ze nenasiel forum ( resp. nezmenil tie priklady ) :) Pokial si clovek precita priklady na fore + trochu porozmysla, tak na pisomnej skuske nema co robit. V podstate trivialna vec. Vacsina ludi ma potom 3 body z troch za pisomnu cast. Co sa tyka ustnej, tak ja som mal kolegu Kuceru a musim povedat, je to tazky rypal. Dostal som ulohu dokazat, ze KACHL je NP-uplny. Tak som zacal tradicny dokaz... On hned z ostra, ze nikde nemam definovane, co je NP-uplnost. Potom chcel vediet, co je NP, z tadial sa dostal na Turingove stroje ( DTS aj NTS ). Takze vyzadoval vsetko a dost podrobne. Hocijaka malickost a hned sa do nej obul. Inak, NP uplnost som mal definovanu, len on sa akosi nediva poriadne na papier - aj kachliky chcel obkecat, preco su take druhy ako su a comu zodpovedaju, hoci som to mal napisane na papieri. Nakoniec som ho ale zdolal a s tazkych povzdychom povedal: "Dajte index." To mi bohato stacilo a rychlo som utekal za Cepkom po zapocet.
Celkovo je Kucera rypal, dobra rada je nenechat sa zatlacit do kuta, ale opatovat mu to, ze to tam mate, popripade, ze ste nic podobne nepovedali ( ak to je pravda ). Neberie si to osobne, skor sportovo :)

Vela zdaru ostatnym a najma tomu nestastnikovi vedla mna, co po tretikrat nedal zapocet :(
Lado
Matfyz(ák|ačka) level I
 
Příspěvky: 16
Registrován: 29. 1. 2007 11:42

Re: [Zk] 12.2.2009

Příspěvekod Jakobicek » 12. 2. 2009 21:52

čepkovi je zcela jasné, že koluje řešení příkladů.... říkal písemku máte všichni za 3 body, tak to asi byla nějaká jednoduchá. :wink:
Minsk will lead with blade and sword Boo will sort out the details
Jakobicek
Matfyz(ák|ačka) level II
 
Příspěvky: 53
Registrován: 26. 1. 2006 12:42
Bydliště: Praha... VSE/MATFYZ

Re: [Zk] 12.2.2009

Příspěvekod Lado » 12. 2. 2009 21:56

V tom pripade je zaujimave, ze to nezmeni - aj ked, NP-uplnych prikladov asi nie je tak vela :)
Otazne je, ci to splni to, co chce - ze to ludia aj chapu, lebo inak to nema zmysel a moze byt rovno ustna a usetri to cas aj jemu, aj nam.
Lado
Matfyz(ák|ačka) level I
 
Příspěvky: 16
Registrován: 29. 1. 2007 11:42

Re: [Zk] 12.2.2009

Příspěvekod twoflower » 12. 2. 2009 22:38

Lado píše:aj ked, NP-uplnych prikladov asi nie je tak vela :)


Jenom v Garey-Johnson jich mas pres 300 a to je knizka stara 30 let :-) Ted uz jich je znamych vic nez 10x tolik.
Uživatelský avatar
twoflower
Supermatfyz(ák|ačka)
 
Příspěvky: 445
Registrován: 22. 9. 2004 20:07
Typ studia: Informatika Ph.D.


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