Složitost II

schaschek
Matfyz(ák|ačka) level I
Příspěvky: 34
Registrován: 13. 6. 2006 17:33

Složitost II

Příspěvek od schaschek »

Ahoj!
Nenašel by se tady náhodou někdo, kdo chodil na přednášky a byl by ochotnej naskenovat nebo nafotit svoje poznámky z 30. dubna? Bohužel jsem tehdy vynechal a tyhle důkazy už ve Strojilovi chybí. Jedná se přibližně o slajdy 32-35. Případně kdyby někdo měl zájem, můžu do studnice hodit i některý svoje poznámky.
Díky
Borek

Re: Složitost II

Příspěvek od Borek »

Cau!

Bohuzel jsem na prednasky nechodil, ucim se taky z materialu ze studnice. Myslim, ze je to celkem kompatibilni s letoskem krome toho konce, takze bych taky rad uvital nejake poznamky z 23. a 30. dubna... Kdyby se nekdo nasel, hodte to prosim do studnice, diky.

Zacal jsem se koukat na ty zkouskove priklady z wiki a modreho a narazil jsem na par problemu...
napr.

Kód: Vybrat vše

NSPACE(n)   vs.   NSPACE(log(n) * n)
ve vysledcich sem nasel jednou ostrou a podruhe neostrou podmnozinu, ale dokazene to nebylo nikde. Neostra podmnozina je jednoducha, viz trivialni vztahy pro NSPACE. Ale ostrou nevim jak dokazat (? pouzit nejak vetu o neterministicke hierarchii?), tak kdyby nekdo vedel poradit, tak bych byl vdecny ;)
Uživatelský avatar
langosh
Matfyz(ák|ačka) level II
Příspěvky: 96
Registrován: 28. 1. 2006 13:20
Typ studia: Informatika Mgr.
Bydliště: Bohnice
Kontaktovat uživatele:

Re: Složitost II

Příspěvek od langosh »

Zápisky z těch dvou přednášek jsem dal sem,
moje poznámky to nejsou, tak nevím jestli tam je vše co se na těch dvou přednáškách dělalo.
schaschek
Matfyz(ák|ačka) level I
Příspěvky: 34
Registrován: 13. 6. 2006 17:33

Re: Složitost II

Příspěvek od schaschek »

Díky moc. Já jsem do studnice přidal zápisky ze všech přednášek, který se ještě zkouší a už je nejde najít ve Strojilovi (kromě té z 30. dubna). Kdyby se někomu chtělo a doplnil by ji tam, bylo by to super. Za ty poznámky, co sem přidal langosh, jsem sice rád, ale přece jenom nejsou na některejch místech úplně čitelný :)
gejza
Matfyz(ák|ačka) level I
Příspěvky: 7
Registrován: 1. 2. 2006 21:31

Re: Složitost II

Příspěvek od gejza »

Borek píše:...problemu...

Kód: Vybrat vše

NSPACE(n)   vs.   NSPACE(log(n) * n)
Ako sam pises, neostra inkluzia je trivialna. Co sa tyka ostrej, tak sa podla mna jedna presne o dosledok Translacneho lemmatu (na Kucerovych slajdoch je to slajd 27) - je to tam sice s DTIME, ale vid. poznamka o slajd vyssie, ze transakcne lema sa da dokazat pre DTIME aj DSPACE aj NTIME, takze to funguje aj pre NSPACE.
WOW
Matfyz(ák|ačka) level I
Příspěvky: 36
Registrován: 14. 6. 2005 11:16
Typ studia: Informatika Mgr.

Re: Složitost II

Příspěvek od WOW »

Cau!
gejza píše:
Borek píše:...problemu...

Kód: Vybrat vše

