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 1110 1111 stocke un entier signé en complément à deux. Quelle est sa valeur N en décimal ?
Une image non compressée fait 640 × 480 pixels avec 24 bits par pixel. Quelle mémoire M occupe-t-elle, en Kio (1 Kio = 1024 octets) ?
Quelle formule est logiquement équivalente à p → q ? 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.
Un multiplexeur 4 vers 1 a ses entrées de sélection S₁ = A et S₀ = B, et ses entrées de données reliées à I₀ = 0, I₁ = 1, I₂ = 1, I₃ = C′. Pour combien des 8 combinaisons de A, B et C la sortie vaut-elle F = 1 ? Trouvez N.
Pour F(A, B, C, D) = Σm(0, 2, 8, 11, 14) + d(9, 12, 13), où d marque les états indifférents, trouvez le nombre N d’implicants premiers essentiels.
Trouvez l’inverse de 37 modulo 91 : le nombre x avec 0 < x < 91 et 37·x ≡ 1 (mod 91).
Une clé RSA utilise les nombres premiers p = 19 et q = 31 et l’exposant public e = 13. Trouvez l’exposant privé d (0 < d < φ(n)).
Quel algorithme de tri est stable ?
Le tri par insertion s'exécute en O(n) sur une entrée triée. Cela contredit-il la borne inférieure Ω(n log n) des tris par comparaisons ?
Quelle quantité de mémoire une liste d'adjacence utilise-t-elle pour un graphe à V sommets et E arêtes ?
En quoi un arbre radix (trie compressé) améliore-t-il un trie simple ?
Le graphe connexe a-t-il un circuit eulérien, un chemin eulérien qui n’est pas un circuit, ou ni l’un ni l’autre ? Cliquez sur votre réponse.
Utilisez l’algorithme de Dijkstra pour trouver la longueur d(F) du plus court chemin de A à F dans le graphe pondéré.
Que renvoie SELECT COALESCE(phone, 'unknown') FROM customers pour un client dont le téléphone est NULL ?
Le verrouillage à deux phases (2PL) garantit :
Qu'est-ce qui identifie de façon unique une extrémité d'une connexion TCP sur Internet ?
Qu'apporte à lui seul l'échange de clés Diffie-Hellman, et quelle est sa faiblesse ?
Un sous-réseau utilise le masque 255.255.254.0. Combien d’adresses d’hôte utilisables H possède-t-il ?
Le réseau 192.168.175.0/24 est découpé en VLSM pour ces LAN : A: 12 hôtes, B: 6 hôtes, C: 28 hôtes, D: 38 hôtes, E: 30 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: N = −17
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: M = 900 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: ¬p ∨ 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).
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: N = 5
Multiplexeur : un multiplexeur 2ⁿ vers 1 transmet l’une de ses entrées de données à la sortie ; les lignes de sélection, lues comme un nombre binaire, choisissent laquelle. Pour un MUX 4 vers 1 avec sélections S₁S₀ = AB, F = A′B′·I₀ + A′B·I₁ + AB′·I₂ + AB·I₃. En reliant les entrées de données à 0, 1, C ou C′, le MUX produit n’importe quelle fonction de A, B et C, ce qui est une manière courante de réaliser une logique avec un seul circuit.
Réponse: N = 3
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: 37−1 mod 91 = 32
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·37 (mod 91).
Réponse: d = 457
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 · Tri fusion
Le tri fusion est stable si, en cas d'égalité, la fusion prend d'abord dans la moitié gauche. Le tri rapide en place, le tri par tas et le tri par sélection ne sont généralement pas stables.
Réponse: D · Non, la borne inférieure s'applique au pire cas sur toutes les entrées, pas à chaque entrée
La borne dit que tout tri par comparaisons nécessite environ n log n comparaisons sur une certaine entrée de taille n ; des entrées particulières peuvent être bien plus rapides.
Réponse: C · 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 · Il fusionne les chaînes de nœuds à enfant unique en une seule arête étiquetée par une chaîne
Fusionner les chemins sans ramification réduit le nombre de nœuds et la mémoire utilisée tout en conservant la recherche par préfixe.
Réponse: Chemin eulérien, pas de circuit
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.
Le chemin eulérien commence à un sommet impair et finit à l’autre.
Réponse: d(F) = 17
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 · 'unknown'
COALESCE examine ses arguments de gauche à droite et renvoie le premier qui n'est pas NULL, ici 'unknown'.
Réponse: B · Des ordonnancements sérialisables par conflits
Le 2PL garantit la sérialisabilité, mais les interblocages restent possibles et doivent être détectés ou évités.
Réponse: C · Une adresse IP associée à un numéro de port
Une connexion TCP est identifiée par l'adresse IP et le port source ainsi que l'adresse IP et le port de destination. Les ports distinguent les nombreuses applications d'un même hôte.
Réponse: A · Il établit un secret partagé sur un canal public, mais seul il est vulnérable à l'homme du milieu
Diffie-Hellman permet à deux parties de dériver le même secret, que les espions ne peuvent pas calculer. Un attaquant placé au milieu peut mener des échanges séparés avec chaque côté si les valeurs ne sont pas signées ou authentifiées autrement.
Réponse: H = 510
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 = 144
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.175.144/29.
ExamProblems · examproblems.com/courses/computer-science-fundamentals