Teoreticka informatika

[ElMino]

inac neviem ci to tu bolo spomenute, ale teraz mi napadlo, ze na prvom termine sme si mohli po rozdani zadani oficialne medzi sebou vymenit miesta a teda aj skupiny...
Tymto sa chcem zaroven podakovat cloveku, ktoremu sa nepozdavali jeho otazky (turing. vypocit. fcie a alebra logiky a problem fcionalnej uplnosti), co som samozrejme patricne vyuzil

no to som bol zrejme ja Ako vedel som aj TS vypoc. funkcie, ale viac som si bol isty sekvencnymi. No hlavne ze mam skusku.
OTAZKA NA TYCH CO MAJU SKUSKU: ma uz niekto zapisanu znamku v maise? ja nemam a kedze uz preslo 48 hodin od skusky(pracovnych), tak porusili nariadenie Vokiho o zapisovani znamok.

a aby som potesil stvrtakov: minuly rok sa VZDY dalo vymenit skupiny. ide o to, ze sa musi najst ochotna dvojica si navzajom vymenit skupinu.

[Martin18]

([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 

[Casso]

tak zajtra ma to caka... ovladam skoro vsetko od 1 po 9. temu, priklady... necham sa prekvapit. Inak podla mais-u nas bude 15 (25 limit) koho tam stretnem z vas? 

[Pribina]

Hlasim sa do prvej linie

[provasik]

Tak mne este skusku nezapisal a uz presolo takych 5 dni, takze uz pomaly zacinam tratit trpezlivost....

[McLarenPP]

tak zajtra ma to caka... ovladam skoro vsetko od 1 po 9. temu, priklady... necham sa prekvapit. Inak podla mais-u nas bude 15 (25 limit) koho tam stretnem z vas? 

ked ovladas 1 az 9 temu, tak to vlastne ovladas vsetko
Ja som stihol 1-7, ale niektore z nich som nepresiel cele, iba to, co sa uz vyskytlo niekedy na skuske.
A z prikladov toho este je dost, co chcem prebrat.. napr. sekvencne stroje nechapem, a pritom to bude urcite lahke, len neviem prist na ten princip, o co tam ide, na cviceniach sme to nemali.

[ppt]

Vidime sa zajtra Ked mi sadnu 2 priklady a jedna teoreticka, tak bude dobre. Algebra nepredpokladam, ze mi velmi sadne Bude to o stasti (aspon u mna), kludne moze dat aj take otazky, ze nenapisem nic O:).

Ked sa vratim k mojmu predchadzajucemu postu, nedostal sa nahodou niekto k tomu, ako vyriesit nasledujuce priklady?

2.priklad:
je dany bezkontextovy jazyk L1, jazyk L2=(a1a4a7...a3k+1; k je vacsie rovne 1, ai patri L1) treba dokazat, ze L2 je tiez bezkontextovy jazyk
-tu mam zostrojit nejaky zasobnikovy automat? Ak ano, tak aky? Ake slova ma akceptovat, ked nie je presne definovana L1?

3.priklad:
Zostrojte algoritmus Dijstra pre triedenie postupnosti pouzitim Minimalneho prvku zostupne (tha alebo nieco v tom zmysle ak som neprepisal vsetko uplne presne)
-WTF? Neviete kde by som nasiel nejaky vyrieseny priklad?

4.priklad:
sekv stroj z L1={a^i b^j} zostrojit L2={a^k b^l c^m}, pricom (i=>0, j>1, i<=k+l<=2i, 1<=m<j)
-WTF? To ako ma vyzerat ten sekvencny stroj?

Nieco mi odpisal McLarenPP, ale aj tak tomu nechapem. Vdaka vopred.

[SSPPYY]

Tak mne este skusku nezapisal a uz presolo takych 5 dni, takze uz pomaly zacinam tratit trpezlivost....

A presne preto som si to dal zapisat aj do indexu 

[Pribina]

Vidime sa zajtra Ked mi sadnu 2 priklady a jedna teoreticka, tak bude dobre. Algebra nepredpokladam, ze mi velmi sadne Bude to o stasti (aspon u mna), kludne moze dat aj take otazky, ze nenapisem nic O:).

Ked sa vratim k mojmu predchadzajucemu postu, nedostal sa nahodou niekto k tomu, ako vyriesit nasledujuce priklady?

