Formulaires, étapes clés de la méthode pour chaque thème et 20 exercices, avec les corrigés complets à la fin.
Écris −111 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 ?
Positionnez les bits sur le résultat sur 8 bits de 1100 0100 << 1. Quelle est la valeur R du résultat en décimal ?
Quelle formule est logiquement équivalente à (r ∧ q) → p ? Cliquez dessus.
Quel énoncé est équivalent à ¬∀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, 1, 4, 5, 7, 12, 13). 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, 3, 4, 7, 8, 11, 14) + d(2, 5, 10, 15), où d marque les états indifférents. Combien de littéraux L contient-elle ?
Trouvez l’inverse de 79 modulo 89 : le nombre x avec 0 < x < 89 et 79·x ≡ 1 (mod 89).
Chiffre le message m = 432 avec la clé publique RSA (n, e) = (527, 7). Trouvez le chiffré c.
Pourquoi la programmation dynamique n'apporte-t-elle aucune accélération réelle au tri fusion ?
La multiplication de Karatsuba vérifie T(n) = 3T(n/2) + O(n). Quelle en est la solution ?
Dans un tas binaire min stocké dans un tableau (indices commençant à 0), les enfants du nœud d'indice i se trouvent aux indices :
Quelle propriété un arbre rouge-noir doit-il respecter ?
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.
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 nombre de commandes par client ?
Pourquoi SELECT dept, name, COUNT(*) FROM emp GROUP BY dept est-il invalide en SQL standard ?
Combien d'adresses d'hôtes utilisables compte un réseau IPv4 /24 ?
Dans une connexion TCP, que contrôle la fenêtre de réception (rwnd) ?
Le réseau 192.168.10.0/24 doit être divisé en au moins 6 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 ?
Le réseau 192.168.45.0/24 est découpé en VLSM pour ces LAN : A: 3 hôtes, B: 21 hôtes, C: 7 hôtes, D: 28 hôtes, E: 6 hôtes. Les sous-réseaux sont attribués à partir de .0 en montant, le LAN ayant le plus d’hôtes en premier, chacun recevant le plus petit sous-réseau qui convient. Quel est le quatrième octet x de l’adresse réseau du LAN B ?
Réponse: U = 145
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 = 136
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.
Un décalage à gauche de 1 déplace chaque bit de 1 positions vers la gauche ; les bits qui sortent à l’extrémité gauche sont perdus et des zéros entrent à droite.
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 ∀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 = 7
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 = 10
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: 79−1 mod 89 = 80
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·79 (mod 89).
Réponse: c = 182
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 · 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: C · Θ(nlog₂ 3), soit environ n1,585
Comme log₂ 3 ≈ 1,585 > 1, les feuilles dominent d'après le théorème maître, ce qui bat la méthode scolaire en O(n²).
Réponse: D · 2i + 1 et 2i + 2
Pour des tableaux indexés à partir de 0, l'enfant gauche est en 2i + 1, l'enfant droit en 2i + 2 et le parent en ⌊(i − 1)/2⌋.
Réponse: B · Tout chemin d'un nœud vers ses feuilles descendantes contient le même nombre de nœuds noirs
Règles rouge-noir : les nœuds sont rouges ou noirs, la racine est noire, les nœuds rouges ont des enfants noirs et tous les chemins ont la même hauteur noire, ce qui maintient la hauteur ≤ 2 log₂(n + 1).
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: D
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: C · SELECT customer_id, COUNT(*) FROM orders GROUP BY customer_id
GROUP BY customer_id crée un groupe par client, et COUNT(*) compte les lignes de chaque groupe.
Réponse: C · name n'est ni regroupé ni agrégé, il n'a donc pas une valeur unique par groupe
Chaque colonne de la liste du SELECT doit figurer dans GROUP BY ou dans un agrégat (ou dépendre fonctionnellement des colonnes de regroupement) ; sinon la valeur est ambiguë.
Réponse: A · 254
Un /24 a 8 bits d'hôte, soit 2⁸ = 256 adresses. Les adresses de réseau et de diffusion sont réservées, il en reste 254 pour les hôtes.
Réponse: A · La quantité de données non acquittées que l'émetteur peut envoyer, en fonction du tampon du récepteur
Le récepteur annonce l'espace disponible dans son tampon ; l'émetteur limite en conséquence les données non acquittées, ce qui évite de surcharger le récepteur.
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 = 32
VLSM : chaque LAN reçoit le plus petit sous-réseau tel que 2ʰ − 2 ≥ son nombre d’hôtes, c’est-à-dire un préfixe 32 − h. Attribuer d’abord les plus grands sous-réseaux garde chaque bloc aligné sur un multiple de sa propre taille, donc les adresses réseau s’obtiennent en additionnant les tailles de bloc.
LAN B : 192.168.45.32/27.
ExamProblems · examproblems.com/courses/computer-science-fundamentals