Složitost II

THX-1138
Matfyz(ák|ačka) level I
Příspěvky: 5
Registrován: 30. 6. 2008 19:41
Typ studia: Informatika Mgr.

Re: Složitost II

Příspěvek od THX-1138 »

Ahoj,
nemohl by sem někdo dát příklady, které se dělaly na cvičení?
THX-1138
Matfyz(ák|ačka) level I
Příspěvky: 5
Registrován: 30. 6. 2008 19:41
Typ studia: Informatika Mgr.

Re: Složitost II

Příspěvek od THX-1138 »

THX-1138 píše:Ahoj,
nemohl by sem někdo dát příklady, které se dělaly na cvičení?
Prosím? :)
ascorti
Matfyz(ák|ačka) level I
Příspěvky: 7
Registrován: 26. 11. 2006 18:42
Typ studia: Informatika Mgr.

Re: Složitost II

Příspěvek od ascorti »

Bohužel nevím, co se tam dělalo, ale přednášející říkal, že to, co bylo na cvičeních, zkoušet nebude - že to bylo navíc.
Honya

Re: Složitost II

Příspěvek od Honya »

Ahoj,

mam za sebou zkousku, takze prubeh je stale stejny, nejprve "prakticka cast" (viz wiki, dokonce myslim, ze jsme dostali jednu z pisemek tam napsanych, ale bez zaruky:)) a pak si losujete otazku. Soude dle delky seznamu (mel ho psany rukou takze sem moc neprecetl) tam ma asi 20 otazek, takze bych rekl, ze se pta uplne na vsechno - jinak ja mel stesti - prevod k-paskoveho na 1 paskovy, za mnou bylo translacni lemma, zbytek otazek jsem bohuzel neslysel (treba je nekdo prida). Na postup je treba 7/10 ale udelali to vsichni a myslim, ze pokud tam nenapisete uplny kraviny tak vas nevyhodi. Celkove je strasne hodnej, bohuzel ma otazka jaksi byla prilis jednoducha na to, abych zjistil jak moc chce jit do hloubky atp. - jedine co, ze u me nechtel konstruovat primo ten stroj, coz jsem ale stejne udelal:)).

Takze hodne zdaru u zkousky
Kubees
Matfyz(ák|ačka) level II
Příspěvky: 65
Registrován: 12. 1. 2007 22:22
Typ studia: Informatika Mgr.
Kontaktovat uživatele:

Re: Složitost II

Příspěvek od 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.
peci1
Matfyz(ák|ačka) level II
Příspěvky: 86
Registrován: 21. 1. 2009 20:08
Typ studia: Informatika Bc.

Re: Složitost II

Příspěvek od peci1 »

Kubees píše: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.
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 :) ).
Kubees
Matfyz(ák|ačka) level II
Příspěvky: 65
Registrován: 12. 1. 2007 22:22
Typ studia: Informatika Mgr.
Kontaktovat uživatele:

Re: Složitost II

Příspěvek od Kubees »

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. :)
Gerome

Re: Složitost II

Příspěvek od Gerome »

Kubees píše: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. :)
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).
Uživatelský avatar
Andreas
Matfyz(ák|ačka) level I
Příspěvky: 26
Registrován: 18. 1. 2006 16:47
Typ studia: Informatika Bc.
Kontaktovat uživatele:

Re: Složitost II

Příspěvek od Andreas »

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
New systems generate new problems:)
tadeas

Re: Složitost II

Příspěvek od tadeas »

Andreas píše: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
to by som bol povdacny, a mozno aj ostatni, co to este nedali...
dik za tie nahravky. :-)
Kubees
Matfyz(ák|ačka) level II
Příspěvky: 65
Registrován: 12. 1. 2007 22:22
Typ studia: Informatika Mgr.
Kontaktovat uživatele:

Re: Složitost II

Příspěvek od Kubees »

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)
peci1
Matfyz(ák|ačka) level II
Příspěvky: 86
Registrován: 21. 1. 2009 20:08
Typ studia: Informatika Bc.

Re: Složitost II

Příspěvek od peci1 »

Kubees píše:Nevite o nejakem zdroji, ze kterho by se daly naucit ty vety a dukazy, ktere chybi ve Strojilovi?
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 =)
peci1
Matfyz(ák|ačka) level II
Příspěvky: 86
Registrován: 21. 1. 2009 20:08
Typ studia: Informatika Bc.

[Zk] 21. 6. 2012

Příspěvek od peci1 »

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 :) ).
JakubT

Re: Složitost II

Příspěvek od JakubT »

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 :)
Kubees
Matfyz(ák|ačka) level II
Příspěvky: 65
Registrován: 12. 1. 2007 22:22
Typ studia: Informatika Mgr.
Kontaktovat uživatele:

Re: Složitost II

Příspěvek od Kubees »

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.
Přílohy
P6230005.JPG
P6230004.JPG
Odpovědět

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