Python pour l'épreuve E3 : bases, PGCD, matrices et graphes

À l'épreuve E3 « Mathématiques pour l'informatique » du BTS SIO, Python sert à programmer les algorithmes du module d'algorithmique appliquée, souvent appliqués aux autres modules : arithmétique, matrices, algèbre de Boole, ensembles, graphes. Ce chapitre rassemble ce que Python offre pour ces notions (opérateurs, fonctions intégrées, structures), les pièges propres aux maths en Python, la façon de vérifier ses algorithmes pendant l'épreuve, et un sujet complet de type situation A, corrigé. Les algorithmes eux-mêmes sont détaillés dans les cours de maths et d'algorithmique, indiqués à chaque fois.

Ce que l'E3 attend en Python

L'épreuve E3 (coefficient 3) est commune aux deux options. Le référentiel du BTS SIO recommande Python (« recommandé sans être imposé ») et la définit ainsi :

Les huit critères d'évaluation de la situation A, le déroulé minute par minute et la méthode pour l'oral sont détaillés dans le cours Algorithmique. Le cours Épreuve E3 rassemble les règles, les sujets et la méthode de toute l'épreuve. Retiens deux choses du référentiel : seule l'algorithmique est évaluée en situation A (la méthode mathématique est fournie dans le sujet), et deux critères sur huit portent sur les tests et la correction d'erreurs.

Les outils de Python pour l'arithmétique et les bases

>>> divmod(2026, 16)
(126, 10)
>>> 2026 // 16, 2026 % 16
(126, 10)
>>> -7 // 2, -7 % 2
(-4, 1)
>>> import math
>>> math.gcd(1071, 462), math.lcm(12, 18)
(21, 36)
>>> math.isqrt(50)
7
>>> pow(3, 200, 26)
9
>>> pow(7, -1, 26)
15
>>> bin(177), hex(177), oct(493)
('0b10110001', '0xb1', '0o755')
>>> int("10110001", 2), int("B1", 16), int("755", 8)
(177, 177, 493)
>>> format(177, "08b"), format(177, "X")
('10110001', 'B1')
>>> 177 & 0b11110000, 177 | 0b1111, 177 ^ 255, 177 >> 4
(176, 191, 78, 11)

Deux remarques. Le reste % de Python est toujours du signe du diviseur : -7 % 2 vaut 1, ce qui correspond à la congruence des maths (−7 ≡ 1 [2]) ; d'autres langages renvoient −1. Et pow(3, 200, 26) calcule 3²⁰⁰ modulo 26 sans jamais construire ce nombre de 96 chiffres.

Écrire soi-même le PGCD et les changements de base

Trois algorithmes d'arithmétique sont à savoir écrire sans aide : le PGCD par l'algorithme d'Euclide, l'écriture d'un nombre dans une base (2, 8 ou 16) et la lecture d'une écriture en base b. Les voici écrits sans les fonctions intégrées, qui servent seulement à les vérifier :

# algos_e3.py : le PGCD et les changements de base écrits à la main, vérifiés par les fonctions intégrées
import math

CHIFFRES = "0123456789ABCDEF"


def pgcd(a, b):
    """Algorithme d'Euclide : pgcd(a, b) = pgcd(b, a mod b), jusqu'à un reste nul."""
    while b != 0:
        a, b = b, a % b
    return a


def vers_base(n, base):
    """Écriture de l'entier n >= 0 en base 2 à 16, par divisions successives."""
    if n == 0:
        return "0"
    resultat = ""
    while n > 0:
        n, reste = divmod(n, base)
        resultat = CHIFFRES[reste] + resultat     # le reste est le chiffre suivant, vers la gauche
    return resultat


def depuis_base(texte, base):
    """Valeur décimale d'une écriture en base 2 à 16, par le schéma de Horner."""
    valeur = 0
    for caractere in texte.upper():
        valeur = valeur * base + CHIFFRES.index(caractere)
    return valeur


