Navigacija
Lista poslednjih: 16, 32, 64, 128 poruka.

TURING-ova mašina - utvrđivanje deljivosti ?

[es] :: Matematika :: TURING-ova mašina - utvrđivanje deljivosti ?

[ Pregleda: 4013 | Odgovora: 9 ] > FB > Twit

Postavi temu Odgovori

Autor

Pretraga teme: Traži
Markiranje Štampanje RSS

anon315

Član broj: 315
Poruke: 1657
*.verat.net



+13 Profil

icon TURING-ova mašina - utvrđivanje deljivosti ?26.08.2004. u 12:23 - pre 238 meseci
Haug !

Dakle evo jednog pitanja iz diskretne matematike.

Data je azbuka Turing-ove mašine S={b, 0, 1}. Prirodni brojevi se predstavljaju svojim binarnim zapisom na traci. Potrebno je konstruisati program za T.M. koja utvrđuje da li je zadani broj deljiv sa 4. .

Da bi broj bio deljiv sa 4 potrebno je da bar poslednje dve cifre budu nule. Zašto je to tako ? Ima neke veze sa 4=1002, ali ne kapiram baš kakve. Na primer, koji bi bio kriterijum da je potrebno da broj bude deljiv sa 3 ili 5 ili nekim trećim brojem ?

Pitanje vezano za sam program ; evo mog koda:

f(q0, 1) = (q1, 1, 1)
f(q1, b) = (q-, b, -1)
f(q1, 1) = (q1, 1, 1)
f(q1, 0) = (q1, 0, 1)
f(q1, b) = (q2, b, -1)
f(q2, 1) = (q-, 1, -1)
f(q2, 0) = (q3, 0, -1)
f(q3, 1) = (q-, 1, -1)
f(q3, 0) = (q+, 0, -1)

Kod u rešenju zadatka se razlikuje u tome što su dodatno ubačena dva koraka i to prelazak iz stanja jedan u stanje dva kada se čita 1 ili 0, a tek onda se "vrti" to stanje dokle god se pojavljuju nule tj. kečevi, a dalje je sve isto. Čemu ti, meni se čini, nepotrebni koraci ?

 
Odgovor na temu

-zombie-
Tomica Jovanovic
freelance programmer
ni.ac.yu

Član broj: 4128
Poruke: 3448
195.252.85.*

Sajt: localhost


+5 Profil

icon Re: TURING-ova mašina - utvrđivanje deljivosti ?26.08.2004. u 13:00 - pre 238 meseci
Citat:
Vanja Petreski:
Dakle evo jednog pitanja iz diskretne matematike.


nisam nikada bio baš najbolji sa tim klasifikacijama, ali nisam siguran da je diskretna matematika prava kategorija za TM.. ;)

Citat:
Potrebno je konstruisati program za T.M. koja utvrđuje da li je zadani broj deljiv sa 4. .


dobro, TM treba da utvrdi, ali kako to da signalizira? mislim, da li treba da upiše u neku ćeliju 0 ili 1, zavisno od toga da li je deljiv sa 4 ili ne?

Citat:
Da bi broj bio deljiv sa 4 potrebno je da bar poslednje dve cifre budu nule. Zašto je to tako ? Ima neke veze sa 4=1002, ali ne kapiram baš kakve. Na primer, koji bi bio kriterijum da je potrebno da broj bude deljiv sa 3 ili 5 ili nekim trećim brojem ?


čekaj, šališ se, jel da? mislim, tebe sam viđao kako rešavaš neke "ružne" jednačine sa integralima i diferencijalima, baš na ovom forumu.. a ne znaš zašto broj koji je deljiv sa 4 mora da ima najmanje poslednje dve nule u binarnom zapisu?

ako se ne šališ, evo ti hint: predstavi broj koji je deljiv sa 4 kao proizvod, i predstavi taj broj preko stepena dvojke (onaj međuproizvod kada pretvaraš broj iz dekadnog u binarni zapis).


