Author Topic: Teoreticka informatika  (Read 157599 times)

Pribina

  • Sr. Member
  • ****
  • Posts: 297
  • Kapitan Spok
    • View Profile
Re: Teoreticka informatika
« Reply #525 on: 12.01.2010, 23:36:10 »
By ma skor vyhodil :D
plllllp prepinan kapitan Spok

Miro

  • Jr. Member
  • **
  • Posts: 64
    • View Profile
Re: Teoreticka informatika
« Reply #526 on: 13.01.2010, 00:36:11 »
zajtra sa hlasim aj ja .. nech nas Cila sprevadza :DD .. plllp

johnyo13

  • Hero Member
  • *****
  • Posts: 629
  • I can stand my own ground...
    • View Profile
Re: Teoreticka informatika
« Reply #527 on: 13.01.2010, 02:28:40 »
uz mam znamku v maise!
☼Ѿ☼ ... ☼Ѿ☼

badi

  • Full Member
  • ***
  • Posts: 170
  • G ( . )( . ) GLE => Silicony Valery
    • View Profile
Re: Teoreticka informatika
« Reply #528 on: 13.01.2010, 02:51:03 »
uz mam znamku v maise!

AJ JA CHCEM :)
Som rýchly ako Intel, lebo iba hádam, ale jedinečný ako AMD, keďže to viem aj zdôvodniť.

popko

  • Newbie
  • *
  • Posts: 41
    • View Profile
Re: Teoreticka informatika
« Reply #529 on: 13.01.2010, 02:57:10 »
Odhlasujem sa z terminu 15.1. do 2 hodin.
S tym kto mi skor napise sa dohodnem na presnom case mojho odhlasenia.

EDIT: Uz sa stalo
« Last Edit: 13.01.2010, 04:51:47 by popko »

Payne

  • Sr. Member
  • ****
  • Posts: 408
    • View Profile
Re: Teoreticka informatika
« Reply #530 on: 13.01.2010, 04:57:04 »
([q,B],a,B,[q,a],R) - cize pamata si "B", na vstupe je "a", zapise tam "B" a pamata si "a" a posunie sa doprava
([q,a],b,a,[q,b],R) - pamata si "a", na vstupe je "b", zapise tam "a" a pamata si "b" a posunie sa doprava
([q,a],B,a,[q,B],R) - (na konci retazca) pamata si "a", na vstupe je "B", zapise tam "a" a pamata si "B" a posunie sa doprava
([q,B],a,a,[q,B],L) - a toto je naco ?
([q,B],B,B,[p,B],R) - a teraz len skontrolujem, ze je koniec retazca a prejdem do finalneho stavu "p"

je to tak ? a potom preco ked si pamatam "b" tak uz nie je pre nho dalsia instrukcia  ? ... napriklad ([q,b],a,b,[q,a],R) ... som z toho jelen :)

toto co sa posuvas do lava tak si nie som isty ,ale bolo tam cosi take ze ked posunies to na paske tak sa vratis asi na zaciatok,ale neviem urcite

a to ze tam neni instrukcia pre b tak to je asi chyba,alebo neviem

cely princip je v tom ze si zapamatas co si prave precital a zapises co si mal zapamatane 

treba to vysvetlit presne jak to ma byt, ci uz nie? ja som odpisoval a neviem ze co neposlalo...

mio

  • Newbie
  • *
  • Posts: 28
    • View Profile
Re: Teoreticka informatika
« Reply #531 on: 13.01.2010, 05:23:24 »
([q,B],a,B,[q,a],R) - cize pamata si "B", na vstupe je "a", zapise tam "B" a pamata si "a" a posunie sa doprava
([q,a],b,a,[q,b],R) - pamata si "a", na vstupe je "b", zapise tam "a" a pamata si "b" a posunie sa doprava
([q,a],B,a,[q,B],R) - (na konci retazca) pamata si "a", na vstupe je "B", zapise tam "a" a pamata si "B" a posunie sa doprava
([q,B],a,a,[q,B],L) - a toto je naco ?
([q,B],B,B,[p,B],R) - a teraz len skontrolujem, ze je koniec retazca a prejdem do finalneho stavu "p"