if __name__ == "__main__":
    for a, b in [(1071, 462), (84, 36), (17, 5), (12, 0)]:
        assert pgcd(a, b) == math.gcd(a, b)
    for n in [0, 1, 177, 255, 2026]:
        assert vers_base(n, 2) == format(n, "b")
        assert vers_base(n, 16) == format(n, "X")
        assert depuis_base(vers_base(n, 8), 8) == n
    print(pgcd(1071, 462), vers_base(177, 2), vers_base(2026, 16), depuis_base("7EA", 16))

21 10110001 7EA 2026

Le PGCD. À chaque tour, (a, b) devient (b, a % b) ; quand le reste est nul, a contient le dernier reste non nul, c'est-à-dire le PGCD. Pour pgcd(1071, 462) :

L'affectation simultanée a, b = b, a % b calcule les deux valeurs de droite avant de les ranger : en pseudo-code, il faut une variable intermédiaire (r ← a mod b, a ← b, b ← r), et c'est ainsi qu'on l'écrit sur table.

Vers une base. Chaque division par la base donne un reste, qui est le chiffre suivant en partant de la droite : d'où CHIFFRES[reste] + resultat, qui ajoute le chiffre à gauche. La chaîne CHIFFRES traduit un reste de 10 à 15 en lettre (A à F). Le cas n = 0 est traité à part : sans lui, la boucle ne tournerait pas et la fonction renverrait une chaîne vide.

Depuis une base. Le schéma de Horner lit les chiffres de gauche à droite et multiplie la valeur par la base avant d'ajouter chaque chiffre. Pour "7EA" en base 16 : 7, puis 7 × 16 + 14 = 126, puis 126 × 16 + 10 = 2026. CHIFFRES.index(caractere) donne la valeur d'un chiffre, et upper() accepte aussi "7ea".

Le bloc __main__ est le jeu d'essai : un cas calculé à la main, les limites (0, 1, un PGCD avec 0), la comparaison avec math.gcd et format, et l'aller-retour par la base 8. Les assert restent muets quand tout est juste ; un assert faux arrête le programme sur une AssertionError qui désigne la ligne. Ces algorithmes sont détaillés en pseudo-code, avec leurs justifications, dans les chapitres déjà cités : l'algorithme d'Euclide, les divisions successives et les conversions de base en Python.

Matrices en listes de listes

Python n'a pas de type matrice dans sa bibliothèque standard : une matrice est une liste de lignes, M[i][j] est l'élément de la ligne i et de la colonne j, indices à partir de 0. Le piège classique est la création :

>>> M = [[0] * 3] * 3
>>> M[0][0] = 1
>>> M
[[1, 0, 0], [1, 0, 0], [1, 0, 0]]
>>> M = [[0] * 3 for _ in range(3)]
>>> M[0][0] = 1
>>> M
[[1, 0, 0], [0, 0, 0], [0, 0, 0]]

[[0] * 3] * 3 crée une seule ligne et la répète trois fois : les trois « lignes » sont la même liste, et modifier l'une modifie les trois (le partage de références du chapitre 5). La compréhension crée une nouvelle ligne à chaque tour. Le produit matriciel, la transposée et les puissances s'écrivent avec des boucles imbriquées ou des compréhensions (matrices et produit matriciel en Python) ; la théorie est dans le cours Matrices. Hors épreuve, les calculs matriciels lourds se font avec la bibliothèque NumPy.

Graphes en dictionnaires et en matrices

Un graphe orienté se représente de deux façons, et tu dois savoir passer de l'une à l'autre : le dictionnaire des successeurs (chaque sommet donne la liste de ses successeurs) et la matrice d'adjacence (1 en ligne i, colonne j, s'il y a un arc de i vers j).