Citat:
Kod u rešenju zadatka se razlikuje u tome što su dodatno ubačena dva koraka i to prelazak iz stanja jedan u stanje dva kada se čita 1 ili 0, a tek onda se "vrti" to stanje dokle god se pojavljuju nule tj. kečevi, a dalje je sve isto. Čemu ti, meni se čini, nepotrebni koraci ?


nije mi baš najjasnije tačno koja dva koraka, ali možda samo sređuju/osiguravaju početno/krajnje stanje (nisi naveo gde se nalazi glava na početku, gde treba da se nađe na kraju, itd..), ili su jednostavno mislili da je tako "jednostavniji" program za čitanje.. a i program u TM je i dalje program, i može se rešiti na mnoogo različitih načina, tako da..

a ako baš hoćeš analizu, prekucaj tačno i njihov program, pa da upoređujemo..
 
Odgovor na temu

neor
Nenad Orlovic

Član broj: 26828
Poruke: 74
*.ftn.ns.ac.yu



Profil

icon Re: TURING-ova mašina - utvrđivanje deljivosti ?26.08.2004. u 13:18 - pre 238 meseci
Citat:
Vanja Petreski: ali ne kapiram baš kakve. Na primer, koji bi bio kriterijum da je potrebno da broj bude deljiv sa 3 ili 5 ili nekim trećim brojem ?

Za svaki broj se moze naci slicno pravilo kojim se na osnovu cifara oredjuje deljivost.
Na primer za broj P
proizvoljan broj A zapisan u osnovi B je
A = an...a2a1a0

A ce biti deljivo sa P ako je zbir
a0 * (B0 mod P) + a1 * (B1 mod P) + ... an * (Bn mod P)
deljiv sa P.

Za svako P brojevi (Bi mod P) pocnu da se ponavljaju pa se zato mogu za neke brojeve dati jednostavna pravila (na primer za 2,3,4,5,6,8,9,10,11).
 
Odgovor na temu

anon315

Član broj: 315
Poruke: 1657
*.verat.net



+13 Profil

icon Re: TURING-ova mašina - utvrđivanje deljivosti ?26.08.2004. u 15:07 - pre 238 meseci
U bre zombiju što si ti dosadan neki, više pitaš nego što pomažeš ;)

Ajde zaboravi na te manje bitne detalje, signaliziramo samo sa q+ i to je to, ništa ne upisujemo.

...bbb1.....010...01b....

Glava je na crvenom ...

Ne znam kako je kod tebe na fax-u, ali kod mene se T.M. izučava upravo u diskretnoj koja je jedan deo tzv. matematike 4.

A jel te ne mrzi da mi objasniš kakve veze ova materija ima sa diferencijalima i integralima :P

Ustvari i dalje ne kapiram trik i pored tvog obimnog hint-a. Lako je sa 4, 8, 16 (po analogiji sa 4, haha) ali šta sa 3, ne kontam stvarno. Ajde prosvetli me.

Šta više, pošto me ova materija u o p s t e ne zanima i učim je sa 3% mozga, bilo bi fino da dobijem gotova pravila za brojeve od 2-16 npr. (al sam zahtevan i lenj, hehe), pošto ti je to izgleda extremno lako.

neor, problem je što nemam konkretan broj u binarnom zapisu.
 
Odgovor na temu

Goran Rakić
Beograd

Član broj: 999
Poruke: 3766

Sajt: blog.goranrakic.com


+125 Profil

icon Re: TURING-ova mašina - utvrđivanje deljivosti ?26.08.2004. u 17:21 - pre 238 meseci
3 - zbir cifara deljiv sa 3
4 - poslednje dve cifre deljive sa 4
5 - poslednja cifra 0 ili 5
6 - paran, deljiv sa 3
7 - ???
8 - sa 2 i sa 4
9 - zbir cifara deljiv sa 9
10 - poslednja cifra 0
11 - zvir cifara na parnim - zbir cifara na neparnim mestima deljiv sa 11
12 - sa 6 i sa 2
13 - ???
14 - sa 7 i sa 2
15 - sa 3 i 5
16 - 2 i 8...
http://sr.libreoffice.org — slobodan kancelarijski paket, obrada teksta, tablice,
prezentacije, legalno bez troškova licenciranja
 
Odgovor na temu

anon315

Član broj: 315
Poruke: 1657
*.verat.net



+13 Profil

icon Re: TURING-ova mašina - utvrđivanje deljivosti ?26.08.2004. u 19:10 - pre 238 meseci
Gorane, šta misliš kako bi bilo da svičuješ u binarni. Ovo za decimalni se stvarno zna iz osnovne. Mada mi je sad jasno zašto se zombie čudi, reče mi koleginica da se ovo oko bin. br. i deljivosti radilo kod nje još u mat. gimn., ali kako sam ja isao u XI gimn ... :-))
 
Odgovor na temu

chupcko
Negde
Beograd

Član broj: 5560
Poruke: 1141

Sajt: www.google.com


+63 Profil

icon Re: TURING-ova mašina - utvrđivanje deljivosti ?26.08.2004. u 20:46 - pre 238 meseci
Ja se izvinjavam, ali da prvo razlucimo neke stvari.

Turingova masina ima bas bas bas puno znacaja, a sada kakvog i kojeg, citajte GED ...

Zanima me sta je po tebi f(q1,b) posto vidim da imas dve vrednosti, kada cemo koju da koristimo ??? u pitanju je diskretna i determinasana matematika, pa neka tako i ostane ...

Dakle program ne zadovoljava neke osnovne stvari. (posto sam danas zloban, reci cu, sedi 1).

Dalje kada je u dekadnom brojnom sistemu broj deljiv sa 10^n, kada ima n nula na kraju :)

Dakle kako je 4=2^2 broj ce biti deljiv sa 4 kada u binarnoj reprezentaciji ima 2 nula na kraju :).

Sto se tice programa, najlakse je da se prvo pomeris do pozicije sasvim iza broja, do prvog b, vratis se poziciju levo i gledas da li je 0, ako jeste , proveris to jos jednom za poziciju levo :), ima malo muke oko kodiranja toga, pravljenjua stanja i slicnog.

Sto se tice deljivosti kada je broj u binarnom brojnom sistemu ... sigurno ima, ali ja ne znam :).

[Ovu poruku je menjao chupcko dana 27.08.2004. u 09:48 GMT]
CHUPCKO
 
Odgovor na temu

neor
Nenad Orlovic

Član broj: 26828
Poruke: 74
*.panline.net



Profil

icon Re: TURING-ova mašina - utvrđivanje deljivosti ?26.08.2004. u 21:23 - pre 238 meseci
Evo, uglavnom komplikovanih, pravila za deljivost brojeva u binarnom zapisu. Sva izvedena na nacin opisan u mom prethodnom postu:

2: a0=0
3: razlika zbira cifara na parnim i neparnim mestima deljiva sa 3
4: a0=a1=0
5: [a0 + 2a1 + 4a2 + 3a3]... deljivo sa 5
6: a0 + [2a1 + 4a2]... deljivo sa 6
7: [a0 + 2a1 + 4a2]... deljivo sa 7
8: a0=a1=a2=0
9: podeli se na grupe po 3 cifre, parne grupe se oduzmu od neparnih i rezultat mora da bude deljiv sa 9
10: a0 + [2a1 + 4a2 + 8a3 + 6*a5]... deljivo sa 10
11: kao za 9 ali grupe po 5 cifara i rezultat mora biti deljiv sa 11
12: a0 + 2a1 + [4a2 + 8a3]... deljivo sa 12
13: kao za 9 ali grupe po 6 cifara i rezultat mora biti deljiv sa 13
14: a0 + [2a1 + 4a2 + 8a3]... deljivo sa 14
15= [a0 + 2a1 + 4a2 + 8a3]... deljivo sa 15
16= a0=a1=a2=a3=0

kad broj ima vise cifara onda se za dodatne cifre redom ponavljaju koeficijenti iz uglastih zagrada
 
