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 −40 en complément à deux sur 8 bits. Lu comme un nombre non signé, quelle est la valeur U du motif ?
Quel est l'entier le plus négatif N que l'on peut stocker en complément à deux sur 16 bits ?
Vous voulez prouver (p ∧ r) → q par l’absurde. Quel énoncé supposez-vous au départ ? Cliquez dessus.
Quel énoncé est équivalent à ¬∀x ∃y R(x, y), la négation étant passée complètement à l’intérieur ? Cliquez dessus.
Utilisez le tableau de Karnaugh pour trouver la forme produit de sommes (POS) minimale de F(A, B, C, D) = Σm(0, 8, 9, 12, 15). Combien de termes somme (facteurs) N a-t-elle ?
Un compteur modulo 6 synchrone compte 0, 1, …, 5 puis revient à 0. Il part de 4. Quelle valeur Q (en décimal) affiche-t-il après 23 impulsions d’horloge ?
Trouvez le plus petit entier positif x tel que x ≡ 5 (mod 7) et x ≡ 6 (mod 12).
Chiffre le message m = 876 avec la clé publique RSA (n, e) = (899, 23). Trouvez le chiffré c.
Une fonction exécute une boucle de n itérations, puis, séparément, une autre boucle de n itérations. Quelle est sa complexité temporelle ?
L'algorithme de Strassen multiplie des matrices en utilisant 7 au lieu de 8 multiplications récursives de blocs de taille moitié. Quel est son temps d'exécution ?
Qu'est-ce qui est vrai de la matrice d'adjacence d'un graphe non orienté ?
Quelle garantie les règles des arbres rouge-noir donnent-elles sur la hauteur d'un arbre à n clés ?
Un arbre a 3 sommets de degré 4, 4 sommets de degré 2, et tous ses autres sommets sont des feuilles (degré 1). Combien de feuilles L a-t-il ?
L’algorithme de Prim construit un arbre couvrant minimal en partant du sommet B. Cliquez sur l’arête qu’il ajoute en numéro 2.
Qu'est-ce qu'un déclencheur (trigger) de base de données ?
Qu'est-ce qu'un index couvrant pour une requête ?
À quoi sert un contrôle de redondance cyclique (CRC) dans les trames Ethernet ?
Pourquoi un navigateur affiche-t-il un avertissement lorsqu'un site présente un certificat auto-signé ?
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.185.49/28. Quel est le dernier nombre (quatrième octet) x de l'adresse de diffusion de son sous-réseau ?
Réponse: U = 216
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: N = −32768
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) ∧ ¬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).
Si l’hypothèse mène à une contradiction, l’implication doit être vraie.
Réponse: ∃x ∀y ¬R(x, y)
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
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: Q = 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.
Toutes les 6 impulsions ramènent le compteur au même état.
Réponse: x = 54
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: c = 109
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: A · O(n)
n + n = 2n, et les facteurs constants sont supprimés : la fonction est donc O(n).
Réponse: A · Θ(nlog₂ 7), soit environ n2,81
Avec a = 7 et b = 2, nlog₂ 7 domine le travail d'addition en O(n²), ce qui donne environ n2,81.
Réponse: A · 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 · La hauteur est au plus 2 log2(n + 1)
Chaque chemin contient le même nombre de nœuds noirs et deux nœuds rouges ne peuvent pas être adjacents, donc le plus long chemin fait au plus le double du plus court, ce qui donne une hauteur en O(log n).
Réponse: L = 8
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: arête BD
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: D · Du code exécuté automatiquement lorsqu'un événement précis, comme INSERT, UPDATE ou DELETE, se produit sur une table
Les déclencheurs s'exécutent automatiquement avant ou après la modification de données, par exemple pour écrire un journal d'audit ou faire respecter une règle complexe.
Réponse: D · Un index qui contient toutes les colonnes nécessaires à la requête, si bien que la table elle-même n'a pas besoin d'être lue
Si toutes les colonnes référencées sont dans l'index, le SGBD peut faire un parcours d'index seul (index-only scan) sans aller chercher les lignes de la table, ce qui économise des E/S.
Réponse: B · À détecter les erreurs de transmission
L'émetteur calcule un CRC sur la trame ; le récepteur le recalcule et rejette la trame si les valeurs diffèrent. Le CRC détecte les erreurs mais ne les corrige pas.
Réponse: A · Aucune autorité de certification de confiance ne garantit que la clé appartient bien à ce site
Les navigateurs font confiance aux certificats signés, directement ou via une chaîne, par des AC présentes dans leur magasin de confiance. N'importe qui pourrait créer un certificat auto-signé, par exemple un homme du milieu.
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 = 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