Algorithmes#
Dès la première
Deux algorithmes peuvent donner le même résultat sans demander le même nombre de calculs. La façon
dont ce nombre augmente avec la taille des données est appelée complexité : une boucle parcourant
n valeurs effectue généralement un nombre de passages proportionnel à n, tandis que deux
boucles de n passages imbriquées peuvent en effectuer \(n^2\). Sans formaliser davantage
cette notion, il est utile de se demander ce qui se passerait si les données devenaient dix fois
plus nombreuses.
Algorithme d’Euclide#
L’algorithme d’Euclide calcule le plus grand diviseur commun de deux entiers. Il repose sur l’égalité :
où \(r\) est le reste de la division euclidienne de \(a\) par \(b\). On recommence jusqu’à obtenir un reste nul.
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. Décris ensuite la méthode d’Euclide en deux ou trois phrases, sans utiliser les noms des variables du programme : cette reformulation doit rester valable pour n’importe quels entiers de départ.
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.
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 :
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àZsont décalées dans l’alphabet majuscule ;les lettres de
aàzsont 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.
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.
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.
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 :
Par exemple, 6 = 3 + 3.
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\).
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.
Choisir une autre partie