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 −24 en complément à deux sur 8 bits. Lu comme un nombre non signé, quelle est la valeur U du motif ?
Un système doit donner à chacun de 2846 éléments son propre code binaire, tous de même longueur. Quel est le plus petit nombre de bits b nécessaire ?
Vous voulez prouver ¬q → (r ∧ p) par l’absurde. Quel énoncé supposez-vous au départ ? Cliquez dessus.
Le raisonnement de prémisses q ∨ r; q et de conclusion ¬r est invalide. Cliquez sur la ligne de la table de vérité qui est un contre-exemple.
Utilisez le tableau de Karnaugh pour trouver la forme produit de sommes (POS) minimale de F(A, B, C, D) = Σm(1, 3, 5, 7, 8, 9, 11, 13, 15). Combien de termes somme (facteurs) N a-t-elle ?
Un compteur binaire croissant de 3 bits part de 1 (décimal, Q = 001). Quelle valeur Q (en décimal) affiche-t-il après 11 impulsions d’horloge ?
Trouvez l’inverse de 7 modulo 31 : le nombre x avec 0 < x < 31 et 7·x ≡ 1 (mod 31).
Une clé RSA utilise p = 37, q = 47 et e = 13. Déchiffrez le chiffré c = 433 : trouvez le message m.
Que mesure l'analyse amortie ?
Quel énoncé sur la notation petit o est correct ?
Qu'est-ce qui est vrai de la matrice d'adjacence d'un graphe non orienté ?
Un tableau dynamique double de taille lorsqu'il est plein. Pourquoi de nombreuses implémentations ne le réduisent-elles que lorsqu'il est rempli au quart, et non à moitié ?
Combien de circuits hamiltoniens différents H le graphe complet K4 a-t-il ? Les circuits qui ne diffèrent que par le sommet de départ ou le sens comptent comme un seul.
Combien de marches de longueur 3 vont de C à D ? Une marche peut répéter des sommets et des arêtes. Appelez ce nombre N.
Pourquoi crée-t-on des index sur des colonnes ?
Quelle fonctionnalité SQL convient le mieux pour trouver tous les employés sous un responsable dans un organigramme de profondeur inconnue ?
Comment TLS utilise-t-il généralement la cryptographie asymétrique et symétrique ?
Après des collisions répétées, les stations Ethernet classiques choisissent leur temps d'attente dans un intervalle qui double à chaque fois. Pourquoi ?
Un service a besoin de 1228 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 172.20.17.64/22. Quel est le troisième octet x de l’adresse de diffusion de son sous-réseau ?
Réponse: U = 232
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: b = 12 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: ¬q ∧ ¬(r ∧ 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).
Si l’hypothèse mène à une contradiction, l’implication doit être vraie.
Réponse: q = 1, r = 1
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: 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: Q = 4
Bascules et compteurs : une bascule ne change qu’au front actif de l’horloge. D copie son entrée (Q⁺ = D) ; T change d’état quand T = 1 ; JK conserve pour 00, remet à 0 pour 01, met à 1 pour 10 et change d’état pour 11. Un compteur binaire de n bits a 2ⁿ états et compte modulo 2ⁿ ; un compteur modulo N va de 0, 1, …, N − 1 puis revient à 0, et exige le plus petit n tel que 2ⁿ ≥ N bascules. Chaque étage d’un compteur asynchrone divise la fréquence par deux, donc la dernière sortie d’un compteur modulo N tourne à fclk/N. Un compteur Johnson de n bascules a 2n états, un compteur en anneau n.
Toutes les 8 impulsions ramènent le compteur au même état.
Réponse: 7−1 mod 31 = 9
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·7 (mod 31).
Réponse: m = 211
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 · Le coût moyen par opération sur une suite d'opérations de pire cas
L'analyse amortie répartit le coût des opérations rares et coûteuses sur de nombreuses opérations bon marché, ce qui donne une moyenne garantie pour toute suite.
Réponse: D · n = o(n²), mais n n'est pas o(n)
f = o(g) signifie que f(n) / g(n) tend vers 0 ; n / n² tend vers 0, mais n / n = 1 non.
Réponse: B · 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: B · Pour éviter des redimensionnements répétés lorsque des push et des pop alternent près de la limite
Réduire à la moitié pourrait déclencher un redimensionnement à chaque opération d'une telle séquence ; l'écart entre 1/4 et plein maintient le coût amorti en O(1).
Réponse: H = 3
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 = 2
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: B · Pour accélérer les recherches et les jointures sur ces colonnes
Les index (souvent des arbres B) accélèrent les recherches, mais occupent de l'espace et ralentissent les insertions et mises à jour qui doivent les maintenir.
Réponse: D · Une expression de table commune récursive (WITH RECURSIVE)
Une CTE récursive part d'une requête d'ancrage et joint de façon répétée le résultat précédent à la table ; elle gère donc des hiérarchies de toute profondeur.
Réponse: D · Les méthodes asymétriques servent à convenir des clés et à authentifier ; les chiffrements symétriques chiffrent les données
Les méthodes à clé publique et les certificats établissent un secret partagé et prouvent l'identité. Des chiffrements symétriques rapides comme AES protègent ensuite l'essentiel des données.
Réponse: B · Pour réduire le risque d'une nouvelle collision lorsque de nombreuses stations sont en concurrence
Chaque nouvelle collision suggère davantage de concurrence ; l'intervalle aléatoire s'agrandit donc et les stations ont plus de chances de choisir des créneaux différents. Le mécanisme s'adapte à la charge sans contrôle central.
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 = 19
IPv4 subnetting: an address has 32 bits. The prefix /p says how many leading bits identify the network; the remaining 32 − p bits number the hosts. A subnet has 2³²⁻ᵖ addresses, but the first (network address) and last (broadcast address) cannot be given to hosts, so 2³²⁻ᵖ − 2 hosts fit. Exceptions: a /31 (point-to-point link, RFC 3021) uses both of its 2 addresses for hosts, and a /32 is one single address (a single host or a loopback).
ExamProblems · examproblems.com/courses/computer-science-fundamentals