Teoreticka informatika

[Pribina]

By ma skor vyhodil

[Miro]

zajtra sa hlasim aj ja .. nech nas Cila sprevadza :DD .. plllp

[johnyo13]

uz mam znamku v maise!

[badi]

uz mam znamku v maise!

AJ JA CHCEM

[popko]

Odhlasujem sa z terminu 15.1. do 2 hodin.
S tym kto mi skor napise sa dohodnem na presnom case mojho odhlasenia.

EDIT: Uz sa stalo

[Payne]

([q,B],a,B,[q,a],R) - cize pamata si "B", na vstupe je "a", zapise tam "B" a pamata si "a" a posunie sa doprava
([q,a],b,a,[q,b],R) - pamata si "a", na vstupe je "b", zapise tam "a" a pamata si "b" a posunie sa doprava
([q,a],B,a,[q,B],R) - (na konci retazca) pamata si "a", na vstupe je "B", zapise tam "a" a pamata si "B" a posunie sa doprava
([q,B],a,a,[q,B],L) - a toto je naco ?
([q,B],B,B,[p,B],R) - a teraz len skontrolujem, ze je koniec retazca a prejdem do finalneho stavu "p"

je to tak ? a potom preco ked si pamatam "b" tak uz nie je pre nho dalsia instrukcia  ? ... napriklad ([q,b],a,b,[q,a],R) ... som z toho jelen

toto co sa posuvas do lava tak si nie som isty ,ale bolo tam cosi take ze ked posunies to na paske tak sa vratis asi na zaciatok,ale neviem urcite

a to ze tam neni instrukcia pre b tak to je asi chyba,alebo neviem

cely princip je v tom ze si zapamatas co si prave precital a zapises co si mal zapamatane 

treba to vysvetlit presne jak to ma byt, ci uz nie? ja som odpisoval a neviem ze co neposlalo...

[mio]

([q,B],a,B,[q,a],R) - cize pamata si "B", na vstupe je "a", zapise tam "B" a pamata si "a" a posunie sa doprava
([q,a],b,a,[q,b],R) - pamata si "a", na vstupe je "b", zapise tam "a" a pamata si "b" a posunie sa doprava
([q,a],B,a,[q,B],R) - (na konci retazca) pamata si "a", na vstupe je "B", zapise tam "a" a pamata si "B" a posunie sa doprava
([q,B],a,a,[q,B],L) - a toto je naco ?
([q,B],B,B,[p,B],R) - a teraz len skontrolujem, ze je koniec retazca a prejdem do finalneho stavu "p"

je to tak ? a potom preco ked si pamatam "b" tak uz nie je pre nho dalsia instrukcia  ? ... napriklad ([q,b],a,b,[q,a],R) ... som z toho jelen

toto co sa posuvas do lava tak si nie som isty ,ale bolo tam cosi take ze ked posunies to na paske tak sa vratis asi na zaciatok,ale neviem urcite

a to ze tam neni instrukcia pre b tak to je asi chyba,alebo neviem

cely princip je v tom ze si zapamatas co si prave precital a zapises co si mal zapamatane 

treba to vysvetlit presne jak to ma byt, ci uz nie? ja som odpisoval a neviem ze co neposlalo...

ked budes taky dobry este vzdy mi to pomoze ... dik

[Payne]

no finta je v tom ze a ani b niesu priamo vstupne symboly, ale povedal by som mnozina symbolov 0 a 1, ked teda sa pise a abo b tak sa mysli v ramci oboch ze kazde z nich moze byt 0 alebo 1

Preco teda davame aj a aj b? no davaju sa len vtedy ak potrebujes rozlisit medzi nimi, t.j.:
([q,B],a,B,[q,a],R) zmanena ak som v stave q a nic nemam zapametane, na vstupe je a (teda prakticky 0 alebo 1), prepisem vstup Bckom, zapametam vstup a co je 0 abo 1 (teda ked si vsimnes tak toto je instrukcia aj pre 0 aj pre 1) a idem doprava

