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 −67 en complément à deux sur 8 bits. Lu comme un nombre non signé, quelle est la valeur U du motif ?
Positionnez les bits sur le résultat sur 8 bits de 0110 0101 XOR 1010 0001. Quelle est la valeur R du résultat en décimal ?
Vous voulez prouver ¬q → (p ∨ r) par contraposée. Quelle implication prouvez-vous à la place ? Cliquez dessus.
Quel énoncé est équivalent à ¬∀x F(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, D) = Σm(2, 7, 8, 9, 13). Combien de termes produits N a-t-elle ?
Un compteur modulo 100 est construit avec le nombre minimal de bascules. Combien des états possibles U ne sont jamais utilisés ?
Trouvez l’inverse de 22 modulo 29 : le nombre x avec 0 < x < 29 et 22·x ≡ 1 (mod 29).
Une clé RSA utilise les nombres premiers p = 23 et q = 37 et l’exposant public e = 7. Trouvez l’exposant privé d (0 < d < φ(n)).
Quel est le temps d'exécution du tri par base LSD sur n entiers de d chiffres en base k ?
Prendre les deux extrémités de chaque arête d'un couplage maximal donne une couverture par sommets. Quelle est la qualité de cette couverture ?
Quelle quantité de mémoire une liste d'adjacence utilise-t-elle pour un graphe à V sommets et E arêtes ?
Un arbre de segments (segment tree) est généralement utilisé pour :
Combien de circuits hamiltoniens différents H le graphe complet K5 a-t-il ? Les circuits qui ne diffèrent que par le sommet de départ ou le sens comptent comme un seul.
L’algorithme de Kruskal construit un arbre couvrant minimal. Cliquez sur l’arête qu’il ajoute en numéro 4 ; les arêtes sautées ne comptent pas.
Qu'apporte une expression de table commune (WITH name AS (...)) ?
Les scores sont 90, 90 et 80. Quelles valeurs RANK() OVER (ORDER BY score DESC) donne-t-il ?
Quel champ de l'en-tête IPv4 empêche les paquets de circuler indéfiniment dans une boucle de routage ?
Quelle est l'unité de transmission maximale (MTU) de la charge utile Ethernet standard ?
Le réseau 192.168.10.0/24 doit être divisé en au moins 20 sous-réseaux égaux. Si tu empruntes le moins de bits possible, combien d'hôtes utilisables H chaque sous-réseau a-t-il ?
Le réseau 192.168.186.0/24 est découpé en VLSM pour ces LAN : A: 28 hôtes, B: 9 hôtes, C: 52 hôtes, D: 58 hôtes. Les sous-réseaux sont attribués à partir de .0 en montant, le LAN ayant le plus d’hôtes en premier, chacun recevant le plus petit sous-réseau qui convient. Quel est le quatrième octet x de l’adresse réseau du LAN B ?
Réponse: U = 189
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: R = 196
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.
OU exclusif (XOR) donne 1 quand les deux bits diffèrent.
Réponse: ¬(p ∨ r) → ¬¬q
É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)
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 = 4
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: U = 28
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.
Réponse: 22−1 mod 29 = 4
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·22 (mod 29).
Réponse: d = 679
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: C · O(d(n + k))
Chacune des d passes est un tri par comptage coûtant O(n + k) ; pour d et k fixés, le total est donc linéaire en n.
Réponse: D · Au plus deux fois la taille d'une couverture par sommets minimale
Les arêtes du couplage n'ont aucun sommet en commun : l'optimum nécessite donc au moins un sommet par arête, tandis que cette méthode en prend deux, d'où une 2-approximation.
Réponse: B · O(V + E)
Chaque sommet a une liste et chaque arête apparaît une fois (orienté) ou deux fois (non orienté), ce qui donne O(V + E).
Réponse: A · Répondre à des requêtes sur intervalles (comme des sommes d'intervalles) et à des mises à jour en O(log n)
Un arbre de segments stocke des agrégats pour des intervalles et permet des requêtes sur intervalles et des mises à jour ponctuelles en temps O(log n).
Réponse: H = 12
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 BE
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: A · Un résultat temporaire nommé, utilisable au sein d'une seule instruction
Une CTE donne un nom à une sous-requête, ce qui rend les requêtes complexes plus lisibles, et elle peut être référencée plusieurs fois dans la même instruction.
Réponse: C · 1, 1, 3
RANK donne le même rang aux lignes ex æquo et saute les numéros suivants (1, 1, 3) ; DENSE_RANK donnerait 1, 1, 2.
Réponse: D · La durée de vie (TTL)
Chaque routeur décrémente le TTL ; à zéro, le paquet est détruit et un message ICMP Time Exceeded est généralement envoyé. IPv6 l'appelle hop limit.
Réponse: C · 1500 octets
L'Ethernet standard transporte jusqu'à 1500 octets de charge utile ; les paquets IP plus grands doivent être fragmentés ou utiliser la découverte du MTU de chemin (Path MTU Discovery).
Réponse: H = 6
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 = 160
VLSM : chaque LAN reçoit le plus petit sous-réseau tel que 2ʰ − 2 ≥ son nombre d’hôtes, c’est-à-dire un préfixe 32 − h. Attribuer d’abord les plus grands sous-réseaux garde chaque bloc aligné sur un multiple de sa propre taille, donc les adresses réseau s’obtiennent en additionnant les tailles de bloc.
LAN B : 192.168.186.160/28.
ExamProblems · examproblems.com/courses/computer-science-fundamentals