TD 1 : Algorithmes non formalisés - Notes Exhaustives

Algorithme de la Somme de l’École Primaire

• Calcul de base :     * Exemple : Pour calculer la somme $321 + 12345$, il convient d'ajouter des zéros implicites au nombre le plus court afin d'aligner les colonnes.     * Résultat : $12666$.     * Nombre d'opérations élémentaires : $5$ opérations (une somme d'entiers par colonne). Dans cet exemple, il n'y a aucune retenue.

• Généralisation sans retenue :     * Soit deux entiers de $m$ et $n$ chiffres.     * Le nombre d'opérations élémentaires nécessaires pour effectuer la somme, en supposant l'absence totale de retenue, est défini par $\max(m, n)$.

• Somme avec retenues (cas intermédiaire) :     * Exemple : Pour $2138 + 764$, le résultat est $2902$, nécessitant $6$ opérations élémentaires.     * Analyse du meilleur et du pire cas (sans retenue dans la dernière colonne à gauche) :         * Meilleur cas : Aucune retenue, soit $\max(m, n)$ opérations.         * Pire cas : Une retenue dans chaque colonne excepté la dernière. Cela nécessite deux opérations par colonne, sauf pour la première (à droite) et la dernière (à gauche).         * Calcul du nombre d'opérations au pire cas : $1 + 2 \times (\max(m, n) - 2) + 1$, ce qui se simplifie en $2 \times \max(m, n) - 2$.         * Exemple type du pire cas : $899\dots9$ ($m$ chiffres) $+ 1$.

• Somme avec retenue dans la dernière colonne (cas général) :     * Exemple : $8024 + 2077 = 10101$, nécessitant $8$ opérations élémentaires.     * Taille du résultat : La somme peut comporter soit $\max(m, n)$ chiffres, soit $\max(m, n) + 1$ chiffres si une retenue se produit à la dernière étape.     * Analyse des opérations :         * Meilleur cas : Toujours $\max(m, n)$ opérations.         * Pire cas : Retenue dans chaque colonne, y compris la dernière. On effectue une opération dans la première colonne et deux opérations dans toutes les autres $\max(m, n)$ colonnes.         * Formule du pire cas : $2 \times \max(m, n) + 1$ opérations.         * Exemple type : $999\dots9$ ($m$ chiffres) $+ 1$.

Énigme de la Bergère et de la Traversée de Rivière

• Solution Standard (1 loup, 1 mouton, 1 chou) :     * Séquence d'opérations :         1. transporter mouton         2. traverser (retour à vide)         3. transporter chou         4. transporter mouton (retour avec le mouton pour éviter qu'il ne mange le chou)         5. transporter loup         6. traverser (retour à vide)         7. transporter mouton

• Solution Alternative :     * Il est possible d'inverser l'ordre du loup et du chou :         1. transporter mouton         2. traverser         3. transporter loup         4. transporter mouton         5. transporter chou         6. traverser         7. transporter mouton

• Généralisation avec $\ell$ loups, $m$ moutons et $c$ choux :     * Réduction des valeurs : Si une solution existe pour des valeurs données, elle reste valide pour des valeurs inférieures en remplaçant « transporter $x$ » par une simple traversée à vide si $x$ n'est plus présent.     * Situations impossibles :         * $\ell = 2, m = 1, c = 1$ : Impossible, car le mouvement forcé ramène systématiquement à l'état initial.         * $\ell = 1, m = 1, c = 2$ : Situation symétrique à la précédente, donc impossible.         * $\ell = 1, m = 2, c = 1$ : Aucun choix possible dès la première opération sans qu'un animal soit mangé.     * Impact de l'ajout d'éléments : Ajouter des animaux ou des choux ne peut jamais rendre une situation résolvable car cela ne supprime aucune menace de prédation existante.     * Solution avec plusieurs bergères : L'ajout d'une seconde bergère rend toute situation résolvable.         * Méthode : Une bergère surveille la rive de départ pendant que l'autre transporte les loups et les choux un par un. Ensuite, la première bergère traverse pour surveiller la rive d'arrivée pendant que la seconde transporte les moutons.

