Author Topic: Teoreticka informatika  (Read 155926 times)

Killian

  • Full Member
  • ***
  • Posts: 191
    • View Profile
Re: Teoreticka informatika
« Reply #50 on: 26.11.2009, 22:28:02 »
Tak uvidime co to bude  :).

Pre pobavenie, Turingov stroj postaveny z Lega  :)
http://www.youtube.com/watch?v=cYw2ewoO6c4&feature=fvst

trek

  • Hero Member
  • *****
  • Posts: 568
  • cestu sme mali spolo?nú ale nohy ma bolia vlastné
    • View Profile
Re: Teoreticka informatika
« Reply #51 on: 26.11.2009, 22:35:44 »
cooooooooooooooooool :D:D:D:D:D:D:D:D:D:D:D

Casso

  • Full Member
  • ***
  • Posts: 216
  • XSS locator
    • View Profile
    • casso <at> ic <at> cz
Re: Teoreticka informatika
« Reply #52 on: 26.11.2009, 22:48:59 »
Tak uvidime co to bude  :).

Pre pobavenie, Turingov stroj postaveny z Lega  :)
Priznaj sa ze si googlil pri uceni a tak si sa k tomu dostal  :angel: ale peckove to je ;D ;D

ApokalypS

  • Hero Member
  • *****
  • Posts: 5801
  • apokalyps(a) sa mení..
    • View Profile
    • projekt k mojej diplomovke..
Re: Teoreticka informatika
« Reply #53 on: 27.11.2009, 00:32:55 »
No len opravak nebude, Hudak povedal  :).
to kedy povedal? ja som nic take nepostrehol..
80% mozgu človeka tvorí kvapalina, v mojom prípade brzdová..

CHCEM S5 :zuzka: STARY IS :zuzka: !!!!
http://www.tu-ke.com/forum/o-nicom/otvoreny-list-vedeniu-firmy-dupress-(dodavatel-mais)/

Killian

  • Full Member
  • ***
  • Posts: 191
    • View Profile
Re: Teoreticka informatika
« Reply #54 on: 27.11.2009, 01:20:50 »
Lalova citovala Hudaka na cvikach, povedal ze sme mali moznost ziskat dost bodov na zapocet aj bez zapoctovky (prednasky + aktivita = 18 a staci 16 tusim), kvoli tomu netreba opravnu.

Ludia mam otazku ku prikladu 4.4 z Plocicovych prikladov.
Code: [Select]
Navrhnite zásobníkový automat pre jazyk 1 = {x ∈ {a, b}∗,Na(x) = Nb(x)}

Spravne vyriesene to ma byt podla toho takto:
Code: [Select]
(q0, a,Z, q0, aZ)
(q0, a, a, q0, aa)
(q0, b, a, q0, ¸)
(q0, b,Z, q0, bZ)
(q0, b, b, q0, bb)
(q0, a, b, q0,lamb)
(q0, lamb, Z, q0, lamb)

Nechapem ako si vystacil iba  s jednym stavom q0. Pozrite si ten posledny krok "ak najdem lambda a zasobnik je prazdny, tak ostanem v stave q0 a dam lambda znak na zasobnik"? Kedy to skonci? Ako viem, ci uz bolo slovo skontrolovane... Nepojde to nejak donekonecna?
« Last Edit: 27.11.2009, 01:29:28 by Killian »

Casso

  • Full Member
  • ***
  • Posts: 216
  • XSS locator
    • View Profile
    • casso <at> ic <at> cz
Re: Teoreticka informatika
« Reply #55 on: 27.11.2009, 02:32:30 »
Nechapem ako si vystacil iba  s jednym stavom q0. Pozrite si ten posledny krok "ak najdem lambda a zasobnik je prazdny, tak ostanem v stave q0 a dam lambda znak na zasobnik"? Kedy to skonci? Ako viem, ci uz bolo slovo skontrolovane... Nepojde to nejak donekonecna?
Mnohe PDA, ktore sme mali v na cviku, si vystacili s jedinym stavom. tiez mi nieje jasna ta posledna instrukcia ale pda urcuje neakceptovanie retazca tym ze sa zastavi (nedefinovana trojica stav-paska-zasobnik)

milaninho

  • Jr. Member
  • **
  • Posts: 99
    • View Profile
