Discussioni su Algebra astratta, Logica Matematica, Teoria dei Numeri, Matematica Discreta, Teoria dei Codici, Algebra degli insiemi finiti, Crittografia.
16/06/2023, 17:05
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$?
16/06/2023, 17:11
$(a,b)\rarr2^a3^b$?
17/06/2023, 01:07
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".
17/06/2023, 19:21
thedarkhero ha scritto: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.
18/06/2023, 09:41
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).
Ultima modifica di
Migliorabile il 18/06/2023, 11:28, modificato 1 volta in totale.
18/06/2023, 10:03
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%
Skuola.net News è una testata giornalistica iscritta al Registro degli Operatori della Comunicazione.
Registrazione: n° 20792 del 23/12/2010.
©2000—
Skuola Network s.r.l. Tutti i diritti riservati. — P.I. 10404470014.