Odgovor na temu

anon315

Član broj: 315
Poruke: 1657
*.verat.net



+13 Profil

icon Re: TURING-ova mašina - utvrđivanje deljivosti ?26.08.2004. u 21:49 - pre 238 meseci
Problem je rešen.

U svakom slučaju hvala svima na diskusiji.
 
Odgovor na temu

-zombie-
Tomica Jovanovic
freelance programmer
ni.ac.yu

Član broj: 4128
Poruke: 3448
195.252.85.*

Sajt: localhost


+5 Profil

icon Re: TURING-ova mašina - utvrđivanje deljivosti ?27.08.2004. u 11:36 - pre 238 meseci
Citat:
Vanja Petreski:
U bre zombiju što si ti dosadan neki, više pitaš nego što pomažeš ;)


pa mora sve (matematički) precizno.. a ti si valjda veći matematičar od mene.. ;)

Citat:
Ne znam kako je kod tebe na fax-u, ali kod mene se T.M. izučava upravo u diskretnoj koja je jedan deo tzv. matematike 4.


ehh.. ja sam TM učio najmanje tri puta.. (valjda u srednjoj, pa na bivšem faxu u okviru ORTa (osnove računara), pa na novom faxu, ponovo iz Introduction to Computing ;)

da je bar neka malo opširnija/komplikovanija tema, pa bi mogao sad i da doktoriram na TM.. :-P

Citat:
A jel te ne mrzi da mi objasniš kakve veze ova materija ima sa diferencijalima i integralima :P


pa nema.. ali mi se ova materija (brojni sistemi, deljivost brojeva..) čini mnoogo jednostavija od integrala i diferencijala..

Citat:
Šta više, pošto me ova materija u o p s t e ne zanima i učim je sa 3% mozga,


a vidiš, mene ti integrali nisu uopšte zanimali (binarno kodiranje jeste -- zbog programiranja), pa ih verovatno zato nikada nisam pošteno ni naučio, tj i dan danas su mi nekako "ružni".. :-P

(mada, i dalje mi se čini ovo oko deljenja prostije ;)

Citat:
Ustvari i dalje ne kapiram trik i pored tvog obimnog hint-a. Lako je sa 4, 8, 16 (po analogiji sa 4, haha) ali šta sa 3, ne kontam stvarno. Ajde prosvetli me.


ja sam prvenstveno mislio na deljenje sa stepenima dvojke, pošto cenim da će samo to i da bude na ispitu.. znači, ako ste na vežbama radili deljenje sa 4, na ispitu može da bude deljenje sa 8, jer je poJenta da se vidi da li si skontao princip rada TM, a ne da li znaš da deliš brojeve ;)

Citat:
Vanja Petreski:
Mada mi je sad jasno zašto se zombie čudi, reče mi koleginica da se ovo oko bin. br. i deljivosti radilo kod nje još u mat. gimn., ali kako sam ja isao u XI gimn ... :-))


da, izvini ako sam možda delovao nadmeno tipa "ja to znam -- a ti ne znaš" i slično ;), jer stvarno nije imalo veze sa tim.. samo sam se bio malo začudio (zbog onih integrala ;).

a jeste, mi (MG "istureno odeljenje" u nišu) smo to radili od prvog srednje, a u programiranju koristili bukvalno stalno (ja još od osnovne). prosto mi ponekad čudno kada shvatim da ljudi oko mene ne znaju napamet stepene dvojke do 220/232, ili da im za prebacivanje brojeve do par hiljada iz binarnog u dekadni i obrnuto trebaju papir i olovka!! :-P

meni to dođe kao profesionalna deformacija.. ;)

 
Odgovor na temu

[es] :: Matematika :: TURING-ova mašina - utvrđivanje deljivosti ?

[ Pregleda: 4013 | Odgovora: 9 ] > FB > Twit

Postavi temu Odgovori

Navigacija
Lista poslednjih: 16, 32, 64, 128 poruka.