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 1111 0010 stocke un entier signé en complément à deux. Quelle est sa valeur N en décimal ?
Un système doit donner à chacun de 2511 éléments son propre code binaire, tous de même longueur. Quel est le plus petit nombre de bits b nécessaire ?
Vous voulez prouver ¬a → (c ∧ b) par contraposée. Quelle implication prouvez-vous à la place ? Cliquez dessus.
Combien des 16 lignes de la table de vérité rendent ((a ∨ b) ∨ (c → d)) ∨ ((b → c) ↔ (d ∧ a)) vraie ? Appelez ce nombre N.
Simplifiez F = ABC + A′B′C + AC′ à sa forme somme de produits minimale. Combien de littéraux L contient l’expression simplifiée ?
Un compteur Johnson de 4 bits Q₃Q₂Q₁Q₀ part de 0000. À chaque front d’horloge, les bits se décalent d’une place vers la droite (Q₃ → Q₂ → Q₁ → Q₀) et Q₃ reçoit l’inverse de Q₀. Donnez l’état Q = Q₃Q₂Q₁Q₀ sous forme de nombre décimal après 7 fronts d’horloge.
Trouvez le plus petit entier positif x tel que x ≡ 1 (mod 3) et x ≡ 0 (mod 5).
Utilisez le carré répété pour trouver 2833 mod 43.
Quelle est la complexité temporelle du tri rapide (quicksort) dans le pire cas ?
Quel est le coût amorti de l'incrémentation d'un compteur binaire, sachant qu'une incrémentation peut inverser de nombreux bits ?
Combien de nœuds possède un arbre binaire parfait de hauteur h, la hauteur étant comptée en arêtes ?
Pourquoi un serveur pourrait-il choisir sa fonction de hachage au hasard dans une famille universelle ?
Un graphe connexe a 14 sommets et 25 arêtes. Combien d’arêtes k faut-il retirer pour obtenir un arbre couvrant ?
L’algorithme de Dijkstra part de A. Cliquez sur le sommet qui est fixé (rendu définitif) au tour 6 ; A lui-même est le tour 1.
Quelle affirmation sur HAVING est correcte ?
Les scores sont 90, 90 et 80. Quelles valeurs RANK() OVER (ORDER BY score DESC) donne-t-il ?
Que précise un enregistrement MX dans le DNS ?
Les requêtes DNS utilisent normalement UDP. Quand le DNS utilise-t-il généralement TCP ?
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 hôte a l'adresse 10.20.138.113/30. Quel est le quatrième octet x de la dernière adresse d'hôte utilisable de son sous-réseau ?
Réponse: N = −14
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 = 12 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: ¬(c ∧ b) → ¬¬a
É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).
La contraposée est équivalente à l’énoncé initial, donc la prouver prouve l’énoncé.
Réponse: N = 15
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 = 7
Algèbre de Boole : les règles qui simplifient les expressions sont X + X′ = 1 et X·X′ = 0, X + X = X, l’absorption X + X·Y = X, la règle de combinaison X·Y + X·Y′ = X, X + X′Y = X + Y et le théorème du consensus XY + X′Z + YZ = XY + X′Z. Les lois de De Morgan transforment (X·Y)′ en X′ + Y′ et (X + Y)′ en X′·Y′. Un tableau de Karnaugh applique ces règles graphiquement : chaque groupe de deux cases voisines est une utilisation de XY + XY′ = X.
Réponse: Q = 1
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: x = 10
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: 2833 mod 43 = 8
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: A · O(n²)
Avec des pivots systématiquement mauvais (par ex. une entrée déjà triée et le premier élément comme pivot), les partitions sont déséquilibrées, ce qui donne O(n²). Le cas moyen est O(n log n).
Réponse: C · O(1) par incrémentation
Sur n incrémentations, le bit i s'inverse environ n / 2ⁱ fois : le total est inférieur à 2n inversions, soit en moyenne O(1) chacune.
Réponse: A · 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 · Pour rendre très improbable qu'un attaquant puisse choisir de nombreuses clés qui entrent toutes en collision
Avec le hachage universel, le nombre attendu de collisions est faible pour tout ensemble de clés, puisque l'attaquant ne sait pas quelle fonction a été choisie.
Réponse: k = 12
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: E
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: B · Elle peut utiliser des fonctions d'agrégation pour filtrer les groupes
HAVING filtre les groupes après l'agrégation et peut faire référence à des agrégats ; WHERE ne le peut pas.
Réponse: D · 1, 1, 3
RANK donne le même rang aux lignes ex æquo et saute les numéros suivants (1, 1, 3) ; DENSE_RANK donnerait 1, 1, 2.
Réponse: C · Les serveurs de messagerie qui acceptent le courrier d'un domaine
Les enregistrements MX (mail exchange) listent les serveurs de messagerie avec leurs priorités, afin que les serveurs expéditeurs sachent où livrer le courrier de ce domaine.
Réponse: A · Pour les réponses trop grandes pour UDP et pour les transferts de zone
Si une réponse UDP est tronquée, le résolveur réessaie en TCP. Les transferts de zone entre serveurs de noms utilisent aussi TCP car ils transportent beaucoup de données.
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: x = 114
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