Re: Teoreticka informatika
« Reply #56 on: 27.11.2009, 04:07:34 »
Quote
Uvidime, ja uz mam v pondelok  . Teraz pozeram do zasobnikovych automatov, tie deterministicke chapem ale nedeterministicke v niektorych pripadoch su nejake zaujimave (ako pri tom pripade s palindromom x.x^R, kde automat len tipne ze ci je v strede slova - takze realne ak zle odhadne stred slova tak skonci a nerozpozna to, alebo to nejako viackrat robi??  ).
co sa tyka toho nedeterminizmu je to tak ako spominal hore kolega.. prosste nedeterminizmus je o tom ze nevies presne ako zareagovat a preto si len tipnes.. potom bud krachnes, alebo ak je nejako implementovany navrat tak sa vies na to vetvenie vratit a skusit inu cestu(teda vsetky rozne moznosti a podla toho napokon prijmes alebo neprijmes slovo). ak som trepol nejaku somarinu tak ma kludne opravte:)

cepi

  • Sr. Member
  • ****
  • Posts: 268
  • chodia mravci ?
    • View Profile
Re: Teoreticka informatika
« Reply #57 on: 27.11.2009, 04:12:15 »
Nechapem ako si vystacil iba  s jednym stavom q0. Pozrite si ten posledny krok "ak najdem lambda a zasobnik je prazdny, tak ostanem v stave q0 a dam lambda znak na zasobnik"? Kedy to skonci? Ako viem, ci uz bolo slovo skontrolovane... Nepojde to nejak donekonecna?
Mnohe PDA, ktore sme mali v na cviku, si vystacili s jedinym stavom. tiez mi nieje jasna ta posledna instrukcia ale pda urcuje neakceptovanie retazca tym ze sa zastavi (nedefinovana trojica stav-paska-zasobnik)
takze ked sa zastavi a je daco v zasobniku tak slovo neakceptval, a ak sa zasobnik vyprazdni tak jo ?
som kto som vdaka palenke

Casso

  • Full Member
  • ***
  • Posts: 216
  • XSS locator
    • View Profile
    • casso <at> ic <at> cz
Re: Teoreticka informatika
« Reply #58 on: 27.11.2009, 04:17:23 »
Nechapem ako si vystacil iba  s jednym stavom q0. Pozrite si ten posledny krok "ak najdem lambda a zasobnik je prazdny, tak ostanem v stave q0 a dam lambda znak na zasobnik"? Kedy to skonci? Ako viem, ci uz bolo slovo skontrolovane... Nepojde to nejak donekonecna?
Mnohe PDA, ktore sme mali v na cviku, si vystacili s jedinym stavom. tiez mi nieje jasna ta posledna instrukcia ale pda urcuje neakceptovanie retazca tym ze sa zastavi (nedefinovana trojica stav-paska-zasobnik)
takze ked sa zastavi a je daco v zasobniku tak slovo neakceptval, a ak sa zasobnik vyprazdni tak jo ?
Jop presne tak, a nepozerajte sa na tie stroje tak realne. Su to abstraktne modely. Nedeterministicke varianty by ste hadam obcas ani na pc nenasimulovali

Killian

  • Full Member
  • ***
  • Posts: 191
    • View Profile
Re: Teoreticka informatika
« Reply #59 on: 27.11.2009, 07:08:29 »
Podla mna by tam ale mal byt aspon jeden prechod stavu, pretoze instrukcia:
(q0, lamb, Z, q0, lamb)
- podla mna to zoberie aj prazdny znak na zaciatku, teda dam mu pasku a bude tam jeden prazdny znak. Tak zasobnik je prazdny, som v q0 a dostanem sa na prazdny znak = automat skonci uspesne. Nie?

ApokalypS

  • Hero Member
  • *****
  • Posts: 5801
  • apokalyps(a) sa mení..
    • View Profile
    • projekt k mojej diplomovke..
Re: Teoreticka informatika
« Reply #60 on: 27.11.2009, 21:02:10 »
aj prazdne slovo je riesenie..

väcsinou sme davali, ze (q0, lamb, Z, qf, lamb); kde qf je finalovy stav
80% mozgu človeka tvorí kvapalina, v mojom prípade brzdová..

CHCEM S5 :zuzka: STARY IS :zuzka: !!!!
http://www.tu-ke.com/forum/o-nicom/otvoreny-list-vedeniu-firmy-dupress-(dodavatel-mais)/

