Algorithmes des maths du BTS SIO en Python

Les sujets d'algorithmique du BTS SIO s'appuient volontiers sur les autres modules de mathématiques pour l'informatique : conversions entre bases, PGCD, nombres premiers, congruences, algèbre de Boole, ensembles et graphes. Ce chapitre programme ces objets en Python : conversion décimal-binaire, algorithme d'Euclide, crible d'Ératosthène, clé de contrôle, table de vérité, parcours en largeur et en profondeur d'un graphe.

Pourquoi ce chapitre ?

Le programme d'algorithmique appliquée recommande de choisir les sujets d'exercices dans les autres modules de mathématiques et dans des thèmes informatiques comme le codage, le cryptage, la redondance de sécurité, le tri ou le parcours de graphes. À l'épreuve, si un exercice s'appuie sur une notion d'un autre module, la méthode est fournie dans le sujet : on ne t'évalue pas sur la théorie, mais sur ta capacité à la programmer. Ce chapitre te fait rencontrer ces sujets avant le jour J. Pour la théorie, renvoie-toi aux cours d'arithmétique, de logique, de matrices et de graphes.

Convertir un nombre dans une autre base

Pour écrire un entier n en base 2, on le divise par 2 tant qu'il n'est pas nul : les restes successifs, lus du dernier au premier, sont ses chiffres binaires. Pour 37 :

En lisant la colonne des restes de bas en haut : 37 s'écrit 100101 en binaire. Dans l'algorithme, on obtient le même ordre en ajoutant chaque nouveau chiffre à gauche de la chaîne résultat.

Fonction DecimalVersBinaire(n : entier) : chaîne
// Précondition : n ≥ 0
    Si n = 0 Alors
        Retourner "0"
    FinSi
    resultat ← ""
    TantQue n > 0 Faire
        resultat ← chaine(n MOD 2) & resultat
        n ← n DIV 2
    FinTantQue
    Retourner resultat
FinFonction

def decimal_vers_base(n, base):
    """Écrit l'entier n ≥ 0 dans une base de 2 à 16."""
    chiffres = "0123456789ABCDEF"
    if n == 0:
        return "0"
    resultat = ""
    while n > 0:
        resultat = chiffres[n % base] + resultat
        n = n // base
    return resultat


print(decimal_vers_base(37, 2), decimal_vers_base(2026, 2))
print(decimal_vers_base(172, 16), decimal_vers_base(2026, 16))

100101 11111101010
AC 7EA

La chaîne chiffres donne le symbole de chaque reste : en base 16, le reste 12 s'écrit C. C'est un usage classique d'une chaîne comme table de correspondance.

L'opération inverse lit les chiffres de gauche à droite : à chaque chiffre, on multiplie le résultat par la base et on ajoute la valeur du chiffre (c'est le schéma de Horner). Pour "100101" : 1, puis 1 × 2 + 0 = 2, 2 × 2 + 0 = 4, 4 × 2 + 1 = 9, 9 × 2 + 0 = 18, 18 × 2 + 1 = 37.

def base_vers_decimal(texte, base):
    """Valeur de l'écriture texte (chiffres 0-9, A-F) dans la base donnée."""
    chiffres = "0123456789ABCDEF"
    valeur = 0
    for c in texte.upper():
        valeur = valeur * base + chiffres.find(c)
    return valeur


print(base_vers_decimal("100101", 2), base_vers_decimal("AC", 16), base_vers_decimal("7ea", 16))

37 172 2026

