Search
 
 
  Engleski
 
 
 
Open in this window (click to change)
Forum@DeGiorgi: Početna
Forum za podršku nastavi na PMF-MO
Login Registracija FAQ Smajlići Članstvo Pretražnik Forum@DeGiorgi: Početna

Zadatak iz Turinga
WWW:

Moja sarma
 
Započnite novu temu   Odgovorite na temu   printer-friendly view    Forum@DeGiorgi: Početna -> Kolegiji diplomskih i starih studija -> Matematička teorija računarstva
Prethodna tema :: Sljedeća tema  
Autor/ica Poruka
cereal
Forumaš(ica)
Forumaš(ica)


Pridružen/a: 03. 06. 2008. (10:23:17)
Postovi: (1)16
Sarma = la pohva - posuda
= 0 - 0

PostPostano: 10:53 uto, 3. 6. 2008    Naslov: Zadatak iz Turinga Citirajte i odgovorite

Dobio sam ovaj zadatak za rijesit, ali ne znam kako. Ako bi mogao netko da baci ideju i pomogne rijesiti bio bih zahvalan.
Imam nekakvu ideju za rijesavanje na engleskom, pa da sad ne postam ovdje ako je netko voljan posljem na PM.

[b]Konstruirati i opisati rad Touringovog stroja koji će izračunavati vrijednosti logičkih izraza s Booleovim operatorima I i ILI. Simbol ulazne trake koji odgovara logičkom operatoru I je *, a simbol ulazne trake koji odgovara logičkom operatoru ILI je +. Primjer zapisa funkcije na ulaznoj traci Touringova stroja: 1+1*0+1*1. Touringov stroj prvo mora ispitati da li je ulazni niz ispravno zadan, a nakon toga izračunati rezultat zadanog logičkog izraza.[/b]
Dobio sam ovaj zadatak za rijesit, ali ne znam kako. Ako bi mogao netko da baci ideju i pomogne rijesiti bio bih zahvalan.
Imam nekakvu ideju za rijesavanje na engleskom, pa da sad ne postam ovdje ako je netko voljan posljem na PM.

Konstruirati i opisati rad Touringovog stroja koji će izračunavati vrijednosti logičkih izraza s Booleovim operatorima I i ILI. Simbol ulazne trake koji odgovara logičkom operatoru I je *, a simbol ulazne trake koji odgovara logičkom operatoru ILI je +. Primjer zapisa funkcije na ulaznoj traci Touringova stroja: 1+1*0+1*1. Touringov stroj prvo mora ispitati da li je ulazni niz ispravno zadan, a nakon toga izračunati rezultat zadanog logičkog izraza.


[Vrh]
Korisnički profil Pošaljite privatnu poruku
vsego
Site Admin
Site Admin


Pridružen/a: 06. 10. 2002. (22:07:09)
Postovi: (355F)16
Spol: zombi
Sarma = la pohva - posuda
854 = 1068 - 214
Lokacija: /sbin/init

PostPostano: 12:11 uto, 3. 6. 2008    Naslov: Citirajte i odgovorite

Uhhh... cini mi se da tu ima posla. :?

Radim odvojeno; lako se poveze. ;)

[b]1. Provjera:[/b]
Trcis po cijeloj rijeci i provjeravas da se naizmjence pojavljuju 0 ili 1 i + ili *, te da su prvi i zadnji znak 0 ili 1 (procjenjujem da ti za ovo ti treba 2 stanja, plus jedno za "ne valja").

[b]2. Racunanje:[/b]
Rijesio bih to u dva prolaza (zbog prioriteta operatora).
Kreces na nekom kraju rijeci (svejedno kojem), u stanju q.
[b]2.1. Racunanje "I":[/b]
U prvom prolazu citas znak i ides u stanje q0 ili q1. Zatim citas znak. Ako je znak "+", vracas se u stanje q. Ako je "*", onda
1. ako si u stanju q0, brises "*" i iduci znak (koji god bio), jer je rezultat 0*x uvijek 0.
2. ako si u stanju q1, brises "*" i prethodni znak (to je 1), jer je rezultat 1*x uvijek x.
Nakon brisanja se vracas na prvi neobrisani znak (ili na pocetak izraza; svejedno) i ides u stanje q.
Brisanje (dva) znaka se radilo na vjezbama, a mislim da ima objasnjeno i u skripti iz Prog1 (ok, samo za 1 znak, no za 2 je slicno). 8)
[b]2.2. Racunanje "ILI":[/b]
Kad je ovo gore gotovo, ides opet kroz cijeli izraz, samo mijenjas ponasanje kad procitas znak (koji je sada sigurno "+" jer smo sve "*" obrisali):
1. ako si u stanju q0, brises "+" i prethodni znak (to je 0), jer je rezultat 0+x uvijek x.
2. ako si u stanju q1, brises "*" i iduci znak (koji god bio), jer je rezultat 1+x uvijek 1.
Pazi da ne pobrkas stanja q, q0 i q1 iz tocaka 2.1 i 2.2: to [b]nisu[/b] ista stanja, nego ja svaki potproblem gledam odvojeno! :tso:

