Algorithmes

Dès la première

Algorithme d’Euclide

L’algorithme d’Euclide calcule le plus grand diviseur commun de deux entiers. Il repose sur l’égalité :

\[\operatorname{PGCD}(a,b)=\operatorname{PGCD}(b,r),\]

où \(r\) est le reste de la division euclidienne de \(a\) par \(b\). On recommence jusqu’à obtenir un reste nul.

Exemple

Algorithme d’Euclide

Prêt

a = 252 b = 105 while b != 0: # Le reste devient la nouvelle deuxième valeur. reste = a % b a = b b = reste print("PGCD :", a)

▶ Exécuter Effacer la sortie

Sortie

Le résultat peut d’abord être retrouvé par une décomposition en facteurs premiers, avant de changer les deux nombres. La boucle ne connaît pas à l’avance le nombre de divisions nécessaires.

Le chiffrement de César

Le chiffrement de César décale chaque lettre d’un même nombre de places dans l’alphabet. Avec un décalage de 3, A devient D, B devient E et X devient A. La clé du chiffrement est le nombre de places choisi.

MessageABC…XYZ

décalage de 3 ↓

Message chiffréDEF…ABC

On numérote les lettres de 0 à 25. Si une lettre occupe la position \(i\), sa position après un décalage \(k\) est \((i+k)\mathbin{\%}26\). Le reste de la division permet de revenir au début de l’alphabet après la lettre Z.

Voici le mécanisme pour une seule lettre :

Exemple

Décaler une lettre

Prêt

alphabet = "ABCDEFGHIJKLMNOPQRSTUVWXYZ" lettre = "X" decalage = 3 position = alphabet.index(lettre) nouvelle_position = (position + decalage) % 26 print(alphabet[nouvelle_position])

▶ Exécuter Effacer la sortie

Sortie

La méthode alphabet.index(lettre) donne la position de lettre dans la chaîne. Pour déchiffrer, il suffit d’effectuer le décalage opposé : une clé de 3 devient un décalage de −3.

Pour traiter un véritable message, on adopte une convention claire :

• les lettres de A à Z sont décalées dans l’alphabet majuscule ;

• les lettres de a à z sont décalées de la même façon, mais restent minuscules ;

• les espaces, les chiffres, la ponctuation et les lettres accentuées sont recopiés sans modification.

On peut donc utiliser deux chaînes, alphabet_majuscule et alphabet_minuscule. Chaque caractère est recherché dans l’une d’elles ; s’il n’appartient à aucune des deux, il est simplement ajouté au résultat.

Activité. Écrire une fonction cesar(message, decalage) qui respecte cette convention. La même fonction doit permettre de déchiffrer lorsqu’elle reçoit un décalage négatif.

Une piste si le retour après Z pose problème

Pour chaque caractère, vérifier s’il appartient à l’alphabet majuscule ou à l’alphabet minuscule. Dans ce cas, calculer sa nouvelle position avec % 26. Sinon, le recopier.

À toi

Chiffrer et déchiffrer un message

À faire

▶ Exécuter Effacer la sortie

Sortie

Ce procédé est intéressant pour comprendre un algorithme de chiffrement, mais il n’est pas sûr : il n’existe que 26 décalages possibles, que l’on peut tous essayer très rapidement.

Décoder par analyse de fréquence

Dans un texte français suffisamment long, la lettre E est généralement la plus fréquente. Si la lettre la plus fréquente d’un message chiffré est, par exemple, L, on peut supposer que le E du texte initial a été transformé en L.

Si \(j\) est la position de la lettre la plus fréquente et si E occupe la position 4, le décalage probable est \((j-4)\mathbin{\%}26\). Il reste alors à appliquer le décalage opposé avec la fonction cesar.

Les espaces et les autres caractères ne doivent pas entrer dans le comptage. Pour réunir majuscules et minuscules, on peut convertir temporairement chaque caractère avec upper() et ne compter que ceux qui appartiennent à "ABCDEFGHIJKLMNOPQRSTUVWXYZ". Les accents, laissés inchangés lors du chiffrement, sont également ignorés par cette analyse simplifiée.

Activité. Écrire une fonction decoder_frequence(message) qui renvoie un couple formé du décalage estimé et du texte décodé. La cellule réutilise automatiquement la fonction cesar écrite dans l’activité précédente : il n’est pas nécessaire de la recopier.

Pour tester la méthode, choisir sans précaution particulière un paragraphe français assez long, lui appliquer un décalage arbitraire avec cesar, puis donner uniquement le texte chiffré à decoder_frequence. Le texte initial doit être retrouvé sans fournir la clé au décodeur.

Un paragraphe chiffré prêt à tester