Python fait aussi ces conversions directement : bin(37) donne '0b100101', hex(172) donne '0xac', int("100101", 2) donne 37, int("AC", 16) donne 172, et format(5, "08b") donne '00000101' (sur 8 bits, avec des zéros de tête, utile pour un octet d'adresse IP). La méthode des divisions est détaillée au cours d'arithmétique (conversions entre décimal, binaire et hexadécimal), qui programme aussi ces conversions sans bin ni int dans ses algorithmes d'arithmétique en Python.

PGCD et algorithme d'Euclide

Le PGCD (plus grand commun diviseur) de deux entiers a et b se calcule avec l'algorithme d'Euclide, qui repose sur une propriété : PGCD(a, b) = PGCD(b, a MOD b), et PGCD(a, 0) = a. On remplace donc le couple (a, b) par (b, a MOD b) jusqu'à ce que b soit nul.

Fonction PGCD(a : entier, b : entier) : entier
// Précondition : a ≥ 0, b ≥ 0, pas tous les deux nuls
    TantQue b ≠ 0 Faire
        r ← a MOD b
        a ← b
        b ← r
    FinTantQue
    Retourner a
FinFonction

Trace de PGCD(252, 105) :

Le PGCD est 21. On vérifie : 252 = 21 × 12 et 105 = 21 × 5, et 12 et 5 n'ont pas de diviseur commun.

def pgcd(a, b):
    while b != 0:
        a, b = b, a % b
    return a


def ppcm(a, b):
    return a * b // pgcd(a, b)


print(pgcd(252, 105), ppcm(252, 105), pgcd(17, 5))

21 1260 1

Le PPCM se déduit du PGCD : PPCM(a, b) × PGCD(a, b) = a × b. Deux entiers dont le PGCD vaut 1 sont premiers entre eux : c'est la condition pour que la clé a d'un chiffrement affine soit utilisable. Python a aussi math.gcd(a, b).

L'algorithme d'Euclide est très rapide : le nombre de tours ne dépasse pas cinq fois le nombre de chiffres du plus petit des deux nombres (c'est le théorème de Lamé). Même pour des nombres de plusieurs centaines de chiffres, comme ceux de la cryptographie, il reste de l'ordre du millier de tours au plus. Une variante plus ancienne, par soustractions successives (on remplace le plus grand par la différence), donne le même résultat mais peut faire énormément de tours : PGCD(1 000 000, 1) en demanderait 999 999.

Nombres premiers

Un entier n ≥ 2 est premier s'il n'a pas d'autre diviseur que 1 et lui-même. Pour le tester, on cherche un diviseur entre 2 et √n : si n = a × b avec a ≤ b, alors a ≤ √n. Inutile d'aller plus loin.

def est_premier(n):
    if n < 2:
        return False
    d = 2
    while d * d <= n:
        if n % d == 0:
            return False
        d = d + 1
    return True


print([n for n in range(1, 30) if est_premier(n)])
print(est_premier(97), est_premier(91))

[2, 3, 5, 7, 11, 13, 17, 19, 23, 29]
True False

97 est premier ; 91 ne l'est pas, car 91 = 7 × 13, ce qu'on oublie souvent. Le test d * d <= n évite de calculer une racine carrée en réel, et la boucle s'arrête dès le premier diviseur trouvé.

Pour lister tous les nombres premiers jusqu'à N, le crible d'Ératosthène est plus efficace que de tester chaque nombre. On part d'un tableau de booléens « premier ? » tous vrais, puis, pour chaque nombre premier p trouvé, on raye ses multiples.

def crible(n):
    premier = [True] * (n + 1)   # premier[k] : k est-il premier ?
    premier[0] = False
    premier[1] = False
    p = 2
    while p * p <= n:
        if premier[p]:
            for multiple in range(p * p, n + 1, p):
                premier[multiple] = False
        p = p + 1
    resultat = []
    for k in range(n + 1):
        if premier[k]:
            resultat.append(k)
    return resultat


print(crible(50))

[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47]

On commence à rayer à p × p : les multiples plus petits (2p, 3p…) ont déjà été rayés par un nombre premier plus petit. Ici, le tableau sert d'indicateur : l'indice est le nombre, la valeur dit s'il est premier.

Congruences et clés de contrôle

Deux entiers sont congrus modulo n s'ils ont le même reste dans la division par n : en Python, a % n == b % n. Les congruences sont partout en informatique : le MOD 26 du code de César, les heures ((22 + 5) % 24 vaut 3), et les clés de contrôle, un exemple de « redondance de sécurité » cité par le programme.

Une clé de contrôle est un chiffre ajouté à la fin d'un code, calculé à partir des autres. Si une erreur de saisie modifie un chiffre, la clé ne correspond plus et l'erreur est détectée. Le code ISBN-13 des livres en est un exemple : on multiplie les 12 premiers chiffres alternativement par 1 et par 3, on fait la somme S, et la clé est le nombre qui complète S jusqu'au multiple de 10 suivant, soit (10 - S MOD 10) MOD 10.

def cle_isbn13(debut):
    """Clé de contrôle des 12 premiers chiffres d'un ISBN-13 (chaîne)."""
    somme = 0
    for i in range(12):
        chiffre = int(debut[i])
        if i % 2 == 0:
            somme = somme + chiffre
        else:
            somme = somme + 3 * chiffre
    return (10 - somme % 10) % 10


def isbn13_valide(code):
    code = code.replace("-", "")
    return len(code) == 13 and code.isdigit() and cle_isbn13(code) == int(code[12])


print(cle_isbn13("978210084927"))
print(isbn13_valide("978-2-10-084927-7"), isbn13_valide("978-2-10-048927-7"))
print(isbn13_valide("978-2-10-084972-7"))

7
True False
True

Pour 978210084927, la somme pondérée vaut 123 ; 123 MOD 10 = 3, et la clé est 10 − 3 = 7. Le deuxième code, où deux chiffres voisins ont été inversés (84 devenu 48), est détecté. Le troisième montre la limite de cette clé : l'inversion de 27 en 72 passe inaperçue, car inverser deux chiffres voisins x et y modifie la somme de 2 × (x − y) (chacun échange son poids 1 contre 3 ou l'inverse) ; avec un écart de 5, la somme change de 10, et la clé reste la même. Aucune clé à un chiffre ne détecte toutes les erreurs : c'est un compromis entre la longueur du code et la sécurité. Le dernier MOD 10 traite le cas où la somme est déjà un multiple de 10 : la clé vaut alors 0, et pas 10.

Tables de vérité et algèbre de Boole

Une expression booléenne de n variables a 2ⁿ combinaisons de valeurs. Des boucles imbriquées sur [False, True] les énumèrent toutes : c'est une table de vérité automatique, qui permet de vérifier une simplification ou une loi.

print("a     b     NON(a ET b)  NON a OU NON b")
for a in [False, True]:
    for b in [False, True]:
        gauche = not (a and b)
        droite = (not a) or (not b)
        print(f"{a!s:5} {b!s:5} {gauche!s:12} {droite!s}")

a     b     NON(a ET b)  NON a OU NON b
False False True         True
False True  True         True
True  False True         True
True  True  False        False

Les deux colonnes de droite sont identiques sur les quatre lignes : la loi de De Morgan est vérifiée. Avec trois variables, on ajoute une troisième boucle (8 lignes). Le format !s:5 convertit le booléen en texte et l'aligne sur 5 caractères. Les lois et les tableaux de Karnaugh sont au cours d'algèbre de Boole.

Les ensembles

Python a un type set (ensemble) : une collection sans doublon et sans ordre, avec les opérations de la théorie des ensembles.

slam = {"Inès", "Hugo", "Léa", "Malik"}
alternants = {"Hugo", "Malik", "Zoé"}
print(sorted(slam | alternants))   # union
print(sorted(slam & alternants))   # intersection
print(sorted(slam - alternants))   # différence
print("Léa" in slam, len(slam))

['Hugo', 'Inès', 'Léa', 'Malik', 'Zoé']
['Hugo', 'Malik']
['Inès', 'Léa']
True 4

sorted est là pour l'affichage : un ensemble n'a pas d'ordre, et Python l'affiche dans un ordre qui peut varier. Sans le type set, l'intersection s'écrit avec deux boucles (pour chaque élément de A, rechercher s'il est dans B) : c'est un bon exercice de recherche séquentielle. La réunion, l'intersection, la différence et le produit cartésien sont expliqués au cours de théorie des ensembles.

Parcourir un graphe

Un graphe est un ensemble de sommets reliés par des arêtes : des routeurs reliés par des liens, des pages web reliées par des liens hypertexte, des tâches reliées par des contraintes d'ordre. On le représente en machine de deux façons.

La matrice d'adjacence : un tableau n × n où la case [i][j] vaut 1 si les sommets i et j sont reliés (chapitre 8). Les listes d'adjacence : pour chaque sommet, la liste de ses voisins. En Python, un dictionnaire de listes s'y prête bien :

reseau = {
    "R1": ["R2", "R3"],
    "R2": ["R1", "R4"],
    "R3": ["R1", "R4", "R5"],
    "R4": ["R2", "R3", "R6"],
    "R5": ["R3"],
    "R6": ["R4"],
}

Le parcours en largeur visite les sommets par distance croissante au départ : d'abord le départ, puis ses voisins, puis les voisins de ses voisins, etc. Il utilise une file (premier arrivé, premier servi) : on retire le sommet en tête, on ajoute à la fin ceux de ses voisins qu'on n'a pas encore vus. Il donne, pour chaque sommet, le nombre minimal d'arêtes depuis le départ : le nombre de sauts d'un paquet dans un réseau.

def parcours_largeur(graphe, depart):
    """Renvoie l'ordre de visite et la distance (en arêtes) de chaque sommet atteint."""
    distance = {depart: 0}
    file = [depart]
    ordre = []
    while len(file) > 0:
        sommet = file.pop(0)           # on retire la tête de la file
        ordre.append(sommet)
        for voisin in graphe[sommet]:
            if voisin not in distance:  # pas encore découvert
                distance[voisin] = distance[sommet] + 1
                file.append(voisin)     # on l'ajoute en fin de file
    return ordre, distance


reseau = {"R1": ["R2", "R3"], "R2": ["R1", "R4"], "R3": ["R1", "R4", "R5"],
          "R4": ["R2", "R3", "R6"], "R5": ["R3"], "R6": ["R4"]}
ordre, distance = parcours_largeur(reseau, "R1")
print(ordre)
print(distance)

['R1', 'R2', 'R3', 'R4', 'R5', 'R6']
{'R1': 0, 'R2': 1, 'R3': 1, 'R4': 2, 'R5': 2, 'R6': 3}

Le dictionnaire distance sert aussi à savoir si un sommet a déjà été découvert : sans ce test, R1 et R2 se renverraient l'un l'autre indéfiniment. file.pop(0) est simple mais lent sur de très grandes files ; en Python professionnel, on utilise collections.deque et sa méthode popleft().

Le parcours en profondeur va le plus loin possible avant de revenir en arrière. Il utilise une pile (dernier arrivé, premier servi) à la place de la file : pile.pop() retire le dernier élément ajouté.

def parcours_profondeur(graphe, depart):
    visites = []
    pile = [depart]
    while len(pile) > 0:
        sommet = pile.pop()             # on retire le sommet du dessus
        if sommet not in visites:
            visites.append(sommet)
            # on empile les voisins à l'envers pour les visiter dans l'ordre de la liste
            for voisin in graphe[sommet][::-1]:
                if voisin not in visites:
                    pile.append(voisin)
    return visites


reseau = {"R1": ["R2", "R3"], "R2": ["R1", "R4"], "R3": ["R1", "R4", "R5"],
          "R4": ["R2", "R3", "R6"], "R5": ["R3"], "R6": ["R4"]}
print(parcours_profondeur(reseau, "R1"))

['R1', 'R2', 'R4', 'R3', 'R5', 'R6']

Depuis R1, le parcours plonge dans R2, puis R4, puis R3 (premier voisin non visité de R4), puis R5 ; arrivé au bout, il dépile jusqu'à trouver R6. Les deux parcours visitent les mêmes sommets dans un ordre différent. Ils répondent à la question « quels sommets sont atteignables ? », et donc « le réseau est-il connexe ? » (tous les sommets sont-ils visités ?). Le vocabulaire des graphes et les algorithmes de plus court chemin sont au cours de graphes, avec l'algorithme de Dijkstra.

Exercices

def somme_diviseurs(n):
    """Somme des diviseurs de n, n exclu."""
    somme = 0
    for d in range(1, n):
        if n % d == 0:
            somme = somme + d
    return somme


for n in range(2, 1000):
    if somme_diviseurs(n) == n:
        print(n)

for a in [False, True]:
    for b in [False, True]:
        for c in [False, True]:
            expr = (a and b) or (not a and c)
            si_alors = b if a else c
            print(a, b, c, expr, expr == si_alors)

def est_connexe(graphe):
    depart = list(graphe.keys())[0]   # un sommet quelconque
    ordre, distance = parcours_largeur(graphe, depart)
    return len(ordre) == len(graphe)