[Zk] 5.2.2009

Odeslat odpověď

Smajlíci
:D :) :( :o :shock: :? 8) :lol: :x :P :oops: :cry: :evil: :twisted: :roll: :wink: :!: :?: :idea: :arrow: :| :mrgreen:

BBCode je zapnutý
[img] je zapnutý
[flash] je vypnutý
[url] je zapnuté
Smajlíci jsou zapnutí

Přehled tématu
   

Rozšířit náhled Přehled tématu: [Zk] 5.2.2009

Zkoušení

od happy » 13. 2. 2010 00:02

Doc. Čepek dává tento rok (2009/10) na zkoušce dva příklady. Pro
připuštění ke zkoušce je potřeba mít aspoň jeden (případné
nesrovnalosti se doťuknou před zkouškou, ale není to časté). Jeden
příklad špatně znamená snížení o stupeň (tj. v úvahu pak připadá rozsah
známek 2-4 :))

Na ústní mu záleží na důkazech, třeba větu o separátoru bez jejího
důkazu nepovažuje za zodpovězenou. (Člověka se pak zeptá jinou otázku.)
Např. u matroidů ho zajímá algoritmus pro hledání optimální množiny,
nebo spíš jeho správnost (konkrétně - pokud ji chce člověk dokazovat
indukcí - ten indukční krok, viz "Lemma 3: existence optimální
podstruktury"). Ale i napsaný algoritmus a definice považuje za "něco".
Po případné třetí otázce se ukáže, jestli to je bod dolů, nebo dva.

Ještě přidám jeden názor (diskutovalo se to ve starším vlákně): Můj
postoj k používání zaběhaných příkladů je kladný. Když se pak má člověk
učit teorii, napadají ho konkrétní příklady a protipříklady k té
teorii. Zápočet a písemná zkouška se dá udělat naučením dobře známých
příkladů, ale mně to dává smysl. Doc. Čepek je schopný pedagog a ví, co
dělá. (I když ten zápočet je pro něj možná jen filtr - aby zbytečně
nezkoušel někoho, kdo neumí převést ani jeden problém na jiný problém
- bez toho zkoušku opravdu nikomu nedá.)

Re: [Zk] 5.2.2009

od Blaf » 5. 2. 2010 16:31

Ahoj, jenom doplnim, ze se me zeptal na definici #P-uplnosti a priklad #P-uplneho problemu, jehoz rozhodovaci verze je jednoduse resitelna (perfektni parovani). Napsal jsem mu i definici transformacnich funkci a souvislost NP a #P. Byl spokojenej, dal mi jednicku :) Byla to prijemna zkouska.
Zaslechl jsem jeste zadani Veta o planarnim separatoru.

[Zk] 5.2.2009

od Boris » 5. 2. 2010 15:11

Dnes jsem úspěšně (JUCHŮŮŮŮŮ!!!!) zdolal zkoušku ze složitosti.

Otázky na písemku: 2R-SAT s co nejlepší složitostí (šlo lineárně vzhledem k počtu proměnných), dále SALBL \in co-NP úplné (převod ze SATu)
Ústní: Já měl Savičovu větu, zaslechl jsem ještě Cook Levina a SP pomocí VP.
K té savičově větě se ještě ptal, k čemu jsou potřeba ty předpoklady, což jsem přesně nevěděl. Takže tedy pro ostatní: Prostorová konstruovatelnost S(n) je potřeba na to, aby se všechny konfigurace daly procházet foreachem (kdybych nevěděl, že je to prostorově konstruovatelný, nevěděl bych, kolik prostoru to zabere aa tudíž bych si to pak nemoh hodit do nějakýho seznamu, kterej budu tim foreachem procházet). S(n) >= log(n) musí být proto, že by 2^dS(n) jinak mohlo být < n, tedy menší než zadání - což je nejmenší možná velikost konfigurací.


Dohromady sem řešil jen 3 otázky (2písemná + 1 ústní) => znamená to, že se složitost zkoušky ze složitosti snižuje?
(Pravda, měl jsem všechno +- dobře (=> 1 :D ), tak mi nedával žádný doplňující dotazy)

Jak dopadli ostatní?

Nahoru