Newsgroup: it.scienza.informatica
Titolo: esercizio di Programmazione

Ciao a tutti vorrei sottoporre alla vostra attenzione il seguente problema:
Realizzare un modello di macchina astratta, tra automa a stati finiti e
macchine di touring, che, dato in input un numero decimale, stabilisca se
esso è divisibile per 3. Giustificare le decisioni prese nella
realizzazione.
Scusate...ma non esiste un teorema che dice che una macchina a stati finiti
non è in grado di contare? Quindi la realizzazione mediante automa è da
escludersi.
L'unico rimasto è la macchina di touring...io ho pensato ad un modo ma non
ne sono affatto sicuro... (mediante "sottrazioni", ma questo lo potrei fare
solo se il numero è rappresentato da linee o altro sibolo...), dato che il
numero deve essere in decimale.... :(
grazie a tutti coloro che mi daranno una manina :)
bye bye
--
Merlino666
"Impariamo soltanto quando dobbiamo creare"
                      \|/
                   (@ @) /
     +----oOO----(_)-----------+
 
http://www.merlino666.cjb.net
 
http://mdgia.cjb.net
 
merli...@hotmail.com
    +------------------oOO------+
                    |__|__|
                       || ||
                  ooO Ooo
      IHGGER number: 295
 Collaboratore di 3d infinity: 
www.3dinfinity.com
 Curatore  unico dell' MDG Italian Archive
 Programmatore capo di FOW
 WebMaster
 VBProgrammer
"Lamer si nasce Hacker si diventa..."

 escludersi.
Ma le proprietà della matematica elementare?
Un numero è divisibile per 3 se lo è la somma dei suoi numeri (decimali), e
questo mi sembra molto facilmente implementabile. Bastano, ad occhio, 100
stati (per sommare 2 cifre alla volta, considerando che in 1 cifra viene
memorizzato il parziale), cento più, cento meno :-)
Però devo dire che è un bel po' che non ho a che fare con automi a stati
finiti, anzi, se c'è qualcuno che vuole acquistare una macchina di Turing
ancora come nuova, con una bella scorta di nastro infinito...
--
Alessandro Monti

Salve, cito:
"Realizzare un modello di macchina astratta, tra automa a stati finiti e
macchine di touring, che, dato in input un numero decimale, stabilisca se
esso è divisibile per 3. Giustificare le decisioni prese nella
realizzazione.
Scusate...ma non esiste un teorema che dice che una macchina a stati finiti
non è in grado di contare? Quindi la realizzazione mediante automa è da
escludersi.
L'unico rimasto è la macchina di touring...io ho pensato ad un modo ma non
ne sono affatto sicuro... (mediante "sottrazioni", ma questo lo potrei fare
solo se il numero è rappresentato da linee o altro sibolo...), dato che il
numero deve essere in decimale.... :(
grazie a tutti coloro che mi daranno una manina :)"
a parte che il fatto che il buon Alan si chiamava Turing mi pare che il
problema sia indipendente dalla rappresentazione nel senso che hai un
modulo che prende un numero in una rappresentazione lo converte in 
un'altra, passa la nuova rappresentazione alla MdT e poi prende il
risultato (se questa si ferma) e lo riconverte nella rappresentazione
di partenza per cui l'idea di sottrarre 3 e' buona a patto di rappresentare
il numero che si vuole sapere se e' divisibile con delle astine (ad es.).
Un algoritmo potrebbe avere tre stati  e ad ogni
spostamento a destra passa da s0 a s1  se trovo una asta, da s1 a s2 se
ne trovo ancora 1 da s2 a s0 se ne trovo un'altra (3), a fine numero
se e' in s0 ho successo se no ho fallimento.
Le macchine a stati finiti non sanno contare nel senso che non sanno
produrre tutte e solo le stringhe con un numero uguale di a e b ad esempio
perche' per fare cio' dovrebbero avere bisogno di un numero infinito di 
stati pero' penso che usando il giusto criterio per la divisibilita'
siano utilizzabili..
Cheers
Yuri

 realizzazione.
Questo problema puo' essere riformulato come il riconoscimento del linguaggio
(sull'alfabeto
{0,1,2,...9}) di tutti i numeri divisibili per tre. Tale linguaggio e'
chiaramente riconoscibile da un DFA (cioe' da un automa a stati finiti
deterministico), in quanto vale il risultato
Un numero e' divisibile per tre sse e' divisibile per tre la somma delle cifre
della sua rappresentazione in base 10.
Per convincersi di cio' basta pensare ad un automa in cui gli stati
corrispondano alle classi di equivalenza della congruenza modulo 3 (cioe' agli
insiemi di tutti i numeri che divisi per tre danno resto n al variare di n in
{0,1,2}).  Esistera' poi una transizione etichettata con i dallo stato
relativo a n allo stato relativo ad m sse un qualunque intero che diviso per 3
ha resto n sommato ad i da un intero che, diviso per 3,  ha resto m. Lo stato
relativo a 0 sara' lo stato iniziale e l'unico stato finale. L'unico
inconveniente di questo automa e' che riconosce come appartenente al
linguaggio anche la stringa vuota, ma tale inconveniente si puo' facilmente
eliminare.
Hai ragione quando dici che i DFA non sanno contare, ma e' anche vero che per
risolvere questo problema non occorre contare in senso stretto, basta contare
modulo 3.
Ciao
Ugo

a parte che il fatto che il buon Alan si chiamava Turing mi pare che il
Ah, ma allora non era Touring come diceva l'altro e quindi non
c'entra con il Touring Club! Che delusione...
Immaginavo già un viaggio turistico a stati finiti.