# graphe.py : un graphe orienté en dictionnaire, puis en matrice d'adjacence
SUCCESSEURS = {"A": ["B", "C"], "B": ["C", "D"], "C": ["D"], "D": ["A"]}
SOMMETS = sorted(SUCCESSEURS)


def matrice_adjacence(successeurs, sommets):
    """Matrice M telle que M[i][j] = 1 s'il y a un arc de sommets[i] vers sommets[j]."""
    return [[1 if y in successeurs[x] else 0 for y in sommets] for x in sommets]


def produit(A, B):
    """Produit de deux matrices carrées de même taille."""
    n = len(A)
    return [[sum(A[i][k] * B[k][j] for k in range(n)) for j in range(n)] for i in range(n)]


def afficher(M, sommets):
    print("   " + " ".join(sommets))
    for x, ligne in zip(sommets, M):
        print(f"{x}  " + " ".join(str(v) for v in ligne))


M = matrice_adjacence(SUCCESSEURS, SOMMETS)
afficher(M, SOMMETS)
M2 = produit(M, M)
print("M² : nombre de chemins de longueur 2")
afficher(M2, SOMMETS)
print("Chemins de longueur 2 de A vers D :", M2[SOMMETS.index("A")][SOMMETS.index("D")])

   A B C D
A  0 1 1 0
B  0 0 1 1
C  0 0 0 1
D  1 0 0 0
M² : nombre de chemins de longueur 2
   A B C D
A  0 0 1 2
B  1 0 0 1
C  1 0 0 0
D  0 1 1 0
Chemins de longueur 2 de A vers D : 2

Le coefficient de la ligne A, colonne D de M² vaut 2 : il y a deux chemins de longueur 2 de A vers D (A → B → D et A → C → D). C'est la propriété des puissances de la matrice d'adjacence (chemins de longueur p). Le cours Graphes programme aussi la fermeture transitive (Roy-Warshall), le plus court chemin (Dijkstra) et l'ordonnancement (méthode MPM), et le cours Algorithmique les parcours en largeur et en profondeur (parcourir un graphe).

Ensembles et tables de vérité

Les ensembles de Python (set) appliquent directement les opérations du cours Ensembles : & pour l'intersection, | pour la réunion, - pour la différence (chapitre 6). Pour la logique, itertools.product énumère toutes les combinaisons de valeurs de vérité, ce qui permet de vérifier une loi ou une simplification sur toute sa table :

# verite.py : vérifier une loi de De Morgan sur toute la table de vérité
from itertools import product

print(" a     b     non(a et b)  (non a) ou (non b)")
for a, b in product([False, True], repeat=2):
    gauche = not (a and b)
    droite = (not a) or (not b)
    print(f"{a!s:<6}{b!s:<6}{gauche!s:<13}{droite}")
    assert gauche == droite
print("Loi vérifiée pour les 4 cas")

 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
Loi vérifiée pour les 4 cas

Remplace les deux expressions par ta simplification d'un exercice d'algèbre de Boole (simplifier une expression booléenne) : si un assert échoue, la ligne affichée juste avant donne le cas qui contredit ton calcul. Avec trois variables, repeat=3 donne les 8 lignes.

Tester ses algorithmes pendant l'épreuve

Le critère « adéquation des tests de validation » se prépare comme au chapitre 15, mais sans pytest : un bloc d'assert sous if __name__ == "__main__": suffit, et il reste dans ton fichier pour être rejoué devant la commission.

1. Un cas normal, calculé à la main sur table.
2. Les cas limites : 0, 1, la liste vide, le plus grand nombre autorisé, un seul élément.
3. Une vérification croisée avec une fonction intégrée (bin, int(…, 2), math.gcd) ou une propriété (convertir puis reconvertir redonne la valeur de départ).
4. Un cas d'erreur, si le sujet en prévoit : que renvoie ta fonction pour une saisie invalide ?

Sujet type situation A : les droits d'accès Linux

