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.
[Zk] 12.2.2009
-
- Matfyz(ák|ačka) level II
- Příspěvky: 53
- Registrován: 26. 1. 2006 12:42
- Typ studia: Informatika Bc.
- Bydliště: Praha... VSE/MATFYZ
[Zk] 12.2.2009
Minsk will lead with blade and sword Boo will sort out the details
Re: [Zk] 12.2.2009
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
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
-
- Matfyz(ák|ačka) level II
- Příspěvky: 53
- Registrován: 26. 1. 2006 12:42
- Typ studia: Informatika Bc.
- Bydliště: Praha... VSE/MATFYZ
Re: [Zk] 12.2.2009
č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á.
Minsk will lead with blade and sword Boo will sort out the details
Re: [Zk] 12.2.2009
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.
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.
- 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: [Zk] 12.2.2009
Jenom v Garey-Johnson jich mas pres 300 a to je knizka stara 30 let :-) Ted uz jich je znamych vic nez 10x tolik.Lado píše:aj ked, NP-uplnych prikladov asi nie je tak vela :)