• 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

« predchdzajce - alie »

Sxx

mozte mi vysvetlit co su jednotlive zatvorky a co su jednotlive pozicie 1. 2. 3. v zatvorkach pri dvoch zasobnikoch?
(q0,(D,Z,Z),(D,Z,Z),q0,(R,R,R))


thom

Quote from: DeViLvs on  30.01.2011, 20:03:15
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.
no opravil som to na Z, mas pravdu.
len jedno mi nejde do hlavy, tato instrukcia : q0, (a,B,B), (a,B,B), qa, (R,-,-) - pride znak "a" a iba sa posunie, nikam si ho neulozi, ako potom mozu suhlasit tie pocty becok a cecok s poctom acok, jedno acko je neulozene

DeViLvs

Quote from: Sxx on  30.01.2011, 20:04:23
mozte mi vysvetlit co su jednotlive zatvorky a co su jednotlive pozicie 1. 2. 3. v zatvorkach pri dvoch zasobnikoch?
(q0,(D,Z,Z),(D,Z,Z),q0,(R,R,R))
(q0,(D,Z,Z),(D,Z,Z),q0,(R,R,R))
v stave q0: (hlava na vstup. paske ukazuje na D, hlava v zasobniku1/pocitadle1 ukazuje na Z, v  zasobniku2/pocitadle2 ukazuje na Z)
((ne)prepis znak na vstup. paske (kde ukazuje) na D, v zasobniku1/pocitadle1 (ne)prepis na Z, v  zasobniku2/pocitadle2 (ne)prepis na Z)
TS prejde do stavu q0 (cize ostane v rovnakom stave)
a (posun hlavu vstup. pasky do prava (o 1 poziciu samozrejme), posun hlavu na zas1 doprava, posun hlavu na zas2 doprava)

DeViLvs

Quote from: thom on  30.01.2011, 20:13:03
no opravil som to na Z, mas pravdu.
len jedno mi nejde do hlavy, tato instrukcia : q0, (a,B,B), (a,B,B), qa, (R,-,-) - pride znak "a" a iba sa posunie, nikam si ho neulozi, ako potom mozu suhlasit tie pocty becok a cecok s poctom acok, jedno acko je neulozene
no ide o to, ze pocet aciek musi byt 2x tolko ako pocet b. a takisto 2x tolko ako pocet c. Cize pocet a = 2x pocet b = 2x pocet b.

Priklad, ked pocet a = pocet b = pocet c (a^n b^n c^n) je lahky, kedze najprv sa posuvas doprava v pocitadle1 (ten zodpoveda poctu aciek), potom sa posuvas doprava v pocitadle2 (co zodpoveda poctu b) a potom ked ti budu prichadzat ccka, tak posuvas sa v pocitadle1 a pocitadle2 naspat dolava. Ak je vstupny retazec validny, tak ti hlavy v pocitadlach budu ukazovat opat na zaciatok, kde si zacal.

Problem je, ze ked pocet aciek je 2x tolko ako bciek. Vtedy sa zvykne postupovat akoby takto: iba kazde druhe a zapocitaj (=posun hlavu v pocitadle1).
AaAaAa bbb ccc

Cize iba pri "malom" a posunie hlavu. Cize ak acok je pocet n, tak hlavu posunie iba n/2 krat, Tak aby ten pocet n/2 sedel k bckam a cckam.

Este spomeniem, ze iba pri stave ked mas parny pocet a moze prist b. Cize iba po malom a moze prist b.

thom

ok super,takto som nad tym neuvazoval ;)
este jedno mi nie je jasne, tato instrukcia:
q1, (c,B,B), (c,B,B), q2, (-,L,L) - precita prve c, neposunie sa a vymazuje, ked potom nasleduje instrukcia:
q2, (c,B,B), (c,B,B), q2, (R,L,L), nie je to tak, ze hlava sa neposunula, cize znova zacina na tom istom znaku?? a dvakrat pracuje s tym istym znakom??
nemalo by byt : q1, (c,B,B), (c,B,B), q2, (R,L,L) ?

Faust

ludia kde najdem algoritmus Dijkstra pre triedenie postupnosti pouzitim Minimalneho prvku zostupne?  ..to je ten bubble sort ci to je nieco ine? vdaka
This is an invasion of PostHumus!

t0Mi

#481
keby bolo q1, (c,B,B), (c,B,B), q2, (R,L,L) tak v case ked odpocitas pocitadla na Z,Z,
tak hlava by bola uz dalej ako je dolar a nýb rž (dolar,Z,Z) nenastane..
nebud lenivy, pouzit pero a papier a kresli si gulicky namiesto hlavy..

