Examen de synthèse corrigé : mathématiques pour l'informatique (201-N11)

a) Le premier bloc rassemble les quatre cases où $A=0$ et $C=0$, c'est-à-dire les minterms 0, 1, 4 et 5 : il donne le terme $\overline{A}\,\overline{C}$. Le second rassemble les cases où $A=1$ et $C=1$, minterms 10, 11, 14 et 15 : il donne $AC$. Dans les deux blocs, $B$ et $D$ prennent toutes les valeurs, ils DISPARAISSENT donc. D'où $f=\overline{A}\,\overline{C}+AC$.

b) La forme normale disjonctive complète énumère un terme par ligne à 1 de la table, soit HUIT termes de quatre littéraux chacun : $\overline{A}\,\overline{B}\,\overline{C}\,\overline{D}+\overline{A}\,\overline{B}\,\overline{C}D+\overline{A}B\overline{C}\,\overline{D}+\overline{A}B\overline{C}D+A\overline{B}C\overline{D}+A\overline{B}CD+ABC\overline{D}+ABCD$. La simplification de la question a fait passer de 8 termes de 4 littéraux à 2 termes de 2 littéraux, soit de 32 littéraux à 4 : c'est exactement ce que mesure l'économie de portes d'un circuit.

c) La fonction ne dépend que de $A$ et $C$ : elle vaut 1 quand $A=C=0$ et quand $A=C=1$, c'est-à-dire quand $A$ et $C$ sont ÉGAUX, et 0 sinon. C'est la porte XNOR, aussi appelée porte d'équivalence ou de coïncidence. On l'écrit $f=A\odot C=\overline{A\oplus C}$, où $\oplus$ est le OU exclusif.

d) La négation échange les quantificateurs et nie le prédicat : « il EXISTE un utilisateur $u$ tel que POUR TOUT fichier $f$, $u$ ne peut PAS lire $f$ ». Autrement dit, un utilisateur au moins ne peut lire aucun fichier. La règle est mécanique : chaque « pour tout » devient « il existe », chaque « il existe » devient « pour tout », et la propriété finale est niée. Sauter une seule inversion produit un énoncé qui n'a rien à voir.

e) $P\Rightarrow Q$ n'est PAS équivalente à sa réciproque $Q\Rightarrow P$ : sur $P$ vrai et $Q$ faux, la première est fausse et la seconde vraie. Elle EST équivalente à sa contraposée $\overline{Q}\Rightarrow\overline{P}$, comme le montre la table : les deux valent 0 uniquement dans le cas $P$ vrai et $Q$ faux, et 1 dans les trois autres. C'est ce qui autorise le raisonnement par contraposée, et c'est aussi pourquoi confondre réciproque et contraposée est la faute la plus coûteuse en logique.

a) Divisions successives par 2 : $202=128+64+8+2$, donc $202=11001010_{2}$. En hexadécimal, on groupe par quartets : $1100$ vaut C et $1010$ vaut A, donc $202=\mathrm{CA}_{16}$. Contrôle : $12\times 16+10=202$ ✓. Le passage par l'hexadécimal évite de recompter tous les bits.

b) On écrit d'abord $75=01001011_{2}$, car $75=64+8+2+1$. On INVERSE tous les bits : $10110100$. On AJOUTE 1 : $10110101$. C'est $-75$ en complément à deux, soit $\mathrm{B5}_{16}$, c'est-à-dire 181 si on le lisait comme un nombre non signé. Contrôle : $181+75=256=2^{8}$ ✓, ce qui est la définition même du complément à deux.

c) $0111$ vaut $+7$, la plus grande valeur positive sur 4 bits. En ajoutant 1 on obtient $1000$, qui vaut $-8$ et non $+8$ : le bit de signe s'est allumé. Sur la roue, on est passé de la position la plus haute du demi-cercle positif à la première du demi-cercle négatif, en franchissant la seule discontinuité de l'échelle. C'est un DÉBORDEMENT signé, et l'addition binaire ne l'a pas signalé.

d) $100=01100100$ et $50=00110010$. Leur somme binaire vaut $10010110$, soit $150$ en non signé mais $-106$ en complément à deux, puisque $150-256=-106$. Il y a donc DÉBORDEMENT signé : le résultat exact, 150, dépasse le maximum représentable, qui est 127. On le détecte au fait que deux opérandes POSITIFS ont donné un résultat de signe négatif, ce qu'aucune retenue sortante n'indique ici.

