Il sistema di numerazione utilizzato normalmente è il sistema decimale posizionale; nell’uso pratico sopravvivono sistemi diversi, ad esempio il sistema sessagesimale relativo alla misura degli angoli, o quello misto relativo alla misura del tempo.
L’espressione generale (posizionale) di un numero è:
(an…a1a0)b = anbn+…+a1b1 + a0b0
dove b è la base del sistema di numerazione e a0, a1, … an sono simboli (numeri) appartenenti ad un insieme di b simboli diversi, per il sistema decimale essi sono {0,1,2,3,4,5,6,7,8,9}.
Il calcolatore lavora con numeri binari, cioè con numeri formati con i due simboli 0 e 1, per esempio il numero decimale (241)10 = 2*102 + 4*101 + 1*100 è (11110001)2 = 1*107 + 1*106 + 1*105 + 1*104 + 0*103 + 0*102 + 0*101 + 1*100).
Per comodita talvolta si rappresenta il contenuto della memoria in notazione esadecimale: ogni byte è rappresentato con due simboli appartenenti alll’insime {0,1,2,3,4,5,6,7,8,9,A,B,C,D,E,F}, (241)10 è dunque (F1)16.
Un metodo veloce per trasformare un numero binario in uno esadecimale si ottiene considerando le cifre binarie a gruppi di 4: (241)10 = (1111 0001)2 = (F1)16.
Sia N il numero da convertire nell’equivalente in base b (N) b: ogni cifra di (N)b, a partire dall’unità, è il resto della divisione di N per b, e successivamente il resto del risultato della divisione per b, fino a quando il risultato é < b.
La parte intera di un numero frazionario si trasforma secondo quanto visto nel paragrafo precedente. Per la parte frazionaria ciò non vale: ad esempio (0,5)10 equivale a (0,50)10, in base al fatto che si possono aggiungere quanti zeri si vogliono, ma trasformando i due numeri otteniamo (0,5)7 che è diverso da (0,101)7. Entrambe le trasformazioni sono tuttavia errate perché (0,5)7 = (5*7-1)10 = (5/7)10 ben diverso da (1/2)10, e analogamente (0,101)7 = (1*7-1+1*7-2)10 = (8/49)10.
Per ottenere una conversione corretta le varie cifre q1 q2 … qn sono [1] :
qi = Int(b·ri·f)
dove b è la base, f è la parte frazionaria nella forma 0,.. e r1 = 1 e ri+1 = b·ri – Int(qi / f).
La congruenza è una derivazione del concetto di divisibilità fra numeri, sono un concetto centrale della teoria dei gruppi. Dal punto di vista pratico sono alla base della prova del 9 delle operazioni aritmetiche, e nei moderni sistemi di cifratura dei dati (v. par. 5.2 ). La definizione è i numeri a e b sono congrui modulo m, se a/m e b/m hanno lo stesso resto, in altre parole:
a ≡ b mod m se (a – b) = cm
E' facile verificare che la congruenza è una relazione di equivalenza. Per essa valgono le regole di addizione, sottrazione e moltiplicazione ed elevazione a potenza, da a ≡ a' mod m e b ≡ b' mod m:
i) a + b ≡ a' + b' mod m
ii) a - b ≡ a' - b' mod m
iii) a · b ≡ a' · b' mod m
iv) an ≡ bn mod m (se a ≡ b mod m )
ad esempio la iii):
(a – a') = cm
(b - b') = c'm
si moltiplichino ambo i membri della prima uguaglianza per b, e della seconda per a', quindi si sottragga dalla prima la seconda:
ba – ba' – a'b + a'b' = (b – a')cm ■
la iv) si può dimostrare per induzione:
essa vale per n = 1 per l'ipotesi, se vale per n generico, vale anche per n+1, infatti applicando la iii) dove al posto di a,a' si legga a,b e al posto di b,b' leggasi an,bn. ■
Il calcolo combinatorio elementare permette di determinare, dati certi oggetti, quante elencazioni di questi si possono fare sotto certe condizioni.
Siano dati n oggetti si dice permutazione o fattoriale di n, e lo si indica con n!, il numero di elencazioni possibili, senza ripetizione, degli n oggetti. Il valore di n! lo si ricava osservando che il primo elemento si può scegliere in n modi, per ognuno di questi, il secondo elemento si può scegliere in (n – 1) modi, e così via, in definitiva:
n! = n(n-1)…2.1
ad esempio le permutazioni di L = {A,B,C} sono 6: ABC, ACB, BAC, BCA, CAB, CBA.
Se invece degli n oggetti se ne vogliono k, con k < n, la formula è analoga:
Dn,k = n(n-1)…(n-k+1)
Che moltiplicato e diviso per (n-k)! diventa:
Dn,k = n! / (n-k)!
Dn,k è detto k-permutazioni o disposizioni (di k oggetti su n).
Poichè Dn,n = n! si assume che per convenzione sia 0! = 1.
Ad esempio le disposizioni di due oggetti da L = {A,B,C} sono 6: AB, AC, BA, BC, CA, CB
Le disposizioni con ripetizione di k oggetti su n sono kn, infatti nella prima posizione si possono avere n oggetti, nella seconda ancora n e così via.
Ad esempio le disposizioni con ripetizione di due oggetti da L = {A,B,C} sono 9: AA, AB, AC, BA, BB, BC, CA, CB, CC.
Si dice combinazione di k oggetti su n il numero degli insiemi distinti di k oggetti ottenibili da n. Nelle disposizioni di k oggetti da n ogni combinazione appare k! volte, quindi:
Cn,k = Dn,k / k! = n! / (n-k)!k!
Dalla relezione precedente si deduce che Cn,k = Cn,n-k.
Ad esempio le combinazioni di due oggetti da L = {A,B,C} sono 3: AB, AC, BC.
[1] Adattato da [FF] Vol. I pag. 269/270.