([q,a],b,a,[q,b],R) znamena ak som v stave q a mam zapametane a (moze byt 0 abo 1) a na vstupe je b (tiez moze byt aj 0 aj 1 ale nijako to od a nezavisi) prepisem to ackom (teda tou 0 abo 1 ktora bola zapametana), potom idem do stavu q a zapametam b(cize tu 0 abo 1 ktora bola na vstupe)

teda mam 0 alebo 1, ale potrebujem ich od seba rozlisit ktora je ktora

ty si pisal, ze

([q,B],a,B,[q,a],R) - cize pamata si "B", na vstupe je "a", zapise tam "B" a pamata si "a" a posunie sa doprava

to nemoze byt dobre, lebo potom by si mohol zacinat len symbolom a, bckom by sa nemohlo zacinat

dalsia vec je ze kuknes na povahu instrukcii a v nich prve stavy tak tam mas len [q,a] alebo [q,B], cize ty by si podla teba potom ani nemohol vobec odpametavat symbol b

dufam ze je to zrozumitelnejsie, a tam ked si uvedomis tak ide len o to, ze sa to takto pise aby si mal menej instrukcii, teda tota druha co pisem, tak by si mohol mat odpametane 2 symboly a dalsie 2 na vstupe => len jedna instukcia namiesto 4 a to len ked uvazujes ze mas 2 vstupne symboly keby ich bolo viac tak este viac usetris

cize aj dalej vsetko tak treba rozmyslat a davat na to bacha



pomoct ti to pomoze sak TIcko nieje az taka strasne vec, isto mi to viac davalo zmysel jak stavba

[Casso]

Today is day D. Fear in my eyes!

[LONEr]

Caute, kde najdem odpovede na otazky :
-metody konstruovania TS -> PAMATANIE STAVU , M-STOPOVY
-POSTOV problem, Rozhodnutelnost / nerozhodnutelnost
-Uzaverove operacie nad jazykom
(to su otazky z minuleho roka)
+ odkial tahate SHudak_TIuvod.pdf ? nie je to na kane.sk

[K5]

http://hornad.fei.tuke.sk/~korecko/storage/SHudak_TIuvod.pdf

tamto som nasiel napr. aj v eminkinych poznamkach..

[McLarenPP]

no, takze moja prognoza sa naplnila a boli presne tie iste otazky, ako pred rokom na druhom termine:

1.Halting problem + dokaz + univerzalny turingov stroj
2.Dijkstrova algebra
Priklady:
1. Turingov stroj s 2 pocitadlami (a na 2n; b na n; c na n )
2. je dany bezkontextovy jazyk L1, jazyk L2=(a1a4a7...a3k+1; k je vacsie rovne 1, ai patri L1)
    a trebalo dokazat, ze L2 je tiez bezkontextovy jazyk

ale boli 2 skupiny, druha vsak mala tiez nieco z toho, co je v tom subore s minulorocnymi otazkami.
Korecko ale vravel nieco o tom, ze asi vymyslia aj nove skupiny s otazkami.

[Killian]

  Skoda, ze som sa prehlasil na 15.1. a necital tu tvoju prognozu. Vie niekto, ake otazky nasledovali na dalsom termine minuly rok? Nepredpokladam, ze tretikrat daju to iste, ale pre istotu...

[Mao]

Podla zakulisnych informacii druha skupina mala tieto otazky 
T1 Uzaverove operacie. Uzaverove operacie nad jazykom.
  Elementerne uzaverove operacie nad triedami jazykov

T2 Algebra: baza, poly mono druhova algebra. Alegebraicke systemy. Logicko funkcne modely.

P1 Dokazte ze zobrazenie Fi je realizovatelne na nejakom KA
Fi = "a" ak N2(xi) mod 3 = 0
"n" inak.
Vstup je {0,1,2}* -> {a,n}*