e) Parce que le complément à deux est conçu pour cela : l'addition modulo $2^{n}$ est la même opération quelle que soit la lecture, seul le NOM donné aux codes change. En revanche le débordement est un débordement de l'INTERVALLE représentable, et cet intervalle diffère : $[0;255]$ en non signé, $[-128;127]$ en signé. On le détecte donc par la retenue sortante en non signé, et par le changement de signe inattendu en signé. Un processeur calcule les deux indicateurs simultanément et laisse le programme choisir celui qui le concerne.

a) RÉFLEXIVE : tout $x$ a le même reste que lui-même ✓. SYMÉTRIQUE : si $x$ et $y$ ont le même reste, $y$ et $x$ aussi ✓. TRANSITIVE : si $x$ et $y$ ont le même reste et $y$ et $z$ aussi, alors $x$ et $z$ également ✓. C'est donc une relation d'équivalence, et ses classes sont les trois ensembles $\{0,3,6\}$, $\{1,4,7\}$ et $\{2,5,8\}$, correspondant aux restes 0, 1 et 2.

b) $E$ compte 9 éléments, donc $2^{9}=512$ parties, chaque élément étant pris ou non. Celles à exactement 3 éléments sont au nombre de $\binom{9}{3}=\frac{9\times 8\times 7}{6}=84$. On vérifie la cohérence par la somme des coefficients binomiaux de la ligne 9, qui vaut bien 512.

c) $A=\{0,2,4,6,8\}$ compte 5 éléments, $B=\{0,3,6\}$ en compte 3, et $A\cap B=\{0,6\}$, les multiples de 6, en compte 2. Donc $\left|A\cup B\right|=5+3-2=6$, et l'on vérifie directement : $A\cup B=\{0,2,3,4,6,8\}$, six éléments ✓. Sans le retranchement, on compterait deux fois 0 et 6.

d) RÉFLEXIVE : tout entier se divise lui-même ✓. ANTISYMÉTRIQUE : si $a$ divise $b$ et $b$ divise $a$ avec $a,b>0$, alors $a=b$ ✓. TRANSITIVE : si $a$ divise $b$ et $b$ divise $c$, alors $a$ divise $c$ ✓. C'est donc une relation d'ORDRE, mais elle n'est PAS totale : 2 et 3 ne sont pas comparables, aucun ne divisant l'autre. On parle d'ordre PARTIEL, et c'est le cas de figure le plus courant en informatique, par exemple pour les dépendances entre modules.

e) Ce sont deux descriptions du même objet, et le passage se fait dans les deux sens. À partir d'une relation d'équivalence, les CLASSES forment une partition : elles sont non vides, deux à deux disjointes, et leur réunion est $E$. À partir d'une partition, on définit une relation en déclarant équivalents deux éléments appartenant au même morceau, et l'on vérifie qu'elle est réflexive, symétrique et transitive. Les trois propriétés de l'équivalence correspondent donc exactement aux trois propriétés d'une partition, ce qui explique qu'aucune ne puisse être supprimée.

a) D'après la matrice affichée : $A$ pointe vers $B$ et $C$, degré 2 ; $B$ vers $C$ et $D$, degré 2 ; $C$ vers $D$, degré 1 ; $D$ vers $E$, degré 1 ; $E$ vers $A$, degré 1. Somme des degrés sortants : $2+2+1+1+1=7$, ce qui est bien le nombre d'ARCS du graphe. Dans un graphe orienté, cette somme vaut toujours le nombre d'arcs, et non son double comme dans le cas non orienté.

b) Le coefficient $(i,j)$ de $M^{2}$ vaut $\sum_{k}M_{ik}M_{kj}$ : chaque terme vaut 1 si et seulement s'il existe un arc de $i$ vers $k$ ET un arc de $k$ vers $j$. La somme compte donc le nombre de CHEMINS DE LONGUEUR 2 de $i$ vers $j$. De $A$ vers $D$ : par $B$, puisque $A\to B\to D$ ✓, et par $C$, puisque $A\to C\to D$ ✓. Le coefficient vaut donc 2.

