Matfyz Wiki
Takže dneska nás potěšil novým testem.
Zkouška má 3 části, test, příklady a ústní. Pro známku musíte projít všemi třemi, už nestačí dát dobře třeba jen test (to zdůraznil). Test je klasika. Příklady také.
Na tyto dvě části jsou 2 hodiny, dělat je můžete jak chcete. Jen příklad dostanete až vám opraví test a když odevzdáte někde uprostřed (lidí) tak počítejte až půl hodiny +- než ho opraví. Do dvou hodin musíte vše odevzdat.
Pak je ústní, už asi nění časově omezená. Tam zřejmě bude rejpat do prvních dvou částí, u příkladů jestli máte dobře a u testu zda ste to neopsali a víte o co go :-)
Opravuje a kdo má aspoň 19, dostane rovnou příklad, co nemají si dává stranou a na konci si je zavolá. 18 dal ještě také příklad a ostaní by.
Dnes měli 3 18b a si 7-8 lidí pod 18b. Ale myslím že někdo měl i 29b.
Jinak po včerejšky kdy to měli skoro všichni to radši změnil. Test je ale téměř stejný. +-15 otázek je skoro stejných, ostatní pozměnil a pěkně ošklivě :) Třeba v zadání jem změnil deterministický na nedeterministický atd.
Co si pamatuji:
Graf a stavy: automat přečte slovo baab. Zásadní problém je že ho nepřijme, takže se může dostat i do nekoncových stavů (detail který mi unikl).
Přechodová funkce pro slovo z jazyka u nedeterministického a. Tím že je nedeterministický nebyla ani jedna možnost správně.
Jazyk rozpoznatelný konečným automatem, tam to pozměnil nějak tak, že platili všechny místo a-cd. Rozdíl jsem nenašel, říkal že nahoře v zadání je jen implikace.
Pak tam bylo něco s reduktem automatu a zda je izomorfní, homomorfní ekvivalentní atd. Platilo vše.
Otázky kdy byly 1-2 automaty a dělal se znich 2-3 a různě se pospojovávali ty jejich množiny celé přeházel. Bylo těžký se v tom vyznat :-)
Jedna úloha byla zase z A1 a A2 vznikl A a měl koncový stav jako (Q1,F2). Odpovědi F1, F2, F1-F2, F2-F1, správně bylo jen F2, ten koncový stav je vždycky jen u F2 a k tomu připojí všechny počáteční stavy Q1.
Gramatika s pravidly X->u ale jen tři odpovědi, jinak stejné.
Otázka listy derivačního stromu změněna na vnitřní vrcholy (nějak mě zmátl tím vrcholy... kdyby aspoň napsal uzly....) Odpověď měla být N
Derivační stromy BG bylo stejné.
Doplněk a tady asi bylo jen rekurzivního jazyka? Teď už nevím, odpověď měla být rekurzivně spočetný a rekurzivní (pokud si pamatuji), ale nechápu to :-)
Regulární gramatiky (nebo výrazy?) jsou....
a) levá lineární b) pravá lineární zbytek byl špatně.
Pak záludné otázka, zda jde nedeteministický turinguv stroj simulovat... a nějaké odpovědi typu: a) prohledáváním do hloubky, b) do šířky, c) backtrakingem d) nejde simulovat, správně bylo buď a nebo b, uz nevím.
Pak tam byla otázka o nejakém problemu zastaveni u TS, slysel jsem poprve :-) Správne byla posledni odpoved za d).
Kvocient zustal, jen se zmenili slova, jinak lehky.
První otázku zmenil na (L1 sjenodceni L2)* a nebyli tyto jazyky dany, a odpovedi byli neco jako (L1* U L2*) a podobne varianty skor se nelisici :-)
Otázka na ekvivalenci stavu zustala, je to ta s X* a ne ta s L(a).