Numerazione biunivoca - Bijective numeration

La numerazione biunivoca è un qualsiasi sistema numerico in cui ogni intero non negativo può essere rappresentato esattamente in un modo usando una stringa finita di cifre . Il nome deriva da questa biiezione (corrispondenza biunivoca) tra l'insieme degli interi non negativi e l'insieme delle stringhe finite utilizzando un insieme finito di simboli (le "cifre").

La maggior parte dei sistemi numerici ordinari, come il sistema decimale comune , non è biunivoca perché più di una stringa di cifre può rappresentare lo stesso numero intero positivo. In particolare, l'aggiunta di zeri iniziali non modifica il valore rappresentato, quindi "1", "01" e "001" rappresentano tutti il ​​numero uno . Anche se solo il primo è normale, il fatto che gli altri siano possibili significa che il decimale non è biunivoco. Tuttavia, unario , con una sola cifra, è biunivoco.

Una numerazione biunivoca base - k è una notazione posizionale biunivoca . Usa una stringa di cifre dall'insieme {1, 2, ..., k } (dove k ≥ 1) per codificare ogni intero positivo; la posizione di una cifra nella stringa definisce il suo valore come multiplo di una potenza di k . Smullyan (1961) chiama questa notazione k -adic, ma non deve essere confusa con i numeri p -adic : i numeri biunivoci sono un sistema per rappresentare interi ordinari mediante stringhe finite di cifre diverse da zero, mentre i numeri p -adic sono un sistema di valori matematici che contengono gli interi come sottoinsieme e possono richiedere sequenze infinite di cifre in qualsiasi rappresentazione numerica.

Definizione

Il sistema di numerazione biunivoco in base k usa l'insieme di cifre {1, 2, ..., k } ( k ≥ 1) per rappresentare in modo univoco ogni intero non negativo, come segue:

• Lo zero intero è rappresentato dalla stringa vuota .
• L'intero rappresentato dalla stringa di cifre non vuota

a _n a _{n −1} ... a ₁ a ₀

è

a _n k ⁿ + a _{n −1} k ^{n -1} + ... + a ₁ k ¹ + a ₀ k ⁰ .

• La stringa di cifre che rappresenta l'intero m > 0 è

a _n a _{n −1} ... a ₁ a ₀

dove

${\displaystyle {\begin{aligned}a_{0}&=m-q_{0}k,&q_{0}&=f\left({\frac {m}{k}}\right)&\\a_ {1}&=q_{0}-q_{1}k,&q_{1}&=f\sinistra({\frac {q_{0}}{k}}\destra)&\\a_{2}& =q_{1}-q_{2}k,&q_{2}&=f\left({\frac {q_{1}}{k}}\right)&\\&\,\,\,\vdots &&\,\,\,\vdots \\a_{n}&=q_{n-1}-0k,&q_{n}&=f\left({\frac {q_{n-1}}{k} }\right)=0\end{allineato}}}$

e

${\displaystyle f(x)=\lceil x\rceil -1,}$

${\displaystyle \lceil x\rceil}$essendo il minimo intero non minore di x (la funzione massimale ).

Al contrario, la notazione posizionale standard può essere definita con un algoritmo ricorsivo simile dove

${\displaystyle f(x)=\lfloor x\rfloor ,}$

Estensione a numeri interi

Per base , il sistema biunivoco base- numerazione potrebbe essere esteso agli interi negativi allo stesso modo del sistema standard base- numero utilizzando un numero infinito della cifra , dove , rappresentato come una sequenza infinita di cifre . Questo perché la sommatoria di Eulero${\displaystyle k>1}$${\displaystyle k}$${\displaystyle b}$${\displaystyle d_{k-1}}$${\displaystyle f(d_{k-1})=k-1}$${\displaystyle \ldots d_{k-1}d_{k-1}d_{k-1}={\overline {d_{k-1}}}}$

${\displaystyle g({\overline {d_{k-1}}})=\sum _{i=0}^{\infty}f(d_{k-1})k^{i}=-{\ frac {k-1}{k-1}}=-1}$

intendendo che