NSPACE(n)   vs.   NSPACE(log(n) * n)
Ako sam pises, neostra inkluzia je trivialna. Co sa tyka ostrej, tak sa podla mna jedna presne o dosledok Translacneho lemmatu (na Kucerovych slajdoch je to slajd 27) - je to tam sice s DTIME, ale vid. poznamka o slajd vyssie, ze transakcne lema sa da dokazat pre DTIME aj DSPACE aj NTIME, takze to funguje aj pre NSPACE.
Kucera asi predelaval slajdy, takze tedka je na strane 27 je polynomialni hierarchie... Mozna je i Tvoje reseni dobre, ale ja jsem tedka pri cteni slajdu nasel na strane 35 dusledek vztahu NSPACE(S(n)) = co-NSPACE(S(n)):
Důsledek: Věta o deterministické prostorové hierarchii platí i pro nedeterministický prostor.
cimz mame ostrou nerovnost primo dokazanou (predpoklady vety jsou snad splneny).

btw. nevite nekdo psl nahodou, jestli jsou nejake pozadavky k ustni? Te teorie je nejak moc, takze co by melo stacit na "splneni" zkousky ;) dik
Uživatelský avatar
hippies
Admin(ka) level I
Příspěvky: 990
Registrován: 29. 9. 2004 12:46
Typ studia: Informatika Mgr.
Bydliště: Mladá Boleslav
Kontaktovat uživatele:

Re: Složitost II

Příspěvek od hippies »

Ted jsem prochazel slajdy a u Vety o vztazich mezi tridami se body c) a d) dost odlisujou (i kdyz baj voko to rika totez), .. dokazovalo se to stejne, nebo jinak?
Chjo, dovede te si představit svět, kde by byla každá harmonická diferenciální forma (jistého typu) nesingulární projektivní algebraické variety racionální kombinací kohomologických tříd algebraických cyklů..
Uživatelský avatar
langosh
Matfyz(ák|ačka) level II
Příspěvky: 96
Registrován: 28. 1. 2006 13:20
Typ studia: Informatika Mgr.
Bydliště: Bohnice
Kontaktovat uživatele:

Re: Složitost II

Příspěvek od langosh »

To myslíš jako rozdíl od skript?
To d. stejně, v těch slajdech je jenom ta nejsilnější podmínka, víš, že NTIME i DSPACE je pod NSPACE (viz a. a c.), je to tam myslim jako c'.
To c. je asi horší, teď tam nevidim že by to plynulo z těch vět ve skriptech, ale je vidět, že pokud platí to v těch slajdech, tak platí i všechny ty ve skriptech (je to silnější podmínka).
Ono to máš jedno jak se to dokazovalo, podle mě mu tam stačí napsat ten důkaz co je ve skriptech a nějak to převýst.
Uživatelský avatar
hippies
Admin(ka) level I
Příspěvky: 990
Registrován: 29. 9. 2004 12:46
Typ studia: Informatika Mgr.
Bydliště: Mladá Boleslav
Kontaktovat uživatele:

Re: Složitost II

Příspěvek od hippies »

No taky si to myslim, ale radsi bych videl dokazany to jeho zneni;)
Chjo, dovede te si představit svět, kde by byla každá harmonická diferenciální forma (jistého typu) nesingulární projektivní algebraické variety racionální kombinací kohomologických tříd algebraických cyklů..
Uživatelský avatar
Myshaak
Matfyz(ák|ačka) level III
Příspěvky: 162
Registrován: 18. 1. 2006 22:29
Typ studia: Informatika Mgr.

zk. [12.6.09']

Příspěvek od Myshaak »

Nechce se mi zakladat novy vlakno. :) Takze dnesni (12.6.) pisemka:

-priklady byly pomerne jednoduche, u 2 vztahu nebylo nic, velka vetsina inkluzi byla ostra

-teoreticka otazka: Borodinova veta ... takze super, sice pomerne tezsi, ale umel jsem to, takze na nic vic se uz neptal.
"Go for the eyes Boo, go for the eyes! Yeahh!!"
Uživatelský avatar
looky
Matfyz(ák|ačka) level I
Příspěvky: 9
Registrován: 25. 4. 2005 17:31
Typ studia: Informatika Mgr.