je to tak ? a potom preco ked si pamatam "b" tak uz nie je pre nho dalsia instrukcia  ? ... napriklad ([q,b],a,b,[q,a],R) ... som z toho jelen :)

toto co sa posuvas do lava tak si nie som isty ,ale bolo tam cosi take ze ked posunies to na paske tak sa vratis asi na zaciatok,ale neviem urcite

a to ze tam neni instrukcia pre b tak to je asi chyba,alebo neviem

cely princip je v tom ze si zapamatas co si prave precital a zapises co si mal zapamatane 

treba to vysvetlit presne jak to ma byt, ci uz nie? ja som odpisoval a neviem ze co neposlalo...
ked budes taky dobry este vzdy mi to pomoze :) ... dik

Payne

  • Sr. Member
  • ****
  • Posts: 408
    • View Profile
Re: Teoreticka informatika
« Reply #532 on: 13.01.2010, 05:59:51 »
no finta je v tom ze a ani b niesu priamo vstupne symboly, ale povedal by som mnozina symbolov 0 a 1, ked teda sa pise a abo b tak sa mysli v ramci oboch ze kazde z nich moze byt 0 alebo 1

Preco teda davame aj a aj b? no davaju sa len vtedy ak potrebujes rozlisit medzi nimi, t.j.:
([q,B],a,B,[q,a],R) zmanena ak som v stave q a nic nemam zapametane, na vstupe je a (teda prakticky 0 alebo 1), prepisem vstup Bckom, zapametam vstup a co je 0 abo 1 (teda ked si vsimnes tak toto je instrukcia aj pre 0 aj pre 1) a idem doprava

([q,a],b,a,[q,b],R) znamena ak som v stave q a mam zapametane a (moze byt 0 abo 1) a na vstupe je b (tiez moze byt aj 0 aj 1 ale nijako to od a nezavisi) prepisem to ackom (teda tou 0 abo 1 ktora bola zapametana), potom idem do stavu q a zapametam b(cize tu 0 abo 1 ktora bola na vstupe)

teda mam 0 alebo 1, ale potrebujem ich od seba rozlisit ktora je ktora

ty si pisal, ze
Quote from: mio
([q,B],a,B,[q,a],R) - cize pamata si "B", na vstupe je "a", zapise tam "B" a pamata si "a" a posunie sa doprava
to nemoze byt dobre, lebo potom by si mohol zacinat len symbolom a, bckom by sa nemohlo zacinat

dalsia vec je ze kuknes na povahu instrukcii a v nich prve stavy tak tam mas len [q,a] alebo [q,B], cize ty by si podla teba potom ani nemohol vobec odpametavat symbol b

dufam ze je to zrozumitelnejsie, a tam ked si uvedomis tak ide len o to, ze sa to takto pise aby si mal menej instrukcii, teda tota druha co pisem, tak by si mohol mat odpametane 2 symboly a dalsie 2 na vstupe => len jedna instukcia namiesto 4 a to len ked uvazujes ze mas 2 vstupne symboly keby ich bolo viac tak este viac usetris

cize aj dalej vsetko tak treba rozmyslat a davat na to bacha



pomoct ti to pomoze sak TIcko nieje az taka strasne vec, isto mi to viac davalo zmysel jak stavba
« Last Edit: 13.01.2010, 06:09:42 by Payne »

Casso

  • Full Member
  • ***
  • Posts: 216
  • XSS locator
    • View Profile
    • casso <at> ic <at> cz
Re: Teoreticka informatika
« Reply #533 on: 13.01.2010, 13:16:27 »
Today is day D. Fear in my eyes! bu

LONEr

  • Full Member
  • ***
  • Posts: 202
    • View Profile