tie algoritmy nenajdes, treba pochopit ako sa to robi.. aj tak by
si si to nezapamatal.. tu mas princip, ked vies ako funguje UM,
d(a,b), UST(a,b) a boolovske funkcie, vies spravit algoritmus..

http://www.maths.abdn.ac.uk/~igc/tch/mx4002/notes/node30.html
(bacha korecko chce ZOSTUPNE, takze musis Y1 posuvat od konca)
ostatne 2 algoritmy, pre insertion a shell sort, su na youtube..

:)

DeViLvs

Quote from: thom on  30.01.2011, 20:36:34
...
jj je to tak, ze pracuje 2x s tym istym cckom. Ale to IBA s prvym cckom.
A to preto, lebo treba si predstavit uplne jednoduchy priklad, napriklad ze x=a^n b^n. a nech n=1, cize x=ab

Sleduj len pocitadlo1. (oznacme ho Z,B1,B2.....)

V 1.instrukcii pride (Cpreskrtnute), co pre nas vstupny retazec este "nic neznamena". Ale hlavu v poc1 uz posunie na B1.
Az teraz pride a a posunie hlavu v poc1 na B2. Cize acok mame len jedno, ale hlava uz ukazuje na druhe B (B2).
A teraz keby prislo to jedno ccko, tak by sme sa posunuli len o 1 poziciu dolava, cize na B1. Lenze my chceme, aby hlava uz ukazovala na Z.

Preto treba najprv poriesit to, ze po vsetkych ackach hlava ukazuje o 1 viac doprava. Preto ju treba posunut raz dolava.

napr:
C    a    a     a
Z    B1  B2   B3  B4  B5  ....
                      |

Cize ked pridu 3 accka, tak hlava ukazuje uz na stvrte Bcko. teda ju treba posunut naspat:

C    a    a     a
Z    B1  B2   B3  B4  B5  ....
                 |

A teraz nam uz mozu chodit ccka :D

thom

No teraz uz tomu rozumiem. :bannana_guitar:
Este jednu otazku mam.Na cvikach sme riesili priklad "a^n b^n c^n"  a k tej instrukcii q1, (c,B,B), (c,B,B), q2, (-,L,L)
mam zapisane pre TS s dvoma zasobnikmi q1, (c,B,B), (c,B,B), q2, (R,L,L)
                 a pre TS s dvoma pocitadlami q1, (c,B,B), (c,B,B), q2, (-,L,L)
Je to chyba, alebo to tak ma byt??Pretoze ak tomu spravne rozumiem tak obidva typy sa rovnako pohybuju po paske, cize obidva budu o jeden znak "napred" a spravne pre TS s dvoma zasobnikmi by malo byt : q1, (c,B,B), (c,B,B), q2, (-,L,L) ??

DeViLvs

Quote from: thom on  30.01.2011, 21:05:10
No teraz uz tomu rozumiem. :bannana_guitar:
Este jednu otazku mam.Na cvikach sme riesili priklad "a^n b^n c^n"  a k tej instrukcii q1, (c,B,B), (c,B,B), q2, (-,L,L)
mam zapisane pre TS s dvoma zasobnikmi q1, (c,B,B), (c,B,B), q2, (R,L,L)
                  a pre TS s dvoma pocitadlami q1, (c,B,B), (c,B,B), q2, (-,L,L)
Je to chyba, alebo to tak ma byt??Pretoze ak tomu spravne rozumiem tak obidva typy sa rovnako pohybuju po paske, cize obidva budu o jeden znak "napred" a spravne pre TS s dvoma zasobnikmi by malo byt : q1, (c,B,B), (c,B,B), q2, (-,L,L) ??
zalezi od dalsich instrukcii. Tych rieseni je kopa. Vsetko co som pisal, to je len jedna z moznosti. Neviem ako ste to pocitali na cvikach, ale ja mam k 2 zasobnikom tiez napisane (-,L,L). Napis si na papier jednoduchy priklad a uvidis.

Sxx

#485
ja som to pochopil len teraz lebo som nevedel co su zatvorky ale je to jednoduche a ked som si to kreslil na papier ako sa pohybuje hlava a zasobniky tak mi vychadza ze tam ma byt RLL

EDIT: (-,L,L) predsa len :))))


Matejus

Quote from: Faust on  30.01.2011, 20:41:00
ludia kde najdem algoritmus Dijkstra pre triedenie postupnosti pouzitim Minimalneho prvku zostupne?  ..to je ten bubble sort ci to je nieco ine? vdaka
to by mal byť podľa mojich informácii SELECTION SORT

Sxx

31.1.

1. Podobnost konecnostavovych automatov
2. Algoritmy graf. reprezentacia alg. graf. schemy algoritmov

Priklad : TS L={an bn cn | n>=1}


