Teoreticka informatika

[zuzanka]

neviem, sa potvrdilo, ze hudak je fakt nedeterministicky....pri nom nikdy nevies....

[DeViLvs]

ma niekto nejakeho tipa, co bude zajtra?

[sri]

na predchadzajucom termine sa mi zda ze boli otazky z prveho terminu, takze teraz by som tipol ze budu z druheho

1.Halting problem + dokaz + univerzalny turingov stroj
2.Dijkstrova algebra
Priklady:
1. Turingov 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

alebo

T1 Uzaverove operacie. Uzaverove operacie nad jazykom.
   Elementerne uzaverove operacie nad triedami jazykov
T2 Algebra: baza, poly mono druhova algebra. Alegebraicke systemy. Logicko funkcne modely.
P1 Dokazte ze zobrazenie Fi je realizovatelne na nejakom KA
Fi = "a" ak N2(xi) mod 3 = 0
"n" inak.
Vstup je {0,1,2}* -> {a,n}*
P2 Zostrojte algoritmus Dijstra pre triedenie postupnosti pouzitim Minimalneho prvku zostupne

ale neriadte sa tym pre istotu

[puq]

tu sa uz neda tipovat fakt ale PKP este nebol...a dalej 3x po sebe neverim ze da algebru logiky a metalgebru...cize cakajte Algebry: bázy, mono- a poly- druhové algebry.  Algebraické systémy, potom dijkstrovu algebru moze dat...a z prvych okruhov tipujem ze da univerzalny TS + halting a mozno zajebe nerodove ekvivalencie a daco k tomu

edit: no trafil som sa k tomu co napisal kolega vyssie cize je to realne no

[sri]

tu sa uz neda tipovat fakt ale PKP este nebol...a dalej 3x po sebe neverim ze da algebru logiky a metalgebru...cize cakajte Algebry: bázy, mono- a poly- druhové algebry.  Algebraické systémy, potom dijkstrovu algebru moze dat...a z prvych okruhov tipujem ze da univerzalny TS + halting a mozno zajebe nerodove ekvivalencie a daco k tomu

edit: no trafil som sa k tomu co napisal kolega vyssie cize je to realne no

bodaj by sme mali pravdu, to co si napisal su otazky ku ktorym by som vedel aspon pipnut

[TradeMark]

Kde najdem riesenia tych prikladov? Napr ten turing s pocitadlami, alebo ten algoritmus pre triedenie? Dik

[buhehe]

tie pocitadla su tu a to druhe by som aj rad vedel

[TradeMark]

fuuuha 3.2 aj 5.2 full... zajtra posledny pokus evidentne

[.dusan.]

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

- to vyriesim ze pre oba zostrojim ZA? Alebo ako?

[Mao]

zostrojis sekvencny stroj, ten ma na vstupe slova jazyka L1, a  na vystup bude na ich zaklade davat slova jazyka L2

[SSPPYY]

zostrojis sekvencny stroj, ten ma na vstupe slova jazyka L1, a  na vystup bude na ich zaklade davat slova jazyka L2

No to by ma zaujmalo ako ked o L1 vies tak akurat ze je bezkontextovy.
Podla mna to staci dokazat pomocou uzavretosti na substitucii.

[sri]

tiez som pocul ze sa to riesi cez sekvencny (EDIT: vraj to tak Korecko vyzadoval na skuske), len nemam velmi sajn ako O L1 vieme aj ako vyzera ci len ze je bezkontextovy?

[carin]

zostrojis sekvencny stroj, ten ma na vstupe slova jazyka L1, a  na vystup bude na ich zaklade davat slova jazyka L2

No to by ma zaujmalo ako ked o L1 vies tak akurat ze je bezkontextovy.
Podla mna to staci dokazat pomocou uzavretosti na substitucii.

Dokaz pomocou uzavretosti ti skor neprejde ako prejde.. myslim tiez sekvencny stroj, a mimochodom mas tam take nieco ai patri do L1...

[.dusan.]

Uz som to nasiel mali sme to na cviku a robilo sa to cez ten sekvencny stroj.

[Viper_No1]

mohol by si to prepisat a naskenovat a upnut to tu??

