• Welcome to TUKE FÓRUM - Fórum pre Å¡tudentov Technickej Univerzity v KoÅ¡iciach.
 

Teoretická informatika

Started by markus, 20.09.2010, 02:42:18

« predchádzajúce - ïal¹ie »

thom

Quote from: jardo on  28.01.2011, 19:08:22

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

Quote from: gabikke on  29.01.2011, 01:18:06
Je tu niekto taky, kto este nema zapisanu znamku v maise z 27. 1. 2011?

tak ja som nemal asi 4 dni  ;)
....in dreams until my death i will wander on ....

Cheiftan

Quote from: romeo on  29.01.2011, 02:56:01
Quote from: gabikke on  29.01.2011, 01:18:06
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,  bu  :mishela  :trestac:
tesim sa na pondelok na ten velky fx
Hello!

roman5555

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

P.S: popripade niekto nejaky tahacik ? :D

roman5555

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

jardo

ma niekto este nejake algoritmy triedenia spravene

slax

#457
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 ? :D

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

thom

Quote from: slax on  30.01.2011, 05:16:02
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 ? :D

2 + 2 = 3 mi nejako nesedi :D
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

Quote from: slax on  30.01.2011, 05:16:02
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 ? :D

2 + 2 = 3 mi nejako nesedi :D
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

Quote from: slax on  30.01.2011, 06:39:35
nj jasne uz chapem ... vdaka DeViLvs za vysvetlenie ;)

teraz pozeram, ze tam je n+1
nz

gabikke

Quote from: Cheiftan on  29.01.2011, 03:10:27
Quote from: romeo on  29.01.2011, 02:56:01
Quote from: gabikke on  29.01.2011, 01:18:06
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,  bu  :mishela  :trestac:
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

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

#466
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,(-,-,-))
Odkladanie robí ľahkú vec ťažkou a ťažkú vec nemožnou.

kilomassa

Quote from: slax on  30.01.2011, 08:52:18
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

Quote from: Squirrel_sK on  30.01.2011, 15:48:56
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 bk

Squirrel_sK

Quote from: thom on  30.01.2011, 16:08:12
Quote from: Squirrel_sK on  30.01.2011, 15:48:56
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 bk

ano mas pravdu, je to chybne.. opravujem
Odkladanie robí ľahkú vec ťažkou a ťažkú vec nemožnou.

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

Quote from: Squirrel_sK on  30.01.2011, 15:48:56
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 :D

thom

#473
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

Quote from: thom on  30.01.2011, 19:55:00
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 :D ja by som tam nedal Bcka ale Z.