Re: Složitost II

Příspěvek od looky »

Nevíte někdo náhodou, jestli některé důkazy Čepek NEZKOUŠÍ?

Pokud se dobře pamatuju, tak například u věty o redukci počtu pásek pro časovou složitost se na přednášce asi na 20 minut úplně zamotal a následně prohlásil, že to ani nezkouší, protože i on sám to bez svých papírů nedává... A vypadalo to že má na mysli všechny věty z těch několika úvodních "technických" přednášek. Takže, je to pravda? Dostal jste někdo konkrétně tuhle větu? Učíte se všechno nebo jen něco?
Návštěvník

Re: Složitost II

Příspěvek od Návštěvník »

Nevim jak to je s tim, jestli se něco nezkouší, ale já z osobní zkušenosti můžu říct, že se zkouší i alternující/omezené kvantifikátory... Je tam spousta definic a vět, takže u tý otázky stačí spíš všechno sepsat a vědět o čem to je, než něco dokazovat. Ale i tak, celkem překvapivá otázka si myslim.
Uživatelský avatar
Stevko
Matfyz(ák|ačka) level I
Příspěvky: 17
Registrován: 31. 1. 2007 21:52
Typ studia: Informatika Mgr.
Bydliště: kolej

Re: Složitost II

Příspěvek od Stevko »

Vety zo začiatku sa neskúšajú (redukcia počtu pások na jednu, priestorová kompresia a časová kompresia). Nemalo by to význam, keďže v nich nie je žiadna myšlienka a je to len nepohodlné technické hranie sa (viď napríklad práve priestorovú kompresiu).
Uživatelský avatar
looky
Matfyz(ák|ačka) level I
Příspěvky: 9
Registrován: 25. 4. 2005 17:31
Typ studia: Informatika Mgr.

Re: Složitost II

Příspěvek od looky »

Dnešní písemka:

-příklady jsou na wiki (termín 2002-06-21)

-otázku jsem dostal translační lemma a větu o nedeterministické prostorové hierarchii, dále jsem zaslechl větu o časové hierarchii... prostě klasika

celkově pohodová zkouška, odcházel jsem ani ne za hodinu a čtvrt (i s písemkou) s jedničkou...

Malý hint na závěr: pokud víte že máte písemku dobře, udělejte u nějaké inkluze drobnou chybu. Čepek vám pak sice strhne půl bodu až bod, ale pak se vás zeptá na větu, která se tam používala. Takže pokud nějakou větu chcete přímo dostat, tohle je velice elegantní způsob jak to zařídit. Samozřejmě bez záruky, ale dnes to fungovalo snad u všech zůčastněných. :)
Uživatelský avatar
adam
Matfyz(ák|ačka) level I
Příspěvky: 31
Registrován: 10. 1. 2007 12:36
Typ studia: Informatika Mgr.
Kontaktovat uživatele:

Re: Složitost II

Příspěvek od adam »

Jak jsem si dnes mohl na vlastní kůži ověřit, tak se zkouší i věci, co se dělají na cvikách a nejsou ve slajdech, což je podle mě prima, protože je to jednodušší než mnohé důkazy, co se dělaly na přednášce. Ale trochu mě to překvapilo:). Měl jsem (1) PSPACE-úplný problém a dokázat aspoň, že je v PSPACE, a pak (2) co by se stalo, kdyby nějaký A \in \Sigma_k byl PSPACE-úplný. Když jsem dostal tu první otázku, tak jsem si říkal, sakra, kde to v tý přednášce bylo… a pak jsem sám sebe překvapil, co všechno si pamatuju z cvik. Možná ještě štěstí, že jsme to dělali zrovna na těch posledních.
Odpovědět

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