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 1101 0111 stocke un entier signé en complément à deux. Quelle est sa valeur N en décimal ?
Un système doit donner à chacun de 4656 é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 ¬c → a par contraposée. Quelle implication prouvez-vous à la place ? Cliquez dessus.
Quel énoncé est équivalent à ¬∀x A(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(0, 2, 3, 4, 5, 6, 8, 10). Combien de termes produits N a-t-elle ?
Un registre à décalage de 4 bits Q₃Q₂Q₁Q₀ contient 1011. À chaque front d’horloge, les bits se décalent d’une place vers la droite (Q₃ → Q₂ → Q₁ → Q₀, Q₀ est perdu) et l’entrée série entre dans Q₃. L’entrée série vaut 1, 0, 1, 1, 1, 0, 1 aux fronts 7. Donnez l’état final Q = Q₃Q₂Q₁Q₀ sous forme de nombre décimal.
Résolvez 19x ≡ 13 (mod 21). Donnez la solution x avec 0 < x < 21.
19 est premier. Utilisez le petit théorème de Fermat pour trouver 2688768 mod 19.
Quelle est la complexité temporelle de l'algorithme standard de programmation dynamique pour la plus longue sous-séquence commune de chaînes de longueurs m et n ?
Comment se comparent n! et 2ⁿ pour n grand ?
Un nœud d'un arbre binaire de recherche possède un sous-arbre droit. Où se trouve son successeur dans l'ordre infixe ?
Pour qu'une table de hachage fonctionne correctement, quelle règle le hachage et l'égalité doivent-ils respecter ?
Un arbre a 4 sommets de degré 3, 3 sommets de degré 4, 4 sommets de degré 2, et tous ses autres sommets sont des feuilles (degré 1). Combien de feuilles L a-t-il ?
L’algorithme de Dijkstra part de A. Cliquez sur le sommet qui est fixé (rendu définitif) au tour 5 ; A lui-même est le tour 1.
Que renvoie SELECT COALESCE(phone, 'unknown') FROM customers pour un client dont le téléphone est NULL ?
Les scores sont 90, 90 et 80. Quelles valeurs RANK() OVER (ORDER BY score DESC) donne-t-il ?
Un routeur a des routes pour 10.0.0.0/8 et 10.1.0.0/16. Quelle route utilise-t-il pour un paquet à destination de 10.1.5.5 ?
Que fait la retransmission rapide (fast retransmit) de TCP ?
Le réseau 192.168.226.0/24 est divisé en sous-réseaux /29, 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 2 ?
Un hôte a l'adresse 10.20.41.161/29. Quel est le quatrième octet x de son adresse réseau ?
Réponse: N = −41
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: b = 13 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: ¬a → ¬¬c
É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 ¬A(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: Q = 11
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: x = 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).
Réponse: 2688768 mod 19 = 7
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(mn)
La table compte (m + 1)(n + 1) cases et chacune est calculée en O(1) à partir de ses voisines.
Réponse: A · n! croît plus vite que 2ⁿ
Pour n ≥ 4, n! dépasse 2ⁿ, et le rapport croît sans borne car chaque facteur supplémentaire de n! est supérieur à 2.
Réponse: B · Au nœud le plus à gauche de son sous-arbre droit
Toutes les clés plus grandes proches du nœud se trouvent dans son sous-arbre droit, et la plus petite d'entre elles est le nœud le plus à gauche de ce sous-arbre.
Réponse: C · Des clés égales doivent avoir des valeurs de hachage égales
Si deux clés égales avaient des hachages différents, elles seraient stockées dans des compartiments différents et les recherches échoueraient ; des clés différentes peuvent toutefois partager un hachage.
Réponse: L = 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.
Raccourci : L = 2 + Σ (d − 2) sur les sommets de degré d ≥ 3.
Réponse: D
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: B · 'unknown'
COALESCE examine ses arguments de gauche à droite et renvoie le premier qui n'est pas NULL, ici 'unknown'.
Réponse: B · 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 · 10.1.0.0/16, car c'est le préfixe correspondant le plus long
Le routage IP utilise la correspondance du plus long préfixe : parmi toutes les routes qui correspondent à la destination, celle qui a le masque le plus long est choisie.
Réponse: B · Elle renvoie un segment après trois ACK dupliqués, sans attendre l'expiration du délai
Trois ACK dupliqués indiquent fortement la perte d'un seul segment, que TCP retransmet donc aussitôt. La récupération est bien plus rapide qu'en attendant le temporisateur de retransmission.
Réponse: x = 15
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 = 160
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