Funzione iniettiva da $NN^2$ a $NN$, espressione esplicita
Il fatto che si possa costruire una funzione iniettiva $f : NN^2 \to NN$ è noto.
Una costruzione classica consiste nello scrivere gli elementi di $NN^2$ in forma tabellare in modo che in corrispondenza della riga $n$ e della colonna $m$ della tabella si trovi l'elemento $(n,m)$, quindi si considerano le diagonali della matrice a partire da quella che contiene solo l'elemento $(0,0)$, passando poi a quella che contiene gli elementi $(1,0)$ e $(0,1)$ e così via. Si pone $f(0,0)=0$, $f(1,0)=1$, $f(0,1)=2$ e così via, costruendo così una funzione iniettiva $f : NN^2 \to NN$.
Questa rappresenta un po l'idea della costruzione della funzione $f$, ma si può arrivare ad una espressione esplicita per $f$?
Una costruzione classica consiste nello scrivere gli elementi di $NN^2$ in forma tabellare in modo che in corrispondenza della riga $n$ e della colonna $m$ della tabella si trovi l'elemento $(n,m)$, quindi si considerano le diagonali della matrice a partire da quella che contiene solo l'elemento $(0,0)$, passando poi a quella che contiene gli elementi $(1,0)$ e $(0,1)$ e così via. Si pone $f(0,0)=0$, $f(1,0)=1$, $f(0,1)=2$ e così via, costruendo così una funzione iniettiva $f : NN^2 \to NN$.
Questa rappresenta un po l'idea della costruzione della funzione $f$, ma si può arrivare ad una espressione esplicita per $f$?
Risposte
$(a,b)\rarr2^a3^b$?
La funzione che hai proposto dovrebbe essere iniettiva, infatti se $f(a,b)=f(c,d)$ allora $2^a3^b=2^c3^d$, quindi $2^{a-c}=3^{d-b}$, dunque $a-c=0$ e $d-b=0$, cioè $(a,b)=(c,d)$.
Tuttavia, non corrisponde alla costruzione "per diagonali" che avevo descritto. Mi chiedevo se fosse possibile trovare un'espressione esplicita della funzione che si costruisce "per diagonali".
Tuttavia, non corrisponde alla costruzione "per diagonali" che avevo descritto. Mi chiedevo se fosse possibile trovare un'espressione esplicita della funzione che si costruisce "per diagonali".
"thedarkhero":
Tuttavia, non corrisponde alla costruzione "per diagonali" che avevo descritto. Mi chiedevo se fosse possibile trovare un'espressione esplicita della funzione che si costruisce "per diagonali".
Non avevo letto/capito bene. Pensavo volessi una funzione iniettiva qualsiasi.
Si puo' fare, ovviamente: bisogna trovare una formuletta che converta $(r,c)$ in $i$, e per farlo devi costruirti una tabellina iniziale
r,c=>i
0,0=>0
1,0=>1
0,1=>2
2,0=>3
1,1=>4
0,2=>5
...
(nota che $r+c$ e' una costante sulla diagonale).
a seconda se vai a zig/zag, oppure usi qualche altro 'pattern'.
Ma non e' l'unico modo!
C'e' tutta la teoria delle curve che possono ricoprire il piano e poiche' non hanno intersezioni, sono invertibili (curve di hilbert e di peano, cerca su wikipedia).
r,c=>i
0,0=>0
1,0=>1
0,1=>2
2,0=>3
1,1=>4
0,2=>5
...
(nota che $r+c$ e' una costante sulla diagonale).
a seconda se vai a zig/zag, oppure usi qualche altro 'pattern'.
Ma non e' l'unico modo!
C'e' tutta la teoria delle curve che possono ricoprire il piano e poiche' non hanno intersezioni, sono invertibili (curve di hilbert e di peano, cerca su wikipedia).
Nota che che $r+c+1$ e' il numero di celle che compongono la diagonale da $(0,r+c)$ a $(r+c,0)$.
Quindi, banalmente, devi trovare la formuletta che dato $(r,c)$, salta abbastanza celle e poi selezioni la cella del vettore che ti serve. Ho fatto il 95% del lavoro, ti manca il rimanente 5%
Quindi, banalmente, devi trovare la formuletta che dato $(r,c)$, salta abbastanza celle e poi selezioni la cella del vettore che ti serve. Ho fatto il 95% del lavoro, ti manca il rimanente 5%
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo