Formulaires, étapes clés de la méthode pour chaque thème et 20 exercices, avec les corrigés complets à la fin.
Écris −43 comme motif de 8 bits en complément à deux. Lis ce motif comme un nombre binaire non signé : quelle est sa valeur U en décimal ?
Quel est le plus grand entier non signé N qui tient sur 16 bits ?
Quelle formule est logiquement équivalente à ¬(q → r) ? Cliquez dessus.
Les prémisses q → r; r → p; ¬p sont données. Quelle conclusion en découle ? Cliquez dessus.
Utilisez le tableau de Karnaugh pour trouver la forme produit de sommes (POS) minimale de F(A, B, C, D) = Σm(3, 6, 9, 10, 11, 12, 13, 15). Combien de termes somme (facteurs) N a-t-elle ?
Trouvez la forme SOP minimale de F(A, B, C, D) = Σm(1, 7, 8, 12) + d(6, 9), où d marque les états indifférents. Combien de littéraux L contient-elle ?
Trouvez l’indicatrice d’Euler φ(169), le nombre d’entiers de 1 à 169 premiers avec 169.
Une clé RSA utilise les nombres premiers p = 13 et q = 43 et l’exposant public e = 19. Trouvez l’exposant privé d (0 < d < φ(n)).
Quelle est la solution de la récurrence T(n) = T(n − 1) + O(n) ?
Lequel de ces problèmes de satisfiabilité est connu pour être résoluble en temps polynomial ?
Un nœud d'un arbre binaire de recherche possède un sous-arbre droit. Où se trouve son successeur dans l'ordre infixe ?
En quoi un arbre radix (trie compressé) améliore-t-il un trie simple ?
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é.
Une table employees possède une colonne manager_id qui fait référence à un autre employé. Comment lister chaque employé à côté du nom de son responsable ?
Avec le contrôle de concurrence multiversion (MVCC), comment les lecteurs évitent-ils de bloquer les écrivains ?
Laquelle de ces plages est une plage d'adresses IPv4 privée ?
Pourquoi l'option de mise à l'échelle de la fenêtre TCP (window scale) a-t-elle été introduite ?
Le réseau 192.168.10.0/24 doit être divisé en au moins 8 sous-réseaux égaux. Si tu empruntes le moins de bits possible, combien d'hôtes utilisables H chaque sous-réseau a-t-il ?
Un hôte a l’adresse 172.20.68.209/22. Quel est le troisième octet x de l’adresse de diffusion de son sous-réseau ?
Réponse: U = 213
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: N = 65535
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: q ∧ ¬r
É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: ¬q
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.
Réponse: N = 5
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: L = 9
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: φ(169) = 156
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: d = 451
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²)
Le travail totalise environ n² / 2 ; c'est la récurrence du tri par sélection ou du tri rapide avec le pire pivot.
Réponse: A · 2-SAT, où chaque clause a au plus deux littéraux
2-SAT est dans P (temps linéaire via les composantes fortement connexes), tandis que 3-SAT est NP-complet.
Réponse: B · Au nœud le plus à gauche de son sous-arbre droit
Toutes les clés plus grandes proches du nœud se trouvent dans son sous-arbre droit, et la plus petite d'entre elles est le nœud le plus à gauche de ce sous-arbre.
Réponse: D · Il fusionne les chaînes de nœuds à enfant unique en une seule arête étiquetée par une chaîne
Fusionner les chemins sans ramification réduit le nombre de nœuds et la mémoire utilisée tout en conservant la recherche par préfixe.
Réponse: Chemin eulérien, pas de circuit
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.
Le chemin eulérien commence à un sommet impair et finit à l’autre.
Réponse: d(F) = 17
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: C · Joindre la table employees à elle-même avec deux alias
Une auto-jointure comme FROM employees e JOIN employees m ON e.manager_id = m.id permet à un alias de représenter l'employé et à l'autre son responsable.
Réponse: B · Les lecteurs voient un instantané cohérent des versions validées des lignes, tandis que les écrivains créent de nouvelles versions
Le MVCC conserve les anciennes versions des lignes afin qu'un lecteur voie les données telles qu'elles étaient dans son instantané, tandis qu'un écrivain crée une nouvelle version au lieu d'écraser sur place.
Réponse: B · 192.168.0.0/16
Les plages privées sont 10.0.0.0/8, 172.16.0.0/12 et 192.168.0.0/16 ; elles ne sont pas routées sur l'Internet public.
Réponse: D · Le champ de fenêtre de 16 bits limite la fenêtre à 65535 octets, trop peu pour les chemins rapides et longs
L'en-tête d'origine permet au plus 65535 octets de données non acquittées. La mise à l'échelle multiplie cette valeur par une puissance de deux pour que les chemins à fort produit bande passante-délai puissent être remplis.
Réponse: H = 30
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 = 71
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).
ExamProblems · examproblems.com/courses/computer-science-fundamentals