Stránka 1 z 1

[Zk] 12.2.2009

Napsal: 12. 2. 2009 20:43
od Jakobicek
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.

Re: [Zk] 12.2.2009

Napsal: 12. 2. 2009 21:48
od Lado
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 :(

Re: [Zk] 12.2.2009

Napsal: 12. 2. 2009 21:52
od Jakobicek
č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:

Re: [Zk] 12.2.2009

Napsal: 12. 2. 2009 21:56
od Lado
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.

Re: [Zk] 12.2.2009

Napsal: 12. 2. 2009 22:38
od twoflower
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.