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 −84 en complément à deux sur 8 bits. Lu comme un nombre non signé, quelle est la valeur U du motif ?
Une image non compressée fait 1920 × 1080 pixels avec 8 bits par pixel. Quelle mémoire M occupe-t-elle, en Kio (1 Kio = 1024 octets) ?
(p ∨ q) ∧ (¬p ∧ ¬q) 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 (d ∨ (b ∧ c)) ∧ ((a ↔ c) ∧ (a → ¬b)) vraie ? Appelez ce nombre N.
Utilisez le tableau de Karnaugh pour trouver la forme somme de produits (SOP) minimale de F(A, B, C, D) = Σm(3, 5, 8, 11, 12). Combien de termes produits N a-t-elle ?
Trouvez la forme SOP minimale de F(A, B, C, D) = Σm(0, 8, 11, 13, 15) + d(3, 12, 14), où d marque les états indifférents. Combien de termes produits N a-t-elle ?
Trouvez l’inverse de 42 modulo 53 : le nombre x avec 0 < x < 53 et 42·x ≡ 1 (mod 53).
Résolvez 68x ≡ 24 (mod 74). Donnez la plus petite solution positive x.
Que signifie qu'un problème possède une sous-structure optimale ?
Quelle borne est correcte pour log(n!) ?
Une application a besoin de recherches rapides, mais aussi de lister les clés dans l'ordre trié et de répondre à des requêtes par intervalle. Quelle structure convient le mieux ?
La structure union-find (ensembles disjoints) avec union par rang et compression de chemin a un coût amorti par opération de :
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 fermées de longueur 2 partent de D et y reviennent ? Une marche peut répéter des sommets et des arêtes. Appelez ce nombre N.
Une clé étrangère est déclarée avec ON DELETE CASCADE. Que se passe-t-il quand une ligne parente est supprimée ?
La table employee(emp_id, dept_id, dept_name) a pour clé emp_id, et dept_id → dept_name. Quelle affirmation est correcte ?
Quel préfixe unique résume à la fois 192.168.0.0/24 et 192.168.1.0/24 ?
Le blocage en tête de ligne (head-of-line blocking) de HTTP/2 sur TCP se produit parce que :
Un service a besoin de 900 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.215.166/29. Quel est le quatrième octet x de la dernière adresse d'hôte utilisable de son sous-réseau ?
Réponse: U = 172
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: M = 2025 KiB
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: contradiction
É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 = 3
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 = 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.
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.
Il existe un autre regroupement de même taille ; il a le même nombre de termes et de littéraux.
Réponse: 42−1 mod 53 = 24
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·42 (mod 53).
Réponse: x = 33
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: 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: C · Θ(n log n)
log(n!) ≤ n log n, et les n / 2 plus grands facteurs donnent log(n!) ≥ (n / 2) log(n / 2) ; c'est pourquoi le tri par comparaisons nécessite Ω(n log n).
Réponse: C · Un arbre binaire de recherche équilibré
Un BST équilibré offre des recherches en O(log n) et garde les clés ordonnées, ce qui facilite le parcours infixe et les requêtes par intervalle ; une table de hachage disperse les clés.
Réponse: D · O(α(n)), l'inverse de la fonction d'Ackermann, pratiquement constant
Avec les deux optimisations, les opérations prennent un temps amorti O(α(n)) ; α(n) ≤ 4 pour tout n réaliste.
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 = 3
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: A · Les lignes enfants qui y font référence sont supprimées automatiquement
CASCADE propage la suppression aux lignes qui font référence à la ligne supprimée ; les autres options sont RESTRICT/NO ACTION (refus) et SET NULL.
Réponse: C · Elle est en 2NF mais pas en 3NF
La clé n'a qu'une colonne, la 2NF est donc respectée, mais emp_id → dept_id → dept_name est une dépendance transitive, ce qui viole la 3NF.
Réponse: A · 192.168.0.0/23
0 et 1 partagent tous les bits du troisième octet sauf le dernier ; un préfixe raccourci d'un bit (/23) commençant à 192.168.0.0 couvre donc exactement les deux.
Réponse: D · Un segment TCP perdu retarde tous les flux multiplexés jusqu'à sa retransmission
TCP livre les octets dans l'ordre, donc une seule perte bloque tous les flux de la connexion. QUIC (HTTP/3) gère les flux indépendamment au-dessus d'UDP.
Réponse: p = 22
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 = 166
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