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 1001 1011 stocke un entier signé en complément à deux. Quelle est sa valeur N en décimal ?
Un système doit donner à chacun de 2855 é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 b → (c ∨ a) par l’absurde. Quel énoncé supposez-vous au départ ? Cliquez dessus.
Quel énoncé est équivalent à ¬∀x (F(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 produit de sommes (POS) minimale de F(A, B, C, D) = Σm(1, 2, 4, 7, 9, 11). Combien de termes somme (facteurs) N a-t-elle ?
Un compteur binaire croissant de 4 bits part de 11 (décimal, Q = 1011). Quelle valeur Q (en décimal) affiche-t-il après 28 impulsions d’horloge ?
Trouvez le plus petit entier positif x tel que x ≡ 2 (mod 5) et x ≡ 10 (mod 13).
Combien de solutions N a 44x ≡ 18 (mod 54) dans {0, 1, …, 53} ?
Pourquoi la programmation dynamique n'apporte-t-elle aucune accélération réelle au tri fusion ?
Quelle affirmation concernant P et NP est correcte ?
Quel type abstrait de données l'algorithme de Dijkstra utilise-t-il pour choisir le prochain sommet à traiter ?
Quelle affirmation sur le tri par tas (heapsort) est correcte ?
Un graphe connexe a 20 sommets et 26 arêtes. Combien d’arêtes k faut-il retirer pour obtenir un arbre couvrant ?
Trouvez le poids total W d’un arbre couvrant minimal du graphe pondéré.
Que renvoie INTERSECT utilisé entre deux requêtes SELECT ?
Pourquoi NATURAL JOIN est-il considéré comme risqué dans les requêtes de production ?
Qu'est-ce qui identifie de façon unique une extrémité d'une connexion TCP sur Internet ?
Quel mécanisme empêche les boucles de diffusion dans un réseau avec des liens redondants entre commutateurs ?
Un sous-réseau utilise le masque 255.255.255.252. Combien d’adresses d’hôte utilisables H possède-t-il ?
Un hôte a l'adresse 10.20.170.124/27. Quel est le dernier nombre (quatrième octet) x de l'adresse de diffusion de son sous-réseau ?
Réponse: N = −101
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: b ∧ ¬(c ∨ 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).
Si l’hypothèse mène à une contradiction, l’implication doit être vraie.
Réponse: ∃x (F(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: N = 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.
Chaque groupe est un rectangle de 2ᵏ cases ; les cases de bord sont voisines des cases du bord opposé.
Réponse: Q = 7
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.
Toutes les 16 impulsions ramènent le compteur au même état.
Réponse: x = 62
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: N = 2
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: B · Ses sous-problèmes ne se chevauchent pas, il n'y a donc rien à réutiliser
Les moitiés du tri fusion sont disjointes et chacune est résolue une seule fois ; la PD n'aide que lorsque les sous-problèmes se répètent, comme pour Fibonacci.
Réponse: A · Tout problème de P appartient aussi à NP
P ⊆ NP : si vous pouvez résoudre un problème rapidement, vous pouvez vérifier une solution rapidement. La question P = NP reste ouverte.
Réponse: D · Une file de priorité min
Une file de priorité min, généralement un tas binaire, renvoie efficacement le sommet non visité de plus petite distance.
Réponse: D · Il trie sur place en O(n log n) dans le pire cas, mais n'est pas stable
Le tri par tas construit un tas max et extrait le maximum n fois dans le même tableau ; des échanges sur de longues distances peuvent réordonner des clés égales.
Réponse: k = 7
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 = 51
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 · Les lignes présentes dans les deux résultats
INTERSECT ne garde que les lignes présentes dans les deux requêtes et, comme UNION, supprime les doublons par défaut.
Réponse: A · Il joint sur toutes les colonnes de même nom, si bien qu'une nouvelle colonne peut modifier le résultat sans prévenir
Une jointure naturelle fait correspondre toutes les colonnes de même nom, par exemple une colonne "name" ou "created_at" sans rapport ; une clause ON ou USING explicite est plus sûre.
Réponse: B · Une adresse IP associée à un numéro de port
Une connexion TCP est identifiée par l'adresse IP et le port source ainsi que l'adresse IP et le port de destination. Les ports distinguent les nombreuses applications d'un même hôte.
Réponse: C · Spanning Tree Protocol
STP élit un pont racine (root bridge) et bloque les chemins redondants, puis les débloque si un lien actif tombe en panne.
Réponse: H = 2
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