Teoretická informatika

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

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.

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]

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]

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

[t0Mi]

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]

...

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

[thom]

No teraz uz tomu rozumiem.
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]

No teraz uz tomu rozumiem.
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]

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]

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={aⁿ bⁿ cⁿ | 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 

[bubo]

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

[Macro]

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..

[t0Mi]

...

...

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]

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]

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?

[hijovec]

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 

[scream]

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

[slax]

E-51 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