Formulaires, étapes clés de la méthode pour chaque thème et 20 exercices, avec les corrigés complets à la fin.
Le motif de 8 bits 1110 1111 stocke un entier signé en complément à deux. Quelle est sa valeur N en décimal ?
Quel est l'entier le plus négatif N que l'on peut stocker en complément à deux sur 10 bits ?
Quelle formule est logiquement équivalente à (p ∧ q) → r ? Cliquez dessus.
Combien des 16 lignes de la table de vérité rendent (c ∧ b) ↔ ((d ∧ a) ∨ d) vraie ? Appelez ce nombre N.
Un multiplexeur 4 vers 1 a ses entrées de sélection S₁ = A et S₀ = B, et ses entrées de données reliées à I₀ = 0, I₁ = 1, I₂ = 1, I₃ = 0. Pour combien des 8 combinaisons de A, B et C la sortie vaut-elle F = 1 ? Trouvez N.
Pour F(A, B, C, D) = Σm(6, 7, 9, 10, 13, 14, 15) + d(0, 3, 5, 11), où d marque les états indifférents, trouvez le nombre N d’implicants premiers essentiels.
Trouvez l’indicatrice d’Euler φ(209), le nombre d’entiers de 1 à 209 premiers avec 209.
Utilisez le carré répété pour trouver 2181 mod 32.
Quelle est la complexité temporelle du calcul du n-ième nombre de Fibonacci avec une table remplie de bas en haut ?
Pourquoi toute recherche par comparaisons dans un tableau trié nécessite-t-elle Ω(log n) comparaisons dans le pire cas ?
Dans une file circulaire stockée dans un tableau de capacité n, comment calcule-t-on la position suivant l'indice i ?
Les clés 5, 3, 8, 1 sont insérées dans cet ordre dans un tas binaire min vide stocké dans un tableau. Quel est le tableau final ?
Un graphe connexe a 10 sommets et 10 arêtes. Combien d’arêtes k faut-il retirer pour obtenir un arbre couvrant ?
L’algorithme de Dijkstra part de A. Cliquez sur le sommet qui est fixé (rendu définitif) au tour 3 ; A lui-même est le tour 1.
Quelle requête renvoie le nombre de commandes par client ?
Quel est un inconvénient connu de la décomposition des tables en BCNF par rapport à la 3NF ?
Combien d'adresses d'hôtes utilisables compte un réseau IPv4 /24 ?
Un pare-feu bloque tout l'ICMP. Les petites requêtes web fonctionnent, mais les gros téléchargements se bloquent sur certains chemins. Quelle est la cause probable ?
Un service a besoin de 336 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.176.225/29. Quel est le dernier nombre (quatrième octet) x de l'adresse de diffusion de son sous-réseau ?
Réponse: N = −17
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.
Les autres bits gardent leurs valeurs positives habituelles.
Réponse: N = −512
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: p → (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: N = 8
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 = 4
Multiplexeur : un multiplexeur 2ⁿ vers 1 transmet l’une de ses entrées de données à la sortie ; les lignes de sélection, lues comme un nombre binaire, choisissent laquelle. Pour un MUX 4 vers 1 avec sélections S₁S₀ = AB, F = A′B′·I₀ + A′B·I₁ + AB′·I₂ + AB·I₃. En reliant les entrées de données à 0, 1, C ou C′, le MUX produit n’importe quelle fonction de A, B et C, ce qui est une manière courante de réaliser une logique avec un seul circuit.
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: φ(209) = 180
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: 2181 mod 32 = 21
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: B · O(n)
Remplir la table de 0 à n demande une addition par entrée : le travail est linéaire au lieu d'exponentiel.
Réponse: A · Un arbre de décision à n issues possibles doit avoir une profondeur d'au moins log₂ n
Chaque comparaison divise au mieux par deux l'ensemble des possibilités restantes ; distinguer n positions nécessite donc au moins log₂ n comparaisons.
Réponse: B · (i + 1) mod n
L'opération modulo ramène l'indice n − 1 à 0, ce qui permet de réutiliser le tableau sans décaler les éléments.
Réponse: B · [1, 3, 8, 5]
Après 5, 3, 8, le tableau est [3, 5, 8] ; 1 va à l'indice 3, s'échange avec son parent 5 puis avec 3, ce qui donne [1, 3, 8, 5].
Réponse: k = 1
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: C
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 · 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: A · Certaines dépendances fonctionnelles peuvent ne plus être vérifiables au sein d'une seule table
Une décomposition BCNF sans perte existe toujours, mais elle peut ne pas préserver les dépendances ; la 3NF peut toujours être à la fois sans perte et préservatrice des dépendances.
Réponse: D · 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 découverte du MTU du chemin échoue car les messages « fragmentation nécessaire » sont bloqués
La PMTUD s'appuie sur des messages ICMP pour apprendre le MTU plus petit. S'ils sont supprimés, les gros paquets disparaissent sans bruit, créant une connexion « trou noir ».
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 = 231
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