Fórum studentů MFF UK

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)

[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]

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

[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

[b]Pozor! Odpoved muze byt, ze pro danou dvojici nemame patricny aparat, kterym muzeme vztah dokazat.[/b]
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! [b]Nesnazte se dokazat, ze inkluze neplati.[/b] 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:
[latex]DTIME(2^{n^2}), DSPACE(n^2),DSPACE(n\log(n)),NTIME(n\log(n)),NSPACE(\sqrt(n)\log(n))[/latex]

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

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

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

Pozorovani:
Ve 3 pripadech ze 3 [co jsou na foru] melo zadani tvaru:
[b][N|D]SPACE(vyraz)[/b] se tridou [b]DTIME(2^vyraz)[/b], odpoved "?" [tj. nedovedeme rozhodnout]

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á).

Tak ja uz to mam konecne taky uspesne za sebou. Mas pravdu, ze ty chybejici dukazy se daji najit v naskenovanych poznamkach, a diky bohu za to, protoze jsem dostal opet dukaz PH <= PSPACE, na kterym jsem den predtim vyletel, ovsem tentokrat jsem byl pripraven => 1 :D Jako doplnujici otazku jsem jeste dostal dukaz, ze NTIME <= DSPACE - uz jen v rychlosti nacrtnout. Cepek zrejme s oblibou dava stejnou otazku, ktera vas zabila u predchoziho terminu (pokud si zapamatuje vas ksicht), kolegovi vedle udelal totez s alternujicimi kvnatifikatory.

Jinak nejbeznejsi otazky co jsem zaslechl - tyhle tam tocil neustale na vsech 3 terminech co jsem byl (ale nejen ty):
- nedet. pros. hierarchie
- veta o vztazich (verze NTIME <= DSPACE a verze exponencialni strceni NSPACE do DTIME)
- translacni lemma
- definice PH pomoci orakul a PH <= PSAPCE
- definice PH pomoci alt. kvant. + nejaky dukaz ale nevim ceho

Co se tyce pisemky: kdyz se clovek nauci princip, ktery neni tezky, tak uz je to brnkacka. Staci umet Vety o hierarchii a o vztazich a Savicovu vetu. (ktere stejne musite umet na ustni :) )

Pokud by mel nekdo zajem tak prihazuju skeny 2 mych vstupnich testu, je tam jen jedna drobna chyba, jinak jsou ok. Zajimave je mozna to, ze proslo ze NSPACE(n) je neostra podmnozina NSPACE(n log n), coz se resilo na zacatku tohoto vlakna.

Třídy složitosti byly v pohodě. Jen je dobré nezapomenout (jako já), že jde používat i "jednoduché" věty (lineární zrychlení).

Větší část otázky byla Borodinova věta - lemmata stačilo zformulovat. Pak následovaly definice prostorové konstruovatelnosti & vyčíslitelnosti v lineárním čase a idea důkazu ekvivalence.

Obecně mi styl zkoušení přišel "hodný, pokud do toho člověk trochu vidí" - tj. pokud jsem se třeba přeřekl (že jsem řekl lineární zrychlení místo lineární prostorové komprese atd.), nic se nedělo. Ale jinak pan Čepek docela důkaz zkoumá, není to styl Pultr/Kučera, u kterých vcelku stačí na papír +- načmárat ideu.

Jinak se asi docela potvrzuje ten algoritmus na zisk otázky na nějakou hierarchii :)

Ahoj, pridavam svuj minireport ze zkousky. Tridy slozitosti si nepamatuju, akorat jedna mi uvizla v hlave. Bylo to neco jako DSPACE(n) a DTIME(2^(n*log n)). Pres Vetu o vztazich jsem jednoduse odvodil neostrou nerovnost, ale da se i ostra! A to tak, ze ten DS(n) ostre vlozite treba do DS(n * loglog n).

Moje otazka byla veta o determ. cas. hierarchii. Dukaz zkoumal docela dukladne, takze urcite nestaci jenom povrchni znalost (teda, asi staci na 2 nebo 3, ale ne na 1 :) ). A jako doplnek se me zeptal na zneni Ladnerovy vety (tj. mam pocit snad uplne posledni prednaska).

Neni treba se Cepka bat, je hodnej (ale ferovej :) ).

[quote="Kubees"]Nevite o nejakem zdroji, ze kterho by se daly naucit ty vety a dukazy, ktere chybi ve Strojilovi?[/quote]

Treba Veta o vztazich je na wiki.matfyz.info . Def. PH pres alt. kvant. je v nejakych poznamkach na Studnici. Myslim, ze to pujde +- vsechno poskladat.