Rezultat je ono sto prezivi na traci. 8)

Brisanje se moze i olaksati tako da stavis neki znak lijevo i desno od izraza, npr. "|". Tada seces po izrazu izmedju tih znakova, a u setanjima zanemarujes sve razmake. Tada se "brisanje" svodi na "zamijeni razmacima". ;) Uz takvu implementaciju, pazi da na kraju pozicioniras glavu na rezultat. :)

Nadam se da nisam fulao. ;)

Molim da ovdje objavis (ili mi posaljes na PM/mail) rjesenje... mozda bih zadatak iskoristio u nastavi (ako smijem, that is). :D
Uhhh... cini mi se da tu ima posla. Confused

Radim odvojeno; lako se poveze. Wink

1. Provjera:
Trcis po cijeloj rijeci i provjeravas da se naizmjence pojavljuju 0 ili 1 i + ili *, te da su prvi i zadnji znak 0 ili 1 (procjenjujem da ti za ovo ti treba 2 stanja, plus jedno za "ne valja").

2. Racunanje:
Rijesio bih to u dva prolaza (zbog prioriteta operatora).
Kreces na nekom kraju rijeci (svejedno kojem), u stanju q.
2.1. Racunanje "I":
U prvom prolazu citas znak i ides u stanje q0 ili q1. Zatim citas znak. Ako je znak "+", vracas se u stanje q. Ako je "*", onda
1. ako si u stanju q0, brises "*" i iduci znak (koji god bio), jer je rezultat 0*x uvijek 0.
2. ako si u stanju q1, brises "*" i prethodni znak (to je 1), jer je rezultat 1*x uvijek x.
Nakon brisanja se vracas na prvi neobrisani znak (ili na pocetak izraza; svejedno) i ides u stanje q.
Brisanje (dva) znaka se radilo na vjezbama, a mislim da ima objasnjeno i u skripti iz Prog1 (ok, samo za 1 znak, no za 2 je slicno). Cool
2.2. Racunanje "ILI":
Kad je ovo gore gotovo, ides opet kroz cijeli izraz, samo mijenjas ponasanje kad procitas znak (koji je sada sigurno "+" jer smo sve "*" obrisali):
1. ako si u stanju q0, brises "+" i prethodni znak (to je 0), jer je rezultat 0+x uvijek x.
2. ako si u stanju q1, brises "*" i iduci znak (koji god bio), jer je rezultat 1+x uvijek 1.
Pazi da ne pobrkas stanja q, q0 i q1 iz tocaka 2.1 i 2.2: to nisu ista stanja, nego ja svaki potproblem gledam odvojeno! Trudim Se Objasniti...

Rezultat je ono sto prezivi na traci. Cool

Brisanje se moze i olaksati tako da stavis neki znak lijevo i desno od izraza, npr. "|". Tada seces po izrazu izmedju tih znakova, a u setanjima zanemarujes sve razmake. Tada se "brisanje" svodi na "zamijeni razmacima". Wink Uz takvu implementaciju, pazi da na kraju pozicioniras glavu na rezultat. Smile

Nadam se da nisam fulao. Wink

Molim da ovdje objavis (ili mi posaljes na PM/mail) rjesenje... mozda bih zadatak iskoristio u nastavi (ako smijem, that is). Very Happy



_________________
U pravilu ignoriram pitanja u krivim topicima i kodove koji nisu u [code]...[/code] blokovima.
Takodjer, OBJASNITE sto vas muci! "Sto mi je krivo?", bez opisa u cemu je problem, rijetko ce zadobiti moju paznju.
Drzim prodike
[Vrh]
Korisnički profil Pošaljite privatnu poruku
Prethodni postovi:   
Započnite novu temu   Odgovorite na temu   printer-friendly view    Forum@DeGiorgi: Početna -> Kolegiji diplomskih i starih studija -> Matematička teorija računarstva Vremenska zona: GMT + 01:00.
Stranica 1 / 1.

 
Forum(o)Bir:  
Ne možete otvarati nove teme.
Ne možete odgovarati na postove.
Ne možete uređivati Vaše postove.
Ne možete izbrisati Vaše postove.
Ne možete glasovati u anketama.
You can attach files in this forum
You can download files in this forum


Powered by phpBB © 2001, 2002 phpBB Group
Theme created by Vjacheslav Trushkin
HR (Cro) by Ančica Sečan