Formulaires, étapes clés de la méthode pour chaque thème et 20 exercices, avec les corrigés complets à la fin.
Écris −42 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 ?
Une image non compressée fait 1920 × 1080 pixels avec 16 bits par pixel. Quelle mémoire M occupe-t-elle, en Kio (1 Kio = 1024 octets) ?
Vous voulez prouver ¬r → (p ∧ q) par contraposée. Quelle implication prouvez-vous à la place ? Cliquez dessus.
Quel énoncé est équivalent à ¬∃x (F(x) ∧ G(x)), la négation étant passée complètement à l’intérieur ? Cliquez dessus.
Simplifiez F = ABC′ + A′BC + ABC à sa forme somme de produits minimale. Combien de littéraux L contient l’expression simplifiée ?
Une bascule T déclenchée sur front montant part de Q = 0 et reçoit les entrées représentées sur 7 fronts montants d’horloge. Combien de fois N Q change-t-il d’état ?
Trouvez l’inverse de 27 modulo 31 : le nombre x avec 0 < x < 31 et 27·x ≡ 1 (mod 31).
Une clé RSA utilise les nombres premiers p = 7 et q = 23 et l’exposant public e = 5. Trouvez l’exposant privé d (0 < d < φ(n)).
Le parcours en largeur (BFS) sur un graphe non pondéré trouve :
Quel énoncé sur la sélection du k-ième plus petit élément d'un tableau non trié est correct ?
Quelle est la hauteur, dans le pire des cas, d'un arbre binaire de recherche à n nœuds si les clés sont insérées dans l'ordre trié ?
Un filtre de Bloom peut répondre à la question « cet élément appartient-il à l'ensemble ? » avec :
Un arbre a 3 sommets de degré 4, et tous ses autres sommets sont des feuilles (degré 1). Combien de feuilles L a-t-il ?
Combien de marches fermées de longueur 2 partent de E et y reviennent ? Une marche peut répéter des sommets et des arêtes. Appelez ce nombre N.
La deuxième forme normale (2NF) élimine :
Deux transactions lisent toutes deux stock = 10, retirent chacune 1 et écrivent le résultat, ce qui donne 9 au lieu de 8. De quelle anomalie s'agit-il ?
Comment TLS utilise-t-il généralement la cryptographie asymétrique et symétrique ?
Un attaquant sur un LAN envoie de fausses réponses ARP revendiquant l'adresse IP de la passerelle. Quel est le résultat probable ?
Un service a besoin de 134 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.139.20/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 = 214
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: M = 4050 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: ¬(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).
La contraposée est équivalente à l’énoncé initial, donc la prouver prouve l’énoncé.
Réponse: ∀x (F(x) → ¬G(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: L = 4
Algèbre de Boole : les règles qui simplifient les expressions sont X + X′ = 1 et X·X′ = 0, X + X = X, l’absorption X + X·Y = X, la règle de combinaison X·Y + X·Y′ = X, X + X′Y = X + Y et le théorème du consensus XY + X′Z + YZ = XY + X′Z. Les lois de De Morgan transforment (X·Y)′ en X′ + Y′ et (X + Y)′ en X′·Y′. Un tableau de Karnaugh applique ces règles graphiquement : chaque groupe de deux cases voisines est une utilisation de XY + XY′ = X.
Réponse: N = 6
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.
Une bascule T change d’état à chaque front montant quand T = 1 et conserve quand T = 0.
Réponse: 27−1 mod 31 = 23
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·27 (mod 31).
Réponse: d = 53
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 · Les plus courts chemins en nombre d'arêtes depuis le nœud de départ
BFS visite les nœuds par ordre de distance (en arêtes) depuis la source ; il trouve donc les plus courts chemins non pondérés en O(V + E).
Réponse: C · Quickselect s'exécute en O(n) en espérance, et la médiane des médianes garantit O(n) dans le pire cas
Le travail espéré de quickselect vaut n + n/2 + n/4 + ... = O(n) avec des pivots aléatoires ; choisir le pivot comme médiane des médianes rend le pire cas linéaire.
Réponse: D · n (il devient une liste chaînée)
Des insertions triées créent un arbre dégénéré de hauteur n, ce qui rend les recherches en O(n). Les arbres équilibrés évitent ce problème.
Réponse: B · Des faux positifs possibles mais aucun faux négatif
Si l'un des bits d'un élément vaut 0, il est assurément absent ; si tous valent 1, il est probablement présent. Les filtres de Bloom sacrifient la précision au profit d'une très faible consommation de mémoire.
Réponse: L = 8
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.
Raccourci : L = 2 + Σ (d − 2) sur les sommets de degré d ≥ 3.
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: D · Les dépendances partielles des colonnes non clés vis-à-vis d'une partie d'une clé composée
La 2NF exige la 1NF et que chaque attribut non clé dépende de la clé entière, et pas seulement d'une partie.
Réponse: C · Une mise à jour perdue (lost update)
Dans une mise à jour perdue, les deux transactions partent de la même ancienne valeur et la seconde écriture efface la première ; le verrouillage (SELECT ... FOR UPDATE) ou des mises à jour atomiques l'empêchent.
Réponse: C · 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: A · Les victimes envoient à l'attaquant le trafic destiné à la passerelle, ce qui permet une attaque de l'homme du milieu
L'usurpation ARP empoisonne les caches ARP des hôtes avec l'adresse MAC de l'attaquant pour l'IP de la passerelle. L'attaquant peut alors lire, modifier ou supprimer le trafic ; l'inspection ARP dynamique aide à l'empêcher.
Réponse: p = 24
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 = 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).
ExamProblems · examproblems.com/courses/computer-science-fundamentals