${\displaystyle g({\overline {d_{k-1}}}d_{k})=f(d_{k})\sum _{i=1}^{\infty}f(d_{k-1 })k^{i}=1+\sum _{i=0}^{\infty }f(d_{k-1})k^{i}=0}$

e per ogni numero positivo con numerazione biunivoca la rappresentazione della cifra è rappresentata da . Per base , i numeri negativi sono rappresentati da con , mentre per base , i numeri negativi sono rappresentati da . Questo è simile a come nelle rappresentazioni con cifre con segno , tutti gli interi con rappresentazioni con cifre sono rappresentati come dove . Questa rappresentazione non è più biunivoca, in quanto l'intero insieme di sequenze di cifre infinite a sinistra viene utilizzato per rappresentare gli interi -adic , di cui gli interi sono solo un sottoinsieme. ${\displaystyle n}$${\displaystyle d}$${\displaystyle {\overline {d_{k-1}}}d_{k}d}$${\displaystyle k>2}$${\displaystyle n<-1}$${\displaystyle {\overline {d_{k-1}}}d_{i}d}$${\displaystyle i<k-1}$${\displaystyle k=2}$${\displaystyle n<-1}$${\displaystyle {\overline {d_{k}}}d}$${\displaystyle n}$${\displaystyle d}$${\displaystyle {\overline {d_{0}}}d}$${\displaystyle f(d_{0})=0}$${\displaystyle k}$

Proprietà dei numeri biunivoci base- k

Per una data base k ≥ 1,