deCode666

dneska bol teda dobrý LOL na skúške :)

Matejus

31.1 druhá skupina

1. Bezkontextové gramatiky: Greibachov tvar a kanonický tvar
2. Metaalgebra algoritmiky a dajaké subalgebry: dačo dačo
P: AD do AJ (boli tam dva vnorené cykly s kopou kompozícii a nakoniec jedna alternatíva)

Ja už som väčšiu smolu mať ani nemohol dnes. Najprv si presadnem a vďaka tomu som vychytal tu horšiu skupinu. Potom zistím že príklad, ktorý som napísal mi Ľaľová opravila na fullko a nakoniec som mal pripravené ťaháky na všetko možné, len nie na tieto moje dve otázky. O tých som nemal ani šajnu.
Super ze teraz mám vo štvrtok o 8:00 opravnú z TI a o 9:00 z Unixu. To len bude psycho.

hijovec

parada panove... :) som rad ze uz "len unix" mi ostal... trimem vam vsetkym prsty aby ste to nejak ustali :) a utecha ale na hovno ze vela by som ani na nevedel pisat k tym otazkam :( dost salenota  :ropebanana: :ropebanana:

bubo

E-51 :ropebanana: chvala Bohu dnes fakt chcel davat kazdemu znamku ak ste aspon daco k veci mali napisane.
:puf:

Macro

#492
to uz je co za skusku!
vyhodil ma len tak z nalady :(

a btw vidi niekto otazku Podobnost konecnostavovych automatov v sylaboch? lebo ja nie. hlavne ze hovoria ze davaju iba z toho
a ani v slidoch na moodly

bubo

Zial je to tam.. ja som k tomu tiez skoro nic nemal k veci, ale je to v tych 230s skriptach na strane 49.

Ale fakt tie otazky zo zadku tahali..
:puf:

t0Mi

Quote from: Cheiftan on  31.01.2011, 05:39:23
Quote from: Skr3k0 on  31.01.2011, 02:46:24
...
...
minimum element sort nerobi swap, selection je nieco ine..
please editni si prispevok, lepsie povedane vymaz ho, nech
to ostatnych nemyli, mas to cele zle pochopene..

scream

Quote from: Macro on  31.01.2011, 21:56:25
to uz je co za skusku!
vyhodil ma len tak z nalady :(

a btw vidi niekto otazku Podobnost konecnostavovych automatov v sylaboch? lebo ja nie. hlavne ze hovoria ze davaju iba z toho
a ani v slidoch na moodly

to iste u mna... priklad + zapich 40 bodov... a 50 bodov z teorie len tak puuuuf bez jedinej otazky....  k podobnosti som mal asi kus hluposti ale k schemam som to mal celkom dobre podla toho co citam zo skript.

domino3d

Quote from: Macro on  31.01.2011, 21:56:25
to uz je co za skusku!
vyhodil ma len tak z nalady :(

a btw vidi niekto otazku Podobnost konecnostavovych automatov v sylaboch? lebo ja nie. hlavne ze hovoria ze davaju iba z toho
a ani v slidoch na moodly
dpc a to uz bol najedeny a nemal naladu?
vivat academicus

hijovec

Quote from: scream on  31.01.2011, 22:48:48
Quote from: Macro on  31.01.2011, 21:56:25
to uz je co za skusku!
vyhodil ma len tak z nalady :(

a btw vidi niekto otazku Podobnost konecnostavovych automatov v sylaboch? lebo ja nie. hlavne ze hovoria ze davaju iba z toho
a ani v slidoch na moodly

to iste u mna... priklad + zapich 40 bodov... a 50 bodov z teorie len tak puuuuf bez jedinej otazky....  k podobnosti som mal asi kus hluposti ale k schemam som to mal celkom dobre podla toho co citam zo skript.

vacsinou to je tak ze ked napises hluposti tak ta vyjebe jedna radost :) to iste aj mna na prvom termine.. len mi povedal toto zle toto zle uvidime sa nabuduce  :ropebanana:

scream

hej, presne tak dajako to bolo... ze toto mate zle musite prist nabuduce

slax

Quote from: bubo on  31.01.2011, 20:36:24
E-51 :ropebanana: chvala Bohu dnes fakt chcel davat kazdemu znamku ak ste aspon daco k veci mali napisane.

toto si skadial zase dostal????

praveze dnes naopak to bola riadna brutalita ... kazdy kto mal znamku a nebolo ich az tak vela, tak mal max E51 .... aj ked body na ovela viac vychadzalo

dnes nejako asi nemal naladu ... ked mu clovek povedal iba nejaky nezmysel, tak ho vyhodil

ale tak ja mam E51 spokojnost :)