c) Les chemins de longueur 2 partant de $A$ passent d'abord par $B$ ou par $C$. Depuis $B$ : $A\to B\to C$ et $A\to B\to D$. Depuis $C$ : $A\to C\to D$. Total : TROIS chemins. C'est la somme de la ligne de $A$ dans $M^{2}$, et l'on peut la calculer sans écrire toute la matrice, en additionnant les degrés sortants des successeurs de $A$, soit $2+1=3$.

d) Oui : $A\to B\to C\to D\to E\to A$ est un circuit de longueur 5 qui passe par tous les sommets, c'est-à-dire un circuit hamiltonien. Il en existe un second, plus court : $A\to C\to D\to E\to A$, de longueur 4. Un graphe possédant un circuit n'admet aucun tri topologique, ce qui interdit par exemple de l'utiliser comme graphe de dépendances entre modules.

e) Son coefficient $(i,j)$ compte le nombre total de chemins de longueur 1, 2, 3 ou 4 allant de $i$ vers $j$. Un tel coefficient est non nul si et seulement s'il existe un chemin de $i$ vers $j$, car dans un graphe à 5 sommets, tout chemin sans répétition de sommet a au plus 4 arcs. Cette matrice permet donc de lire l'ACCESSIBILITÉ, et sa version booléenne est la fermeture transitive du graphe.

a) $2026=26\times 77+24$, donc $2026\bmod 26=24$. Pour $-45$ : le reste doit être positif, donc on prend $q=-2$ et $-45=26\times(-2)+7$, d'où $-45\bmod 26=7$. Le réflexe $-45=26\times(-1)-19$ donnerait $-19$, qui n'est pas un reste valide.

b) $y=5\times 12+8=68$, et $68=26\times 2+16$, donc $y=16$. La lettre de rang 12 est M, celle de rang 16 est Q : M devient Q. On réduit toujours APRÈS l'addition, jamais entre les deux opérations, ce qui est permis par la compatibilité de la congruence avec les deux opérations.

c) Le coefficient doit être INVERSIBLE modulo 26, c'est-à-dire premier avec 26. On a $\mathrm{pgcd}(5,26)=1$ ✓, donc 5 convient. En revanche $\mathrm{pgcd}(13,26)=13$ : avec 13, la fonction $x\mapsto 13x+8$ n'est pas injective, elle envoie toutes les lettres sur seulement deux valeurs, et le message devient indéchiffrable même pour son destinataire. CRITÈRE : $a$ convient si et seulement si $\mathrm{pgcd}(a,26)=1$, ce qui laisse 12 coefficients possibles sur 26.

d) On cherche $u$ tel que $5u\equiv 1\pmod{26}$. En essayant : $5\times 21=105=26\times 4+1$ ✓, donc l'inverse est 21. Déchiffrement : de $y=5x+8$ on tire $5x=y-8$, puis $x=21\left(y-8\right)\bmod 26$. On peut développer : $x=21y-168$, et $-168\bmod 26=14$ puisque $-168=26\times(-7)+14$, donc $x=21y+14\bmod 26$.

e) $x=21\times 3+14=63+14=77$, et $77=26\times 2+25$, donc $x=25$. Vérification par le chiffrement : $5\times 25+8=133$, et $133=26\times 5+3$ ✓, on retrouve bien 3. Les deux fonctions sont donc réciproques l'une de l'autre, ce qui est exactement ce que garantit l'inversibilité de 5 modulo 26.

a) INITIALISATION en $n=1$ : à gauche $1^{3}=1$, à droite $\left(\frac{1\times 2}{2}\right)^{2}=1$ ✓. HÉRÉDITÉ : supposons la formule vraie au rang $k$. Alors la somme au rang $k+1$ vaut $\left(\frac{k(k+1)}{2}\right)^{2}+(k+1)^{3}=\frac{k^{2}(k+1)^{2}+4(k+1)^{3}}{4}=\frac{(k+1)^{2}\left(k^{2}+4k+4\right)}{4}=\frac{(k+1)^{2}(k+2)^{2}}{4}=\left(\frac{(k+1)(k+2)}{2}\right)^{2}$ ✓. L'hypothèse a servi à remplacer la somme des $k$ premiers cubes, et le pas décisif est la factorisation par $(k+1)^{2}$. Contrôle en $n=4$ : $1+8+27+64=100$ et $\left(\frac{4\times 5}{2}\right)^{2}=10^{2}=100$ ✓.

