Složitost II
Složitost II
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
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
Re: Složitost II
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.
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
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)
- 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
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.
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.
Re: Složitost II
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ý
Re: Složitost II
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.Borek píše:...problemu...Kód: Vybrat vše
NSPACE(n) vs. NSPACE(log(n) * n)
-
- 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
Cau!
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
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)):gejza píše: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.Borek píše:...problemu...Kód: Vybrat vše
NSPACE(n) vs. NSPACE(log(n) * n)
cimz mame ostrou nerovnost primo dokazanou (predpoklady vety jsou snad splneny).Důsledek: Věta o deterministické prostorové hierarchii platí i pro nedeterministický prostor.
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
- hippies
- Admin(ka) level I
- Příspěvky: 990
- Registrován: 29. 9. 2004 12:46
- Typ studia: Informatika Mgr.
- Login do SIS: procj4am
- Bydliště: Mladá Boleslav
- Kontaktovat uživatele:
Re: Složitost II
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ů..
- 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
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.
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.
- hippies
- Admin(ka) level I
- Příspěvky: 990
- Registrován: 29. 9. 2004 12:46
- Typ studia: Informatika Mgr.
- Login do SIS: procj4am
- Bydliště: Mladá Boleslav
- Kontaktovat uživatele:
Re: Složitost II
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ů..
- Myshaak
- Matfyz(ák|ačka) level III
- Příspěvky: 162
- Registrován: 18. 1. 2006 22:29
- Typ studia: Informatika Mgr.
- Login do SIS: michp5am
zk. [12.6.09']
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.
-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!!"
- 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
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?
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?
Re: Složitost II
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.
- 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
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).
- 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
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.
-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.
- 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
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ý 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.