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 ?
Un système doit donner à chacun de 556 éléments son propre code binaire, tous de même longueur. Quel est le plus petit nombre de bits b nécessaire ?
Dans combien des 8 lignes de sa table de vérité (¬a ∨ ¬c) ∧ (¬(c ∧ b) ∧ a) est-elle vraie ? Appelez ce nombre N.
Quel énoncé est équivalent à ¬∀x A(x), 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) = Σm(1, 4, 6). Combien de termes produits N a-t-elle ?
Trouvez la forme SOP minimale de F(A, B, C, D) = Σm(1, 3, 4, 8, 11, 12, 14) + d(0, 2, 9, 10, 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 ≡ 7 (mod 8) et x ≡ 5 (mod 11).
Résolvez 32x ≡ 4 (mod 46). Donnez la plus petite solution positive x.
Quelle est la solution de la récurrence T(n) = T(n − 1) + O(n) ?
Quel algorithme trouve un arbre couvrant de poids minimal en ajoutant de façon répétée l'arête la moins coûteuse qui ne forme pas de cycle ?
Qu'est-ce qui est vrai de la matrice d'adjacence d'un graphe non orienté ?
Quelle structure de données permet un cache LRU (least recently used) avec get et put en O(1) ?
Un graphe connexe a 16 sommets et 21 arêtes. Combien d’arêtes k faut-il retirer pour obtenir un arbre couvrant ?
L’algorithme de Prim construit un arbre couvrant minimal en partant du sommet B. Cliquez sur l’arête qu’il ajoute en numéro 4.
Que renvoie SELECT SUM(amount) FROM orders lorsque la clause WHERE ne correspond à aucune ligne ?
Une base de données de reporting copie les noms des clients dans la table des commandes pour éviter des jointures. Quel est le principal coût de cette dénormalisation ?
Combien d'adresses d'hôtes utilisables compte un réseau IPv4 /24 ?
Le problème du comptage à l'infini se produit dans quel type de protocole de routage, et qu'est-ce qui aide à le contrer ?
Un service a besoin de 1631 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.155.225/25. Quel est le quatrième octet x de la dernière adresse d'hôte utilisable 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: b = 10 bit
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 = 2
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: ∃x ¬A(x)
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: 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: x = 71
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: x = 3
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: 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: B · L'algorithme de Kruskal
Kruskal trie les arêtes par poids et les ajoute si elles relient des composantes différentes ; Prim fait croître un seul arbre à partir d'un sommet de départ.
Réponse: C · Elle est symétrique par rapport à la diagonale principale
Dans un graphe non orienté, l'arête {u, v} signifie que M[u][v] et M[v][u] sont tous deux renseignés, donc la matrice est égale à sa transposée.
Réponse: A · Une table de hachage combinée à une liste doublement chaînée
La table de hachage trouve les nœuds en O(1) et la liste doublement chaînée déplace les éléments consultés vers l'avant et évince par l'arrière en O(1).
Réponse: k = 6
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: arête AC
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: D · NULL
SUM, AVG, MIN et MAX renvoient NULL sur un ensemble vide, alors que COUNT renvoie 0 ; COALESCE(SUM(amount), 0) donne 0 à la place.
Réponse: C · Les copies redondantes doivent rester cohérentes chaque fois que les données client changent
La dénormalisation accélère les lectures mais réintroduit de la redondance ; les mises à jour doivent donc modifier chaque copie, sinon des anomalies apparaissent.
Réponse: C · 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: C · À vecteur de distance ; l'horizon partagé (split horizon) et l'empoisonnement inverse (poison reverse)
Après une panne, les routeurs à vecteur de distance peuvent continuer à s'annoncer mutuellement des routes périmées, la métrique augmentant lentement. L'horizon partagé, l'empoisonnement inverse et une métrique maximale limitent ce phénomène.
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 = 254
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