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 −50 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 1001 0101 OR 1010 1011. Quelle est la valeur R du résultat en décimal ?
Dans combien des 8 lignes de sa table de vérité ¬((c ∧ a) → (¬c ∨ b)) ↔ ¬(¬a ∨ b) est-elle vraie ? Appelez ce nombre N.
Le raisonnement de prémisses q → p; ¬q et de conclusion ¬p est invalide. Cliquez sur la ligne de la table de vérité qui est un contre-exemple.
Simplifiez F = A′C + ABC′ + AB′C′ à sa forme somme de produits minimale. Combien de littéraux L contient l’expression simplifiée ?
Trouvez la forme SOP minimale de F(A, B, C, D) = Σm(0, 2, 5, 7, 10, 11, 12, 14) + d(1, 3, 9, 13), où d marque les états indifférents. Combien de termes produits N a-t-elle ?
Trouvez le plus petit entier positif x tel que x ≡ 1 (mod 6) et x ≡ 0 (mod 13).
Une clé RSA utilise les nombres premiers p = 23 et q = 29 et l’exposant public e = 19. Trouvez l’exposant privé d (0 < d < φ(n)).
Que signifie qu'un problème possède une sous-structure optimale ?
Lequel de ces problèmes de satisfiabilité est connu pour être résoluble en temps polynomial ?
Les clés 50, 30, 70, 20, 40 sont insérées dans cet ordre dans un arbre binaire de recherche vide. Quel est l'enfant gauche de 30 ?
Quelle paire de parcours détermine toujours un arbre binaire unique à clés distinctes ?
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.
Combien de marches de longueur 2 vont de D à A ? Une marche peut répéter des sommets et des arêtes. Appelez ce nombre N.
Quelle requête renvoie le salaire le plus élevé de chaque service ?
Il existe un index composé sur (last_name, first_name). Quelle condition peut l'utiliser le plus efficacement ?
Que précise un enregistrement MX dans le DNS ?
Un étudiant fait tourner un serveur de jeu sur un PC derrière un routeur NAT domestique. Ses amis sur Internet ne peuvent pas s'y connecter. Quelle est la solution habituelle ?
Un service a besoin de 444 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.195.237/30. Quel est le quatrième octet x de la dernière adresse d'hôte utilisable de son sous-réseau ?
Réponse: U = 206
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 = 191
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.
OU donne 1 quand au moins un bit vaut 1.
Réponse: N = 7
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: p = 1, q = 0
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.
Un raisonnement de cette forme ressemble à une règle valide, mais une seule ligne suffit à montrer qu’il ne l’est pas.
Réponse: L = 4
Algèbre de Boole : les règles qui simplifient les expressions sont X + X′ = 1 et X·X′ = 0, X + X = X, l’absorption X + X·Y = X, la règle de combinaison X·Y + X·Y′ = X, X + X′Y = X + Y et le théorème du consensus XY + X′Z + YZ = XY + X′Z. Les lois de De Morgan transforment (X·Y)′ en X′ + Y′ et (X + Y)′ en X′·Y′. Un tableau de Karnaugh applique ces règles graphiquement : chaque groupe de deux cases voisines est une utilisation de XY + XY′ = X.
Réponse: N = 4
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: x = 13
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 = 227
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: C · Une solution optimale peut être construite à partir de solutions optimales de ses sous-problèmes
La sous-structure optimale est nécessaire pour que les algorithmes gloutons comme la programmation dynamique produisent des réponses correctes.
Réponse: B · 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: A · 20
20 est plus petit que 50 et que 30, il devient donc l'enfant gauche de 30 ; 40 devient son enfant droit.
Réponse: D · Préfixe et infixe
Le parcours préfixe donne la racine, et sa position dans la séquence infixe sépare les sous-arbres gauche et droit ; préfixe et postfixe sont ambigus lorsqu'un nœud a un seul enfant.
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: N = 1
Degrés : le degré d’un sommet est le nombre d’arêtes qui y aboutissent. Chaque arête a deux extrémités, donc les degrés totalisent deux fois le nombre d’arêtes : Σ deg(v) = 2|E| (le lemme des poignées de main). Le nombre de sommets de degré impair est donc pair. Kn a n(n − 1)/2 arêtes, un graphe k-régulier à n sommets en a nk/2, et un arbre à n sommets a n − 1 arêtes.
Réponse: D · 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: C · WHERE last_name = 'Jansen'
Un index B-tree composé est ordonné par last_name puis par first_name ; une recherche sur la colonne de tête fonctionne, mais first_name seule ne peut pas exploiter cet ordre.
Réponse: B · Les serveurs de messagerie qui acceptent le courrier d'un domaine
Les enregistrements MX (mail exchange) listent les serveurs de messagerie avec leurs priorités, afin que les serveurs expéditeurs sachent où livrer le courrier de ce domaine.
Réponse: D · Configurer une redirection de port sur le routeur vers l'adresse privée du PC
Le NAT ne crée des correspondances que pour les connexions initiées depuis l'intérieur. Une règle de redirection de port associe un port public à l'hôte interne pour que les connexions entrantes puissent l'atteindre.
Réponse: p = 23
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 = 238
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