Newsgroup: it.comp.programmare
Titolo: Algoritmi formali

Devo svolgere degli esercizi , le uniche informazioni che il Prof. ci ha
dato sono le seguenti:
- Def di algoritmo formale : se A è un alfabeto, A* è l'insieme delle
sequenze finite di elementi di A (quindi ad esempio
                                          l'insieme delle parole), e B* è un
altro insieme, allora l'algoritmo formale è una funzione F
                                          così definita :
| e : A* -> C
F  :  |  t : C -> C
|  d : C -> B*
                                          dove C è l'insieme delle
configurazioni, e è la funzione d'ingresso, t è la funzione di transizione,
                                          e d è la funzione d'uscita.
- Esempio : descrivere un algoritmo formale per decidere se x appartiene a
X, dove X={ dei multipli di nove}.
                   si sceglie come C={(w,k,n)| w è la rappresentazione
decimale di x, k è il puntatore alla cifra corrente, n è la
                   classe corrente}. Se avete un numero di cifre
a0,a1,a2,...,a9 sappiamo che la classe di questo numero coincide
                   con la sommatoria degli ai.Sto sfruttando il fatto che un
numero è divisibile per nove se la somma delle sue cifre
                   è divisibile per nove. Quindi la soluzione è :
                   C={(u,k,n) appartenente al prodotto A* x N(naturali) x
{0,1,...,8}}
                   F={e,t,d} dove :  e(u)=(u,0,0) dove u è la parola
                                              t
(u,k,n)=(u,k+1,n+u_{k+1}(mod9))
                                              d(u,k,n)= | 1 se k=l, n=0
dove l è la lunghezza della parola u
                                                             |  0 se k=l, n
è diverso da zero
                                                             | non è
definita se k è diversa da l
                    ad esempio se prendo il numero 3271 appartenente ad A* ,
allora l = 4 e viene :
                         e(3271)=(3271,0,0)
                         t(3271,0,0)=(3271,1,0+3 mod9)=(3271,1,3)
                         t(3271,1,3)=(3271,2,3+2 mod9)=(3271,2,5)
                         t(3271,2,5)=(3271,3,5+7 mod9)=(3271,3,3)
                         t(3271,3,3)=(3271,4,3+1 mod9)=(3271,4,4)
                        d(3271,4,4)=0 perchè k=l=4 e n=4 che è diverso da
zero.
                   quindi 3271 non è divisibile per nove!
Questo è tutto quello che sappiamo sugli algoritmi formali. E ora ecco a voi
gli esercizi :
Es 1 : Definire gli algoritmi formali per il calcolo delle operazioni
aritmetiche :
          + : Z x Z -> Z            (dove Z sono gli interi)
          * : Z x Z -> Z             (dove con * ho indicato il prodotto)
          il sugg. sarebbe di usare la rappresentazione unaria e come
alfabeto il seguente : A={+, - , # , | } dove + e - sono i
          segni dei numeri (positivi o negativi) , | indica una unità e #
indica la fine del primo addendo e l'inizio del secondo.
          Ad esempio :                      - | | | | | | | | |  # + | | | |
|     indica (- 9 + 5 )
            oppure :                            + | | | | | | | | | | | | |
| | # + | | | | | | | | |     indica ( +15 +9)
Es 2 : Dati due algoritmi formali :
                                                     | e1 : A* -> C1
                                              F1 : | t1  : C1 -> C1
                                                     | d1 : C1 -> B*1
        ed
                                                     | e2 : B* -> C2
                                              F2 : | t2 : C2 -> C2
                                                     | d2 : C2 -> D*
          definire la composizione dei due algoritmi come :
                                                     | e1 : A* -> C1 U C2
                                      F1 ° F2 : |  t   : C1 + C2 -> C1 +C2
                                                     |  d  : C1 +C2 -> D*
           in modo che per ogni computazione x appartenente a X, se F1(x)=y,
F2(y)=z, si abbia F1 ° F2(x)=F2(F1(x))=z.
Qualunque idea è ben accetta! Grazie a tutti .
Centaine.

 Qualunque idea è ben accetta! Grazie a tutti .
Pensi veramente che qualcuno abbia voglia di farti i compiti?
-- 
 Ciao, Bianco.
 Reply to luca.bianco (at) 
tiscalinet.it

 Pensi veramente che qualcuno abbia voglia di farti i compiti?
manca "gratis" ;)
--
saluti
f.riccardo
[sostituire 
linux.it
 al dominio nell'indirizzo]

manca "gratis" ;)
cribbio!... ho letto il testo del problema e ne ho capita + o - la
meta' :-(
ma questo tipo di esercizi serve a qualche cosa? Io sono uno di quelli
che si e' formato sul campo in quanto ai tempi della scuola i computer
erano davvero rarita' .... specie nelle scuole :-(( e con i miei 15
anni di programmazione non riesco neanche a capire il senso di un
problema!!! .... qualche cosa nopn mi torna....
Andrea
