12.1.2010

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: 12.1.2010

Re: 12.1.2010

od JiriD » 12. 1. 2011 16:43

Jenom co se týče zkoušky,
písemná část není nejjednodušší, pokud to chce člověk vymyslet na místě.
U 2SATu jsem napsal sice správný algoritmus, ale bez důkazu polynomiality - půl bodu.
MMNM jsem věděl - 1 bod.

U ústní jsem dostal ÚPAS pro Součet Podmnožiny. Stačilo napsat co je to AS, PAS, ÚPAS, relativní chyba - definice, zadání úlohy, napsat algoritmus a asi pět lemmat - pouze znění, pomocí kterých dokážeme korektnost algoritmu. Říkal, že důkazy nemusím, že se kdyžtak zeptá, kdyby ho to zajímalo. K důkazu stačilo potom jenom říct: to je technická analýza, tohle indukcí, tole rozborem případů atd. Asi viděl, že to umím a nechal mě s 1 jít.

Jinak co jsem slyšel z dalších zadání, tak padlo obvyklé: #P a NP a Test 2-souvislosti grafu + označení artikulací (upravené DFS)

Hodně štěstí u zkoušky.

Re: 12.1.2010

od Neznalek » 12. 1. 2011 12:06

Poznamka k TAUT nalezi? NP:
Kdyz jsem odevzdaval, ptal jsem se na to, a dokazovat, ze by to implikovalo NP=co-NP nebylo potreba. Mel jsem tam jen ze TAUT nalezi co-NP a proc a ze o NP nic nevime.

Re: 12.1.2010

od pasky » 12. 1. 2011 12:04

Mimochodem, studujici verejnost by mohlo potesit, ze Cepek rikal, ze zvazi navyseni kapacity vypsanych terminu a jeden pred 25.1. asi jeste prida. Take zminil, ze mozna po svem odjezdu pozada jeste o odzkouseni jednoho terminu Petra Kuceru a sam se vrati v cervnu, kdy budou zase jeste nejake dalsi terminy.

Re: 12.1.2010

od pasky » 12. 1. 2011 12:00

Zkouska - jen strucne, zkouseni jiste napisou podrobnosti:

* polynomialni algoritmus na 2-SAT
* nejvetsi nezavisla monochromaticka mnozina

Zapocet (jestli bylo vic zadani, tak to moje):

* oblibena TAUT - je v NP (sic) a jakou ma slozitost pro CNF?
* testovani polosouvislosti grafu - popsat algoritmus O(n+m)
* dokazat, ze 0-1 CP je NP-uplne

U TAUT mi bylo blbe psat "nevime jestli je v NP", tak jsem tam napsal o co-NP a na miste vydedukoval, ze jestli je v NP by mohlo zalezet na tom, jestli P=NP (na tom imho zalezi, jestli testovani certifikatu je v PTIME), doufam, ze to neni uplna blbost...

Re: 12.1.2010

od pasky » 11. 1. 2011 17:00

Jasne, diky - sorry za sum, uz jsem zjistil, ze to jde ze SISu vykutat dokonce i bez prihlaseni. No alespon sem muzeme psat zitrejsi zazitky. ;-)

Re: 12.1.2010

od fox » 11. 1. 2011 16:57

Potvrzuji, v SISu je jenom jeden termin Slozitosti I vypsany na 12.1.2011 od 10:30 v S5

Re: 12.1.2010

od Him » 11. 1. 2011 15:39

Ja tam vidim jen jeden od 10:30 v S5.

12.1.2010

od pasky » 11. 1. 2011 15:37

Ahoj! Asi diky podivne interakci ldap.cuni a ucitelskeho uctu se nemuzu dostat do SISu (a to jsem si po novem roce uz heslo menil), muzete mi prosim nekdo prozradit, jestli zitra budou opravdu _dva_ predterminy (10:30 a 14:00), jak jsem dostal mailem, a v jakych mistnostech se to bude konat? Diky!

Nahoru