Numération¶

Prélude platonicien : un nombre entier, concept indépendant de notre manière de le représenter ou de le dire.

Nécessité de

représenter des nombres entiers
calculer sur cette représentation

remarque dans ce cours, conserver encore le système décimal comme base naturelle, ne pas trop vite généraliser.

Représentations¶

bâtons, points
ajout de symboles pour certains multiples
règles d’écriture, ex. chiffres romains

exercice 1 (commodité des calculs)
système indien, arabe : chiffres et position

exemples¶

système décimal, binaire, hexadécimal (noter le besoin de symboles)...

Système positionnel¶

système positionnel la valeur d’un chiffre dépend de sa position
base nombre de symboles (chiffres) utilisés dans le système

Fonctionne de manière générale avec tout entier \(n>=2\). notation utilisée ici : (symboles)_(base)

remarque il faut bien différencier un nombre de son écriture, en particulier «onze» désigne un nombre, qui s’écrit 11 en décimal, mais \((1011)_2\) en binaire. On évitera de lire «onze» le nombre \((11)_2\) puisque c’est en réalité «trois», il vaut mieux dire «un-un en base deux»

valeur d’un nombre¶

exercice 2 (convertir en décimal)

par convention, le nombre écrit

\[a_na_{n-1}\dots a_1a_0\]

en base \(b\) désigne l’entier

\[\sum_{i=0}^n a_ib^i = a_n\times b^n + \dots + a_1\times b + a_0\]

Remarques : combien de nombres représentés par au plus \(k\) symboles ? combien de symboles pour représenter \(n\) ? noter la formidable économie des systèmes positionnels

écriture d’un nombre¶

exercice 3 (décompositions, amener à la technique générale)

pour écrire un entier \(n\) dans une base \(b\) :

commencer par trouver le chiffre des unités, c’est le reste \(r\) de la division euclidienne \(n=q\times b+r\) ;

recommencer avec \(q\) pour obtenir les chiffres à gauche.

exercice 4, 5, 6 (décompositions)

Opérations¶

Très pénibles sans système positionnel, elles se réalisent sinon avec les techniques de primaire : tables d’addition et de multiplication sur les symboles, propagation des retenues.

exercices 8 et 9 (opérations binaire)

exercices 10 et 11 (autre base)

Algorithmes de conversion¶

Theoreme

Dans un système positionnel, il y a unicité de l’écriture de chaque entier.

Evaluation¶

Suivant la définition

def valeur(ecriture, symboles):
    base = len(symboles)
    nombre = 0
    i = 0
    for a in ecriture[::-1]: # parcours a l'envers
        ai = symboles.index(a)
        nombre = nombre + ai * base**i
        i = i + 1
    return nombre

>>> valeur('1233', '01234')
193
>>> valeur('11000001', '01')
193
>>> valeur('DB', '0123456789ABCD')
193
>>> valeur(u'•¶‡', u'ø•†‡◊ı∂∫¶')
193

Algorithme de Horner

def valeur(ecriture, symboles):
    base = len(symboles)
    nombre = 0
    for a in ecriture:
        nombre = nombre * base + symboles.index(a)
    return nombre

exercice 12 (Hörner)

Décomposition¶

Technique usuelle

def decomposition(n, symboles):
    base = len(symboles)
    if n < base:
        return symboles[n]
    else:
        q,r = n // base, n % base
        return decomposition(q, symboles) + symboles[r]

>>> decomposition(193, '01234')
'1233'
>>> decomposition(193, '01')
'11000001'
>>> decomposition(193, '0123456789ABCD')
'DB'
>>> print decomposition(193, u'ø•†‡◊ı∂∫¶')
•¶‡

À ce point, amener le fait que la base décimale n’a rien de canonique. Tout peut se faire en référence à une base privilégiée, ou même sans référence auquel cas la conversion peut se faire soit par décomposition (calculs dans la base de départ) soit par évaluation (calculs dans la base d’arrivée).

exercice 13 (Hörner en base 5)