Predtermin 12.5.2008 - 6:4 po prvej tretine

Skladam klobuk pred kreativitou pana docenta Bartaka - skvele otazky, ktore mali spad, stavu a vtip.

Na tomto predtermine bolo 10 ludi, ktory robili skusku z Automatov (zvysok robil Programovani s omezujicimi podminkami).

Po prvej tretine (rozumej po teste) bol stav 6:4 pre pana docenta - tz. ze ulohu zadal len styrom (vlastne piatim - ale kolega s 21 bodmi to psychycky nevzdrzal a, citujem, "zblbol", takze sa vzdal moznosti riesit priklad.) Na druhej strane slecna so 17 bodmi nastupila aj do druhej tretiny.

V zavere by som chcel len podotknut, ze skutocnost, ze po prvej tretine bol stav 6:4 neznamena, ze ho pan docent v nasledujucich dvoch tretinach nezvysil. Katka, Klara, napiste ako ste dopadli.

Tak tak,test byl vyzivny...
Nicmene mam alespon nejakou pozitivni zpravu: i pokud je prvni cast zvlanuta jen tak tak, s odrenyma usima a zavrenyma ocima k tomu, da se to jeste napravit. Ja jsem zminena slecna, ktere dal sanci psat druhou cast i se 17 body z testu (po tom, co jsme s panem docentem spolecnymi silami nasli dve otazky, ktere jsem si byla schopna jakz takz opravit...) - No a o dve hodiny pozdeji jsem odchazela s jednickou v indexu :D

Zadani druhe casti jsem mela uz nekolikrat zde zminovane: napsat kontextovou gramatiku pro jazyk L = {a^i b^j c^k | i > j > k}, ukazat ze neni bezkontextovy + definice monotonni gramatiky a kontextove gramatiky, formulovat a dokazat vztah mezi nimi. Kdyz jsem se pote na ustni casti i pres zpackany test chtela "trapit kvuli lepsi znamce" (btw velmi ferove mi pripada jednani, ze vam Bartak rekne, jak hodnoti vase dosavadni vykony, nabidne moznost znamku vylepsit, ale nikoho tam nedusi v nejistote ci proti jeho vuli), mela jsem podrobne dokazat pumping lemma pro bezkontextove jazyky, zodpovedet par doplnujicich otazek k nemu a finisovy boj o jednicku pak znamenal rozhodnout, zda rekurzivne spocetne jazyky jsou uzavrene na doplnek a toto tvrzeni dokazat.

Tak to zacina lepsie ako minuly rok. :roll:
Co tak sa podelit o otazky z testiku? :wink:

no jednoduse...vezmes nejakou definici z prednasky, ten nejmensi znak z ni odstranis a pak to das do testu...takhle vygenerujes celej test :P

Ja jsem mela 18 bodu, to je o bod pod hranici.
Otazku jsem mela: Regularni vyraz, prevest ho na automat, popsat ten postup tak, aby se dal uzit obecne na prevody regularnich vyrazu na automaty a dokazat proc mohu prevadet regularni vyrazy na automaty.
Tuto otazku jsem pokazila, a pak jsem to u ustni casti s decentni pomoci dala dohromady a odesla jsem s 2.
U ustniho uz byla o dost prijemnejsi atmosfera. Pokud se nepletu tak myslim, ze u druhe casti snad uz uspeli vsichni (vim jiste ze 3 uspeli).

peterblack wrote:no jednoduse...vezmes nejakou definici z prednasky, ten nejmensi znak z ni odstranis a pak to das do testu...takhle vygenerujes celej test :P

Hmm...
Viem ako sa (de)generuju testy pana Bartaka - par som ich uz absolvoval. Skor mi islo o konkretne otazky, zaludnosti...

Jedna zaujimava bola:

Definicia ZA bez poslednej hviezdicky - generuje to jazyk, ktory prijimaja:

• DZA

• (N)ZA

• KA

• NKA

Samozrejme, clovej prehliadne chybajucu hviezdicku a zaskrtne horne moznosti ALE (!!!) chyba tam hviezdicka, takze spravna odpoved je posledne dve moznosti.

Nechť L1 a L2 jsou dva bezkontextové jazyky. Potom (L1prunik L2)* je vždy
[ ] = L1* prunik L2*
[ ] ≠ L1* prunik L2*
[ ] http://upload.wikimedia.org/math/a/0/7/ ... 47fbd5.png L1* prunik L2*
[ ] obracenehttp://upload.wikimedia.org/math/a/0/7/ ... 47fbd5.png L1* prunik L2*

odpověď:
BC (podle slajdů L1 prunik L2= { w | w elm L1 & w elm L2 },
odpoved A obecně neplatí například pro
L1 = {a}, L2 = {aa}
leva strana: (L1 prunik L2)* = {lambda}
prava strana: L1* prunik L2* = {(aa)*}

(plati mnozinova inkluze http://upload.wikimedia.org/math/a/0/7/ ... 47fbd5.png)

• nerovna se a podmnožinu s rovna se soucasne pouziva v pisemkach casto...proc se to nevylucuje?
  (zkontrolujte pls jestli je moje uvaha k otazce spravna)

peterblack wrote:Nechť L1 a L2 jsou dva bezkontextové jazyky. Potom (L1prunik L2)* je vždy
[ ] = L1* prunik L2*
[ ] ≠ L1* prunik L2*
[ ] http://upload.wikimedia.org/math/a/0/7/ ... 47fbd5.png L1* prunik L2*
[ ] obracenehttp://upload.wikimedia.org/math/a/0/7/ ... 47fbd5.png L1* prunik L2*

Mno ja by som to videl takto:
[ ] = L1* prunik L2*
[ ] ≠ L1* prunik L2*
[X] http://upload.wikimedia.org/math/a/0/7/ ... 47fbd5.png L1* prunik L2*
[ ] obracenehttp://upload.wikimedia.org/math/a/0/7/ ... 47fbd5.png L1* prunik L2*

Odpoved B je nespravna vzhladom na jazyky L1={a} a L2={a}.

peterblack wrote:nerovna se a podmnožinu s rovna se soucasne pouziva v pisemkach casto...proc se to nevylucuje?
(zkontrolujte pls jestli je moje uvaha k otazce spravna)

Samozrejme sa to nevylucuje.... to ze mas vztah "byt podmnozinou s =" este neznamena ze to nemoze byt "!=" k tvojmu vysledku.
predstav si priklad:
{a} "je podmnozinou s =" {a,b,c} --- tvrdenie plati
{a} "!=" {a,b,c} --- tvrdenie plati

Pouziva to ako chytak - pretoze z dvoch podmnozinovych relacii namiesas rovnasa a to vacsinou cloveku v strese nedojde. :evil:
V tomto pripade to ale pouzite nieje ale objavila sa uz aj varianta kde bolo spravne =, =podmnozinou a =nadmnozinou. :roll:

Snad som pomohol a ak sa mylim, tak ma pls opravte. :)