Složitost II

Uživatelský avatar
Davpe
Matfyz(ák|ačka) level II
Příspěvky: 98
Registrován: 22. 9. 2010 16:07
Typ studia: Informatika Bc.
Kontaktovat uživatele:

24.06.2014

Příspěvek od Davpe »

Písemka stejná jako příspěvek přede mnou. Doporučuju si pořádně přečíst zdůvodnění k bodu 3: poslední inkluze ve zdůvodnění je neostrá, měl jsem ji jako ostrou a hned to vygeneruje 4 chyby (a přišlo mi, že to byla častá chyba). Každopádně Čepek počítal stejné chyby jako jednu chybu takže zápočet dostali i ti se 4 chybami (tolerovány jsou normálně 3).

(Zdůvodnění proč nemůže být inkluze ostrá je jako kdybych měl otevřený interval (0, e) kde e <1 a (0,e) < (0,1) (tady je ostrá pro každé e). Ale nekonečné sjednocení těchto intervalů U (0,e) <= (0,1) už může být i interval (0,1). A v tom zdůvodnění se sjednocuje přes všechny ty konstanty. Tak nějak to vysvětloval Čepek, snad jsem to nezkazil).

A jako důsledek písemky jsem dostal větu o vztazích, část b. Tady v důkazu pozor, že hrany v tom grafu jsou ohodnoceny vstupními symboly aby se poznalo kdy ten stroj má přijímat (ptal se kdy ten DTS který vyrobím bude přijímat). Jinak zkoušení mírné, myšlenka důkazu mu stačila i když jsem tam měl často špatné výpočty a někde blbosti. Výsledek za 2.

A slyšel jsem otázku QBF je PSPACE úplný (ale tuším že to byla druhá otázka - záchranná).
Control
Matfyz(ák|ačka) level I
Příspěvky: 3
Registrován: 27. 8. 2009 13:07
Typ studia: Informatika Bc.

Re: Složitost II

Příspěvek od Control »

Prijde mi, ze Slozitost II forum i wiki jsou na slozitostni zkousky ponekud skoupe, pojdme to vylepsit.

[24.6.2014] Pisemka pro ziskani zapoctu mela stejny prubeh jako drive.
- zadano 5 slozitostnich trid
- pro vsech 10 dvojic ukazat, zda existuje inkluze a pokud existuje, zda je ostra

Pozor! Odpoved muze byt, ze pro danou dvojici nemame patricny aparat, kterym muzeme vztah dokazat.
Napr. na obrazcich pisemek zde na foru jsou vztahy takovych trid oznaceny otazniky.
Vetsinou jsou v pisemce tak 3 z 10 takove, o kterych neumime rozhodnout.
Skutecne tam staci dat otaznik.

Bacha! Nesnazte se dokazat, ze inkluze neplati. Vetsinou ten vztah plati, ale patricny aparat se neprednasi.
Dnesni pisemka [nadepsana cislo 4] byla skutecne stejna jako ta druha zde na foru.

Na cvicenich se loni delaly tyto tridy:
DTIME(2^{n^2}), DSPACE(n^2),DSPACE(n\log(n)),NTIME(n\log(n)),NSPACE(\sqrt(n)\log(n))

1. DSPACE (n \log(n)) ve vztahu k: DSPACE(n^2)
2. DSPACE (n \log(n)) ve vztahu k: DTIME(2^{n^2})
3. DSPACE (n \log(n)) ve vztahu k: NSPACE(\sqrt(n)\log(n))
4. DSPACE (n \log(n)) ve vztahu k: NTIME(n\log(n))
5. DSPACE(n^2) ve vztahu k: DTIME(2^{n^2})
6. DSPACE(n^2) ve vztahu k: NSPACE(\sqrt(n)\log(n))
7. DSPACE(n^2) ve vztahu k: NTIME(n\log(n))
8. DTIME(2^{n^2}) ve vztahu k: NSPACE(\sqrt(n)\log(n))
9. DTIME(2^{n^2}) ve vztahu k: NTIME(n\log(n))
10.NSPACE(\sqrt(n)\log(n)) ve vztahu k: NTIME(n\log(n))

