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 −108 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 1011 0001 << 2. Quelle est la valeur R du résultat en décimal ?
Dans combien des 8 lignes de sa table de vérité ¬((p ↔ (p ∨ r)) ∧ (q ↔ (¬q ∧ ¬r))) est-elle vraie ? Appelez ce nombre N.
Le raisonnement de prémisses r → (q ∨ p); r et de conclusion q est invalide. Cliquez sur la ligne de la table de vérité qui est un contre-exemple.
Utilisez le tableau de Karnaugh pour trouver la forme somme de produits (SOP) minimale de F(A, B, C, D) = Σm(1, 3, 5, 7, 9, 10, 11, 12, 15). Combien de termes produits N a-t-elle ?
Une bascule JK déclenchée sur front montant part de Q = 0 et reçoit les entrées représentées sur 6 fronts montants d’horloge. Combien de fois N Q change-t-il d’état ?
Résolvez 77x ≡ 33 (mod 89). Donnez la solution x avec 0 < x < 89.
59 est premier. Utilisez le petit théorème de Fermat pour trouver 1540211 mod 59.
Quel algorithme trouve les plus courts chemins depuis une source dans un graphe dont les poids des arêtes sont positifs ou nuls ?
Quel algorithme trouve un arbre couvrant de poids minimal en ajoutant de façon répétée l'arête la moins coûteuse qui ne forme pas de cycle ?
Combien de nœuds possède un arbre binaire parfait de hauteur h, la hauteur étant comptée en arêtes ?
Quelle propriété maintient tout B-arbre parfaitement équilibré ?
Combien de circuits hamiltoniens différents H le graphe complet K8 a-t-il ? Les circuits qui ne diffèrent que par le sommet de départ ou le sens comptent comme un seul.
Utilisez l’algorithme de Dijkstra pour trouver la longueur d(D) du plus court chemin de A à D dans le graphe pondéré.
Que fait ROLLBACK TO SAVEPOINT s1 ?
Qu'exige la règle de la journalisation anticipée (write-ahead logging, WAL) ?
Quel est le but de la poignée de main en trois temps (three-way handshake) de TCP ?
Que fait la retransmission rapide (fast retransmit) de TCP ?
Le réseau 192.168.10.0/24 doit être divisé en au moins 16 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 ?
Un hôte a l'adresse 10.20.24.232/25. Quel est le dernier nombre (quatrième octet) x de l'adresse de diffusion de son sous-réseau ?
Réponse: U = 148
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.
Un décalage à gauche de 2 déplace chaque bit de 2 positions vers la gauche ; les bits qui sortent à l’extrémité gauche sont perdus et des zéros entrent à droite.
Réponse: N = 7
Tables de vérité : une formule à n variables distinctes a 2ⁿ lignes, une pour chaque combinaison de valeurs de vérité (1 = vrai, 0 = faux). Travaillez de l’intérieur vers l’extérieur et donnez à chaque sous-formule sa propre colonne. ¬a inverse la valeur ; a ∧ b vaut 1 seulement quand les deux valent 1 ; a ∨ b vaut 0 seulement quand les deux valent 0 ; a → b vaut 0 seulement quand a = 1 et b = 0 ; a ↔ b vaut 1 quand les deux côtés sont égaux.
Réponse: p = 1, q = 0, r = 1
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.
Un raisonnement de cette forme ressemble à une règle valide, mais une seule ligne suffit à montrer qu’il ne l’est pas.
Réponse: N = 5
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: N = 3
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 JK : 00 conserve, 01 remet à 0 (Q = 0), 10 met à 1 (Q = 1), 11 change d’état.
Réponse: x = 64
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: 1540211 mod 59 = 35
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 · L'algorithme de Dijkstra
L'algorithme de Dijkstra fonctionne avec des poids positifs ou nuls ; Bellman-Ford gère les poids négatifs ; Kruskal construit des arbres couvrants de poids minimal.
Réponse: B · L'algorithme de Kruskal
Kruskal trie les arêtes par poids et les ajoute si elles relient des composantes différentes ; Prim fait croître un seul arbre à partir d'un sommet de départ.
Réponse: B · 2h+1 − 1
La somme 1 + 2 + 4 + ... + 2h vaut 2h+1 − 1 ; par exemple, une hauteur de 2 donne 7 nœuds.
Réponse: D · Toutes les feuilles sont à la même profondeur
Les nœuds pleins se scindent vers le haut et l'arbre ne grandit que lorsque la racine se scinde, donc toutes les feuilles restent toujours au même niveau.
Réponse: H = 2520
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(D) = 20
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: C · Il annule les modifications effectuées après le point de sauvegarde s1, en gardant la transaction ouverte
Un point de sauvegarde marque un point à l'intérieur d'une transaction ; y revenir annule le travail ultérieur, tandis que les modifications antérieures restent en attente jusqu'au COMMIT.
Réponse: B · L'enregistrement de journal d'une modification doit atteindre le support stable avant la page de données modifiée
Écrire d'abord le journal permet au SGBD de refaire le travail validé et de défaire le travail non validé après une panne, ce qui garantit l'atomicité et la durabilité.
Réponse: B · Établir une connexion et synchroniser les numéros de séquence
La poignée de main établit une connexion et fixe les numéros de séquence initiaux des deux côtés avant l'envoi des données.
Réponse: A · 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: H = 14
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 = 255
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