Teoretická informatika

[thom]

V TIMgr7122010
[/quote]

a to kde najdem?
[/quote]
no na moodli, heslo je jahodka,a vola sa to "Ucebne materialy k TI"

[gabikke]

Je tu niekto taky, kto este nema zapisanu znamku v maise z 27. 1. 2011?

[romeo]

Je tu niekto taky, kto este nema zapisanu znamku v maise z 27. 1. 2011?

tak ja som nemal asi 4 dni 

[Cheiftan]

Je tu niekto taky, kto este nema zapisanu znamku v maise z 27. 1. 2011?

tak ja som nemal asi 4 dni 

oh zavidim vam, ze ake porblemy tu riesite, zaroven aj gratulujem

fuj z toho ucenia my uz je zle,     
tesim sa na pondelok na ten velky fx

[roman5555]

ma niekto vypracovane otazky ktore boli a aj priklady aby sa to dalo nejak zrozumitelne pochopit ?

P.S: popripade niekto nejaky tahacik ?

[roman5555]

prosim nema niekto vsetky typy prikladov tak aby tomu porozumel aj debil ?

[jardo]

ma niekto este nejake algoritmy triedenia spravene

[slax]

nejako nemozem pochopit tomu prikladu k turingovmu stroju na f(x,y) = x + y

a je tam na zaciatku 11B11 cize ako tam pise potom m1 by malo byt tie prve dve jednotky, cize 2 a m2 tie druhe dve jednotky, cize tiez 2

jedine co tam spravi, ze vymaze prvu jednotku a potom tam pise, ze vysledok je pocet jednotiek (cize <qk>) co je vo finalovom stave (1B11) = 3 a to ma byt m1 + m2 ?

2 + 2 = 3 mi nejako nesedi
neviem tomu pochopit ako je to tam myslene :-/

[thom]

nejako nemozem pochopit tomu prikladu k turingovmu stroju na f(x,y) = x + y

a je tam na zaciatku 11B11 cize ako tam pise potom m1 by malo byt tie prve dve jednotky, cize 2 a m2 tie druhe dve jednotky, cize dve

jedine co tam spravi, ze vymaze prvu jednotku a potom tam pise, ze vysledok je pocet jednotiek (cize <qk>) co je vo finalovom stave (1B11) = 3 a to ma byt m1 + m2 ?

2 + 2 = 3 mi nejako nesedi
neviem tomu pochopit ako je to tam myslene :-/

No ja som inac tiez nad tym dumal, ale ked som si cital o tom v skriptach tak tam sa pise:
                                             uqi sj v
, t.j. že aktuálna bunka obsahuje symbol sj , TS M je v stave qi a že obsah vstupnej pásky naľavo od
aktuálnej bunky je u a obsah vstupnej pásky napravo od aktuálnej bunky je v

Cize ked mas fin. konfiguraciu : B1m1 Bq4 11m2, tak to co je pred stavom q4 - to je to cez co vsetko si musel prejst po tej paske, kym si sa dostal do fin. konfiguracie -  z hladiska konecneho vypoctu pre teba nezaujimave znaky. Zaujima ta iba to co je za tym q4, pretoze v tom stave prave si - cize 11m2. co je spravny vysledok.

Tak som to pochopil ja,opravte  ma niekto ak je to nespravne.

[DeViLvs]

nejako nemozem pochopit tomu prikladu k turingovmu stroju na f(x,y) = x + y

a je tam na zaciatku 11B11 cize ako tam pise potom m1 by malo byt tie prve dve jednotky, cize 2 a m2 tie druhe dve jednotky, cize tiez 2

jedine co tam spravi, ze vymaze prvu jednotku a potom tam pise, ze vysledok je pocet jednotiek (cize <qk>) co je vo finalovom stave (1B11) = 3 a to ma byt m1 + m2 ?

2 + 2 = 3 mi nejako nesedi
neviem tomu pochopit ako je to tam myslene :-/

trochu zle to chapes:
zoberme, ak je na zaciatku 11B11, napisal si "m1 by malo byt tie prve dve jednotky" co je asi hlavny problem. m1 je nejake prirodz. cislo a ma v tomto pripade hodnotu 1. Co sa zapise ako 11 (DVE jednotky). Precitaj si vyssie v skriptach ako sa to koduje. ak m1 je nejake cislo, povedzme 4, tak sa zakoduje piatimi jednotkami.

Z toho vyplyva, ze v tomto pripade, ktory si ty napisal, ma m1 hodnotu 1 a m2 tiez 1. Ked scitas 1+1 = 2. A cislo 2 sa zakoduje 3 jednotkami.

Musis pochopit, ze cislo m sa koduje ako 1 1^m...............(napr. m=5, tak 1 11111.......co je dokopy sest jednotiek)


Problem nastava, ze pri scitani ti vzniknu dve taketo "nadbytocne" jednotky. Preto treba jednu "skrtnut"