Ale mas pravdu, asi neni dostupne nic, kde by to bylo komplet pohromade. Nahral jsem teda do Studince (zatim v INCOMING/Slozitost II/poznamky/peci1) svoje 4strankove vypisky. Je tam uplne vsechno, jen to mozna neni obcas moc k precteni, nemam zrovna vystavni pismo =)

Nevite o nejakem zdroji, ze kterho by se daly naucit ty vety a dukazy, ktere chybi ve Strojilovi?

Konkretne mam na mysli definice PH Pomoci orakul/alternujicich kvantifikatoru + vztahy okolo, ta veta ze existuje NP problem ktery neni P ani NP-uplny, vztah NTIME <= DSPACE, a mozna jeste nejake dalsi....

Ono je totiz docela blbe, kdyz se clovek krasne nauci dukazy ze Strojila a pak vyleti na dukazu ktery tam chybi :D (uz 2x)

[quote="Andreas"]Když nebudu líný, tak ještě přidám naskenované poznámky, aby to bylo trochu k něčemu.
http://www.uloz.to/xSkbVmD/slozitostii-rar[/quote]

to by som bol povdacny, a mozno aj ostatni, co to este nedali...
dik za tie nahravky. :-)

Zřejmě poslední moje zkouška na MFF :) Písemku jsem měl napsanou z minulého termínu, kde jsem nešel na ústní, a měl jsem asi mínus 1,5 bodu. Dneska jsem dostal PH definovat pomocí alt. kvantifikátorů a k tomu napsat nějaké vztahy. Tohle jsem při učení nejak vypustil, takže jsem měl temno. Dostal jsem tedy náhradní otázku, která se mi naopak dost líbila. Nedeterministická prostor. hierarchie pro polynomy. U důkazu jsem neměl zdůvodněné ty zřetězené inkluze(proč platí), tak mě to nechal dopsat a pak jsem odešel s trojkou(vzhledem k né úplně super písemce a té PH), což mi prostě stačilo. Kolega, který byl se mnou a taky měl písemku z minula, dostal PH definovat pomocí orákulových strojů a k tomu vztah PH a PSPACE. Uměl to na 1-2 a dostal nabídku znovu si napsat písemku, aby mohl dostat jedničku. Nabídku přijal, ale jak dopadl už nevím.
GL všem, které to ještě čeká.

Zde je pár přednášek a mezi nimi jedno cvičení nahrané na diktafon. Když nebudu líný, tak ještě přidám naskenované poznámky, aby to bylo trochu k něčemu.
http://www.uloz.to/xSkbVmD/slozitostii-rar

[quote="Kubees"]A jeste jedna otazka: Existuje nejaky seznam casto kladenych teoretickych otazek? Proc tady na foru do haje nic neni?! :D Lidi nebudte lini a napiste sem na co se vas ptal, diky. :)[/quote]

Nejspíš všechny věty u kterých neříkal, že je nezkouší... tipnul bych si, že bude preferovat věty ze slajdů 12-14 (ono většina jiných slajdů jsou definice :-), ale neručím za to...
Já dostal VoDPH... na to že jsem se na zkoušku učil půl noci a tenhle důkaz se vůbec neučil a jen ho prolétl abych alespoň trochu tušil, takže jsem téměř celý důkaz vymýšlel, to dopadlo velice dobře (1)... Když člověku něco chybí, ale většinu už má, tak to s ním projde, nechá doplnit chybějící... pokud člověk doplní něco špatně a není to hned potřeba, tak jde dál a nechá člověku čas si uvědomit, že vlastně řekl blbost a opravit to, nepočítá to rovnou jako mínus... občas i něco poradí.
Akorát je dobré odevzdávat tu zápočtovou písemku mezi prvními - bral cca. po třech (tři jsme šli hned a tři měli přijít odhadem za hodinu, hodinu a půl).

Diky. :wink:

A jeste jedna otazka: Existuje nejaky seznam casto kladenych teoretickych otazek? Proc tady na foru do haje nic neni?! :D Lidi nebudte lini a napiste sem na co se vas ptal, diky. :)

[quote="Kubees"]Ahoj, kdo jste uz bylli letos na slozitosti II - chapu to spravne, ze zapocet a zkouska se dela najednou? Z Cepkovo stranky to na me pusobi, jako by se delalo kazde zvlast, stejne jako u slozitosti I.[/quote]

Ahoj, na zkousce jsem jeste nebyl, ale presne na tohle jsem se ho ptal na posledni prednasce. Rikal, ze to na webu opravi. Situace je opravdu takova, ze prakticka i teoreticka cast je najednou (postupne, samozrejme :) ).

Ahoj, kdo jste uz bylli letos na slozitosti II - chapu to spravne, ze zapocet a zkouska se dela najednou? Z Cepkovo stranky to na me pusobi, jako by se delalo kazde zvlast, stejne jako u slozitosti I.