Re: Teoreticka informatika
« Reply #534 on: 13.01.2010, 16:02:56 »
Caute, kde najdem odpovede na otazky :
-metody konstruovania TS -> PAMATANIE STAVU , M-STOPOVY
-POSTOV problem, Rozhodnutelnost / nerozhodnutelnost
-Uzaverove operacie nad jazykom
(to su otazky z minuleho roka)
+ odkial tahate SHudak_TIuvod.pdf ? nie je to na kane.sk

K5

  • Newbie
  • *
  • Posts: 17
    • View Profile
Re: Teoreticka informatika
« Reply #535 on: 13.01.2010, 16:25:10 »
http://hornad.fei.tuke.sk/~korecko/storage/SHudak_TIuvod.pdf

tamto som nasiel napr. aj v eminkinych poznamkach..

McLarenPP

  • Jr. Member
  • **
  • Posts: 88
    • View Profile
    • Stop pravici!
Re: Teoreticka informatika
« Reply #536 on: 13.01.2010, 16:40:10 »
no, takze moja prognoza sa naplnila a boli presne tie iste otazky, ako pred rokom na druhom termine:

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

ale boli 2 skupiny, druha vsak mala tiez nieco z toho, co je v tom subore s minulorocnymi otazkami.
Korecko ale vravel nieco o tom, ze asi vymyslia aj nove skupiny s otazkami.

Killian

  • Full Member
  • ***
  • Posts: 191
    • View Profile
Re: Teoreticka informatika
« Reply #537 on: 13.01.2010, 16:59:14 »
 bu bu Skoda, ze som sa prehlasil na 15.1. a necital tu tvoju prognozu. Vie niekto, ake otazky nasledovali na dalsom termine minuly rok? Nepredpokladam, ze tretikrat daju to iste, ale pre istotu...

Mao

  • Sr. Member
  • ****
  • Posts: 392
    • View Profile
Re: Teoreticka informatika
« Reply #538 on: 13.01.2010, 16:59:55 »
Podla zakulisnych informacii druha skupina mala tieto otazky  :)
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
(tha alebo nieco v tom zmysle ak som neprepisal vsetko uplne presne)
« Last Edit: 13.01.2010, 17:03:21 by Mao »

ppt

  • Hero Member
  • *****
  • Posts: 935
    • View Profile
Re: Teoreticka informatika
« Reply #539 on: 13.01.2010, 17:06:47 »
Potvrdzujem Maovu spravu.

Killian

  • Full Member
  • ***
  • Posts: 191
    • View Profile
Re: Teoreticka informatika
« Reply #540 on: 13.01.2010, 17:07:02 »
Tak ta druha bola podla mna ovela tazsia, aspon ze to uz asi neda na dalsom termine  ;D.

Killian

  • Full Member
  • ***
  • Posts: 191
    • View Profile