[slax]

nj jasne uz chapem ... vdaka DeViLvs za vysvetlenie

teraz pozeram, ze tam je n+1

[DeViLvs]

nj jasne uz chapem ... vdaka DeViLvs za vysvetlenie

teraz pozeram, ze tam je n+1

nz

[gabikke]

Je tu niekto taky, kto este nema zapisanu znamku v maise z 27. 1. 2011?

tak ja som nemal asi 4 dni 

oh zavidim vam, ze ake porblemy tu riesite, zaroven aj gratulujem

fuj z toho ucenia my uz je zle,     
tesim sa na pondelok na ten velky fx

ver si ze to spravis, a ked dostanes otazky, nieco napises, pred ustnou sa to poriadne douc, casu je dost a uvidis ze to zvladnes.

[slax]

Code [Select] Expand

TS s dvoma pocitadlami (a^2n,b^n,c^n)

ako sa vyriesi toto. Existuje take nieco, ze posuniem v jednom kroku dvakrat dolava napr. v jednom zasobniku (ze napr. LL)
alebo ze zapise len kazde druhe a-cko nejako vyriesit

nasiel som vyriesene s dvoma zasobnikmi a aj dvoma pocitadlami ale len pre { a^n,b^n,c^n | n>=1}
nie je niekde vyrieseny tento priklad?

[pinderko]

skus nad tym rozmyslat tak,ze pocet a = pocet b+pocet c...takze ked pridu acka a zapises ich tak potom bckami a ceckami ich dokazes vymazat

[slax]

no to je pekny napad ... ale myslim, ze vzdy by to nemuselo sediet ... napr. ze Bciek by bolo viac ako n a Ceciek by bolo menej ako n ale sucet by daval aj tak 2n

[Squirrel_sK]

takto nejak by to mohlo byt, opravte ma, ak sa mylim

(q0,(©,Z,Z),(©,Z,Z),q1,(R,-,-))
(q1,(a,Z,Z),(a,B,B),q2,(R,R,R))
(q2,(a,B,B),(a,B,B),q1,(R,-,-))
(q1,(a,B,B),(a,B,B),q2,(R,R,R))
(q1,(b,B,B),(b,B,B),q3,(R,L,-))
(q3,(b,B,B),(b,B,B),q3,(R,L,-))
(q3,(c,Z,B),(c,Z,B),q4,(R,-,L))
(q4,(c,Z,B),(c,Z,B),q4,(R,-,L))
(q4,($,Z,Z),($,Z,Z),qF,(-,-,-))

[kilomassa]

Code [Select] Expand

TS s dvoma pocitadlami (a^2n,b^n,c^n)

ako sa vyriesi toto. Existuje take nieco, ze posuniem v jednom kroku dvakrat dolava napr. v jednom zasobniku (ze napr. LL)
alebo ze zapise len kazde druhe a-cko nejako vyriesit

nasiel som vyriesene s dvoma zasobnikmi a aj dvoma pocitadlami ale len pre { a^n,b^n,c^n | n>=1}
nie je niekde vyrieseny tento priklad?

mozno by bolo len dobre povedat ze ak mas na zaciatku a pride acko prepnes sa do stavu pre dve acka cize cakas druhe a ked ti to druhe pride prepnes sa naspet s tym ze ho akoby ignorujes nikam nepises ani nikde neyzapisujes a mozes ocakavat bcko no a to cko je presne na to ako ti pisali na odpametavanie/vymazavnie akoby tych dvoch s tym ze ak vsetko suhlasi dostanes sa vsade(2poc/zas) na zaciatok a zaroven na koniec vstupnej pasky

[thom]

takto nejak by to mohlo byt, opravte ma, ak sa mylim

(q0,(©,Z,Z),(©,Z,Z),q1,(R,-,-))
(q1,(a,Z,Z),(a,B,B),q2,(R,R,R))
(q2,(a,B,B),(a,B,B),q1,(R,-,-))
(q1,(a,B,B),(a,B,B),q2,(R,R,R))
(q1,(b,B,B),(a,B,B),q3,(R,L,-))
(q3,(b,B,B),(b,B,B),q3,(R,L,-))
(q3,(c,Z,B),(c,Z,B),q4,(R,-,L))
(q4,(c,Z,B),(c,Z,B),q4,(R,-,L))
(q4,($,Z,Z),($,Z,Z),qF,(-,-,-))

neviem ci nemas chybu v tejto instrukcii (q1,(b,B,B),(a,B,B),q3,(R,L,-)), pride ti na vstupe b a prepisujes ho na a.nerozumiem tomu

[Squirrel_sK]

takto nejak by to mohlo byt, opravte ma, ak sa mylim

