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 0111 0111 stocke un entier signé en complément à deux. Quelle est sa valeur N en décimal ?
Positionnez les bits sur le résultat sur 8 bits de 1111 0010 OR 1011 0100. Quelle est la valeur R du résultat en décimal ?
Quelle formule est logiquement équivalente à (q ∧ r) → p ? Cliquez dessus.
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.
Une bascule D 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 9 modulo 23 : le nombre x avec 0 < x < 23 et 9·x ≡ 1 (mod 23).
Chiffre le message m = 42 avec la clé publique RSA (n, e) = (235, 5). Trouvez le chiffré c.
Quelle est la solution de la récurrence T(n) = T(n − 1) + O(n) ?
Le tri topologique n'est possible que pour :
Quel est le coût de l'insertion d'un élément au milieu d'un tableau de n éléments ?
Que fait un arbre splay (splay tree) après chaque accès ?
Un graphe connexe a 10 sommets et 10 arêtes. Combien d’arêtes k faut-il retirer pour obtenir un arbre couvrant ?
Utilisez l’algorithme de Dijkstra pour trouver la longueur d(F) du plus court chemin de A à F dans le graphe pondéré.
Quelle propriété ACID signifie que des transactions concurrentes ne voient pas les modifications inachevées les unes des autres ?
Que calcule SELECT day, SUM(amount) OVER (ORDER BY day) FROM sales ?
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 ?
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 955 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.214.25/17. Quel est le troisième octet x de son adresse réseau ?
Réponse: N = 119
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: R = 246
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 donne 1 quand au moins un bit vaut 1.
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).
Les colonnes après la barre sont les options dans l’ordre affiché.
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 = 10
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 = 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.
Une bascule D copie D à chaque front montant : Q⁺ = D.
Réponse: 9−1 mod 23 = 18
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·9 (mod 23).
Réponse: c = 212
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 · O(n²)
Le travail totalise environ n² / 2 ; c'est la récurrence du tri par sélection ou du tri rapide avec le pire pivot.
Réponse: D · Les graphes orientés acycliques (DAG)
Un ordre topologique existe si et seulement si le graphe orienté ne contient pas de cycle ; on peut le trouver en O(V + E) avec DFS ou l'algorithme de Kahn.
Réponse: B · O(n), car les éléments suivants doivent être décalés
Tous les éléments situés après le point d'insertion se décalent d'une position vers la droite, ce qui prend un temps proportionnel à n.
Réponse: B · Il fait remonter le nœud accédé jusqu'à la racine par des rotations
Le splaying déplace le nœud accédé vers la racine par des rotations ; une opération isolée peut coûter O(n), mais le coût amorti est O(log n).
Réponse: k = 1
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: d(F) = 14
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.
Chaque ligne : le sommet fixé, sa distance définitive, et les voisins dont la distance s’améliore.
Réponse: D · L'isolation
L'isolation sépare les transactions concurrentes ; les niveaux d'isolation déterminent avec quelle rigueur elle est appliquée.
Réponse: B · Un total cumulé de amount, ordonné par day
Avec ORDER BY et sans cadre explicite, la fenêtre va de la première ligne jusqu'à la ligne courante (et ses ex æquo), ce qui donne une somme cumulée.
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: C · 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 = 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).
Réponse: x = 128
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