od Krakonoš » 26. 6. 2014 10:10
Zápočet 24.6. 2014: byl klasický, byly tam nějaké
, 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
přes orákula a dokázat, že
. 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
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 216 x
-
- vety-k-zapoctu.pdf
- Věty k zápočtu
- (121.34 KiB) Staženo 258 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 250 x
-
- ladner.pdf
- Ladnerova věta
- (100.52 KiB) Staženo 257 x
-
- TQBF-complete.pdf
- Materiál o QBF, určitě dá dobrý náhled
- (102.53 KiB) Staženo 255 x
[b]Zápočet 24.6. 2014[/b]: byl klasický, byly tam nějaké [latex]\log_3[/latex], 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ášť!).
[b]Zkouška 26.6. 2014[/b]: 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 [latex]PH[/latex] přes orákula a dokázat, že [latex]PH \subseteq PSPACE[/latex]. 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 [latex]\exists C[/latex] si psát do rámečků :-)
[b]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).[/b]