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 −13 en complément à deux sur 8 bits. Lu comme un nombre non signé, quelle est la valeur U du motif ?
Positionnez les bits sur le résultat sur 8 bits de 0101 1111 << 1. Quelle est la valeur R du résultat en décimal ?
p → (p ∧ q) est-elle une tautologie, une contradiction ou une contingence ? Cliquez sur votre réponse.
Le raisonnement de prémisses q ∨ p; q 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) = Σm(0, 1, 3, 4, 6). Combien de termes produits N a-t-elle ?
Un compteur modulo 11 synchrone compte 0, 1, …, 10 puis revient à 0. Il part de 7. Quelle valeur Q (en décimal) affiche-t-il après 33 impulsions d’horloge ?
Trouvez l’inverse de 8 modulo 61 : le nombre x avec 0 < x < 61 et 8·x ≡ 1 (mod 61).
Résolvez 25x ≡ 5 (mod 30). Donnez la plus petite solution positive x.
Quel énoncé sur une fonction récursive sans cas de base atteignable est correct ?
Pourquoi la recherche dichotomique ne s'exécute-t-elle pas en O(log n) sur une liste simplement chaînée ?
Quelle est la complexité temporelle de la recherche d'une clé dans un arbre binaire de recherche équilibré ?
Un objet est stocké comme clé dans une table de hachage (hash map), puis un champ utilisé par sa fonction de hachage est modifié. Quel est le résultat probable ?
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 fait GRANT SELECT ON employees TO alice ?
Deux transactions lisent toutes deux stock = 10, retirent chacune 1 et écrivent le résultat, ce qui donne 9 au lieu de 8. De quelle anomalie s'agit-il ?
Quel protocole la commande « ping » utilise-t-elle ?
Que fait principalement BGP sur Internet ?
Un service a besoin de 690 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.115.43/30. Quel est le quatrième octet x de la dernière adresse d'hôte utilisable de son sous-réseau ?
Réponse: U = 243
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: R = 190
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.
Un décalage à gauche de 1 déplace chaque bit de 1 positions vers la gauche ; les bits qui sortent à l’extrémité gauche sont perdus et des zéros entrent à droite.
Réponse: contingence
É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: p = 1, q = 1
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: 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.
Chaque groupe est un rectangle de 2ᵏ cases ; les cases de bord sont voisines des cases du bord opposé.
Il existe un autre regroupement de même taille ; il a le même nombre de termes et de littéraux.
Réponse: Q = 7
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 11 impulsions ramènent le compteur au même état.
Réponse: 8−1 mod 61 = 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).
Chaque reste r s’écrit r ≡ t·8 (mod 61).
Réponse: x = 5
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 · Elle continue de s'appeler jusqu'au débordement de la pile d'appels
Sans cas de base, la récursion ne s'arrête jamais ; en pratique, la mémoire pour les cadres de pile s'épuise et le programme plante.
Réponse: D · Atteindre l'élément du milieu prend O(n) étapes, faute d'accès direct par indice
La recherche dichotomique nécessite un accès en O(1) au milieu ; sur une liste chaînée, s'y rendre coûte un temps linéaire, si bien que le total est O(n).
Réponse: A · 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 · La recherche de l'objet peut échouer car il se trouve dans le compartiment de son ancien hachage
L'emplacement de la clé a été choisi à partir de son ancien hachage ; avec un nouveau hachage, les recherches examinent le mauvais compartiment, c'est pourquoi les clés devraient être immuables.
Réponse: Circuit eulérien
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: d(F) = 16
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: B · Il autorise l'utilisatrice alice à lire la table employees
GRANT accorde un privilège sur un objet ; SELECT n'autorise que la lecture, tandis qu'INSERT, UPDATE et DELETE sont des privilèges distincts.
Réponse: D · Une mise à jour perdue (lost update)
Dans une mise à jour perdue, les deux transactions partent de la même ancienne valeur et la seconde écriture efface la première ; le verrouillage (SELECT ... FOR UPDATE) ou des mises à jour atomiques l'empêchent.
Réponse: B · ICMP
Ping envoie des requêtes ICMP echo et mesure le temps jusqu'au retour des réponses echo.
Réponse: D · Il échange des informations de routage entre systèmes autonomes
BGP est le protocole de routage inter-domaines ; les systèmes autonomes (AS) annoncent les préfixes joignables et choisissent les chemins selon des politiques.
Réponse: p = 22
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 = 42
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