Teoretická informatika

puty · 10.01.2011, 22:54:50

nazdar,

vedel by niekto vysvetlit, co konkretne treba vediet k: Nerozhodnuteľnosť problému zastavenia TS.

teda okrem toho ze neexistuje univerzalny TS ktory by vedel rozhodnut ci sa lubovolny TS na nejakom vstupe zastavi alebo nie. jedine co som k tomu nasiel je obrazok so 4 obdlznikmi a vela sipkami.. ale co nam chcel autor obrazku povedat ??

vdaka

kamelot · 10.01.2011, 23:08:35

k tomu HP, mozno este z hopcrofta&ullmana nejak v skratke povedat ze co tie U a H robia...

Cheiftan · 11.01.2011, 00:31:20

ja mam skusku stvrtok, ale mam taky pocit ze z toho bude velky FX

ucite sa aj take veci ako: KSA, zasobnikove aut., Bezkontextove jazyky ( Chomskeho a Greibachovej normalny tvar) - boli otazky na tie temy aj minuly rok?

alebo sa zameriavate na Turinga a Algebru algoritmov?

uz sa mi z toho zacina sibnut

ballky · 11.01.2011, 01:19:11

nemate niekto riesenie na tento priklad ?

priklad : 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

tusec · 11.01.2011, 04:26:09

Pokial je ten jazyk bezkontextovy tak musi byt riesitelny zasobnikovym automatom (deterministickym) z toho vyplyva ze by sa k nemu aj mal dat zostrojit. Ak tam bolo a1 a4 ... tak by to mohlo byt nieco ako:
L={a^3k+1|a patri L1 k <=1 }
(q0,a,Z,q1,aZ)
(q1,a,a,q1, aa)
(q1,aa,Z,qf,Z)
Neviem ci je to dobre.

domino3d · 11.01.2011, 04:51:41

Quote from: Cheiftan on 11.01.2011, 00:31:20
ja mam skusku stvrtok, ale mam taky pocit ze z toho bude velky FX

ucite sa aj take veci ako: KSA, zasobnikove aut., Bezkontextove jazyky ( Chomskeho a Greibachovej normalny tvar) - boli otazky na tie temy aj minuly rok?

alebo sa zameriavate na Turinga a Algebru algoritmov?

uz sa mi z toho zacina sibnut

aj mne z toho už trtká, nie si sám
turinga, alg, aj secko ostatne

snad budem daco vediet...

stamperlik · 11.01.2011, 06:43:19

Quote from: puty on 10.01.2011, 22:54:50
nazdar,

vedel by niekto vysvetlit, co konkretne treba vediet k: Nerozhodnuteľnosť problému zastavenia TS.

teda okrem toho ze neexistuje univerzalny TS ktory by vedel rozhodnut ci sa lubovolny TS na nejakom vstupe zastavi alebo nie. jedine co som k tomu nasiel je obrazok so 4 obdlznikmi a vela sipkami.. ale co nam chcel autor obrazku povedat ??

vdaka

Skus pozriet http://sk.wikipedia.org/wiki/Probl%C3%A9m_zastavenia

domino3d · 11.01.2011, 16:12:30

TI2I.6 : Turingovsky-vypocitatelne funkcie. Definicia a ilustracia na priklade.

TI2II.6 : Algebra logiky a problem funkcionalnej uplnosti.
Algebra boolovskych funkcii (BF) a problem funkcionalnej uplnosti systemov BF.

Priklad
Previest do algebry Janova z Dijkstru.

radix · 11.01.2011, 16:41:35

za hodinu to zacne

markus · 11.01.2011, 16:43:09

a za 30 sekund skonci?

romeo · 11.01.2011, 21:08:09

Mna by zaujimalo ci sa da s tym ratat ze p. Hudak na stvrtkovom termine nebude davat tie otazky ktore boli zatial na tych 2 terminoch. Este ma z coho vyberat

domino3d · 11.01.2011, 21:49:42

mám Cicimbus

C-75
jak ostatny? radix, cory... ?

