12.1.2010

Základní přednáška o teorii složitosti algoritmů. Zhruba první polovina přednášky je věnována studiu složitosti konkrétních algoritmů různých typů (grafové, rozděl a panuj, hladové na matroidech) pracujících v polynomiálním čase. Složitost je zkoumána jak "klasicky" (složitost v nejhorším případě), tak amortizovaně. Druhá polovina přednášky je pak věnována studiu třídy NP, polynomiální převoditelnosti problémů a důkazům NP-úplnosti problémů. Závěr přednášky je věnován tématům souvisejícím se studiem NP-úplnosti: pseudopolynomiálním algoritmům a silné NP-úplnosti, početním úlohám a třídě #P.
pasky
Matfyz(ák|ačka) level II
Příspěvky: 89
Registrován: 4. 1. 2005 22:57
Typ studia: Informatika Bc.
Kontaktovat uživatele:

12.1.2010

Příspěvek 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!
Next lecture on time travel will be held on previous Monday.
Him
Supermatfyz(ák|ačka)
Příspěvky: 400
Registrován: 25. 1. 2008 19:59
Typ studia: Informatika Bc.

Re: 12.1.2010

Příspěvek od Him »

Ja tam vidim jen jeden od 10:30 v S5.
Pracoval jsem na poměrně hodně materiálech pro různé předměty. Pokud Ti něco z toho ušetřilo čas, vyjádři svůj dík v podobě pár satoshi: 1H5JPTrsXie7epAQXbXhMjdgwyLbJ5NHBW ;)
fox
Matfyz(ák|ačka) level I
Příspěvky: 5
Registrován: 6. 1. 2011 19:55
Typ studia: Informatika Mgr.

Re: 12.1.2010

Příspěvek od fox »

Potvrzuji, v SISu je jenom jeden termin Slozitosti I vypsany na 12.1.2011 od 10:30 v S5
pasky
Matfyz(ák|ačka) level II
Příspěvky: 89
Registrován: 4. 1. 2005 22:57
Typ studia: Informatika Bc.
Kontaktovat uživatele:

Re: 12.1.2010

Příspěvek 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. ;-)
Next lecture on time travel will be held on previous Monday.
pasky
Matfyz(ák|ačka) level II
Příspěvky: 89
Registrován: 4. 1. 2005 22:57
Typ studia: Informatika Bc.
Kontaktovat uživatele:

Re: 12.1.2010

Příspěvek 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...
Next lecture on time travel will be held on previous Monday.
pasky
Matfyz(ák|ačka) level II
Příspěvky: 89
Registrován: 4. 1. 2005 22:57
Typ studia: Informatika Bc.
Kontaktovat uživatele:

Re: 12.1.2010

Příspěvek 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.
Next lecture on time travel will be held on previous Monday.
Uživatelský avatar
Neznalek
Matfyz(ák|ačka) level I
Příspěvky: 15
Registrován: 29. 1. 2008 21:14
Typ studia: Informatika Bc.
Kontaktovat uživatele:

Re: 12.1.2010

Příspěvek 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.
JiriD
Matfyz(ák|ačka) level I
Příspěvky: 44
Registrován: 2. 2. 2008 09:35
Typ studia: Informatika Bc.

Re: 12.1.2010

Příspěvek 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.
Wenn ich morgen meinem Gott gegenüberstehe, kann ich sagen:
Ich bin unschuldig,
ich habe niemanden betrogen,
ich habe niemandem weh getan,
ausser mir selbst.

Und das wird er mir wohl verzeihen!
Odpovědět

Zpět na „TIN062 Složitost I“