Google Groups no longer supports new Usenet posts or subscriptions. Historical content remains viewable.
Dismiss
algorithms mcd
25 views
Skip to first unread message
Bert_emme
Jun 3, 2012, 9:36:52 AM6/3/12
to
Esercizio preso da art of computer programming (Donald E. Knuth):
Give the "effective" formal algorithm for computing the greatest
common divisor of positive integer m and n. Let the input be
rapresented by the string (a^m)(b^n), that is, m a's follow n's b.
Soluzione:
Presa la quadrupla (Q,I,O,f) dove Q è l'insieme contenente i due
sottinsiemi I, O e I è l'input e O è l'output ed f è una funzione da Q
in se stesso. Inoltre f deve lasciare O invariato, ossia f(q)=q se q
appartiene a O.
Definito l'insiema A ={a,b} e l'insieme A* con le possibili
combinazioni degli elemnti di A che hanno la forma (a^m)(b^n) con
m,n>0.
Il mio insieme Q diventa ($,,j,i) son $ appartenente ad A* ed 0<i , ,j
< m,n
L'insieme I = $
L'insieme O = j
La funzione f che definisce l'algoritmo diventa:
f(( $, ,j, i )) = f(( (a^j)(b^i), | j-i |, min( i,,j ) )) se i è
diverso da 0
f(( $, j, i )) = f(( (a^j), j, j )) se i = 0
f(( (a^j), j, j )) = j
La mia domanda è la seguente: ha un senso quello che ho scritto? io di
matematica ne capisco poco ma se mi illuminate posso continuare a
leggere il libro
Give the "effective" formal algorithm for computing the greatest
common divisor of positive integer m and n. Let the input be
rapresented by the string (a^m)(b^n), that is, m a's follow n's b.
Soluzione:
Presa la quadrupla (Q,I,O,f) dove Q è l'insieme contenente i due
sottinsiemi I, O e I è l'input e O è l'output ed f è una funzione da Q
in se stesso. Inoltre f deve lasciare O invariato, ossia f(q)=q se q
appartiene a O.
Definito l'insiema A ={a,b} e l'insieme A* con le possibili
combinazioni degli elemnti di A che hanno la forma (a^m)(b^n) con
m,n>0.
Il mio insieme Q diventa ($,,j,i) son $ appartenente ad A* ed 0<i , ,j
< m,n
L'insieme I = $
L'insieme O = j
La funzione f che definisce l'algoritmo diventa:
f(( $, ,j, i )) = f(( (a^j)(b^i), | j-i |, min( i,,j ) )) se i è
diverso da 0
f(( $, j, i )) = f(( (a^j), j, j )) se i = 0
f(( (a^j), j, j )) = j
La mia domanda è la seguente: ha un senso quello che ho scritto? io di
matematica ne capisco poco ma se mi illuminate posso continuare a
leggere il libro
El Filibustero
Jun 4, 2012, 5:42:10 AM6/4/12
to
On Sun, 3 Jun 2012 06:36:52 -0700 (PDT), Bert_emme wrote:
>Esercizio preso da art of computer programming (Donald E. Knuth):
>
>Give the "effective" formal algorithm for computing the greatest
>common divisor of positive integer m and n. Let the input be
>rapresented by the string (a^m)(b^n), that is, m a's follow n's b.
>
>Soluzione:
>
>Presa la quadrupla (Q,I,O,f) dove Q � l'insieme contenente i due
>Esercizio preso da art of computer programming (Donald E. Knuth):
>
>Give the "effective" formal algorithm for computing the greatest
>common divisor of positive integer m and n. Let the input be
>rapresented by the string (a^m)(b^n), that is, m a's follow n's b.
>
>Soluzione:
>
>sottinsiemi I, O e I � l'input e O � l'output ed f � una funzione da Q
>in se stesso. Inoltre f deve lasciare O invariato, ossia f(q)=q se q
>appartiene a O.
>Definito l'insiema A ={a,b} e l'insieme A* con le possibili
>combinazioni degli elemnti di A che hanno la forma (a^m)(b^n) con
>m,n>0.
>Il mio insieme Q diventa ($,,j,i) son $ appartenente ad A* ed 0<i , ,j
>< m,n
>L'insieme I = $
>L'insieme O = j
>La funzione f che definisce l'algoritmo diventa:
>
> f(( $, ,j, i )) = f(( (a^j)(b^i), | j-i |, min( i,,j ) )) se i �
>appartiene a O.
>Definito l'insiema A ={a,b} e l'insieme A* con le possibili
>combinazioni degli elemnti di A che hanno la forma (a^m)(b^n) con
>m,n>0.
>Il mio insieme Q diventa ($,,j,i) son $ appartenente ad A* ed 0<i , ,j
>< m,n
>L'insieme I = $
>L'insieme O = j
>La funzione f che definisce l'algoritmo diventa:
>
>diverso da 0
> f(( $, j, i )) = f(( (a^j), j, j )) se i = 0
> f(( (a^j), j, j )) = j
>
>La mia domanda � la seguente: ha un senso quello che ho scritto?
> f(( $, j, i )) = f(( (a^j), j, j )) se i = 0
> f(( (a^j), j, j )) = j
>
L' arita' di alcuni operatori e' IMHO incomprensibile. min ha 3 argomenti?
f opera su una quadrupla o una tripla (come si direbbe da
>f(( (a^j), j, j )) = j
input e output. Non e' sufficiente definire l'algoritmo mediante la
funzione f:
f(m,n) := n se m=n
f(m,n) := f(|m-n|,min(m,n))
?
>io di matematica ne capisco poco ma se mi illuminate posso continuare a
>leggere il libro
simboli distinti lascia supporre che l'"effective formal algorithm"
richiesto sia un programma per macchina di Turing, che a grandi linee fa
quanto segue (il . rappresenta il blank):
1) individua un'estremita' (diciamo la sinistra) della stringa di "a" e "b"
........aaaaaaaaabbbb.........
^
2) a sinistra del blank della "a" piu' a sinistra mette un'altra "a" come
marker; fa lo stesso verso destra con la "b"
......a.aaaaaaaaabbbb.b.......
^
3) cancella reiteratamente una "a" e una "b" interne finche' non esaurisce
o le "a" o le "b" o entrambe. Se le lettere "a" e "b" non erano in parita',
si prosegue con 4); altrimenti l'algoritmo termina con la riscrittura delle
"a" (o "b", indifferente) che erano state cancellate e con la cancellazione
dei markers. La quantita' di lettere rimaste sul nastro e' il GCD.
......a.....aaaaa.....b.......
^
4) riscrive quelle lettere in minoranza che erano state cancellate (nel
nostro esempio sono le "b", e cio' e' possibile grazie al marker b di
destra):
......a.....aaaaabbbb.b.......
^
5) rimette a posto il marker di sinistra:
..........a.aaaaabbbb.b.......
e si riprende da 3)
Ciao
Elio Fabri
Jun 7, 2012, 2:57:03 PM6/7/12
to
Bert_emme ha scritto:
Io non sono riuscito a trovarlo.
--
Elio Fabri
> Esercizio preso da art of computer programming (Donald E. Knuth):
>
> Give the "effective" formal algorithm for computing the greatest
> common divisor of positive integer m and n. Let the input be
> rapresented by the string (a^m)(b^n), that is, m a's follow n's b.
Potresti dare indicazioni più precise?
>
> Give the "effective" formal algorithm for computing the greatest
> common divisor of positive integer m and n. Let the input be
> rapresented by the string (a^m)(b^n), that is, m a's follow n's b.
Io non sono riuscito a trovarlo.
--
Elio Fabri
Bert_emme
Jun 10, 2012, 11:40:30 AM6/10/12
to
Elio Fabri
Jun 12, 2012, 2:56:25 PM6/12/12
to
Bert_emme ha scritto:
cercavo da tutt'altra parte...
--
Elio Fabri
> esercizio 8 pag 9 book 1
Grazie. Non mi aspettavo che fosse addirittura a pag. 9, per cui lo
cercavo da tutt'altra parte...
--
Elio Fabri
0 new messages