Contexte. Sous Linux, les droits d'un fichier tiennent sur 9 bits : lecture (r), écriture (w) et exécution (x) pour le propriétaire, le groupe et les autres (droits Linux). Ils s'écrivent en symbolique (rwxr-xr--) ou en octal, avec un chiffre par catégorie (754). Le technicien de Sorbier veut un petit outil qui passe d'une écriture à l'autre et calcule les droits réellement appliqués à un nouveau fichier.

Méthode fournie. Chaque chiffre octal est la somme des poids des droits accordés : r vaut 4, w vaut 2, x vaut 1 (7 = 4 + 2 + 1 = rwx, 5 = 4 + 1 = r-x). Le masque (umask) retire des droits : pour chaque chiffre, les droits effectifs sont les bits des droits demandés ET NON les bits du masque.

Composant fourni.

LETTRES = "rwx"


def chiffre_vers_symboles(chiffre):
    """Composant fourni : 7 -> 'rwx', 5 -> 'r-x', 0 -> '---'."""
    resultat = ""
    for rang, poids in enumerate([4, 2, 1]):
        if chiffre >= poids:
            resultat += LETTRES[rang]
            chiffre -= poids
        else:
            resultat += "-"
    return resultat

Sur table.

1. Fais la trace de chiffre_vers_symboles(5) : valeurs de rang, poids, chiffre et resultat à chaque tour.
2. Écris la fonction symbolique(octal), qui reçoit une chaîne de 3 chiffres ("754") et renvoie la chaîne de 9 symboles ("rwxr-xr--"), en utilisant le composant.
3. Écris la fonction inverse octal(symboles) : "rwxr-x---" donne "750".

Sur machine.

4. Écris droits_effectifs(demandes, umask) : droits_effectifs("666", "022") renvoie "644".
5. Programme le tout et propose un jeu d'essai justifié.

"""droits.py : sujet type situation A, les droits d'accès Linux (corrigé)."""

LETTRES = "rwx"


def chiffre_vers_symboles(chiffre):
    """Composant fourni : 7 -> 'rwx', 5 -> 'r-x', 0 -> '---'."""
    resultat = ""
    for rang, poids in enumerate([4, 2, 1]):
        if chiffre >= poids:
            resultat += LETTRES[rang]
            chiffre -= poids
        else:
            resultat += "-"
    return resultat


def symbolique(octal):
    """Question 2 : '754' -> 'rwxr-xr--'."""
    return "".join(chiffre_vers_symboles(int(c)) for c in octal)


def octal(symboles):
    """Question 3 : 'rwxr-x---' -> '750'."""
    resultat = ""
    for debut in range(0, 9, 3):
        bloc = symboles[debut:debut + 3]
        valeur = 0
        for rang, poids in enumerate([4, 2, 1]):
            if bloc[rang] != "-":
                valeur += poids
        resultat += str(valeur)
    return resultat


def droits_effectifs(demandes, umask):
    """Question 4 : droits demandés ET NON umask, en octal ('666', '022' -> '644')."""
    return "".join(str(int(d) & ~int(u) & 7) for d, u in zip(demandes, umask))


if __name__ == "__main__":
    # Question 5 : jeu d'essai, avec des cas limites
    assert symbolique("754") == "rwxr-xr--"
    assert symbolique("000") == "---------"
    assert symbolique("777") == "rwxrwxrwx"
    assert octal("rwxr-x---") == "750"
    assert octal(symbolique("640")) == "640"
    assert droits_effectifs("666", "022") == "644"
    assert droits_effectifs("777", "027") == "750"
    assert droits_effectifs("640", "777") == "000"
    for code in ["754", "640", "600", "775"]:                 # vérification croisée
        assert int(octal(symbolique(code)), 8) == int(code, 8)
    print("Jeu d'essai : tous les tests passent")
    print(symbolique("754"), octal("rw-r-----"), droits_effectifs("666", "027"))

Jeu d'essai : tous les tests passent
rwxr-xr-- 640 640