(q0,(©,Z,Z),(©,Z,Z),q1,(R,-,-))
(q1,(a,Z,Z),(a,B,B),q2,(R,R,R))
(q2,(a,B,B),(a,B,B),q1,(R,-,-))
(q1,(a,B,B),(a,B,B),q2,(R,R,R))
(q1,(b,B,B),(a,B,B),q3,(R,L,-))
(q3,(b,B,B),(b,B,B),q3,(R,L,-))
(q3,(c,Z,B),(c,Z,B),q4,(R,-,L))
(q4,(c,Z,B),(c,Z,B),q4,(R,-,L))
(q4,($,Z,Z),($,Z,Z),qF,(-,-,-))

neviem ci nemas chybu v tejto instrukcii (q1,(b,B,B),(a,B,B),q3,(R,L,-)), pride ti na vstupe b a prepisujes ho na a.nerozumiem tomu

ano mas pravdu, je to chybne.. opravujem

[slax]

nuz ano tak som aj ja rozmyslal, ze by sa to riesilo, ze jedno acko posunie a dalsie ignoruje

inac neviem ci som si dobre vsimol, ale rozdiel medzi 2 zasobnikmi a 2 pocitadlami je, ze pri 2 zasobnickoch zapisujem tie znaky aj do zasobnika a pri 2 pocitadlach len posuvam a nic nezapisujem?

[t0Mi]

jop a tym padom ten s pocitadlami je vacsi hlupak, lebo az v
poslednom stave zistis ze nedojdes do qF (lebo nenastane $,Z,Z)..
pri zasobnikovom sa to dojebe uz skorej, ak nie je dany retazec validny..

[DeViLvs]

takto nejak by to mohlo byt, opravte ma, ak sa mylim

(q0,(©,Z,Z),(©,Z,Z),q1,(R,-,-))
(q1,(a,Z,Z),(a,B,B),q2,(R,R,R))
(q2,(a,B,B),(a,B,B),q1,(R,-,-))
(q1,(a,B,B),(a,B,B),q2,(R,R,R))
(q1,(b,B,B),(b,B,B),q3,(R,L,-))
(q3,(b,B,B),(b,B,B),q3,(R,L,-))
(q3,(c,Z,B),(c,Z,B),q4,(R,-,L))
(q4,(c,Z,B),(c,Z,B),q4,(R,-,L))
(q4,($,Z,Z),($,Z,Z),qF,(-,-,-))

nesuhlasim.
V 2. instrukcii prepisujes Z v pocitadlach na Bcka (co nemozes jednak lebo to su pocitadla a jednak, ze to nesedi dalej...) A potom mas dalej v instrukciach, ze je v pocitadlach Z. Lenze Z uz si zmazal.

Preto by som prve dve instrukcie dal takto:
(q0,(©,Z,Z),(©,Z,Z),q1,(R,R,R))
(q1,(a,B,B),(a,B,B),q2,(R,R,R))

aj tak si nie som celkom isty, ci to potom bude sediet. Tento priklad uz tu bol rieseny, pricom sa objavili aj chybne riesenia, kedze v niektorom bol tusim ten problem, ako uz bolo spomenute, ze pocet a = pocet b + pocet c. Co samozrejme zdaleka nemusi byt to iste ako a^2n b^n c^n.

Hladajte, malo by to tu byt niekde. Spravny algoritmus pouzival stavy qa a qa2. Kebyze ste nenasli, mam ho aj v zosite, len sa mi nechce prepisovat

[thom]

asi myslis toto:

q0, (c(preskrtnute),Z,Z), (c(preskrtnute),Z,Z), q0, (R,R,R)

q0, (a,B,B), (a,B,B), qa, (R,-,-)

qa, (a,B,B), (a,B,B), qa2, (R,R,-)

qa2, (b,B,B), (b,B,B), q1, (R,-,R)

qa2, (a,B,B), (a,B,B), qa, (R,-,-)

q1, (b,B,B), (b,B,B), q1, (R,-,R)

q1, (c,B,B), (c,B,B), q2, (-,L,L)

q2, (c,B,B), (c,B,B), q2, (R,L,L)

q2, (s,Z,Z), (s,Z,Z), qF, (-,-,-)

[DeViLvs]

asi myslis toto:

q0, (c(preskrtnute),Z,Z), (c(preskrtnute),Z,Z), q0, (R,R,R)

q0, (a,B,B), (a,B,B), qa, (R,-,-)

qa, (a,B,B), (a,B,B), qa2, (R,R,-)

qa2, (b,B,B), (b,B,B), q1, (R,-,R)

qa2, (a,B,B), (a,B,B), qa, (R,-,-)

q1, (b,B,B), (b,B,B), q1, (R,-,R)

q1, (c,B,B), (c,B,B), q2, (-,L,L)

q2, (c,B,B), (c,B,B), q2, (R,L,L)

q2, (s,B,B), (s,B,B), qF, (-,-,-)

hej, len pozeram, ze tu je zas asi chyba v poslednej instrukcii ja by som tam nedal Bcka ale Z.