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 −112 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 0011 1010 >> 3. Quelle est la valeur R du résultat en décimal ?
a → (a ∨ b) est-elle une tautologie, une contradiction ou une contingence ? Cliquez sur votre réponse.
Quel énoncé est équivalent à ¬∃x (F(x) → G(x)), la négation étant passée complètement à l’intérieur ? Cliquez dessus.
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.
Trouvez la forme SOP minimale de F(A, B, C, D) = Σm(2, 7, 9, 10, 11, 13, 14) + d(1, 5), où d marque les états indifférents. Combien de littéraux L contient-elle ?
Trouvez l’inverse de 49 modulo 72 : le nombre x avec 0 < x < 72 et 49·x ≡ 1 (mod 72).
Combien de solutions N a 20x ≡ 5 (mod 25) dans {0, 1, …, 24} ?
Quel espace de pile utilise une fonction factorielle récursive simple fact(n) = n × fact(n − 1) ?
Pourquoi une recherche dans une table de hachage est-elle en O(1) en moyenne mais en O(n) dans le pire cas ?
Un tampon circulaire (ring buffer) est couramment utilisé pour implémenter :
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 ?
Le graphe connexe a-t-il un circuit eulérien, un chemin eulérien qui n’est pas un circuit, ou ni l’un ni l’autre ? Cliquez sur votre réponse.
Utilisez l’algorithme de Dijkstra pour trouver la longueur d(F) du plus court chemin de A à F dans le graphe pondéré.
Qu'est-ce qu'un déclencheur (trigger) de base de données ?
Le verrouillage à deux phases (2PL) garantit :
À quelle couche OSI un commutateur (switch) fonctionne-t-il normalement ?
Pourquoi IPv6 n'a-t-il pas besoin du NAT pour pallier la pénurie d'adresses ?
Un sous-réseau utilise le masque 255.255.255.240. Combien d’adresses d’hôte utilisables H possède-t-il ?
Un hôte a l'adresse 10.20.78.111/27. Quel est le dernier nombre (quatrième octet) x de l'adresse de diffusion de son sous-réseau ?
Réponse: U = 144
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 = 7
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 à droite de 3 déplace chaque bit de 3 positions vers la droite ; les bits qui sortent à l’extrémité droite sont perdus et des zéros entrent à gauche.
Réponse: tautologie
É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: ∀x (F(x) ∧ ¬G(x))
Quantificateurs et raisonnements : ¬∀x P(x) ≡ ∃x ¬P(x) et ¬∃x P(x) ≡ ∀x ¬P(x). Faites passer une négation vers l’intérieur, échangez chaque quantificateur qu’elle traverse, et niez la formule intérieure avec les lois propositionnelles, comme ¬(a → b) ≡ a ∧ ¬b. Un raisonnement est valide quand la conclusion vaut 1 dans toutes les lignes où toutes les prémisses valent 1. Une seule ligne avec des prémisses vraies et une conclusion fausse est un contre-exemple et montre que le raisonnement est invalide.
Les autres options laissent un quantificateur inchangé, changent l’ordre des quantificateurs, ou nient mal la formule intérieure.
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: L = 14
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: 49−1 mod 72 = 25
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·49 (mod 72).
Réponse: N = 5
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: C · O(n)
La récursion atteint une profondeur de n appels avant tout retour, et chaque appel nécessite un cadre de pile : elle utilise donc un espace O(n).
Réponse: D · De nombreuses clés peuvent entrer en collision dans le même compartiment
Avec une bonne fonction de hachage et un facteur de charge adapté, les compartiments restent courts en moyenne ; un hachage malveillant ou médiocre peut placer toutes les clés dans un seul compartiment.
Réponse: D · Une file de taille fixe
Un tampon circulaire utilise des indices de tête et de queue qui reviennent au début, ce qui permet enqueue et dequeue en O(1) dans une mémoire fixe.
Réponse: C · 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: Circuit eulérien
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: d(F) = 26
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.
Chaque ligne : le sommet fixé, sa distance définitive, et les voisins dont la distance s’améliore.
Réponse: D · 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 · Des ordonnancements sérialisables par conflits
Le 2PL garantit la sérialisabilité, mais les interblocages restent possibles et doivent être détectés ou évités.
Réponse: A · Liaison de données (couche 2)
Un commutateur standard apprend les adresses MAC et transmet les trames en couche 2. Les commutateurs de couche 3 effectuent aussi du routage.
Réponse: D · Son espace d'adressage de 128 bits est assez grand pour donner une adresse globale à chaque appareil
IPv6 compte environ 3,4 × 10³⁸ adresses, donc la pénurie qui a motivé le NAT en IPv4 disparaît ; les pare-feu assurent toujours la sécurité.
Réponse: H = 14
IPv4 subnetting: an address has 32 bits. The prefix /p says how many leading bits identify the network; the remaining 32 − p bits number the hosts. A subnet has 2³²⁻ᵖ addresses, but the first (network address) and last (broadcast address) cannot be given to hosts, so 2³²⁻ᵖ − 2 hosts fit. Exceptions: a /31 (point-to-point link, RFC 3021) uses both of its 2 addresses for hosts, and a /32 is one single address (a single host or a loopback).
Réponse: x = 127
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