Casso

  • Full Member
  • ***
  • Posts: 216
  • XSS locator
    • View Profile
    • casso <at> ic <at> cz
Re: Teoreticka informatika
« Reply #61 on: 28.11.2009, 17:43:47 »
aj prazdne slovo je riesenie..

väcsinou sme davali, ze (q0, lamb, Z, qf, lamb); kde qf je finalovy stav
Uz som si to dostudoval, Akceptovanie moze byt realizovane dvojako:
1. vyprazdnenim zasobnika (nahradenim symbolu Z symbolom "lambda")
2. Prechodom do finalneho stavu (Zvycajne qf)

Snow

  • Newbie
  • *
  • Posts: 24
    • View Profile
Re: Teoreticka informatika
« Reply #62 on: 28.11.2009, 18:24:50 »
Na zapocte by nemali byt ulohy z 10.cvika, pretoze v pondelok jedno cviko nebolo, kedze im nebol nikto zastupovat. Takze by to nebolo voci nim fer, takze 10.cviko na zapocte nebude. Tak to tvrdil Korecko na prednaske vcera, ze? A tiez nieco spominal, ze tie prve cvika nebudu, no neviem presne, coho sa to tyka, co nebude na zapocte. Je to tak?

buhehe

  • Hero Member
  • *****
  • Posts: 1583
    • View Profile
Re: Teoreticka informatika
« Reply #63 on: 28.11.2009, 18:34:26 »
nemali by byt 1.cviko (gramatiky) a 10.cviko.
1 priklad ma byt z lahsich cvik (konecne automaty, Mealy->Moore a naopak, redukcia, ekvivalencia automatov, determinizacia, ksa a reg.vyrazy...) a dalsie 2 priklady by mali byt zo zasobnikovych automotov, sekvencnych zobrazeni alebo TS. Tak nejak som to pochopil na prednaske...

buhehe

  • Hero Member
  • *****
  • Posts: 1583
    • View Profile
Re: Teoreticka informatika
« Reply #64 on: 28.11.2009, 18:37:46 »
aj prazdne slovo je riesenie..

väcsinou sme davali, ze (q0, lamb, Z, qf, lamb); kde qf je finalovy stav
Uz som si to dostudoval, Akceptovanie moze byt realizovane dvojako:
1. vyprazdnenim zasobnika (nahradenim symbolu Z symbolom "lambda")
2. Prechodom do finalneho stavu (Zvycajne qf)
potom pre priklad 4.1 nestaci takto?
Code: [Select]
(q0, 0,Z, q0, 0Z)
(q0, 0, 0, q0, 00)
(q0, 1, 0, q0, lambda)
nebude slovo akceptovane vyprazdnenim zasobnika?

Casso

  • Full Member
  • ***
  • Posts: 216
  • XSS locator
    • View Profile
    • casso <at> ic <at> cz
Re: Teoreticka informatika
« Reply #65 on: 28.11.2009, 18:46:31 »
potom pre priklad 4.1 nestaci takto?
Code: [Select]
(q0, 0,Z, q0, 0Z)
(q0, 0, 0, q0, 00)
(q0, 1, 0, q0, lambda)
nebude slovo akceptovane vyprazdnenim zasobnika?
podlamna je to jedna z variant. Myslim ze by ti to cviciaci uznal, a ak nie tak by si sa dohadal k pravde
« Last Edit: 28.11.2009, 18:48:38 by Casso »

ApokalypS

  • Hero Member
  • *****
  • Posts: 5801
  • apokalyps(a) sa mení..
    • View Profile
    • projekt k mojej diplomovke..
Re: Teoreticka informatika
« Reply #66 on: 28.11.2009, 19:54:26 »
imho, zaklad bude, ze tomu chapeme..
Ľaľová spominala, ze sa nemusime presne dopracovat k vysledku, hlavne, ze sme to dobre zacali.. aj na ukor bodov..
aspon ja to tak chapem..
80% mozgu človeka tvorí kvapalina, v mojom prípade brzdová..

CHCEM S5 :zuzka: STARY IS :zuzka: !!!!
http://www.tu-ke.com/forum/o-nicom/otvoreny-list-vedeniu-firmy-dupress-(dodavatel-mais)/

kOsTi

  • Hero Member
  • *****
  • Posts: 12765
    • View Profile
    • pretaktovanie.sk
