Teoreticka informatika

[Final_Destructer]

ako tak pozeram, tak k prvemu okruhu najdem relevantne info akurat v TI.pdf a v TI 2002, ci?

[badi]

temu cislo 6 ste sa ako ucili ? , mozno ze blba otazka, ale to sa neda toto :-(

[ppt]

nemyslim, ze blba. Ja by som to tvoje cislo rozsiril o interval <5,11>

[badi]

no to PKP je celkom v pohode .. aspon sa zda zatial :-), ale tie triedy jazykov a substitucie, a neviem co vsetko toot je uplne nepochopitelne

[McLarenPP]

nejako sa odhlasujete.. 16/25, tak malo nebolo ani na prvom termine

[badi]

uvazujem ze sa odhlasim tiez, to jednoducho sa neda stihnut  a este tooolko toho je co som ani nevidel 

ale tak pomimo .. ty si napisal spravne logicky .. 16/25 ( 16 z 25 ) ale taky MAIS co je opak rozumnosti a inteligencie .. vypisuje 25 / 16

[pepco]

akoze tiez si velke sance nedavam ale ked sa odhlasim tak potom najblizsie az 29.01... takto aspon mam sancu sa znovu prihlasit na opravny termin kdezto ti co pojdu na tie terminy co su posledne z tych obsadenych a nespravia, tak asi nebudu sa mat ani kde znovu prihlasit lebo terminy zaplnia ti co z predoslych nespravili

[ppt]

jo, zdielam pepcovu teoriu. Preto by sa mali ti piati prihlasit s5 na stredu, aby nam zbytocne nezaberali koncove terminy na opravaky

[McLarenPP]

ked som cital minulorocne forum, tak som si vsimol jednu zaujimavost - minuly rok mali prvu skusku 5.1, a ake mali otazky? Tie iste, co boli tohto roku na prvom termine. Mozno nahoda, mozno nie, kazdopadne velmi zaujimave. A na druhy termin bolo vlani nahlasenych malo ludi (14), z toho prislo len 11 a mali len 1 skupinu -
Otazky:
1.halting problem + dokaz + univerzalny turingov stroj
2.Dijkstrova algebra
Priklady:
1. stroj s 2 pocitadlami (a na 2n; b na n; c na n )
2. je dany bezkontextovy jazyk L1, jazyk L2=(a1a4a7...a3k+1; k je vacsie rovne 1, ai patri L1)
    a trebalo dokazat, ze L2 je tiez bezkontextovy jazyk

Takze ked sa teraz este 2 ludia odhlasia, je celkom mozne, ze to bude v stredu vyzerat rovnako

[ApokalypS]

Takze ked sa teraz este 2 ludia odhlasia, je celkom mozne, ze to bude v stredu vyzerat rovnako

zeby deja vu? epizoda sa opakuje?

btw: dve pocitadla si myslim, ze nebudu.. to sme nebrali

[McLarenPP]

dve pocitadla si myslim, ze nebudu.. to sme nebrali

a polynom zegalkina sme brali? alebo prevod do algebry janova? A tiez bolo na prvom termine..

[ApokalypS]

ako tak pozeram poznamky z prednasok, tak obe tieto veci spomenute boli..

[badi]

ked som cital minulorocne forum, tak som si vsimol jednu zaujimavost - minuly rok mali prvu skusku 5.1, a ake mali otazky? Tie iste, co boli tohto roku na prvom termine. Mozno nahoda, mozno nie, kazdopadne velmi zaujimave. A na druhy termin bolo vlani nahlasenych malo ludi (14), z toho prislo len 11 a mali len 1 skupinu -
Otazky:
1.halting problem + dokaz + univerzalny turingov stroj
2.Dijkstrova algebra
Priklady:
1. stroj s 2 pocitadlami (a na 2n; b na n; c na n )
2. je dany bezkontextovy jazyk L1, jazyk L2=(a1a4a7...a3k+1; k je vacsie rovne 1, ai patri L1)
    a trebalo dokazat, ze L2 je tiez bezkontextovy jazyk

Takze ked sa teraz este 2 ludia odhlasia, je celkom mozne, ze to bude v stredu vyzerat rovnako

hmm .. to nie moc dobre otazky .. ani jednu by som nevedel

tak k HALTING problem mu napisem toto :
"pretoze Ti sa nakoniec zastavi, univTS sa nakoniec zastavi a urci, ci Ti akceptuje xi alebo nie. V kazdom pripade sa T zastavi, pricom akceptuje xi v pripade, ze Ti ho nezakceptuje a neakceptuje xi, ak ho Ti akceptuje."
som zvedavy ci to pochopi

[Pribina]

ako tak pozeram poznamky z prednasok, tak obe tieto veci spomenute boli..