[.dusan.]

Jasne : takto som to nasiel v zosite sice neviem uplne presne ako sa tam dostali tie S-ka ale je to ten priklad

[letolto]

Ja som to na skuske riesil sekcencnym strojom, ale nevedel som to.... (0 bodov). Na ustnej sa ma prof. Hudak spytal, ci viem spravne riesenie... stacilo k tomu spravit det. ZA!!!!. Pribina zas tam napisal 2-3 vety o subsitucie a bezkont. jazyk. a sekvenc. strojoch (abo nieco podobne) a ked sa nemylim, tak to tiez stacilo...
ale ak viete, tak mozete to robit aj cez sekv. stroje

Drzim palce vsetkym dnes

[SSPPYY]

Jasne : takto som to nasiel v zosite sice neviem uplne presne ako sa tam dostali tie S-ka ale je to ten priklad

No tak bez riadneho zadania sa to tazko robi. Z tohoto riesenia by som povedal ze L1 je jazyk pozostavajuci zo slov Si (ja by som to skor oznacil ako ai aby to bolo pochopitelne) a jazyk L2 pozostava len z niektorych slov z L1, takych ze slovo z L2 sa generuje len pre kazde druhe prichodzie slovo z L1.

Potom ten priklad co bol na skuske je to iste len tam je pre kazde tretie slovo, teda automat by mal mat 3 stavy.

[buhehe]

hmm to uz su vsetci z dneska ozraty ze este nikto nedal report?
jedna skupina pre vsetkych, bolo nas na skuske 16!!! z prihlasenych 25

1. Metody konstrukcie TS: odpamatavanie do stavov - princip a priklad, m-stopove TS - princip a priklad
2. Dijkstrova algebra. Kriterium funkcionalnej uplnosti v Dijsktrovej algebre.

I. Urcit ci je sekvencne zobr. Fi: {0,1}* -> {o,1}* realizovatelne KSA yi = 1 ak N1(xi) = N0(xi), inak 0
II. Spravit polynom Zegalkina (uz si napamatam presne zadanie, snad dakto doplni)

Inac dnes bola vysoka uspesnost...predomnou vsetci (6 ci 7) spravili. Ujo mal dobru naladu a vyzeralo to ze chce dat prejst kazdemu.

[antikleia]

Nerozmiem, tych 9 ludi co blokovali miesto niekomu inemu sa nedostavili lebo... ?

[buhehe]

dobra otazka...jednoducho neprisli

[antikleia]

Hej... podarene... Ja tu drzim miesto jednemu chalanovi aby mohol ist na opravak lebo je vsetko uplne obsadene, moji spoluziaci sa stresuju co ked nespravia skusku lebo uz nie su volne terminy a niekto sa jednoducho prihlasi a nepride... Nech ziju egoisti...

[Ing. nemtom]

to budu taky co drzia miesto kamosom, kamos spravi a dalej maju v prdeli aby sa odhlasili

[TradeMark]

Ok ja som dnes mal:

1. Metody kontrukcie turingovych strojov (2 metody popisat - m-paskovy a este tie stavy v RJ)
2. Dijkster

Priklady:

1. Urcit ci je dana haluska realizovatelna konecnym automatom N0=N1
2. Zegelkin

Za priklady dokopy 4 body (Zegelkina som nemal, v prvom som urobil fatalnu chybu). Za holandana mi dal 5 bodov a za turinga 15. Zratal a vychadzalo 41. Ta sa ho pytam ze preco iba 15 ked som tam mal vsetko. Tak sa na to pozrel a opytal sa ma ci by som vedel zostrojit TS pomocou zasobnika, povedal som ze hej - pomocou dvoch. Pridal 10 bodov, E51 vo finale.

Btw. dnes nejako rozdaval tie skusky, ja som siel prvy a pomne dalsi dvaja tiez urobili. V kazdom pripade GL Korecko spominal ze na dalsie terminy budu uz ine otazky (tieto bol imho dooost lahke)

[Padres]

Tak to verim ze ti co drzali miesta dnesnym, ktori spravili, sa aspon poodhlasuju z nasledujucich terminov...