Problème Géométrique : Le Château de Cartes

• Règle de construction récursive :     * Pour passer d'un château de niveau $n$ à un niveau $n+1$, il faut :         * Ajouter une structure triangulaire au niveau 1 (bas), surmontée d'une carte horizontale.         * Répéter cela pour les niveaux $2, 3, \dots, n$.         * Ajouter une structure triangulaire finale au sommet ($n+1$).

• Modélisation Mathématique :     * Soit $c(n)$ le nombre de cartes pour $n$ niveaux.     * Valeurs initiales : $c(1) = 2$, $c(2) = 7$, $c(3) = 15$.     * Formule de récurrence : $c(n+1) = c(n) + 3n + 2$. Chaque nouveau niveau ajoute $3$ cartes par niveau existant (triangle + horizontale) plus un triangle de sommet ($2$ cartes).

• Application numérique :     * Calcul pour $40$ cartes :         * $c(3) = 15$         * $c(4) = 15 + 3(3) + 2 = 15 + 9 + 2 = 26$         * $c(5) = 26 + 3(4) + 2 = 26 + 12 + 2 = 40$     * Conclusion : Un château de $40$ cartes possède $5$ niveaux.

Cryptologie : Étude du Chiffrement de César

• Définitions fondamentales :     * Cryptographie : Art de transformer une information pour la rendre secrète (chiffrement).     * Cryptanalyse : Analyse des messages chiffrés pour en découvrir le sens sans posséder la clé.

• Mécanisme du Code de César (Chiffrement par décalage) :     * Chaque lettre est remplacée par une autre située à une distance fixe (clé $d$) dans l'alphabet latin ($26$ lettres).     * Calcul mathématique : Si une lettre est associée à un nombre $c \in {0, \dots, 25}$, la lettre chiffrée est $(c + d) \pmod{26}$.     * Les caractères non alphabétiques (ponctuation, espaces) restent inchangés.

• Exemples de chiffrement :     * Message : "La vie est un long fleuve tranquille"     * Clé 3 : "Od ylh hvw xq orqj iohxyh wudqtxlooh."     * Clé -7 : "Et obx xlm ng ehgz yexnox mktgjnbeex."

• Analyse Algorithmique :     * Complexité du chiffrement : Pour un message de $n$ caractères, l'algorithme effectue $n$ opérations de décalage.     * Déchiffrement : Utilisation de la clé opposée $-d$. Exemple : Déchiffrer « kajex » avec la clé $9$ donne « bravo ».     * Attaque par force brute : Sans clé, on peut tester les $25$ décalages effectifs possibles. La complexité est de $25n$, ce qui est très rapide pour un ordinateur.

• Analyse Fréquentielle et Sécurité :     * Le code de César est considéré comme peu sûr car il ne modifie pas la distribution fréquentielle des lettres, il ne fait que la décaler.     * En français (Wikipedia 2008), les fréquences d'apparition sont :         * $e$ : $12,10\%$         * $a$ : $7,11\%$         * $i$ : $6,59\%$         * $s$ : $6,51\%$         * $n$ : $6,39\%$         * $r$ : $6,07\%$         * $t$ : $5,92\%$         * $o$ : $5,02\%$         * $l$ : $4,96\%$         * $u$ : $4,49\%$         * $d$ : $3,67\%$         * $c$ : $3,18\%$         * $m$ : $2,62\%$         * $p$ : $2,49\%$         * $g$ : $1,23\%$         * $b, v, h, f$ : env. $1,11\%$         * $q$ : $0,65\%$         * $y$ : $0,46\%$         * $x$ : $0,38\%$         * $j$ : $0,34\%$         * $k$ : $0,29\%$         * $w$ : $0,17\%$         * $z$ : $0,15\%$     * En identifiant la lettre la plus fréquente du message chiffré, on peut facilement deviner qu'elle correspond au 'e' et ainsi déduire la clé.