Formulaires, étapes clés de la méthode pour chaque thème et 20 exercices, avec les corrigés complets à la fin.
Positionnez les bits pour qu’ils représentent −93 en complément à deux sur 8 bits. Lu comme un nombre non signé, quelle est la valeur U du motif ?
Positionnez les bits sur le résultat sur 8 bits de 0100 0010 << 3. Quelle est la valeur R du résultat en décimal ?
Dans combien des 8 lignes de sa table de vérité ¬(¬(¬a → c) → c) ∨ (b → a) est-elle vraie ? Appelez ce nombre N.
Combien des 16 lignes de la table de vérité rendent ((r → q) ∨ s) → ((p ∨ q) ∧ p) vraie ? Appelez ce nombre N.
Utilisez le tableau de Karnaugh pour trouver la forme somme de produits (SOP) minimale de F(A, B, C, D) = Σm(1, 3, 5, 7, 8, 9, 10, 11, 13). Combien de termes produits N a-t-elle ?
Trouvez la forme SOP minimale de F(A, B, C, D) = Σm(6, 12, 14, 15) + d(2, 5, 13), où d marque les états indifférents. Combien de termes produits N a-t-elle ?
Trouvez l’inverse de 10 modulo 59 : le nombre x avec 0 < x < 59 et 10·x ≡ 1 (mod 59).
Une clé RSA utilise p = 17, q = 47 et e = 13. Déchiffrez le chiffré c = 543 : trouvez le message m.
La complexité temporelle de la version récursive naïve de Fibonacci (fib(n) = fib(n−1) + fib(n−2)) est :
Pourquoi l'algorithme de Dijkstra peut-il donner des résultats faux lorsque certains poids d'arêtes sont négatifs ?
Combien de nœuds possède un arbre binaire parfait de hauteur h, la hauteur étant comptée en arêtes ?
Un objet est stocké comme clé dans une table de hachage (hash map), puis un champ utilisé par sa fonction de hachage est modifié. Quel est le résultat probable ?
Combien de circuits hamiltoniens différents H le graphe complet K4 a-t-il ? Les circuits qui ne diffèrent que par le sommet de départ ou le sens comptent comme un seul.
Trouvez le poids total W d’un arbre couvrant minimal du graphe pondéré.
Qu'est-ce qu'un déclencheur (trigger) de base de données ?
Quelle fonctionnalité SQL convient le mieux pour trouver tous les employés sous un responsable dans un organigramme de profondeur inconnue ?
Comment TLS utilise-t-il généralement la cryptographie asymétrique et symétrique ?
Un pare-feu bloque tout l'ICMP. Les petites requêtes web fonctionnent, mais les gros téléchargements se bloquent sur certains chemins. Quelle est la cause probable ?
Le réseau 192.168.10.0/24 doit être divisé en au moins 10 sous-réseaux égaux. Si tu empruntes le moins de bits possible, combien d'hôtes utilisables H chaque sous-réseau a-t-il ?
Un routeur a des routes vers ces réseaux : 10.142.211.0/24, 10.142.212.0/24. Quelle est la plus grande longueur de préfixe p d’une route résumée unique qui les couvre tous ?
Réponse: U = 163
Positionner les bits : chaque bit vaut une puissance de deux (128, 64, …, 1). Un chiffre hexadécimal correspond exactement à quatre bits, et en complément à deux sur 8 bits, le bit le plus à gauche vaut −128. Les opérations bit à bit s’appliquent séparément à chaque position de bit.
Réponse: R = 16
Positionner les bits : chaque bit vaut une puissance de deux (128, 64, …, 1). Un chiffre hexadécimal correspond exactement à quatre bits, et en complément à deux sur 8 bits, le bit le plus à gauche vaut −128. Les opérations bit à bit s’appliquent séparément à chaque position de bit.
Un décalage à gauche de 3 déplace chaque bit de 3 positions vers la gauche ; les bits qui sortent à l’extrémité gauche sont perdus et des zéros entrent à droite.
Réponse: N = 7
Tables de vérité : une formule à n variables distinctes a 2ⁿ lignes, une pour chaque combinaison de valeurs de vérité (1 = vrai, 0 = faux). Travaillez de l’intérieur vers l’extérieur et donnez à chaque sous-formule sa propre colonne. ¬a inverse la valeur ; a ∧ b vaut 1 seulement quand les deux valent 1 ; a ∨ b vaut 0 seulement quand les deux valent 0 ; a → b vaut 0 seulement quand a = 1 et b = 0 ; a ↔ b vaut 1 quand les deux côtés sont égaux.
Réponse: N = 9
Tables de vérité : une formule à n variables distinctes a 2ⁿ lignes, une pour chaque combinaison de valeurs de vérité (1 = vrai, 0 = faux). Travaillez de l’intérieur vers l’extérieur et donnez à chaque sous-formule sa propre colonne. ¬a inverse la valeur ; a ∧ b vaut 1 seulement quand les deux valent 1 ; a ∨ b vaut 0 seulement quand les deux valent 0 ; a → b vaut 0 seulement quand a = 1 et b = 0 ; a ↔ b vaut 1 quand les deux côtés sont égaux.
Réponse: N = 3
Tableaux de Karnaugh : les cases sont ordonnées en code de Gray (00, 01, 11, 10), donc les cases voisines, y compris celles de part et d’autre des bords, diffèrent par exactement une variable. Regroupez les 1 en rectangles de 1, 2, 4, 8 ou 16 cases, aussi grands que possible et en aussi petit nombre que possible, jusqu’à ce que chaque 1 soit couvert. Chaque groupe est un terme produit : les variables qui restent constantes à l’intérieur. Un groupe de 2ᵏ cases perd k variables. Les états indifférents (X) peuvent servir à agrandir les groupes mais n’ont jamais besoin d’être couverts. Regrouper les 0 donne la forme POS minimale.
Chaque groupe est un rectangle de 2ᵏ cases ; les cases de bord sont voisines des cases du bord opposé.
Réponse: N = 2
Tableaux de Karnaugh : les cases sont ordonnées en code de Gray (00, 01, 11, 10), donc les cases voisines, y compris celles de part et d’autre des bords, diffèrent par exactement une variable. Regroupez les 1 en rectangles de 1, 2, 4, 8 ou 16 cases, aussi grands que possible et en aussi petit nombre que possible, jusqu’à ce que chaque 1 soit couvert. Chaque groupe est un terme produit : les variables qui restent constantes à l’intérieur. Un groupe de 2ᵏ cases perd k variables. Les états indifférents (X) peuvent servir à agrandir les groupes mais n’ont jamais besoin d’être couverts. Regrouper les 0 donne la forme POS minimale.
Les plus grands groupes pouvant être formés de 1 et de X.
Il existe un autre regroupement de même taille ; il a le même nombre de termes et de littéraux.
Réponse: 10−1 mod 59 = 6
Inverses et congruences : a a un inverse modulo n exactement quand pgcd(a, n) = 1. L’algorithme d’Euclide étendu écrit 1 = s·n + t·a, et alors a⁻¹ ≡ t (mod n). Une congruence a·x ≡ b (mod n) avec pgcd(a, n) = 1 a pour solution x ≡ a⁻¹·b. Deux congruences x ≡ r₁ (mod m₁) et x ≡ r₂ (mod m₂) à modules premiers entre eux ont une solution modulo m₁·m₂ (théorème des restes chinois). L’indicatrice d’Euler φ(n) compte les nombres de 1 à n premiers avec n : φ(n) = n·∏(1 − 1/p).
Chaque reste r s’écrit r ≡ t·10 (mod 59).
Réponse: m = 33
Puissances modulaires et RSA : calculez aᵏ mod n par carrés répétés : écrivez k en binaire, élevez au carré, réduisez après chaque étape et multipliez les puissances dont le bit vaut 1. Fermat : aᵖ⁻¹ ≡ 1 (mod p) pour un nombre premier p ne divisant pas a, donc l’exposant peut être réduit modulo p − 1. RSA : choisissez des nombres premiers p et q, n = p·q et φ(n) = (p − 1)(q − 1) ; l’exposant public e est premier avec φ(n), et l’exposant privé est d = e⁻¹ mod φ(n). Chiffre avec c = mᵉ mod n et déchiffrez avec m = cᵈ mod n.
Réponse: B · Exponentielle
L'arbre des appels croît à peu près comme φⁿ (environ 1,618ⁿ). La mémoïsation la réduit à O(n).
Réponse: C · Un sommet est définitivement fixé lorsqu'il est extrait, mais une arête négative ultérieure pourrait encore lui donner un chemin plus court
L'étape gloutonne repose sur des poids positifs ou nuls pour que les distances extraites soient définitives ; on utilise Bellman-Ford quand les poids peuvent être négatifs.
Réponse: C · 2h+1 − 1
La somme 1 + 2 + 4 + ... + 2h vaut 2h+1 − 1 ; par exemple, une hauteur de 2 donne 7 nœuds.
Réponse: B · La recherche de l'objet peut échouer car il se trouve dans le compartiment de son ancien hachage
L'emplacement de la clé a été choisi à partir de son ancien hachage ; avec un nouveau hachage, les recherches examinent le mauvais compartiment, c'est pourquoi les clés devraient être immuables.
Réponse: H = 3
Euler, Hamilton et arbres : un graphe connexe a un circuit eulérien (chaque arête une fois, retour au départ) quand tous les sommets ont un degré pair, et un chemin eulérien qui n’est pas un circuit quand exactement deux sommets ont un degré impair ; le chemin va alors d’un sommet impair à l’autre. Un circuit hamiltonien visite chaque sommet une fois ; Kn en a (n − 1)!/2. Un arbre à n sommets a n − 1 arêtes, et un graphe connexe à m arêtes conserve un arbre couvrant après suppression de m − n + 1 arêtes.
Réponse: W = 30
Plus courts chemins et arbres couvrants : l’algorithme de Dijkstra fixe un sommet par tour : le sommet non fixé de plus petite distance provisoire. Sa distance est alors définitive, et chaque voisin v reçoit d(v) = min(d(v), d(u) + w(u, v)). L’algorithme de Kruskal construit un arbre couvrant minimal en prenant les arêtes de la plus légère à la plus lourde et en sautant toute arête qui fermerait un cycle ; l’algorithme de Prim fait croître un arbre à partir d’un sommet de départ en ajoutant toujours l’arête la plus légère qui en sort. Un arbre couvrant à n sommets a n − 1 arêtes.
Réponse: A · Du code exécuté automatiquement lorsqu'un événement précis, comme INSERT, UPDATE ou DELETE, se produit sur une table
Les déclencheurs s'exécutent automatiquement avant ou après la modification de données, par exemple pour écrire un journal d'audit ou faire respecter une règle complexe.
Réponse: B · Une expression de table commune récursive (WITH RECURSIVE)
Une CTE récursive part d'une requête d'ancrage et joint de façon répétée le résultat précédent à la table ; elle gère donc des hiérarchies de toute profondeur.
Réponse: A · Les méthodes asymétriques servent à convenir des clés et à authentifier ; les chiffrements symétriques chiffrent les données
Les méthodes à clé publique et les certificats établissent un secret partagé et prouvent l'identité. Des chiffrements symétriques rapides comme AES protègent ensuite l'essentiel des données.
Réponse: D · La découverte du MTU du chemin échoue car les messages « fragmentation nécessaire » sont bloqués
La PMTUD s'appuie sur des messages ICMP pour apprendre le MTU plus petit. S'ils sont supprimés, les gros paquets disparaissent sans bruit, créant une connexion « trou noir ».
Réponse: H = 14
Sous-réseaux IPv4 : une adresse a 32 bits. Le préfixe /p indique combien de bits de tête identifient le réseau ; les 32 − p bits restants numérotent les hôtes. Un sous-réseau a 2³²⁻ᵖ adresses, mais la première (adresse réseau) et la dernière (adresse de diffusion) ne peuvent pas être attribuées, il tient donc 2³²⁻ᵖ − 2 hôtes. Exceptions : un /31 (liaison point à point, RFC 3021) utilise ses 2 adresses pour des hôtes, et un /32 est une adresse unique (un seul hôte ou une interface de bouclage).
Réponse: p = 21
Résumé de routes : une route résumée a.b.c.0/p couvre tous les réseaux dont les p premiers bits correspondent. Écrivez en binaire l’octet qui diffère pour le premier et le dernier réseau ; le nombre de bits de tête communs, plus les bits des octets qui le précèdent, donne le plus long préfixe de résumé.
Route résumée : 10.142.208.0/21 (elle couvre aussi 6 réseau(x) qui ne figurent pas dans la liste).
ExamProblems · examproblems.com/courses/computer-science-fundamentals