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 −12 en complément à deux sur 8 bits. Lu comme un nombre non signé, quelle est la valeur U du motif ?
Une image non compressée fait 256 × 256 pixels avec 16 bits par pixel. Quelle mémoire M occupe-t-elle, en Kio (1 Kio = 1024 octets) ?
((r → p) ∧ ¬r) → ¬p est-elle une tautologie, une contradiction ou une contingence ? Cliquez sur votre réponse.
Quel énoncé est équivalent à ¬∀x ∀y (R(x, y) → R(y, x)), la négation étant passée complètement à l’intérieur ? Cliquez dessus.
Dans ce tableau de Karnaugh, exactement un 1 n’a aucun 1 voisin, donc il reste un groupe d’une seule case (un minterme complet de quatre littéraux) dans la forme SOP minimale. Les voisins de part et d’autre des bords du tableau comptent. Cliquez sur cette case.
Pour F(A, B, C, D) = Σm(0, 2, 3, 6, 7) + d(5, 8, 11), où d marque les états indifférents, trouvez le nombre N d’implicants premiers essentiels.
Trouvez l’inverse de 7 modulo 59 : le nombre x avec 0 < x < 59 et 7·x ≡ 1 (mod 59).
Chiffre le message m = 556 avec la clé publique RSA (n, e) = (943, 17). Trouvez le chiffré c.
Un algorithme glouton :
Pour quelle variante du problème du sac à dos la règle gloutonne « prendre les objets par ordre de valeur par unité de poids » donne-t-elle toujours une réponse optimale ?
Un trie (arbre de préfixes) est particulièrement efficace pour :
L'algorithme de Kahn pour le tri topologique retire répétitivement les sommets de degré entrant 0. Quelle structure contient ces sommets ?
Un graphe connexe a 8 sommets et 14 arêtes. Combien d’arêtes k faut-il retirer pour obtenir un arbre couvrant ?
Trouvez le poids total W d’un arbre couvrant minimal du graphe pondéré.
Quelle requête renvoie le nombre de villes différentes dans la table customers ?
Une table a un million de lignes et une colonne booléenne is_active vraie pour 95% d'entre elles. Pourquoi l'optimiseur pourrait-il ignorer un index sur is_active pour WHERE is_active = TRUE ?
Quel champ de l'en-tête IPv4 empêche les paquets de circuler indéfiniment dans une boucle de routage ?
La clé privée d'un serveur sera volée dans un an. Quelle propriété de TLS protège les sessions enregistrées aujourd'hui ?
Le réseau 192.168.16.0/24 est divisé en sous-réseaux /26, numérotés 1, 2, 3, … à partir de l’adresse la plus basse (le sous-réseau 1 commence à .0). Quel est le quatrième octet x de l’adresse de diffusion du sous-réseau 3 ?
Un hôte a l'adresse 10.20.137.69/27. Quel est le quatrième octet x de son adresse réseau ?
Réponse: U = 244
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: M = 128 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: contingence
É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).
Réponse: ∃x ∃y (R(x, y) ∧ ¬R(y, 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: AB = 00, CD = 01
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.
Un 1 ayant un 1 voisin peut rejoindre un groupe de deux ou plus.
Réponse: N = 1
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: 7−1 mod 59 = 17
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 59).
Réponse: c = 209
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: D · Fait le meilleur choix local à chaque étape
Les algorithmes gloutons sont rapides et optimaux pour certains problèmes (par ex. Dijkstra, codage de Huffman), mais pas en général (par ex. le rendu de monnaie avec certains systèmes de pièces).
Réponse: A · Le sac à dos fractionnaire, où les objets peuvent être fractionnés
Lorsque les objets peuvent être fractionnés, prendre d'abord le meilleur rapport est optimal ; dans le sac à dos 0/1, un objet à fort rapport peut bloquer une meilleure combinaison, d'où la nécessité de la programmation dynamique.
Réponse: C · Les recherches par préfixe, comme l'autocomplétion
Les tries stockent les chaînes caractère par caractère le long de chemins, donc les recherches et les requêtes par préfixe prennent un temps proportionnel à la longueur de la clé.
Réponse: B · Une file (ou toute collection) des sommets de degré entrant 0
Les sommets prêts sont conservés dans une file ; en retirer un diminue le degré entrant de ses voisins, et ceux qui atteignent 0 sont ajoutés, ce qui donne un temps en O(V + E).
Réponse: k = 7
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: W = 21
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 · SELECT COUNT(DISTINCT city) FROM customers
COUNT(DISTINCT city) compte les villes uniques non NULL ; un DISTINCT placé hors de COUNT ne supprime que les lignes en double du résultat.
Réponse: B · La plupart des lignes correspondent, donc un parcours complet de la table coûte moins cher que de nombreux accès par l'index
Un index aide quand il réduit la recherche à peu de lignes ; quand la plupart des lignes conviennent, les accès aléatoires par l'index coûtent plus cher qu'une lecture séquentielle de la table.
Réponse: C · 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 · La confidentialité persistante (forward secrecy) grâce à l'échange de clés Diffie-Hellman éphémère
Avec (EC)DHE éphémère, chaque clé de session est dérivée de valeurs temporaires qui sont ensuite effacées. La clé à long terme ne fait que signer l'échange ; la voler plus tard ne permet donc pas de déchiffrer l'ancien trafic.
Réponse: x = 191
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).
Réponse: x = 64
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