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 1011 0100 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 1100 1011 AND 1001 1000. Quelle est la valeur R du résultat en décimal ?
(p → q) ∨ (q → p) est-elle une tautologie, une contradiction ou une contingence ? Cliquez sur votre réponse.
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.
Utilisez le tableau de Karnaugh pour trouver la forme somme de produits (SOP) minimale de F(A, B, C) = Σm(0, 3, 4, 6). Combien de littéraux L contient-elle au total (une variable primée compte pour un littéral) ?
Un compteur modulo 50 doit parcourir 50 états différents. Quel est le nombre minimal de bascules n dont il a besoin ?
Trouvez l’inverse de 83 modulo 97 : le nombre x avec 0 < x < 97 et 83·x ≡ 1 (mod 97).
Une clé RSA utilise p = 17, q = 41 et e = 13. Déchiffrez le chiffré c = 128 : trouvez le message m.
Quelle est la complexité temporelle de : pour i = 1 à n : (j = 1 ; tant que j < n : j = j × 2) ?
Quelle est la complexité temporelle de : pour i = 1 à n : pour (j = i ; j ≤ n ; j = j + i) faire un travail O(1) ?
Quelle est la complexité temporelle de la recherche d'une clé dans un arbre binaire de recherche équilibré ?
Quelle structure permet de calculer le maximum de chaque fenêtre de taille k dans un tableau en O(n) au total ?
Un graphe connexe a 12 sommets et 20 arêtes. Combien d’arêtes k faut-il retirer pour obtenir un arbre couvrant ?
Combien de marches de longueur 3 vont de D à F ? Une marche peut répéter des sommets et des arêtes. Appelez ce nombre N.
Qu'est-ce qu'une injection SQL ?
Que renvoie la requête suivante : SELECT name FROM students WHERE grade > (SELECT AVG(grade) FROM students) ?
Quel hôte se trouve dans le même sous-réseau /16 que 10.1.2.3 ?
Quel mécanisme empêche les boucles de diffusion dans un réseau avec des liens redondants entre commutateurs ?
Le réseau 192.168.62.0/24 est divisé en sous-réseaux /29, numérotés 1, 2, 3, … à partir de l’adresse la plus basse (le sous-réseau 1 commence à .0). Quel est le quatrième octet x de l’adresse réseau du sous-réseau 7 ?
Un hôte a l'adresse 10.20.215.62/27. Quel est le dernier nombre (quatrième octet) x de l'adresse de diffusion de son sous-réseau ?
Réponse: N = −76
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 = 136
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.
ET donne 1 seulement quand les deux bits valent 1.
Réponse: tautologie
É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).
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: L = 7
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 = 6
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.
Réponse: 83−1 mod 97 = 90
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·83 (mod 97).
Réponse: m = 144
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 · O(n log n)
La boucle intérieure s'exécute environ log₂ n fois pour chacune des n itérations extérieures, soit O(n log n).
Réponse: C · O(n log n)
Le total vaut n / 1 + n / 2 + ... + n / n = n × Hn, et le nombre harmonique Hn est Θ(log n).
Réponse: D · O(log n)
Un arbre équilibré a une hauteur d'environ log₂ n, donc une recherche suit un seul chemin de la racine à une feuille.
Réponse: D · Un deque contenant des indices par ordre décroissant de valeur
L'avant du deque est toujours le maximum de la fenêtre ; chaque indice entre et sort du deque une seule fois, donc le travail est linéaire.
Réponse: k = 9
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: N = 3
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: A · 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: 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: B · 10.1.200.5
Avec /16, les 16 premiers bits (10,1) forment la partie réseau. Seul 10.1.200.5 les partage ; il est donc sur 10.1.0.0/16.
Réponse: D · Spanning Tree Protocol
STP élit un pont racine (root bridge) et bloque les chemins redondants, puis les débloque si un lien actif tombe en panne.
Réponse: x = 48
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 = 63
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