P2 Zostrojte algoritmus Dijstra pre triedenie postupnosti pouzitim Minimalneho prvku zostupne
(tha alebo nieco v tom zmysle ak som neprepisal vsetko uplne presne)

[ppt]

Potvrdzujem Maovu spravu.

[Killian]

Tak ta druha bola podla mna ovela tazsia, aspon ze to uz asi neda na dalsom termine  .

[Killian]

Mam otazku k zatvorkovym vyrazom, konkretne tu je z minuleho roku aj s pokecom:

ten zatvorkovy priklad bol na 4 riadky, myslim... je to aj v tej zbierke prikladov na ZI, co sme mali.... tam, kde su priklady na zasobnikove automaty...
nedeterministicky by to vyzeralo takto:
(q0,[,Z,q0,[Z)
(q0,[,[,q0,[[)
(q0,],[,q0,λ)
(q0,λ,Z,qf,Z)
no a prvy a posledny riadok hovoria, ze sa moze rozhodnut, ze ci bude akceptovat alebo nebude, no a v determinizme ide hlavne o to, ze stale ma jednoznacne urcene, co dalej..., takze aby to bolo deterministicke, je potrebne zmenit stav... to je cele, takze:
(q0,[,Z,q1,[Z)
(q1,[,[,q1,[[)
(q1,],[,q1,λ)
(q1,λ,Z,qf,Z)

To prve je preco nedeterministicke? Ved ziadne dve instrukcie nemaju rovnaky stav a necitaju rovnaky vstup - teda automat sa nikde nerozhoduje. To je podla mna deterministicke?

[Mao]

(q0,[,Z,q0,[Z)
(q0,λ,Z,qf,Z)
Kvoli tomuto, lambda neznamena v tommto pripade, ze bol precitany prazdny vstup, ale to ze sa necital, teda automat sa moze rozhodnut ci bude citat vstup podla prvej instrukcie alebo nebude citat vstup a prejde do qf

[Killian]

Okej, dalsia taka otazka:

dokazat ze jazyk  L = {a0ⁿ1ⁿ} U {0ⁿ1²ⁿ} je deterministicky bezkontextovy

Treba tu ratat s tym, ze moze prist prve slovo z prveho jazyka a druhe slovo za nim z druheho jazyka a rozpozna to? Alebo len, ze bud pride na zaciatku a a podla toho sa rozhodnut, ako to budeme rozpoznavat? Lebo v eminkinych je to spravene tak, ze ma aj pre pripad ze idu oba po sebe...

[Payne]

Eminka to tak ma spravene, zle ja som mal len ze bud jedno abo druhe a strhli mi len jeden bod tak neviem...

[DeViLvs]

Kto uz ma TIcko spravene? potreboval by som nieco, odmena ista, PM pls

[Casso]

to bol bullshit... otazky som mal rovnake ako mclarenPP, cca 30 minut ma skusal ( od TS, UTS, problem zastavenia..., cez algebry algoritmov az po funkcionalnu uplnost Bool. funkcii...) a skoncil som s D63 stastny ako blbcha... off, ide sa slavit

[mio]

vie niekto ako dokazem, ze jazyk L={a^i b^j c^k|i<>j alebo j<>k} je nedeterministicky bezkontextovy ? dakujem ...

[badi]

niektori

to bol bullshit... otazky som mal rovnake ako mclarenPP, cca 30 minut ma skusal ( od TS, UTS, problem zastavenia..., cez algebry algoritmov az po funkcionalnu uplnost Bool. funkcii...) a skoncil som s D63 stastny ako blbcha... off, ide sa slavit

niektori tolko stastia nemali
aj ked body som mal na E tak som odisiel s FX ,

[pepco]

sak on proste Ecka nedaval... dnesna bilancia 5z15 nespravili, ale cely den tam cakat jak lools...

P.S.: Korecko opravoval priklady a vsetko odovzdal Hudakovi, kde si nas vsetkych 15 pekne preveril dojem z neho pozitivny, len no niekedy sa pyta take no... ale da sa v pohode