Formulaires, étapes clés de la méthode pour chaque thème et 20 exercices, avec les corrigés complets à la fin.
Le motif de 8 bits 0011 1011 stocke un entier signé en complément à deux. Quelle est sa valeur N en décimal ?
Un système doit donner à chacun de 1362 éléments son propre code binaire, tous de même longueur. Quel est le plus petit nombre de bits b nécessaire ?
(c → a) → (a → c) est-elle une tautologie, une contradiction ou une contingence ? Cliquez sur votre réponse.
Combien des 16 lignes de la table de vérité rendent ((¬r → s) ∧ (¬p ∨ ¬r)) ∧ (q ∨ (p ∧ s)) vraie ? Appelez ce nombre N.
Utilisez le tableau de Karnaugh pour trouver la forme somme de produits (SOP) minimale de F(A, B, C) = Σm(1, 2, 5). Combien de littéraux L contient-elle au total (une variable primée compte pour un littéral) ?
Un compteur modulo 12 synchrone compte 0, 1, …, 11 puis revient à 0. Il part de 9. Quelle valeur Q (en décimal) affiche-t-il après 33 impulsions d’horloge ?
Trouvez l’inverse de 42 modulo 47 : le nombre x avec 0 < x < 47 et 42·x ≡ 1 (mod 47).
Résolvez 54x ≡ 12 (mod 82). Donnez la plus petite solution positive x.
Quel énoncé sur une fonction récursive sans cas de base atteignable est correct ?
Quelle est la complexité temporelle de : pour i = 1 à n : pour (j = i ; j ≤ n ; j = j + i) faire un travail O(1) ?
Les arbres AVL et les arbres rouge-noir garantissent :
Pourquoi ne peut-on pas simplement supprimer des éléments d'un filtre de Bloom standard en remettant leurs bits à zéro ?
Un graphe connexe a 17 sommets et 17 arêtes. Combien d’arêtes k faut-il retirer pour obtenir un arbre couvrant ?
Combien de marches de longueur 3 vont de E à C ? Une marche peut répéter des sommets et des arêtes. Appelez ce nombre N.
Qu'est-ce qu'une lecture sale (dirty read) ?
Étant données les dépendances fonctionnelles A → B, B → C et C → D sur R(A, B, C, D), quelle est la fermeture A+ ?
Qu'est-ce qui caractérise une attaque par déni de service distribué (DDoS) ?
La clé privée d'un serveur sera volée dans un an. Quelle propriété de TLS protège les sessions enregistrées aujourd'hui ?
Un service a besoin de 201 adresses d'hôte dans un seul sous-réseau. Quelle est la plus grande longueur de préfixe p (le plus petit sous-réseau) suffisante ?
Un hôte a l'adresse 10.20.108.111/29. Quel est le dernier nombre (quatrième octet) x de l'adresse de diffusion de son sous-réseau ?
Réponse: N = 59
Systèmes de numération positionnels : chaque chiffre vaut sa valeur multipliée par une puissance de la base. En binaire les positions valent 1, 2, 4, 8, 16, … ; en hexadécimal 1, 16, 256, …, avec A–F pour 10–15. En complément à deux sur 8 bits, le bit de gauche vaut −128 au lieu de +128 : c'est ainsi qu'on stocke les nombres négatifs.
Les autres bits gardent leurs valeurs positives habituelles.
Réponse: b = 11 bit
Systèmes de numération positionnels : chaque chiffre vaut sa valeur multipliée par une puissance de la base. En binaire les positions valent 1, 2, 4, 8, 16, … ; en hexadécimal 1, 16, 256, …, avec A–F pour 10–15. En complément à deux sur 8 bits, le bit de gauche vaut −128 au lieu de +128 : c'est ainsi qu'on stocke les nombres négatifs.
Réponse: contingence
Équivalence logique : deux formules sont équivalentes (≡) quand elles ont la même valeur dans chaque ligne de la table de vérité. Une tautologie vaut 1 dans toutes les lignes, une contradiction 0 dans toutes les lignes, et une contingence n’est ni l’une ni l’autre. Lois utiles : De Morgan, ¬(a ∧ b) ≡ ¬a ∨ ¬b et ¬(a ∨ b) ≡ ¬a ∧ ¬b ; a → b ≡ ¬a ∨ b ≡ ¬b → ¬a (contraposée) ; ¬(a → b) ≡ a ∧ ¬b ; et les lois de distributivité, a ∨ (b ∧ c) ≡ (a ∨ b) ∧ (a ∨ c).
Réponse: N = 5
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: L = 5
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: Q = 6
Bascules et compteurs : une bascule ne change qu’au front actif de l’horloge. D copie son entrée (Q⁺ = D) ; T change d’état quand T = 1 ; JK conserve pour 00, remet à 0 pour 01, met à 1 pour 10 et change d’état pour 11. Un compteur binaire de n bits a 2ⁿ états et compte modulo 2ⁿ ; un compteur modulo N va de 0, 1, …, N − 1 puis revient à 0, et exige le plus petit n tel que 2ⁿ ≥ N bascules. Chaque étage d’un compteur asynchrone divise la fréquence par deux, donc la dernière sortie d’un compteur modulo N tourne à fclk/N. Un compteur Johnson de n bascules a 2n états, un compteur en anneau n.
Toutes les 12 impulsions ramènent le compteur au même état.
Réponse: 42−1 mod 47 = 28
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·42 (mod 47).
Réponse: x = 23
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).
Réponse: D · Elle continue de s'appeler jusqu'au débordement de la pile d'appels
Sans cas de base, la récursion ne s'arrête jamais ; en pratique, la mémoire pour les cadres de pile s'épuise et le programme plante.
Réponse: B · O(n log n)
Le total vaut n / 1 + n / 2 + ... + n / n = n × Hn, et le nombre harmonique Hn est Θ(log n).
Réponse: C · Une hauteur en O(log n) grâce au rééquilibrage
Les arbres auto-équilibrés maintiennent une hauteur logarithmique, donc la recherche, l'insertion et la suppression sont en O(log n) dans le pire des cas.
Réponse: C · Ces bits peuvent aussi appartenir à d'autres éléments, ce qui provoquerait des faux négatifs
Remettre à zéro un bit partagé ferait paraître absent un autre élément ; les filtres de Bloom à compteurs utilisent des compteurs au lieu de bits pour permettre la suppression.
Réponse: k = 1
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: N = 6
Degrés : le degré d’un sommet est le nombre d’arêtes qui y aboutissent. Chaque arête a deux extrémités, donc les degrés totalisent deux fois le nombre d’arêtes : Σ deg(v) = 2|E| (le lemme des poignées de main). Le nombre de sommets de degré impair est donc pair. Kn a n(n − 1)/2 arêtes, un graphe k-régulier à n sommets en a nk/2, et un arbre à n sommets a n − 1 arêtes.
Réponse: A · La lecture de données écrites par une autre transaction qui n'a pas encore été validée
Une lecture sale voit des modifications non validées qui pourraient être annulées ; elle n'est possible qu'au niveau read uncommitted.
Réponse: D · {A, B, C, D}
On part de A, on ajoute B (A → B), puis C (B → C), puis D (C → D) ; comme A+ contient tous les attributs, A est une clé.
Réponse: A · De nombreuses machines compromises inondent une cible de trafic
Dans une attaque DDoS, de nombreuses sources submergent un serveur ou une liaison, si bien que les utilisateurs légitimes ne peuvent plus être servis. La multiplicité des sources rend un simple blocage difficile.
Réponse: B · La confidentialité persistante (forward secrecy) grâce à l'échange de clés Diffie-Hellman éphémère
Avec (EC)DHE éphémère, chaque clé de session est dérivée de valeurs temporaires qui sont ensuite effacées. La clé à long terme ne fait que signer l'échange ; la voler plus tard ne permet donc pas de déchiffrer l'ancien trafic.
Réponse: p = 24
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: x = 111
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).
ExamProblems · examproblems.com/courses/computer-science-fundamentals