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 0010 1100 stocke un entier signé en complément à deux. Quelle est sa valeur N en décimal ?
Quel est le plus grand entier non signé N qui tient sur 20 bits ?
((q ∨ r) ∧ q) → ¬r est-elle une tautologie, une contradiction ou une contingence ? Cliquez sur votre réponse.
Combien des 16 lignes de la table de vérité rendent ¬((s ↔ ¬q) ↔ ((q → ¬p) ∨ r)) vraie ? Appelez ce nombre N.
Utilisez le tableau de Karnaugh pour trouver la forme produit de sommes (POS) minimale de F(A, B, C) = Σm(0, 2, 4, 5). Combien de termes somme (facteurs) N a-t-elle ?
Pour F(A, B, C, D) = Σm(0, 2, 5, 6, 8, 9, 11, 14, 15) + d(1, 3, 7), où d marque les états indifférents, trouvez le nombre N d’implicants premiers essentiels.
Trouvez l’indicatrice d’Euler φ(25), le nombre d’entiers de 1 à 25 premiers avec 25.
Utilisez le carré répété pour trouver 44172 mod 57.
Quelle est la complexité temporelle de : pour i = 1 à n : (j = 1 ; tant que j < n : j = j × 2) ?
Prendre les deux extrémités de chaque arête d'un couplage maximal donne une couverture par sommets. Quelle est la qualité de cette couverture ?
Quel type abstrait de données l'algorithme de Dijkstra utilise-t-il pour choisir le prochain sommet à traiter ?
Sans union par rang ni compression de chemin, quel est le coût dans le pire cas d'une seule opération find dans une structure union-find à n éléments ?
Combien de circuits hamiltoniens différents H le graphe complet K4 a-t-il ? Les circuits qui ne diffèrent que par le sommet de départ ou le sens comptent comme un seul.
L’algorithme de Dijkstra part de A. Cliquez sur le sommet qui est fixé (rendu définitif) au tour 5 ; A lui-même est le tour 1.
Quelle requête renvoie le salaire le plus élevé de chaque service ?
Pourquoi NATURAL JOIN est-il considéré comme risqué dans les requêtes de production ?
Un signal parcourt 2000 km dans une fibre à environ 2 × 10⁸ m/s. Quel est le délai de propagation ?
Que fait la retransmission rapide (fast retransmit) de TCP ?
Un service a besoin de 1349 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.168.181/27. Quel est le quatrième octet x de son adresse réseau ?
Réponse: N = 44
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: N = 1,049 × 10⁶
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: contingence
É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: N = 8
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: N = 2
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: N = 3
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: φ(25) = 20
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: 44172 mod 57 = 25
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: D · O(n log n)
La boucle intérieure s'exécute environ log₂ n fois pour chacune des n itérations extérieures, soit O(n log n).
Réponse: D · Au plus deux fois la taille d'une couverture par sommets minimale
Les arêtes du couplage n'ont aucun sommet en commun : l'optimum nécessite donc au moins un sommet par arête, tandis que cette méthode en prend deux, d'où une 2-approximation.
Réponse: B · 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 · O(n)
Des unions naïves peuvent relier les arbres en une longue chaîne, donc find peut suivre n − 1 pointeurs vers le parent ; les deux heuristiques le rendent presque constant.
Réponse: H = 3
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: C
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 · SELECT dept, MAX(salary) FROM emp GROUP BY dept
GROUP BY dept crée un groupe par service et MAX(salary) prend la valeur la plus élevée de chacun.
Réponse: B · 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: C · 10 ms
2 × 10⁶ m / 2 × 10⁸ m/s = 0,01 s = 10 ms. Le délai de propagation dépend de la distance et du support, pas de la taille du paquet.
Réponse: A · Elle renvoie un segment après trois ACK dupliqués, sans attendre l'expiration du délai
Trois ACK dupliqués indiquent fortement la perte d'un seul segment, que TCP retransmet donc aussitôt. La récupération est bien plus rapide qu'en attendant le temporisateur de retransmission.
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 = 160
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