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 −47 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 2528 é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 à (r ∧ q) → p ? Cliquez dessus.
Quel énoncé est équivalent à ¬∀x (A(x) → ∃y R(x, y)), la négation étant passée complètement à l’intérieur ? Cliquez dessus.
Utilisez le tableau de Karnaugh pour trouver la forme somme de produits (SOP) minimale de F(A, B, C, D) = Σm(0, 3, 6, 7, 9, 11). Combien de littéraux L contient-elle au total (une variable primée compte pour un littéral) ?
Trouvez la forme SOP minimale de F(A, B, C, D) = Σm(1, 4, 8, 9, 12, 13) + d(0, 7), où d marque les états indifférents. Combien de littéraux L contient-elle ?
Trouvez l’inverse de 43 modulo 48 : le nombre x avec 0 < x < 48 et 43·x ≡ 1 (mod 48).
Chiffre le message m = 16 avec la clé publique RSA (n, e) = (1457, 11). Trouvez le chiffré c.
Quel espace de pile utilise une fonction factorielle récursive simple fact(n) = n × fact(n − 1) ?
Quelles sont les deux choses à montrer pour prouver qu'un problème de décision X est NP-complet ?
Comment insère-t-on un nouvel élément dans un tas binaire ?
L'insertion d'une clé dans un arbre AVL rend le sous-arbre gauche d'un nœud trop haut, et la nouvelle clé est allée dans le sous-arbre gauche de son enfant gauche (cas gauche-gauche). Quelle correction applique-t-on ?
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.
Trouvez le poids total W d’un arbre couvrant minimal du graphe pondéré.
Que renvoie SELECT COALESCE(phone, 'unknown') FROM customers pour un client dont le téléphone est NULL ?
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 ?
Quel type d'enregistrement DNS associe un nom d'hôte à une adresse IPv6 ?
Après des collisions répétées, les stations Ethernet classiques choisissent leur temps d'attente dans un intervalle qui double à chaque fois. Pourquoi ?
Un service a besoin de 203 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.91.150/29. Quel est le quatrième octet x de son adresse réseau ?
Réponse: U = 209
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 = 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: 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: ∃x (A(x) ∧ ∀y ¬R(x, y))
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: L = 13
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é.
Il existe un autre regroupement de même taille ; il a le même nombre de termes et de littéraux.
Réponse: L = 6
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.
Réponse: 43−1 mod 48 = 19
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·43 (mod 48).
Réponse: c = 388
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: B · 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 · X est dans NP, et un problème NP-complet connu se réduit à X en temps polynomial
L'appartenance à NP montre que X n'est pas plus difficile que NP ; la réduction depuis un problème NP-complet connu montre que X est au moins aussi difficile que tout NP.
Réponse: A · 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: C · Une rotation simple à droite sur le nœud déséquilibré
Dans le cas gauche-gauche, une rotation à droite fait remonter l'enfant gauche et rétablit l'équilibre ; les cas en zigzag nécessitent une double rotation.
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: W = 56
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: A · 'unknown'
COALESCE examine ses arguments de gauche à droite et renvoie le premier qui n'est pas NULL, ici 'unknown'.
Réponse: B · 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: D · AAAA
Un enregistrement A contient une adresse IPv4, AAAA une adresse IPv6. MX désigne les serveurs de messagerie et CNAME donne un alias.
Réponse: D · Pour réduire le risque d'une nouvelle collision lorsque de nombreuses stations sont en concurrence
Chaque nouvelle collision suggère davantage de concurrence ; l'intervalle aléatoire s'agrandit donc et les stations ont plus de chances de choisir des créneaux différents. Le mécanisme s'adapte à la charge sans contrôle central.
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 = 144
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