Stránka 1 z 1

12.1.2010

Napsal: 11. 1. 2011 15:37
od pasky
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!

Re: 12.1.2010

Napsal: 11. 1. 2011 15:39
od Him
Ja tam vidim jen jeden od 10:30 v S5.

Re: 12.1.2010

Napsal: 11. 1. 2011 16:57
od fox
Potvrzuji, v SISu je jenom jeden termin Slozitosti I vypsany na 12.1.2011 od 10:30 v S5

Re: 12.1.2010

Napsal: 11. 1. 2011 17:00
od pasky
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

Napsal: 12. 1. 2011 12:00
od pasky
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

Napsal: 12. 1. 2011 12:04
od pasky
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

Napsal: 12. 1. 2011 12:06
od Neznalek
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

Napsal: 12. 1. 2011 16:43
od JiriD
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.