Re: Teoreticka informatika
« Reply #541 on: 13.01.2010, 17:19:43 »
Mam otazku k zatvorkovym vyrazom, konkretne tu je z minuleho roku aj s pokecom:
Quote
ten zatvorkovy priklad bol na 4 riadky, myslim... je to aj v tej zbierke prikladov na ZI, co sme mali.... tam, kde su priklady na zasobnikove automaty...
nedeterministicky by to vyzeralo takto:
(q0,[,Z,q0,[Z)
(q0,[,[,q0,[[)
(q0,],[,q0,λ)
(q0,λ,Z,qf,Z)
no a prvy a posledny riadok hovoria, ze sa moze rozhodnut, ze ci bude akceptovat alebo nebude, no a v determinizme ide hlavne o to, ze stale ma jednoznacne urcene, co dalej..., takze aby to bolo deterministicke, je potrebne zmenit stav... to je cele, takze:
(q0,[,Z,q1,[Z)
(q1,[,[,q1,[[)
(q1,],[,q1,λ)
(q1,λ,Z,qf,Z)

To prve je preco nedeterministicke? Ved ziadne dve instrukcie nemaju rovnaky stav a necitaju rovnaky vstup - teda automat sa nikde nerozhoduje. To je podla mna deterministicke?


Mao

  • Sr. Member
  • ****
  • Posts: 392
    • View Profile
Re: Teoreticka informatika
« Reply #542 on: 13.01.2010, 17:26:59 »
(q0,[,Z,q0,[Z)
(q0,λ,Z,qf,Z)
Kvoli tomuto, lambda neznamena v tommto pripade, ze bol precitany prazdny vstup, ale to ze sa necital, teda automat sa moze rozhodnut ci bude citat vstup podla prvej instrukcie alebo nebude citat vstup a prejde do qf

Killian

  • Full Member
  • ***
  • Posts: 191
    • View Profile
Re: Teoreticka informatika
« Reply #543 on: 13.01.2010, 17:59:32 »
Okej, dalsia taka otazka:

Quote
dokazat ze jazyk  L = {a0n1n} U {0n12n} je deterministicky bezkontextovy

Treba tu ratat s tym, ze moze prist prve slovo z prveho jazyka a druhe slovo za nim z druheho jazyka a rozpozna to? Alebo len, ze bud pride na zaciatku a a podla toho sa rozhodnut, ako to budeme rozpoznavat? Lebo v eminkinych je to spravene tak, ze ma aj pre pripad ze idu oba po sebe...

Payne

  • Sr. Member
  • ****
  • Posts: 408
    • View Profile
Re: Teoreticka informatika
« Reply #544 on: 13.01.2010, 19:43:25 »
Eminka to tak ma spravene, zle ja som mal len ze bud jedno abo druhe a strhli mi len jeden bod tak neviem...

DeViLvs

  • Full Member
  • ***
  • Posts: 222
  • f1.yweb.sk
    • View Profile
Re: Teoreticka informatika
« Reply #545 on: 13.01.2010, 20:27:59 »
Kto uz ma TIcko spravene? potreboval by som nieco, odmena ista, PM pls
« Last Edit: 13.01.2010, 20:31:27 by DeViLvs »

Casso

  • Full Member
  • ***
  • Posts: 216
  • XSS locator
    • View Profile
    • casso <at> ic <at> cz
Re: Teoreticka informatika
« Reply #546 on: 13.01.2010, 22:40:24 »
to bol bullshit... otazky som mal rovnake ako mclarenPP, cca 30 minut ma skusal ( od TS, UTS, problem zastavenia..., cez algebry algoritmov az po funkcionalnu uplnost Bool. funkcii...) a skoncil som s D63 stastny ako blbcha... off, ide sa slavit

mio

  • Newbie
  • *
  • Posts: 28
    • View Profile
Re: Teoreticka informatika
« Reply #547 on: 13.01.2010, 23:17:13 »
vie niekto ako dokazem, ze jazyk L={a^i b^j c^k|i<>j alebo j<>k} je nedeterministicky bezkontextovy ? dakujem ...

badi

  • Full Member
  • ***
  • Posts: 170
  • G ( . )( . ) GLE => Silicony Valery
    • View Profile
Re: Teoreticka informatika
« Reply #548 on: 13.01.2010, 23:36:43 »
niektori
to bol bullshit... otazky som mal rovnake ako mclarenPP, cca 30 minut ma skusal ( od TS, UTS, problem zastavenia..., cez algebry algoritmov az po funkcionalnu uplnost Bool. funkcii...) a skoncil som s D63 stastny ako blbcha... off, ide sa slavit

niektori tolko stastia nemali :(
aj ked body som mal na E tak som odisiel s FX :),
Som rýchly ako Intel, lebo iba hádam, ale jedinečný ako AMD, keďže to viem aj zdôvodniť.

pepco

  • Guest
Re: Teoreticka informatika
« Reply #549 on: 13.01.2010, 23:42:09 »
sak on proste Ecka nedaval... dnesna bilancia 5z15 nespravili, ale cely den tam cakat jak lools...

P.S.: Korecko opravoval priklady a vsetko odovzdal Hudakovi, kde si nas vsetkych 15 pekne preveril :) dojem z neho pozitivny, len no niekedy sa pyta take no... ale da sa v pohode
« Last Edit: 14.01.2010, 00:02:40 by pepco »