b) La somme des cubes est le CARRÉ de la somme des entiers : $1^{3}+\dots+n^{3}=\left(1+2+\dots+n\right)^{2}$. C'est une identité remarquable, souvent attribuée à Nicomaque, et qui n'a rien d'évident : rien dans la définition des cubes n'annonce qu'ils s'additionnent en un carré parfait. Elle donne aussi un moyen de contrôle instantané, la somme des cubes est toujours un carré.

c) INITIALISATION en $n=0$ : $7^{0}-1=0$, divisible par 6 ✓. HÉRÉDITÉ : supposons $7^{k}-1=6m$. Alors $7^{k+1}-1=7\times 7^{k}-1=7\left(7^{k}-1\right)+7-1=7\times 6m+6=6\left(7m+1\right)$ ✓. L'astuce est d'écrire $7\times 7^{k}$ comme $7\left(7^{k}-1\right)+7$, de manière à faire apparaître de force l'expression du rang $k$. On aurait aussi pu conclure directement par congruence : $7\equiv 1\pmod 6$ donc $7^{n}\equiv 1$.

d) INITIALISATION : $u_{0}=2\geq\sqrt 2\approx 1{,}414$ ✓. HÉRÉDITÉ : supposons $u_{k}\geq\sqrt 2$, donc $u_{k}>0$. On étudie $u_{k+1}-\sqrt 2=\frac{u_{k}}{2}+\frac{1}{u_{k}}-\sqrt 2=\frac{u_{k}^{2}-2\sqrt 2\,u_{k}+2}{2u_{k}}=\frac{\left(u_{k}-\sqrt 2\right)^{2}}{2u_{k}}$. Le numérateur est un carré, donc positif ou nul, et le dénominateur est strictement positif : la différence est positive ou nulle, donc $u_{k+1}\geq\sqrt 2$ ✓. Le fait de reconnaître un carré parfait est ce qui rend la démonstration immédiate.

e) C'est exactement la méthode de NEWTON appliquée à $f(x)=x^{2}-2$, dont l'itération est $u_{n+1}=\frac{1}{2}\left(u_{n}+\frac{2}{u_{n}}\right)$, ce qui est bien la relation donnée. La question d démontre que la suite reste au dessus de la racine dès le premier tour, ce qui est la propriété observée au chapitre de la récursivité : l'erreur $e_{n+1}=\frac{e_{n}^{2}}{2u_{n}}$ est toujours positive. Calculs : $u_{1}=1{,}5$, $u_{2}\approx 1{,}41667$, $u_{3}\approx 1{,}414216$, contre $\sqrt 2\approx 1{,}414214$.

a) On part de la racine 50 : $40<50$, on va à gauche vers 30. Puis $40>30$, on va à droite vers 40. Enfin $40=40$, trouvé. Le chemin est $50\to 30\to 40$ et il a coûté TROIS comparaisons, contre sept dans le pire cas d'une recherche séquentielle sur les sept clés.

b) L'arbre de la figure a une hauteur de 2, en comptant la racine au niveau 0. Un arbre binaire de hauteur $h$ contient au maximum $2^{h+1}-1$ clés, puisque le niveau $k$ en porte au plus $2^{k}$ et que $\sum_{k=0}^{h}2^{k}=2^{h+1}-1$. Ici $2^{3}-1=7$ ✓, l'arbre est PARFAITEMENT rempli. On reconnaît la formule des tours de Hanoï, ce qui n'est pas un hasard : les deux comptent une structure qui double à chaque niveau.

c) Un arbre équilibré de $n$ clés a une hauteur d'environ $\log_{2}n$, donc il faut au plus $\log_{2}(1000)+1\approx 10{,}97$, soit 11 comparaisons. La recherche séquentielle en demanderait jusqu'à 1000, soit environ 91 fois plus. C'est le même gain que la dichotomie, ce qui est logique : un arbre binaire de recherche équilibré EST une dichotomie matérialisée en mémoire.