Spomenute boli aj pocitadla

[ApokalypS]

hej? kedy?

[Pribina]

TS s ohraniceniami

[DeNaTuReMaN]

sa pripajam k emigrantom z 13 teho, som robil chujoviny a neucil sa heh

[ppt]

Pls, mozete mi helpnut s nasledujucimi prikladmi?

1.priklad (ci spravne chapem):
sekvencne zobrazenie {0,1,2}*-->{p,n} ci je realizovatelne sekvencnym automatom
-tu sa berie, ze na vystupe je bud P alebo N (podla toho ci pocet niektoreho vstupneho symbola je parny alebo neparny)-a teda chyba v zadani, ktory symbol pocitame?

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?

5.priklad:
stroj s 2 pocitadlami (a na 2n; b na n; c na n )
-to je niekde vyriesene v skriptach alebo kde?


Je toho trosku viac, ale urcite to pomoze aj ostatnym. Tak ak sa niekto najde, kto chape niektorym z vyssieuvedenych prikladov, tak dajte pls echo
Diky moc.

[McLarenPP]

Pls, mozete mi helpnut s nasledujucimi prikladmi?

1.priklad (ci spravne chapem):
sekvencne zobrazenie {0,1,2}*-->{p,n} ci je realizovatelne sekvencnym automatom
-tu sa berie, ze na vystupe je bud P alebo N (podla toho ci pocet niektoreho vstupneho symbola je parny alebo neparny)-a teda chyba v zadani, ktory symbol pocitame?

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?

5.priklad:
stroj s 2 pocitadlami (a na 2n; b na n; c na n )
-to je niekde vyriesene v skriptach alebo kde?


Je toho trosku viac, ale urcite to pomoze aj ostatnym. Tak ak sa niekto najde, kto chape niektorym z vyssieuvedenych prikladov, tak dajte pls echo
Diky moc.

pr.1: vystup je "a", ak N2(xi) mod3 = 0 (pocet dvojek na vstupe modulo 3 = 0), a "n" v opacnom pripade.
Vstup je {0,1,2}* -> {a,n}*
(takto vyzeralo znenie prikladu pred rokom, toto tohtorocne bude asi len zle prepisane)

pr.2: riesi sa vraj sekvencnym automatom, rovnako ako priklad 4, ale nerozumiem im, zhanam niekoho kto to vypocita.

pr.3: toto som nikde nenasiel

pr.4  link na obrazok http://img141.imageshack.us/i/sekvencnystrojwv8.jpg/
este v tom obrazku maju chybat prechody:
b/ab z q0 do q1
a/lamba z q3 do q3
ale nerozumiem tomu prikladu

pr.5: nasiel som na fore takuto spravu:

"priklad sa vypocita presne tak, ako s dvoma zasobnikmi a potom sa na 2. a 3. mieste prepisu acka a bcka na velke Bcka.. napr. pri 2 zasobnikoch mas
(q2,(c,a,b),(c,B,b),q2,(R,L,L)) a ta ista instrukcia sa pri 2 pocitadlach zmeni na
(q2,(c,B,B),(c,B,B),q2,(R,L,L))"

[McLarenPP]

ppt: ten 4. priklad som si zmylil, na tom linku je trochu ine znenie.

inak aktualny stav - 15/25

[badi]

McLarenPP
ak mas vypocitane tie priklady co si myslis ze budu, mozes mi to prosim ta sfotit a hodit niekde na net ?
lebo ja mam v tom cisto chaoz :-(

[Pribina]

pr. 5 (moja verzia nehovorim ze spravna) :


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), q0, (R,R,-)
q0, (b,B,B), (b,B,B), q1, (R,-,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(preskrtnute),Z,Z), (s(preskrtnute),Z,Z), qF, (-,-,-)

tak zrucnejsi ludia skuste sa na to pozriet ci moze byt a ked ne opravte.

EDIT: priklad je a^2n b^n c^n som zabudol

[McLarenPP]

McLarenPP
ak mas vypocitane tie priklady co si myslis ze budu, mozes mi to prosim ta sfotit a hodit niekde na net ?
lebo ja mam v tom cisto chaoz :-(

praveze nemam este vypocitane, zatial som sa venoval len teorii, a z prikladov som prepocital iba asi polovicu tych z TI-priklady.pdf. Ale ked budem mat vypocitane tie skuskove priklady zajtra, tak ich sem mozem hodit, ked to uz neurobi niekto skor, za co by som bol vdacny.

[badi]

no ja sa spolieham ze tvoja teoria DEJA VU sa naplni :-) inak nic z toho ...

[Final_Destructer]

poprosil by som niekoho, kto si robil poznamky, aby napisal, ktore dokazy sa robili na prednaske, lebo sa da cakat, ze tym sa pripisuje vaha.