2.priklad:
je dany bezkontextovy jazyk L1, jazyk L2=(a1a4a7...a3k+1; k je vacsie rovne 1, ai patri L1) treba dokazat, ze L2 je tiez bezkontextovy jazyk
-tu mam zostrojit nejaky zasobnikovy automat? Ak ano, tak aky? Ake slova ma akceptovat, ked nie je presne definovana L1?

3.priklad:
Zostrojte algoritmus Dijstra pre triedenie postupnosti pouzitim Minimalneho prvku zostupne (tha alebo nieco v tom zmysle ak som neprepisal vsetko uplne presne)
-WTF? Neviete kde by som nasiel nejaky vyrieseny priklad?

4.priklad:
sekv stroj z L1={a^i b^j} zostrojit L2={a^k b^l c^m}, pricom (i=>0, j>1, i<=k+l<=2i, 1<=m<j)
-WTF? To ako ma vyzerat ten sekvencny stroj?

Nieco mi odpisal McLarenPP, ale aj tak tomu nechapem. Vdaka vopred.

4ku mam tusim a riesenie musim nascanovat abo spravit v skicari dam sa do toho

EDIT : Hmm nemam to kde zavesit na web

[badi]

Hlasim sa do prvej linie

pridavam sa a pevne verim ze otazky budu lahke a si spomenim co vsetko tam treba pisat, kedze mam z toho chaoz.
co citam tak som na tom podobne ako McLarenPP

Tie sekvencne by mohol nejaky dobrak vysvetlit , respektive podelit sa o tie vyssie spominane priklady a riesenia

[ppt]

Pribina: jemin, tolko sposobov umiestnenia na net Aj ked das na rapidshare.com tak bude dobre
badi: pozri si eminkine priklady, tam ma vypocitanych viac tych prikladov na sekvencne automaty

[McLarenPP]

Pribina: jemin, tolko sposobov umiestnenia na net Aj ked das na rapidshare.com tak bude dobre
badi: pozri si eminkine priklady, tam ma vypocitanych viac tych prikladov na sekvencne automaty

my s badim mame na mysli sekvencne stroje, ako je napr. ten priklad zo skusky:
4.priklad:
sekv stroj z L1={a^i b^j} zostrojit L2={a^k b^l c^m}, pricom (i=>0, j>1, i<=k+l<=2i, 1<=m<j)

..to je trochu ine, ako sekvencne zobrazenia. V tom zosite od eminky su na to len 2 priklady, ale ani tym nerozumiem

[ppt]

jaaj, tak to sme na tom rovnako

[Pribina]

Okej ten priklad so sekvencnym strojom je tu

http://www.uloz.to/3622413/gsm.jpg

[ppt]

Vdaka. Vies to ale trosku pre nas lamerov popisat? To by mal byt nakresleny automat L2? A ten vznikne z automatu L1, ktory pozostava v tvojom obrazku zo stavov q0, q1 a q2? Bo saleny som z toho.

[Pribina]

noo ten automat realizuje zobrazenie S(L1) = L2 teda snazi sa pre kazde slovo z L1, ktore je na vstupe vygenerovat slovo patriace do jazyka L2.

[ppt]

hmmmm..
  To pred lomitkom su vstupy a za lomitkom vystupy? Lebo to je nejaky zvlastny automat. Kedy sa dostane do stavu q1? 

[Pribina]

hej pred su vstupy a za su vystupy, je to nedeterministicky automat takze do q1 sa dostane ak bude chciet

[ppt]

hmm, no asi kaslem na to

vdaka aj tak

[Pribina]

Tam nejde o to ze kedy prejde abo ne, snazit sa tu z toho automatu vytrepat vsetky mozne retazce jake z toho mozu vyjst a z toho mozu vyjst iba take jak je L2 v zadani prikladu

[ppt]

aha. Preco potom mas napr pri tom nultom stave prechod do nulteho sposobmi "a/aa" a zaroven aj "a/a"? Nestaci tam mat len "a/a"?

[Pribina]

Ne lebo moze nastaj aj situacia ked k=2i a l=0, cize potrebujes parny pocet acok vygenerovat.

[ppt]

ahaaa, uz tomu zacinam rozumiet pomalicky. Diik

[Pribina]

Som rad dufam ze moja snaha porozumiet TI sa mi zajtra zuroci

[ppt]

jj, poviem ujovi, nech ti pripise nejake body naviac?