d) Chaque nouvelle clé étant plus grande que toutes les précédentes, elle part systématiquement à droite : l'arbre DÉGÉNÈRE en une liste chaînée de hauteur 6. Le coût de recherche redevient LINÉAIRE, jusqu'à 7 comparaisons. C'est le pire cas de la structure, et il survient précisément sur des données déjà triées, situation fréquente en pratique. C'est ce qui motive les arbres équilibrés automatiquement, comme les arbres rouge et noir.

e) Il y a $7!=5040$ ordres d'insertion possibles, tous équiprobables. Un seul donne la chaîne strictement croissante, et un seul la chaîne strictement décroissante, soit 2 ordres dégénérés en ce sens. La probabilité vaut donc $\frac{2}{5040}=\frac{1}{2520}\approx 0{,}0004$, soit environ 0,04 pour cent. Le pire cas est donc extrêmement rare sur des données aléatoires, ce qui explique que la hauteur MOYENNE d'un arbre construit au hasard soit de l'ordre de $1{,}39\log_{2}n$, très proche de l'optimum. On retrouve exactement l'arbitrage du tri rapide : un pire cas catastrophique mais improbable.

1) FAUX, l'implication n'est pas symétrique. $P\Rightarrow Q$ est fausse dans le seul cas $P$ vrai et $Q$ faux, tandis que $Q\Rightarrow P$ est fausse dans le cas symétrique : elles diffèrent donc sur deux des quatre lignes. Ce qui EST équivalent à $P\Rightarrow Q$, c'est sa CONTRAPOSÉE $\overline{Q}\Rightarrow\overline{P}$. Exemple : « s'il pleut, le sol est mouillé » n'entraîne pas « si le sol est mouillé, il pleut ».

2) FAUX si l'on travaille en ENTIERS SIGNÉS. Sur 8 bits signés, l'intervalle représentable est $[-128;127]$, et 150 le dépasse : le motif binaire obtenu, $10010110$, se lit $-106$. Il y a donc DÉBORDEMENT silencieux. L'affirmation n'est correcte qu'en non signé, où l'intervalle va jusqu'à 255. Préciser la convention n'est pas un détail de vocabulaire, c'est ce qui décide du résultat.

3) FAUX, elle est un ordre PARTIEL. Elle est bien réflexive, antisymétrique et transitive, mais elle n'est pas TOTALE : 2 et 3 ne sont pas comparables, aucun des deux ne divisant l'autre. Un ordre total exige que deux éléments quelconques soient toujours comparables, ce qui est le cas de l'ordre usuel mais rarement des ordres issus de l'informatique, comme les dépendances entre tâches.

4) FAUX. La division euclidienne impose $0\leq r<26$, donc $-19$ n'est pas un reste valide. On prend $q=-2$ : $-45=26\times(-2)+7$, donc $-45\bmod 26=7$. C'est aussi ce que renvoie Python. En C ou en Java, l'opérateur donne effectivement $-19$, mais il ne calcule pas le reste euclidien : il faut alors corriger par $((a\ \%\ n)+n)\ \%\ n$.

5) FAUX sans hypothèse d'ÉQUILIBRE. Si les clés sont insérées dans l'ordre croissant, l'arbre dégénère en liste chaînée et la recherche redevient linéaire, avec $n$ comparaisons au lieu de $\log_{2}n$. La garantie logarithmique n'existe que pour les arbres maintenus équilibrés, comme les arbres rouge et noir ou AVL. Sur des insertions ALÉATOIRES, la hauteur moyenne reste voisine de $1{,}39\log_{2}n$, mais une moyenne n'est pas une garantie.

a) Parce qu'une fuite de la base livrerait immédiatement tous les comptes, et pas seulement ceux du site : les utilisateurs réemploient leurs mots de passe ailleurs. Un chiffrement RÉVERSIBLE ne vaut pas mieux, puisque la clé de déchiffrement est nécessairement présente sur le serveur et sera volée avec le reste. Seule une fonction à sens unique convient, c'est-à-dire une fonction de hachage : le serveur vérifie en recalculant le condensat, sans jamais pouvoir remonter au mot de passe.

b) Avec $N=65\,536$ cases, le seuil de 50 pour cent est atteint pour environ $1{,}18\sqrt{N}=1{,}18\times 256\approx 302$ clés. La figure le confirme : la courbe franchit $0{,}5$ juste après 300. Le résultat est frappant, 302 clés sur 65 536 cases suffisent, soit un taux de remplissage inférieur à un demi pour cent. C'est le paradoxe des anniversaires appliqué au hachage.

