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 −69 en complément à deux sur 8 bits. Lu comme un nombre non signé, quelle est la valeur U du motif ?
Un système doit donner à chacun de 883 éléments son propre code binaire, tous de même longueur. Quel est le plus petit nombre de bits b nécessaire ?
Quelle formule est logiquement équivalente à q ∨ (r ∧ p) ? Cliquez dessus.
Combien des 16 lignes de la table de vérité rendent ((p ∨ s) ∧ r) ∧ ¬((q ∨ s) → (q ∧ p)) vraie ? Appelez ce nombre N.
Un multiplexeur 4 vers 1 a ses entrées de sélection S₁ = A et S₀ = B, et ses entrées de données reliées à I₀ = 0, I₁ = C, I₂ = C′, I₃ = 1. Pour combien des 8 combinaisons de A, B et C la sortie vaut-elle F = 1 ? Trouvez N.
Un registre à décalage de 4 bits Q₃Q₂Q₁Q₀ contient 0110. À chaque front d’horloge, les bits se décalent d’une place vers la droite (Q₃ → Q₂ → Q₁ → Q₀, Q₀ est perdu) et l’entrée série entre dans Q₃. L’entrée série vaut 0, 1, 1, 0, 0 aux fronts 5. Donnez l’état final Q = Q₃Q₂Q₁Q₀ sous forme de nombre décimal.
Trouvez l’inverse de 62 modulo 73 : le nombre x avec 0 < x < 73 et 62·x ≡ 1 (mod 73).
Une clé RSA utilise les nombres premiers p = 17 et q = 23 et l’exposant public e = 3. Trouvez l’exposant privé d (0 < d < φ(n)).
La borne inférieure du tri par comparaisons dans le pire cas est :
22n est-il dans O(2ⁿ) ?
Un parcours infixe (in-order) d'un arbre binaire de recherche visite les clés dans :
Sans union par rang ni compression de chemin, quel est le coût dans le pire cas d'une seule opération find dans une structure union-find à n éléments ?
Un graphe connexe a 19 sommets et 27 arêtes. Combien d’arêtes k faut-il retirer pour obtenir un arbre couvrant ?
L’algorithme de Kruskal construit un arbre couvrant minimal. Cliquez sur l’arête qu’il ajoute en numéro 4 ; les arêtes sautées ne comptent pas.
Quelle instruction supprime toutes les lignes d'une table, conserve sa structure et n'accepte pas de clause WHERE ?
La requête FROM customers c LEFT JOIN orders o ON o.customer_id = c.id WHERE o.status = 'paid' élimine de façon inattendue les clients sans commande. Pourquoi ?
À quoi correspond un masque de sous-réseau 255.255.255.0 en notation CIDR ?
D'après le théorème de Shannon, quelle est la capacité d'un canal de 1 MHz avec un rapport signal sur bruit de 255 ?
Un service a besoin de 313 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.89.65/27. Quel est le dernier nombre (quatrième octet) x de l'adresse de diffusion de son sous-réseau ?
Réponse: U = 187
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: b = 10 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: (q ∨ r) ∧ (q ∨ p)
É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).
Les colonnes après la barre sont les options dans l’ordre affiché.
Réponse: N = 3
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 = 4
Multiplexeur : un multiplexeur 2ⁿ vers 1 transmet l’une de ses entrées de données à la sortie ; les lignes de sélection, lues comme un nombre binaire, choisissent laquelle. Pour un MUX 4 vers 1 avec sélections S₁S₀ = AB, F = A′B′·I₀ + A′B·I₁ + AB′·I₂ + AB·I₃. En reliant les entrées de données à 0, 1, C ou C′, le MUX produit n’importe quelle fonction de A, B et C, ce qui est une manière courante de réaliser une logique avec un seul circuit.
Réponse: Q = 3
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.
Réponse: 62−1 mod 73 = 53
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·62 (mod 73).
Réponse: d = 235
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: D · Ω(n log n)
Tout tri par comparaisons nécessite au moins log₂(n!) ≈ n log n comparaisons dans le pire cas. Le tri par dénombrement fait mieux car il n'effectue pas de comparaisons.
Réponse: B · Non, car 22n = 4ⁿ et 4ⁿ / 2ⁿ = 2ⁿ croît sans borne
Une constante ajoutée à l'exposant donne un facteur constant, mais une constante qui multiplie l'exposant change la base et le taux de croissance.
Réponse: B · L'ordre croissant
Visiter le sous-arbre gauche, puis le nœud, puis le sous-arbre droit fournit les clés du BST dans l'ordre trié.
Réponse: C · O(n)
Des unions naïves peuvent relier les arbres en une longue chaîne, donc find peut suivre n − 1 pointeurs vers le parent ; les deux heuristiques le rendent presque constant.
Réponse: k = 9
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: arête DF
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: D · TRUNCATE TABLE
TRUNCATE vide rapidement une table et conserve sa définition ; DELETE peut supprimer certaines lignes et DROP supprime la table elle-même.
Réponse: C · La condition WHERE sur o rejette les lignes remplies de NULL, ce qui en fait une jointure interne
Pour les lignes sans correspondance, o.status vaut NULL, donc le test du WHERE n'est pas TRUE ; déplacer la condition dans la clause ON conserve tous les clients.
Réponse: C · /24
Trois octets à 255 font 24 bits à 1, donc 255.255.255.0 = /24.
Réponse: A · 8 Mbit/s
C = 10⁶ × log₂(256) = 10⁶ × 8 = 8 Mbit/s. C'est la limite supérieure du débit sans erreur sur un canal bruité.
Réponse: p = 23
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 = 95
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