A jako bonus jedno odposlechnute zkouskove zadani: Dokazte mi, ze se cela polynomialni hierarchie vleze do PSPACE.
[btw. hezky obrazek PH je na Wiki http://en.wikipedia.org/wiki/Polynomial_hierarchy ]

Spravne odpovedi: \subsetneqq, \subsetneqq, ? , \supseteq, ?, \supsetneqq,  \supsetneqq, \supsetneqq, \supsetneqq, ?
[Otaznik znaci: nedovedeme rozhodnout].

Pozorovani:
Ve 3 pripadech ze 3 [co jsou na foru] melo zadani tvaru:
[N|D]SPACE(vyraz) se tridou DTIME(2^vyraz), odpoved "?" [tj. nedovedeme rozhodnout]
Krakonoš
Matfyz(ák|ačka) level I
Příspěvky: 14
Registrován: 29. 1. 2009 11:31
Typ studia: Informatika Mgr.

Re: Složitost II

Příspěvek od Krakonoš »

Zápočet 24.6. 2014: byl klasický, byly tam nějaké \log_3, ale nic, čím bychom se měli nechat zastrašit. Písemka byla stejná, jako druhá z ofocených, které jsou na předchozí stránce. Myslím, že nikdo neměl výraznější problémy, Čepek nepopotahoval za drobné chyby a bral to rozumě. Pozor ale na korektní použití věty o Vztazích, pár lidem vytknul, že ji používají špatně (musí se zrychlovat/odhadovat každý jazyk zvlášť!).



Zkouška 26.6. 2014: Dorazili jsme na 8:30 a zápočet měli zapsaný, Čepek rozdal písemky a pak nám pověděl témata. Někomu co neuměl na písemce, někomu něco jiného, jak kdy. Já jsem dostal zadefinovat PH přes orákula a dokázat, že PH \subseteq PSPACE. Tak jsem zadefinoval, trošku neformálně, včetně důkazu. Na pár formalit se mě zeptal (jak je definované to odvozování tříd a proč lze nahradit tázání orákula za orákulum -- protože tázací páska se počítá do složitosti), a dal mi jedničku (ačkoliv jsem měl zápočet "s odřenýma ušima").

Dále jsem slyšel: deterministickou hierarchii (myslím, že časovou), QBF je PSPACE-úplný a Borodinovo větu (!). Jako doplňující otázka padaly části věty o vztazích.

Co se týče učení na zkoušku, tak to hodnotné a těžké jsou: věty o hierarchii (princip je velmi podobný u deterministických, nedeterministická jede přes translační lemma!), borodinovu větu (není zas tak těžká, když použijete lemmata), hierarchie (je tam spoustu vztahů, které se dají snadno odvodit, ale je potřeba tomu rozumět. Nemyslím si, že je potřeba si pamatovat větu, která se skládá z částí 1-10), QBF (skoro jako Savič, materiál v příloze), Ladnerovu větu (idea jednoduchá, je potřeba trošku pokroutit závity, aby jste se dostali do dostatečné úrovně negací :-), materiál v příloze). Navíc by to chtělo rozumět alternujícím kvantifikátorům; tady nemám všelék, mě osobně se osvědčilo si to hezky napsat a třídy \exists C si psát do rámečků :-)

V příloze je malý arch se zněním vět, které jsou potřeba na zápočet (snad to jsou všechny). A pár dalších materiálů, ze kterých jsme se učili ty pokročilejší věci (není moje dílo, ale raději ho uploaduju, aby bylo na věky).
Přílohy
vety-k-zapoctu.tex
Věty k zápočtu (zdroják)
(4.23 KiB) Staženo 213 x
vety-k-zapoctu.pdf
Věty k zápočtu
(121.34 KiB) Staženo 255 x
ph.pdf
Trošku jiný pohled na polynomiální hierarchii podle alternujících kvantifikátorů (spíš pohled, určitě nepokrývá látku!)
(108.86 KiB) Staženo 246 x
ladner.pdf
Ladnerova věta
(100.52 KiB) Staženo 252 x
TQBF-complete.pdf
Materiál o QBF, určitě dá dobrý náhled
(102.53 KiB) Staženo 252 x
Jurášek

Re: Složitost II

Příspěvek od Jurášek »

Otázky o5 klasické:
Hlavní: Immerman.
Slyšel jsem: všemožné hierarchie, Borodin, Ladner.

Doplňující:
Příklad PSPACE-úplného problém.
Co by se stalo kdyby byl PSPACE-úplný problém v Pi_k
Jak zní Boromirova věta ;-)

Poznámka: Existuje triviální PSPACE-úplný problém - ať se nemusíte brblat s QSATem:
Vstup:
1) Program P
2) Vstup programu x
3) Délka paměti kterou má program P k dispozici na spočítání P(x) napsaná v unární soustavě.
Výstup:
P(x) nebo "došla paměť".

(Ve stejném stylu existují triviální NP-úplný, a další X-úplné problémy)
Odpovědět

Zpět na „I1 Ostatní Teoretická informatika“