c) $\frac{200\,000}{65\,536}\approx 3{,}05$ comptes par case en moyenne. Le principe des TIROIRS garantit qu'une case au moins en contient au moins $\left\lceil 3{,}05\right\rceil=4$, ce qui est une borne très faible ; en pratique, avec une bonne fonction de hachage, la case la plus chargée en contient une douzaine. La conclusion importante est qu'il y a NÉCESSAIREMENT des collisions, et que la structure doit donc gérer les listes de débordement.

d) $26^{8}=208\,827\,064\,576\approx 2{,}09\times 10^{11}$, donc environ $21$ secondes pour épuiser l'espace. Sans sel, cet effort casse TOUS les comptes à la fois, puisqu'un même mot de passe donne partout le même condensat, et l'attaquant peut même se contenter d'une table précalculée. Avec un SEL aléatoire par utilisateur, le condensat dépend du compte : l'attaquant doit recommencer les 21 secondes POUR CHAQUE utilisateur, soit environ 48 jours pour 200 000 comptes, et aucune table précalculée ne sert. Le sel ne rend pas un mot de passe faible plus fort, il interdit de mutualiser l'attaque.

e) UN, ne jamais stocker que des condensats, produits par une fonction à sens unique. DEUX, saler chaque mot de passe avec une valeur aléatoire propre à l'utilisateur, pour empêcher toute attaque mutualisée ou par table précalculée. TROIS, choisir une fonction de hachage LENTE et paramétrable, du type bcrypt ou Argon2, afin que les $10^{10}$ essais par seconde de la question d tombent à quelques milliers. Ces trois règles ne dépendent d'aucune technologie particulière, elles découlent directement des comptages de ce cours.

a) Oui. Le chemin $A\to B\to D\to E$ convient, de longueur 3, et $A\to C\to D\to E$ également. On peut le vérifier sur la matrice : le coefficient de $M^{3}$ à la position correspondante est non nul. Comme il existe aussi l'arc $E\to A$, les deux machines sont mutuellement accessibles et appartiennent donc à la même composante fortement connexe.

b) Dans un réseau non orienté, relier toutes les paires demande $\binom{n}{2}=\frac{n(n-1)}{2}$ liaisons. Pour $n=5$ : $\frac{5\times 4}{2}=10$ liaisons. Pour $n=100$ : $\frac{100\times 99}{2}=4950$. Le nombre croît comme le CARRÉ du nombre de machines, ce qui rend le maillage complet impraticable dès quelques centaines de nœuds et explique l'usage de topologies hiérarchiques.

c) On effectue un parcours en PROFONDEUR en marquant chaque sommet selon trois états, non visité, en cours de visite, terminé. Si l'on rencontre un arc menant vers un sommet EN COURS de visite, on a trouvé un circuit. Le parcours visite chaque sommet une fois et examine chaque arc une fois, son coût est donc $O(S+A)$, linéaire en la taille du graphe. C'est aussi l'algorithme qui produit un tri topologique lorsqu'aucun circuit n'est trouvé.

d) Les deux conditions sont d'avoir un CAS DE BASE, ici un sommet sans successeur non visité, et de faire DÉCROÎTRE la quantité de travail restant, ce qui est assuré par le MARQUAGE des sommets déjà vus. Si l'on oublie le marquage, la récursion tourne indéfiniment dès que le graphe contient un circuit, puisqu'on repasse sans fin par les mêmes sommets. C'est exactement la seconde condition de terminaison du chapitre sur la récursivité, transposée aux graphes : l'argument doit se rapprocher du cas de base.

e) PARCOURS EN PROFONDEUR : $O(S+A)=100+300=400$ opérations élémentaires, l'affaire d'une microseconde. TEST NAÏF de tous les chemins : le nombre de chemins simples peut atteindre l'ordre de $99!$, un nombre à 156 chiffres, donc totalement hors d'atteinte. Le rapport n'est pas un facteur mais un changement de nature, du linéaire au factoriel. C'est la leçon générale du cours : la bonne structure de données et le bon parcours transforment un problème impossible en un problème trivial, et aucun matériel ne compense le choix d'un mauvais algorithme.