Re: Teoreticka informatika
« Reply #67 on: 28.11.2009, 20:43:47 »
btw, neviete co su to za priklady na FTP v adresari zapich?
:trestac:

DeViLvs

  • Full Member
  • ***
  • Posts: 222
  • f1.yweb.sk
    • View Profile
Re: Teoreticka informatika
« Reply #68 on: 28.11.2009, 20:58:13 »
btw, neviete co su to za priklady na FTP v adresari zapich?
Vyzera to, ze to su priklady zo ZI (FJaA). Tam sa neberu TS a tie veci z poslednych cvik. Preto sa chcem spytat, kde by sa dali zohnat priklady na tieto veci. Aj tie priklady Plocicu su original z FJaA, cize iba po Zasob.Automaty.

cepi

  • Sr. Member
  • ****
  • Posts: 268
  • chodia mravci ?
    • View Profile
Re: Teoreticka informatika
« Reply #69 on: 28.11.2009, 22:03:11 »
nemali by byt 1.cviko (gramatiky) a 10.cviko.
1 priklad ma byt z lahsich cvik (konecne automaty, Mealy->Moore a naopak, redukcia, ekvivalencia automatov, determinizacia, ksa a reg.vyrazy...) a dalsie 2 priklady by mali byt zo zasobnikovych automotov, sekvencnych zobrazeni alebo TS. Tak nejak som to pochopil na prednaske...
viem tak ze budu TS a ZA nabeton a zrejme nieco z mealy/moore... redukcia, ekvivalencia... co su to tie sekvencne zobrazenia nejak si nepamatam ze by sme to brali
som kto som vdaka palenke

Payne

  • Sr. Member
  • ****
  • Posts: 408
    • View Profile
Re: Teoreticka informatika
« Reply #70 on: 29.11.2009, 02:10:53 »
Hej a take tie regularne vyrazy a take cudne obrazky hned po tom, to nikto nespominal ze by mohlo byt, co? lebo su to celkom dost bludy

cepi

  • Sr. Member
  • ****
  • Posts: 268
  • chodia mravci ?
    • View Profile
Re: Teoreticka informatika
« Reply #71 on: 29.11.2009, 02:57:48 »
nasiel som dobry simulator turinga http://www.isvet.sk/Download/15/Turingov-stroj--v-1-5- vie to krokovat, ukazuje priebeh postupne, este aj stavy kresli. skusal som v nom ten priklad co sme mali na cvikach ze:

x je z {0,1}* N0(x)=N1(x) ten je tu http://uloz.to/3185108/spravne.tm napodiv funguje

uzite v zdravy a kto sa bude nudit tak moze skusit spravit dalsie priklady a hodit ich niekam

a este tu je simulator na zasobnikovy automat ale ten kresli len tie stavy a nerobi s instrukciami ak ma niekto lepsi sem snim

http://ozark.hendrix.edu/~burch/proj/autosim/
« Last Edit: 29.11.2009, 03:04:09 by cepi »
som kto som vdaka palenke

cepi

  • Sr. Member
  • ****
  • Posts: 268
  • chodia mravci ?
    • View Profile
Re: Teoreticka informatika
« Reply #72 on: 29.11.2009, 03:12:04 »
ze sa pytas :)
som kto som vdaka palenke

Casso

  • Full Member
  • ***
  • Posts: 216
  • XSS locator
    • View Profile
    • casso <at> ic <at> cz
Re: Teoreticka informatika
« Reply #73 on: 29.11.2009, 03:14:27 »
Hej a take tie regularne vyrazy a take cudne obrazky hned po tom, to nikto nespominal ze by mohlo byt, co? lebo su to celkom dost bludy
my sme to mali na cviku a je to pomerne jednoduche, teda ak myslis to ze ako sa riesi sekvencia, rekurzia, vetvenie a pod v regularnych vyrazoch. Ku kazdemu prvku r.v. tam je nejaky k.s.a, ktoreho pospajanim ti vznikne k.s.a. rozoznavajuci cely regularny vyraz.  ten sa da este zvycajne zredukovat

cepi

  • Sr. Member
  • ****
  • Posts: 268
  • chodia mravci ?
    • View Profile
Re: Teoreticka informatika
« Reply #74 on: 29.11.2009, 03:17:23 »
a tie sekvnecne to bude ? a chape to niekto ?
som kto som vdaka palenke