• ci sono esattamente k ⁿ base- k numeri biunivoci di lunghezza n ≥ 0.
• se k ≥ 2, il numero di cifre nel numero biunivoco in base- k che rappresenta un intero non negativo n è , contrariamente a quanto avviene per i numeri ordinari in base- k ; se k = 1 (cioè unario), allora il numero di cifre è solo n ;${\displaystyle \lfloor \log _{k}((n+1)(k-1))\rfloor }$${\displaystyle \lceil \log _{k}(n+1)\rceil}$
• se k ≥ 2, i numeri biunivoci in base k e ordinari in base k per un intero non negativo n sono identici se e solo se il numerale ordinario non contiene la cifra 0 (o, equivalentemente, il numerale biunivoco non è né la stringa vuota né contiene la cifra k ).
• una lista di numeri biunivoci in base- k , in ordine naturale degli interi rappresentati, è automaticamente in ordine shortlex (prima il più corto, lessicografico all'interno di ogni lunghezza). Quindi, usando λ per denotare la stringa vuota , i numeri in base 1, 2, 3, 8, 10, 12 e 16 sono i seguenti (dove le rappresentazioni ordinarie sono elencate per il confronto):

Esempi

34152 (in base biunivoca-5) = 3×5 ⁴ + 4×5 ³ + 1×5 ² + 5×5 ¹ + 2×1 = 2427 (in decimale).

119A (in base 10 biunivoca, con "A" che rappresenta il valore della cifra dieci) = 1×10 ³ + 1×10 ² + 9×10 ¹ + 10×1 = 1200 (in decimale).

Un tipico elenco alfabetico con più di 26 elementi è biunivoco, utilizzando l'ordine di A, B, C...X, Y, Z, AA, AB, AC...ZX, ZY, ZZ, AAA, AAB, AAC. ..

Il sistema biunivoco base-10-10

Il sistema biunivoco in base 10 è un sistema numerico posizionale in base dieci che non utilizza una cifra per rappresentare lo zero . Ha invece una cifra per rappresentare dieci, come A .

Come con i decimali convenzionali , ogni posizione di una cifra rappresenta una potenza di dieci, quindi ad esempio 123 è "cento, più due decine, più tre unità". Tutti gli interi positivi rappresentati esclusivamente con cifre diverse da zero in decimale convenzionale (come 123) hanno la stessa rappresentazione in decimale senza zero. Quelli che usano uno zero devono essere riscritti, quindi per esempio 10 diventa A, convenzionale 20 diventa 1A, convenzionale 100 diventa 9A, convenzionale 101 diventa A1, convenzionale 302 diventa 2A2, convenzionale 1000 diventa 99A, convenzionale 1110 diventa AAA, convenzionale 2010 diventa 19AA , e così via.

L'addizione e la moltiplicazione in decimale senza zero sono essenzialmente le stesse del decimale convenzionale, tranne per il fatto che i riporti si verificano quando una posizione supera dieci, piuttosto che quando supera nove. Quindi per calcolare 643 + 759, ci sono dodici unità (scrivi 2 a destra e riporta 1 alle decine), dieci decine (scrivi A senza dover riportare le centinaia), tredici centinaia (scrivi 3 e riporta 1 alle migliaia) e mille (scrivi 1), per dare il risultato 13A2 anziché il convenzionale 1402.

Il sistema biunivoco in base 26

Nel sistema biunivoco in base 26 si possono usare le lettere dell'alfabeto latino da "A" a "Z" per rappresentare i valori di 26 cifre da uno a ventisei . (A=1, B=2, C=3, ..., Z=26)

Con questa scelta di notazione, la sequenza numerica (a partire da 1) inizia con A, B, C, ..., X, Y, Z, AA, AB, AC, ..., AX, AY, AZ, BA, BB , AVANTI CRISTO, ...

Ogni posizione della cifra rappresenta una potenza di ventisei, quindi, ad esempio, il numero ABC rappresenta il valore 1 × 26 ² + 2 × 26 ¹ + 3 × 26 ⁰ = 731 in base 10.

Molti fogli di calcolo, incluso Microsoft Excel, utilizzano questo sistema per assegnare etichette alle colonne di un foglio di calcolo, iniziando da A, B, C, ..., Z, AA, AB, ..., AZ, BA, ..., ZZ, AAA , ecc. Ad esempio, in Excel 2013, possono essere presenti fino a 16384 colonne (2 ¹⁴ in codice binario), etichettate da A a XFD. Una variante di questo sistema viene utilizzata per denominare le stelle variabili . Può essere applicato a qualsiasi problema in cui si desidera una denominazione sistematica utilizzando le lettere, utilizzando le stringhe più corte possibili.

Note storiche

Il fatto che ogni intero non negativo abbia una rappresentazione unica in base biunivoca- k ( k ≥ 1) è un " teorema popolare " che è stato riscoperto molte volte. I primi esempi sono Foster (1947) per il caso k = 10, e Smullyan (1961) e Böhm (1964) per tutti k ≥ 1. Smullyan usa questo sistema per fornire una numerazione Gödel delle stringhe di simboli in un sistema logico; Böhm usa queste rappresentazioni per eseguire calcoli nel linguaggio di programmazione P′′ . Knuth (1969) cita il caso speciale di k = 10, e Salomaa (1973) discute i casi k ≥ 2. Forslund (1995) sembra essere un'altra riscoperta e ipotizza che se gli antichi sistemi di numerazione usassero la base biiettiva k , potrebbero non essere riconosciuto come tale nei documenti archeologici, a causa della scarsa familiarità con questo sistema.

Appunti

Riferimenti

• Böhm, C. (luglio 1964), "Su una famiglia di macchine di Turing e il relativo linguaggio di programmazione", Bollettino ICC , 3 : 191.
• Forslund, Robert R. (1995), "Un'alternativa logica al sistema numerico posizionale esistente", Southwest Journal of Pure and Applied Mathematics , 1 : 27-29, MR  1386376 , S2CID  19010664.
• Foster, JE (1947), "Un sistema numerico senza simbolo zero", Mathematics Magazine , 21 (1): 39–41, doi : 10.2307/3029479 , JSTOR  3029479.
• Knuth, DE (1969), L'arte della programmazione informatica, vol. 2: Algoritmi seminumerici (1a ed.), Addison-Wesley, Soluzione all'esercizio 4.1-24, p. 195. (Discute la base biunivoca-10.)
• Salomaa, A. (1973), Linguaggi formali , Academic Press, Nota 9.1, pp. 90-91. (Discute la base biunivoca- k per ogni k ≥ 2.)
• Smullyan, R. (1961), "9. Ordinamento lessicografico; rappresentazione n- adica di interi" , Teoria dei sistemi formali , Annals of Mathematics Studies, 47 , Princeton University Press, pp. 34-36.