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 1100 0000 stocke un entier signé en complément à deux. Quelle est sa valeur N en décimal ?
Une image non compressée fait 1280 × 720 pixels avec 32 bits par pixel. Quelle mémoire M occupe-t-elle, en Kio (1 Kio = 1024 octets) ?
Quelle formule est logiquement équivalente à (b ∧ c) → a ? Cliquez dessus.
Quel énoncé est équivalent à ¬∀x (P(x) ∨ Q(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, 1, 3, 6, 8, 10, 14) + d(4, 12), où d marque les états indifférents, trouvez le nombre N d’implicants premiers essentiels.
Trouvez l’indicatrice d’Euler φ(1805), le nombre d’entiers de 1 à 1805 premiers avec 1805.
Une clé RSA utilise les nombres premiers p = 29 et q = 43 et l’exposant public e = 5. Trouvez l’exposant privé d (0 < d < φ(n)).
Environ combien de comparaisons la recherche dichotomique nécessite-t-elle dans le pire cas sur un tableau trié de 1,000,000 d'éléments ?
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 ?
Qu'est-ce qui est vrai de la matrice d'adjacence d'un graphe non orienté ?
Un arbre de segments (segment tree) est généralement utilisé pour :
Un arbre a 3 sommets de degré 3, 4 sommets de degré 4, 2 sommets de degré 2, et tous ses autres sommets sont des feuilles (degré 1). Combien de feuilles L a-t-il ?
Combien de marches fermées de longueur 3 partent de A et y reviennent ? Une marche peut répéter des sommets et des arêtes. Appelez ce nombre N.
La table orders compte 5 lignes, chacune faisant référence à un client existant. La table customers compte 3 lignes. Combien de lignes un INNER JOIN sur customer_id renvoie-t-il ?
Que renvoie la requête suivante : SELECT name FROM students WHERE grade > (SELECT AVG(grade) FROM students) ?
Quelles propriétés de sécurité TLS apporte-t-il à HTTPS ?
Comment un réseau de diffusion de contenu (CDN) améliore-t-il principalement les performances web ?
Un service a besoin de 1728 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 10.20.26.79/25. Quel est le dernier nombre (quatrième octet) x de l'adresse de diffusion de son sous-réseau ?
Réponse: N = −64
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 = 3600 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: b → (c → a)
É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 (¬P(x) ∧ ¬Q(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 = 10, 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 = 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: φ(1805) = 1368
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: d = 941
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 · Environ 20
220 ≈ 1,048,576 : après environ 20 divisions par deux, il ne reste qu'un élément.
Réponse: D · 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 · Elle est symétrique par rapport à la diagonale principale
Dans un graphe non orienté, l'arête {u, v} signifie que M[u][v] et M[v][u] sont tous deux renseignés, donc la matrice est égale à sa transposée.
Réponse: D · Répondre à des requêtes sur intervalles (comme des sommes d'intervalles) et à des mises à jour en O(log n)
Un arbre de segments stocke des agrégats pour des intervalles et permet des requêtes sur intervalles et des mises à jour ponctuelles en temps O(log n).
Réponse: L = 13
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: N = 2
Degrés : le degré d’un sommet est le nombre d’arêtes qui y aboutissent. Chaque arête a deux extrémités, donc les degrés totalisent deux fois le nombre d’arêtes : Σ deg(v) = 2|E| (le lemme des poignées de main). Le nombre de sommets de degré impair est donc pair. Kn a n(n − 1)/2 arêtes, un graphe k-régulier à n sommets en a nk/2, et un arbre à n sommets a n − 1 arêtes.
Réponse: D · 5
Chaque commande trouve exactement un client correspondant ; la jointure renvoie donc une ligne par commande, soit 5 lignes.
Réponse: C · Les étudiants dont la note est supérieure à la note moyenne
La sous-requête scalaire calcule la moyenne, et la requête externe conserve les étudiants au-dessus de celle-ci.
Réponse: A · Confidentialité, intégrité et authentification du serveur
TLS chiffre le trafic, détecte les altérations et authentifie le serveur à l'aide de certificats (éventuellement le client aussi).
Réponse: A · Il sert du contenu en cache depuis des serveurs proches des utilisateurs
Les CDN placent des copies du contenu dans de nombreux points de périphérie et dirigent les utilisateurs, souvent via le DNS, vers un serveur proche. Cela réduit la latence et la charge du serveur d'origine.
Réponse: p = 21
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 = 127
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