Formulaires, étapes clés de la méthode pour chaque thème et 20 exercices, avec les corrigés complets à la fin.
Écris −110 comme motif de 8 bits en complément à deux. Lis ce motif comme un nombre binaire non signé : quelle est sa valeur U en décimal ?
Une image non compressée fait 800 × 600 pixels avec 16 bits par pixel. Quelle mémoire M occupe-t-elle, en Kio (1 Kio = 1024 octets) ?
Quelle formule est logiquement équivalente à ¬(p ∧ r) ? Cliquez dessus.
Le raisonnement de prémisses r → p; ¬r et de conclusion ¬p 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(0, 1, 2, 4, 7, 12). Combien de littéraux L contient-elle au total (une variable primée compte pour un littéral) ?
Trouvez la forme SOP minimale de F(A, B, C, D) = Σm(0, 3, 4, 8, 10, 15) + d(1, 2, 5, 11), où d marque les états indifférents. Combien de termes produits N a-t-elle ?
Résolvez 38x ≡ 20 (mod 61). Donnez la solution x avec 0 < x < 61.
37 est premier. Utilisez le petit théorème de Fermat pour trouver 1268183 mod 37.
Que signifie qu'un problème possède une sous-structure optimale ?
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 ?
Comment fonctionne l'extraction du minimum (extract-min) dans un tas binaire min ?
Que fait un arbre splay (splay tree) après chaque accès ?
Un graphe connexe a 11 sommets et 12 arêtes. Combien d’arêtes k faut-il retirer pour obtenir un arbre couvrant ?
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.
Qu'est-ce qu'une injection SQL ?
Après customers LEFT JOIN orders, pourquoi utiliser COUNT(o.id) plutôt que COUNT(*) pour compter les commandes par client ?
En quoi un pare-feu à états (stateful) diffère-t-il d'un simple filtre de paquets ?
Une application de terminal à distance paraît lente parce que les petits paquets de frappe sont retenus. Quel mécanisme TCP en est souvent responsable ?
Le réseau 192.168.10.0/24 doit être divisé en au moins 6 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.116.179/27. Quel est le dernier nombre (quatrième octet) x de l'adresse de diffusion de son sous-réseau ?
Réponse: U = 146
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: M = 937,5 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 ∨ ¬r
É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: p = 1, r = 0
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: L = 13
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 = 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.
Les plus grands groupes pouvant être formés de 1 et de X.
Il existe un autre regroupement de même taille ; il a le même nombre de termes et de littéraux.
Réponse: x = 23
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: 1268183 mod 37 = 34
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: B · Une solution optimale peut être construite à partir de solutions optimales de ses sous-problèmes
La sous-structure optimale est nécessaire pour que les algorithmes gloutons comme la programmation dynamique produisent des réponses correctes.
Réponse: C · 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: C · On déplace le dernier élément à la racine et on le fait descendre
Le dernier élément comble le trou à la racine et est échangé avec son plus petit enfant jusqu'à ce que la propriété de tas soit respectée, en O(log n).
Réponse: C · 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 = 2
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: F
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 · Une attaque dans laquelle une saisie utilisateur modifie la structure d'une requête SQL
Lorsque la saisie utilisateur est concaténée dans le SQL, des attaquants peuvent injecter des commandes. Les requêtes préparées avec paramètres séparent les données du code.
Réponse: A · COUNT(*) compte pour 1 la ligne remplie de NULL des clients sans commande
Pour ces clients, la jointure externe gauche donne une ligne dont les colonnes de commande valent NULL ; COUNT(o.id) ignore le NULL et indique correctement 0.
Réponse: C · Il suit les connexions et autorise les réponses appartenant à des sessions établies
Un pare-feu à états tient une table des connexions actives, de sorte que le trafic de retour est autorisé automatiquement. Un filtre sans état juge chaque paquet isolément.
Réponse: D · L'algorithme de Nagle
L'algorithme de Nagle attend pour regrouper les petits segments tant que les données précédentes ne sont pas acquittées. Cela économise de la bande passante mais ajoute du délai au trafic interactif.
Réponse: H = 30
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 = 191
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