Ce texte a été produit avec la fonction précédente et un décalage inconnu. Il est assez long pour que l’hypothèse sur la lettre E soit pertinente. Il suffit de le placer entre triples guillemets pour le transmettre à decoder_frequence.

Jlaal zlthpul, slz lslclz vizlyclua slz kpmmlylualz lahwlz kl jlaal lewlyplujl.
Psz wyluulua sl altwz kl ylslcly slz tlzbylz, kl jvtwhyly slz ylzbsahaz la kl
ylkpnly luzltisl bul jvujsbzpvu wyljpzl. Sl wyvmlzzlby slby klthukl luzbpal kl
clypmply slbyz jhsjbsz la kl wylzlualy jshpyltlua slby klthyjol klchua sh jshzzl.

Pourquoi faut-il un texte assez long ?

Sur quelques mots, la lettre la plus fréquente peut très bien ne pas être E. L’analyse donne alors une mauvaise clé. Plus le texte est long, plus la fréquence observée a de chances de ressembler à la fréquence habituelle du français. Une méthode plus robuste comparerait les fréquences de toutes les lettres et pas seulement celle de E.

À toi

Retrouver automatiquement un décalage

À faire

▶ Exécuter Effacer la sortie

Sortie

Crible d’Ératosthène

Pour chercher tous les nombres premiers jusqu’à une limite, le crible d’Ératosthène commence par considérer tous les entiers comme premiers, puis élimine successivement les multiples de 2, de 3, de 5, etc.

Exemple

Nombres premiers jusqu’à 50

Prêt

limite = 50 est_premier = [True] * (limite + 1) est_premier[0] = False est_premier[1] = False # Il suffit de chercher les diviseurs jusqu'à la racine de la limite. for p in range(2, int(limite**0.5) + 1): if est_premier[p]: # Les multiples plus petits que p² ont déjà été éliminés. for multiple in range(p*p, limite + 1, p): est_premier[multiple] = False # On rassemble les indices restés associés à True. premiers = [] for n in range(limite + 1): if est_premier[n]: premiers.append(n) print(premiers)

▶ Exécuter Effacer la sortie

Sortie

La liste est_premier associe une valeur True ou False à chaque entier. La fonction int() transforme ici la racine carrée de la limite en entier. Le programme introduit aussi une boucle à l’intérieur d’une autre boucle. Change la limite et observe quels passages du programme n’ont pas besoin d’être modifiés.

Triangle de Pascal

Chaque ligne du triangle de Pascal commence et finit par 1. Entre les deux, un coefficient est la somme des deux coefficients situés au-dessus de lui. La ligne de rang \(n\) contient les coefficients binomiaux \(\binom n0,\ldots,\binom nn\).

La relation utilisée pour construire l’intérieur de la ligne est :

\[\binom{n}{0}=\binom{n}{n}=1, \qquad \binom{n}{k}=\binom{n-1}{k-1}+\binom{n-1}{k}.\]

11

121

1331

14641

15101051

Par exemple, 6 = 3 + 3.

Exemple

Construire les premières lignes

Prêt

ligne = [1] print(ligne) for n in range(1, 7): # Les deux bords de chaque nouvelle ligne valent 1. nouvelle = [1] # Chaque valeur intérieure utilise deux voisines de la ligne précédente. for k in range(1, len(ligne)): nouvelle.append(ligne[k-1] + ligne[k]) nouvelle.append(1) ligne = nouvelle print(ligne)

▶ Exécuter Effacer la sortie

Sortie

La construction réutilise une ligne déjà connue. Pour vérifier une ligne, sa somme doit être égale à \(2^n\).

Deux directions indépendantes. Le premier exercice prolonge directement le triangle. Le mélange aléatoire constitue un défi séparé. Les permutations et les sous-ensembles sont placés plus loin, après la récursivité qui permet de comprendre leur construction.

Construire une ligne donnée

Écrire une fonction ligne_pascal(n) qui renvoie la ligne de rang n. Vérifier également que la somme de ses coefficients vaut \(2^n\).

À toi

Une ligne du triangle

À faire

▶ Exécuter Effacer la sortie

Sortie

Mélanger une liste

Écrire une fonction permutation_aleatoire(L) qui renvoie une nouvelle liste dans un ordre aléatoire, sans modifier la liste reçue et sans utiliser random.shuffle. Une possibilité est de tirer successivement un indice parmi les éléments qui restent.

À toi

Mélanger sans modifier

À faire

▶ Exécuter Effacer la sortie

Sortie

Choisir une autre partie

← Partie précédente : graphiques

Retour aux quatre thèmes

Partie suivante : méthodes numériques →