MackoZlesa · 11.01.2011, 21:51:25

Quote from: romeo on 11.01.2011, 21:08:09
Mna by zaujimalo ci sa da s tym ratat ze p. Hudak na stvrtkovom termine nebude davat tie otazky ktore boli zatial na tych 2 terminoch. Este ma z coho vyberat

neda sa s tym vobec ratat. Pred dvoma rokmi presne takto ojebabral mojho brata, ktory isiel tiez na v poradi tretiu skusku a myslel si, ze otazky z prvych dvoch terminov nebudu. A boli presne tie otazky, co boli na prvych dvoch terminoch

MackoZlesa · 11.01.2011, 22:24:49

ako vlastne vyzera odpoved na otazku, s ktorou je Hudak ako tak spokojny? musia tam byt uvedene ku vsetkemu dokazy, tak ako je to v jeho skriptach?

radix · 11.01.2011, 22:56:37

WUAAAAAAAA TOTO BOL TURINGOVSKY MASAKER NEKONECNOU PASKOU!!!

uspesnost 12 zo 14(1neprisiel na vyhodnotenie)

Quote from: Domino3D on 11.01.2011, 21:49:42
mám Cicimbus C-75
jak ostatny? radix, cory... ?

ja som mu ku druhej otazke nepovedal spravne definiciu ohladom subalgebrier a max. sub, tak mi dal -20b takze iba D65

thom · 11.01.2011, 23:03:55

Quote from: radix on 11.01.2011, 22:56:37
WUAAAAAAAA TOTO BOL TURINGOVSKY MASAKER NEKONECNOU PASKOU!!! uspesnost 12 zo 14(1neprisiel na vyhodnotenie)

Hudak neprisiel a kto skusal?

?

radix · 11.01.2011, 23:05:35

hudak skusal kazdeho osobne

thom · 11.01.2011, 23:08:00

aha 1 neprisiel, pardon. tak ako to prebiehalo???bol zhovievavy alebo ako??/

radix · 11.01.2011, 23:12:47

tak skoro vsetci sme mali priklad na full a teoriu myslim ze tiez potom to uz bolo o tom co sa koho z tej pisomky opyta a potom daval za to body dole

santa99 · 11.01.2011, 23:54:02

Dnes bolo super , len to cakanie.... Neviem si predstavit ze na termine bude 30 ludi , ti posledni zinfarktuju ...

puty · 12.01.2011, 02:03:41

to bola dnes len jedna skupina?

piton · 12.01.2011, 02:04:10

jj, ale boli v dvoch miestnostiach po 7 ludi

libra · 12.01.2011, 02:19:38

Quote from: Jerryh on 09.01.2011, 19:53:06
ludia by sa neodhlasovali keby niekto nedal na poslednu chvilu jeden termin presne kedy je/tesne pred skuskou z TI

Ludia by sa odhlasovali aj keby mali iba tu jedinu skusku a rok na ucenie sa. Tak to vzdy bolo, je a zial, aj bude...

cory · 12.01.2011, 03:58:35

no dnes to bolo aj dobre aj zle. Najprv to zle: CAKANIE................ Nohy ma budu este dva dni boliet z toho preslapovania. Som urobil minimalne desat kilometrov. Uz som mal vychodeny chodnik na kachlickach na piatom poschodi.

A to dobre: profesor Hudak je fajn clovek. Aspon ja som mal z neho taky pocit. Vobec ziadne zakernosti. Pytal sa len na to co si zabudol napisat alebo co si do pisomky zle napisal. Ked si tomu nechapal co sa pytal, kludne sa treba opytat ako to mysli..... Samozrejme ze skusku zadarmo nedal.

Tos vsio. Vela stastia vsetkym a netreba sa bat ale treba sa ucit

Cheiftan · 12.01.2011, 16:30:19

caute,

co znamena presne, ze sekvencne zobrazenie je bez predikcie ?

ja to chapam, ze pre vypocet R(t) neptrobujem hodnotu S(t+1)