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 −39 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 1000 1101 AND 1101 1101. Quelle est la valeur R du résultat en décimal ?
Vous voulez prouver ¬b → (c ∨ a) par contraposée. Quelle implication prouvez-vous à la place ? Cliquez dessus.
Combien des 16 lignes de la table de vérité rendent ((b ∧ d) ∨ b) → (¬d ∨ (a ∧ c)) vraie ? Appelez ce nombre N.
Simplifiez F = AC + A′B + A′BC′ + BC à sa forme somme de produits minimale. Combien de littéraux L contient l’expression simplifiée ?
Une bascule T déclenchée sur front montant part de Q = 0 et reçoit les entrées représentées. Cliquez sur le premier front d’horloge où Q repasse de 1 à 0.
Trouvez l’inverse de 16 modulo 23 : le nombre x avec 0 < x < 23 et 16·x ≡ 1 (mod 23).
Une clé RSA utilise les nombres premiers p = 5 et q = 31 et l’exposant public e = 23. Trouvez l’exposant privé d (0 < d < φ(n)).
Quelle est la complexité temporelle de la multiplication de deux matrices n × n avec la triple boucle standard ?
22n est-il dans O(2ⁿ) ?
Comment insère-t-on un nouvel élément dans un tas binaire ?
Dans le BST de racine 50, avec le sous-arbre gauche 30 (enfants 20, 40) et le sous-arbre droit 70 (enfants 60, 80), on supprime la racine en utilisant le successeur infixe. Quelle clé devient la nouvelle racine ?
Combien de circuits hamiltoniens différents H le graphe complet K8 a-t-il ? Les circuits qui ne diffèrent que par le sommet de départ ou le sens comptent comme un seul.
Combien de marches fermées de longueur 2 partent de B et y reviennent ? Une marche peut répéter des sommets et des arêtes. Appelez ce nombre N.
Quelle instruction supprime toutes les lignes d'une table, conserve sa structure et n'accepte pas de clause WHERE ?
La table employee(emp_id, dept_id, dept_name) a pour clé emp_id, et dept_id → dept_name. Quelle affirmation est correcte ?
Un navigateur reçoit le code d'état HTTP 404. Que signifie-t-il ?
Un commutateur à 8 ports (sans VLAN) a un hôte sur chaque port. Combien y a-t-il de domaines de collision et de domaines de diffusion ?
Un service a besoin de 1965 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.72.236/29. Quel est le dernier nombre (quatrième octet) x de l'adresse de diffusion de son sous-réseau ?
Réponse: U = 217
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 = 141
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.
ET donne 1 seulement quand les deux bits valent 1.
Réponse: ¬(c ∨ a) → ¬¬b
É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 = 13
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 = 4
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: front d’horloge 4
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.
Une bascule T change d’état à chaque front montant quand T = 1 et conserve quand T = 0.
Réponse: 16−1 mod 23 = 13
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·16 (mod 23).
Réponse: d = 47
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³)
Il y a n² entrées et chacune nécessite n multiplications, soit n³ opérations.
Réponse: A · 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: C · On le place à la fin du tableau et on le fait remonter tant qu'il viole la propriété de tas
L'ajout à la fin maintient l'arbre complet ; les échanges avec le parent rétablissent l'ordre en O(log n) étapes.
Réponse: D · 60
Le nœud le plus à gauche du sous-arbre droit est 60 ; 60 remplace donc 50 et son ancienne position est supprimée. Utiliser le prédécesseur donnerait 40.
Réponse: H = 2520
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 = 4
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: 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 · Elle est en 2NF mais pas en 3NF
La clé n'a qu'une colonne, la 2NF est donc respectée, mais emp_id → dept_id → dept_name est une dépendance transitive, ce qui viole la 3NF.
Réponse: C · La ressource demandée est introuvable
404 Not Found signifie que le serveur n'a aucune ressource à cette URL. 200 signifie OK, 401 Unauthorized et 500 Internal Server Error.
Réponse: D · 8 domaines de collision, 1 domaine de diffusion
Chaque port de commutateur forme son propre domaine de collision, mais les diffusions sont transmises à tous les ports ; tout le commutateur forme donc un seul domaine de diffusion. Un concentrateur donnerait un seul domaine de chaque.
Réponse: p = 21
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 = 239
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