Zkouška 11.6.08
Zkouška 11.6.08
Testové otázky byly poměrně klasické, dost možná ty samé, co včera, podle toho, co jsem slyšel.
Myslím, že ani příklady nebyly nijak neklasické, já jsem měl napsat gramatiku a^i b^j c^k i <= j <= k, dokázat že není bezkontextová a napsat definice monotonní a kontextové gramatiky a jaký je mezi nimi vztah (a dokázat ho).
Jelikož číst neumím, tak jsem tam nepsal o tom vztahu, tak mi to dal napsat - napsal jsem to skoro dobře, ale z blbé strany tam přepisoval ta pravidla ze separované na kontextovou, ale říkal jsem, že vím, že tam někde měl být nějaký problém, ale nevím, ze které strany to musím psát a proč, tak mě nad tím ještě nechal zamyslet - pořádně jsem to nevymyslel, ale stejně mi nakonec dal jedničku (z testu jsem měl 20 bodů).
Mezi písemkou a zkoušením byl libovolný čas, kdo chtěl, mohl přijít třeba za dvě nebo tři hodiny, lidí nadšených na zkoušku tam bylo dost a s každým strávil tak pět až deset minut (většinou opakovaně).
Myslím, že hodnocení je docela mírné, pokud člověk měl 17-19 bodů, tak se rozhodoval mezi 2 a 3, pokud více, tak 1 - 2. Nevím o tom, že by někoho vyhodil, i když, co jsem slyšel, někteří pořádně ani nezformulovali pumping lemma. Samozřejmě, test byl smrtelný klasicky pro tu půlku, někteří se prý snažili co nejvíce přiblížit nule...
Myslím, že ani příklady nebyly nijak neklasické, já jsem měl napsat gramatiku a^i b^j c^k i <= j <= k, dokázat že není bezkontextová a napsat definice monotonní a kontextové gramatiky a jaký je mezi nimi vztah (a dokázat ho).
Jelikož číst neumím, tak jsem tam nepsal o tom vztahu, tak mi to dal napsat - napsal jsem to skoro dobře, ale z blbé strany tam přepisoval ta pravidla ze separované na kontextovou, ale říkal jsem, že vím, že tam někde měl být nějaký problém, ale nevím, ze které strany to musím psát a proč, tak mě nad tím ještě nechal zamyslet - pořádně jsem to nevymyslel, ale stejně mi nakonec dal jedničku (z testu jsem měl 20 bodů).
Mezi písemkou a zkoušením byl libovolný čas, kdo chtěl, mohl přijít třeba za dvě nebo tři hodiny, lidí nadšených na zkoušku tam bylo dost a s každým strávil tak pět až deset minut (většinou opakovaně).
Myslím, že hodnocení je docela mírné, pokud člověk měl 17-19 bodů, tak se rozhodoval mezi 2 a 3, pokud více, tak 1 - 2. Nevím o tom, že by někoho vyhodil, i když, co jsem slyšel, někteří pořádně ani nezformulovali pumping lemma. Samozřejmě, test byl smrtelný klasicky pro tu půlku, někteří se prý snažili co nejvíce přiblížit nule...
-
- Matfyz(ák|ačka) level I
- Příspěvky: 37
- Registrován: 23. 1. 2007 16:32
- Typ studia: Informatika Bc.
- Bydliště: Zlínský kraj / Kolej 17. listopadu
- Kontaktovat uživatele:
Re: Zkouška 11.6.08
Jo, když na začátku říkal, že se v testu ptá na věci, co zazněly na přednášce, ale nebyly ve slidech, docela mi zatrnulo, protože jsem pět přednášek vynechal a ani na těch, co jsem absolvoval, jsem si toho navíc moc nepoznamenal.
Nicméně když člověk problematiku trochu zná, dá se většina odpovědí vymyslet. Test jsem odevzdával jako jeden z posledních až něco přes hodinu od začátku a někde jsem i docela hádal. Výsledek 28 z 29 mi docela vyrazil dech...
Příklad jsem měl zhruba takový:
Napsal jsem mu ten automat (ten je docela jednoduchý) a že nejde udělat dereministicky, pokud má přijímat prázdným zásobníkem (protože jazyk není bezprefixový), ale koncovým stavem by to deterministicky šlo a jak (už jenom princip). Pak jsem mu sepsal ty definice a důkaz jsem napsal jenom pro to, že přijímání koncovým stavem a prázdným zásobníkem je rovnocenné z hlediska síly automatu (oba směry).
Když si mě bral na ústní, říkal, že mít z testu o ten bod víc, tak mě pošle domů ihned. Potom velmi rychle proletěl můj výtvor a nakonec se jen zeptal, proč se musí vyztužit zásobník speciálním symbolem u převodu koncový stav -> prázdný zásobník (protože původní automat mohl po přečtení slova vyprázdnit zásobník a nebýt přitom v koncovém stavu, takže nový by bez výztuhy mohl přijímat něco navíc).
Jinak můj dojem z poslouchání toho, jak zkoušel pár lidí přede mnou, je spíš takový, že se docela hodně snaží vytáhnout z lidí něco, co by mu umožilo hodnotit je lépe. Takže největší problém je test...
Nicméně když člověk problematiku trochu zná, dá se většina odpovědí vymyslet. Test jsem odevzdával jako jeden z posledních až něco přes hodinu od začátku a někde jsem i docela hádal. Výsledek 28 z 29 mi docela vyrazil dech...
Příklad jsem měl zhruba takový:
Kód: Vybrat vše
Sestrojte zásobníkový automat, který prázdným zásobníkem přijímá jazyk všech správných uzávorkování nad abecedou {0, 1} (0 je otevírací závorka a 1 uzavírací). Lze udělat deterministicky? Definujte nedeterministický a deterministický zásobníkový automat a způsoby přijímaní slov a dokažte vztahy mezi jazyky, které generují.
Když si mě bral na ústní, říkal, že mít z testu o ten bod víc, tak mě pošle domů ihned. Potom velmi rychle proletěl můj výtvor a nakonec se jen zeptal, proč se musí vyztužit zásobník speciálním symbolem u převodu koncový stav -> prázdný zásobník (protože původní automat mohl po přečtení slova vyprázdnit zásobník a nebýt přitom v koncovém stavu, takže nový by bez výztuhy mohl přijímat něco navíc).
Jinak můj dojem z poslouchání toho, jak zkoušel pár lidí přede mnou, je spíš takový, že se docela hodně snaží vytáhnout z lidí něco, co by mu umožilo hodnotit je lépe. Takže největší problém je test...
-
- Matfyz(ák|ačka) level I
- Příspěvky: 9
- Registrován: 3. 6. 2007 18:23
- Typ studia: Kombinace Informatika - Matematika
Re: Zkouška 11.6.08
Mozna to nekomu pomuze, seznam par veci, co mi v testu prislo nove oproti minulym:
- neco, jestli je F konecna mnozina u determ. K automatu (tak nejak)
- kanonicky TS prijima prave stejne a) jako TS b) TS s jednou zarazkou...
- kdyz ND automat ma n stavu, pak D automat ma maximalne 2 na n stavu, n na n stavu (2 na n, protoze to jsou moznosti potencni mnoziny, n na n se zaskrtne, protoze to je vetsi cislo nez 2 na n)
- neco s poctem stavu u D automatu (asi jako do kazdyho stavu vede hrana (ne, musel by byt redukovany), do kazdyho stavu vede maximalne tolik hran, kolik je stavu, myslim, ze z toho nebyla pravda nic, ale jisty si nejsem).
Pak tam bylo typicky:
- spoji se dve BK gramatiky G1 do G2 do G a ze se to rovna zretezeni (! - u K gramatiky to zvladne vygenerovat vic)
- zase pozor, ze L+ != L* \ {lambda}...
- kdyz je DZA koncovym stavem, tak z toho vyplyne bezkontextovost a vsechno nad ni, naopak regularni a DZA prazdnym zasobnikem ne nutne (muzou byt, ale ne vzdy, nezaskrtava se)
- novy D automat, ktery ma prijima Q-F -> X* - L(A) (kdyby byl ND, tak to neni pravda
- isomorfismy/homomorfismy/ekvivalence reduktu
- q0 je pocatecni stav DKA, w je z F -> w je prijimaci, w je doszitelny...
- zase nejaky DKA s neprazdnym slovem -> existuje slovo w z X*, ze rozsirena prechodova funkce (q0, w) bude z F, existuje slovo taky z L(A) a plati to pro kazdy w z L(A) (a neplati pro kazdy w z X)
Jestli si jeste na neco vzpomenu, tak to sem dopisu, jinak taky treba dopiste, uz tu dlouho nebylo nic uzitecneho k tomu testu, ktery je asi nejvetsi problem
- neco, jestli je F konecna mnozina u determ. K automatu (tak nejak)
- kanonicky TS prijima prave stejne a) jako TS b) TS s jednou zarazkou...
- kdyz ND automat ma n stavu, pak D automat ma maximalne 2 na n stavu, n na n stavu (2 na n, protoze to jsou moznosti potencni mnoziny, n na n se zaskrtne, protoze to je vetsi cislo nez 2 na n)
- neco s poctem stavu u D automatu (asi jako do kazdyho stavu vede hrana (ne, musel by byt redukovany), do kazdyho stavu vede maximalne tolik hran, kolik je stavu, myslim, ze z toho nebyla pravda nic, ale jisty si nejsem).
Pak tam bylo typicky:
- spoji se dve BK gramatiky G1 do G2 do G a ze se to rovna zretezeni (! - u K gramatiky to zvladne vygenerovat vic)
- zase pozor, ze L+ != L* \ {lambda}...
- kdyz je DZA koncovym stavem, tak z toho vyplyne bezkontextovost a vsechno nad ni, naopak regularni a DZA prazdnym zasobnikem ne nutne (muzou byt, ale ne vzdy, nezaskrtava se)
- novy D automat, ktery ma prijima Q-F -> X* - L(A) (kdyby byl ND, tak to neni pravda
- isomorfismy/homomorfismy/ekvivalence reduktu
- q0 je pocatecni stav DKA, w je z F -> w je prijimaci, w je doszitelny...
- zase nejaky DKA s neprazdnym slovem -> existuje slovo w z X*, ze rozsirena prechodova funkce (q0, w) bude z F, existuje slovo taky z L(A) a plati to pro kazdy w z L(A) (a neplati pro kazdy w z X)
Jestli si jeste na neco vzpomenu, tak to sem dopisu, jinak taky treba dopiste, uz tu dlouho nebylo nic uzitecneho k tomu testu, ktery je asi nejvetsi problem
-
- Matfyz(ák|ačka) level III
- Příspěvky: 153
- Registrován: 10. 12. 2006 19:26
Re: Zkouška 11.6.08
prazdnym zasobnikem:Xerxes píše:Příklad jsem měl zhruba takový:Kód: Vybrat vše
Sestrojte zásobníkový automat, který prázdným zásobníkem přijímá jazyk všech správných uzávorkování nad abecedou {0, 1} (0 je otevírací závorka a 1 uzavírací). Lze udělat deterministicky? Definujte nedeterministický a deterministický zásobníkový automat a způsoby přijímaní slov a dokažte vztahy mezi jazyky, které generují.
(p,0,Z)={(p,AZ)}
(p,0,A)={(p,AA)}
(p,1,A)={(p,lambda)}
(p, lambda,Z)={(p,lambda)}
ee v cem je nedeterministicky? chapu ze ten jazyk neni bezprefixovej ale proc ten muj automat je nedeterministickej
diky
-
- Matfyz(ák|ačka) level II
- Příspěvky: 55
- Registrován: 29. 6. 2007 22:00
- Typ studia: Informatika Mgr.
- Bydliště: Praha 6 - Střešovice
Re: Zkouška 11.6.08
v tomhle:peterblack píše:
ee v cem je nedeterministicky? chapu ze ten jazyk neni bezprefixovej ale proc ten muj automat je nedeterministickej
diky
peterblack píše: (p,0,Z)={(p,AZ)}
(p, lambda,Z)={(p,lambda)}
-
- Matfyz(ák|ačka) level III
- Příspěvky: 153
- Registrován: 10. 12. 2006 19:26
Re: Zkouška 11.6.08
jo jasne diky, chapu to tak ze u zasobnikovych automatu existuji i deterministcké lambda krokykr4UT1k píše:v tomhle:peterblack píše:
ee v cem je nedeterministicky? chapu ze ten jazyk neni bezprefixovej ale proc ten muj automat je nedeterministickej
dikypeterblack píše: (p,0,Z)={(p,AZ)}
(p, lambda,Z)={(p,lambda)}
-
- Matfyz(ák|ačka) level II
- Příspěvky: 55
- Registrován: 29. 6. 2007 22:00
- Typ studia: Informatika Mgr.
- Bydliště: Praha 6 - Střešovice
Re: Zkouška 11.6.08
tohle nevim, jak jsi myslel, ale automat je deterministicky, prave kdyz si pri vypoctu nemuze vybirat. Ten tvuj si mohl vybrat, kdyz mel na zasobniku Z na vstupu 0, jestli ji nacte, nebo jestli provede lambda krokpeterblack píše:jo jasne diky, chapu to tak ze u zasobnikovych automatu existuji i deterministcké lambda kroky
-
- Matfyz(ák|ačka) level III
- Příspěvky: 153
- Registrován: 10. 12. 2006 19:26
Re: Zkouška 11.6.08
jo sorry, ja to srovnaval se slidama
uplne nakonci tam ma Bartak taky lambda prechod a pise tam ze to neni nedeterminismus (protoze si nemuzeme vybirat)
uplne nakonci tam ma Bartak taky lambda prechod a pise tam ze to neni nedeterminismus (protoze si nemuzeme vybirat)
Re: Zkouška 11.6.08
To ze si nemuzes vybirat nestaci na definici detministickeho atuomatu, je potreba aby byli definove vsechny situace ktere mohu nastat: kombinace stav a pismeno.ale automat je deterministicky, prave kdyz si pri vypoctu nemuze vybirat. Ten tvuj si mohl vybrat, kdyz mel na zasobniku Z na vstupu 0, jestli ji nacte, nebo jestli provede lambda krok
Definice pro DZA:
Říkáme, že zásobníkový automat
M=(Q,X,Y,δ,q0,Z0,F), je deterministický, jestliže platí:
– ∀p∈Q, ∀a∈X∪{λ}, ∀Z∈Y |δ(p,a,Z)|≤1 //nemuzeme si vybirat
– ∀p∈Q, ∀Z∈Y ( δ(p,λ,Z)≠∅ ⇒ ∀a∈X δ(p,a,Z)=∅ ) //ukonceni vzpoctu
Každý krok výpočtu je přesně určen.
-
- Matfyz(ák|ačka) level III
- Příspěvky: 153
- Registrován: 10. 12. 2006 19:26
Re: Zkouška 11.6.08
myslis vsechny situace (kombinace stav a pismeno), ktere muzou nastat aby slovo bylo prijato?lickra píše: To ze si nemuzes vybirat nestaci na definici detministickeho atuomatu, je potreba aby byli definove vsechny situace ktere mohu nastat: kombinace stav a pismeno.
Definice pro DZA:
Říkáme, že zásobníkový automat
M=(Q,X,Y,δ,q0,Z0,F), je deterministický, jestliže platí:
– ∀p∈Q, ∀a∈X∪{λ}, ∀Z∈Y |δ(p,a,Z)|≤1 //nemuzeme si vybirat
– ∀p∈Q, ∀Z∈Y ( δ(p,λ,Z)≠∅ ⇒ ∀a∈X δ(p,a,Z)=∅ ) //ukonceni vzpoctu
Každý krok výpočtu je přesně určen.
protože jinak jsem našel příklad kdy nejsou definovany vsechny kombinace stav a pismeno:
Přiklad: DZA prijimajici L={wcwR| w∈{a,b}+}.
Řešení: ukládej postupně symboly na zásobník a po přečtení středového symbolu c porovnávej vstupní symboly se symboly postupně umazávanými ze zásobníku
Kód: Vybrat vše
M=({q0,q1,q2}, {a,b,c}, {Z,a,b}, δ, q0, Z, {q2})
δ(q0,X,Y)= (qo,XZ) pro všechna X∈{a,b} a Y∈{Z,a,b}
δ(q0,c,Y)= (q1,Y) pro všechna Y∈{a,b}
δ(q1,X,X)= (q1,λ) pro všechna X∈{a,b}
δ(q1,λ,Z)= (q2,λ)
Re: Zkouška 11.6.08
Jo tak sem to myslel.
Ono to c je tam jenom zarazka.
Ono to c je tam jenom zarazka.