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 1110 1100 stocke un entier signé en complément à deux. Quelle est sa valeur N en décimal ?
Quel est l'entier le plus négatif N que l'on peut stocker en complément à deux sur 12 bits ?
q ↔ ¬q est-elle une tautologie, une contradiction ou une contingence ? Cliquez sur votre réponse.
Les prémisses b → c; c → a; ¬a sont données. Quelle conclusion en découle ? Cliquez dessus.
Utilisez le tableau de Karnaugh pour trouver la forme somme de produits (SOP) minimale de F(A, B, C, D) = Σm(0, 3, 4, 9, 11). 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, 2, 4, 8, 10, 14) + d(1, 6), où d marque les états indifférents. Combien de termes produits N a-t-elle ?
Trouvez l’inverse de 53 modulo 63 : le nombre x avec 0 < x < 63 et 53·x ≡ 1 (mod 63).
Utilisez le carré répété pour trouver 9111 mod 16.
La récurrence T(n) = 2T(n/2) + O(n) a pour solution :
Pourquoi l'algorithme de Dijkstra peut-il donner des résultats faux lorsque certains poids d'arêtes sont négatifs ?
Qu'est-ce qui est vrai de la matrice d'adjacence d'un graphe non orienté ?
Quelle propriété maintient tout B-arbre parfaitement équilibré ?
Un graphe connexe a 20 sommets et 28 arêtes. Combien d’arêtes k faut-il retirer pour obtenir un arbre couvrant ?
Combien de marches de longueur 2 vont de B à C ? Une marche peut répéter des sommets et des arêtes. Appelez ce nombre N.
Pourquoi crée-t-on des index sur des colonnes ?
Quand la décomposition de R en R1 et R2 est-elle garantie sans perte ?
Quel drapeau TCP indique qu'un émetteur a fini d'envoyer des données ?
Quelle est l'unité de transmission maximale (MTU) de la charge utile Ethernet standard ?
Le réseau 192.168.10.0/24 doit être divisé en au moins 8 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 ?
Le réseau 192.168.32.0/24 est découpé en VLSM pour ces LAN : A: 6 hôtes, B: 13 hôtes, C: 19 hôtes, D: 48 hôtes, E: 15 hôtes. Les sous-réseaux sont attribués à partir de .0 en montant, le LAN ayant le plus d’hôtes en premier, chacun recevant le plus petit sous-réseau qui convient. Quel est le quatrième octet x de l’adresse réseau du LAN B ?
Réponse: N = −20
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: N = −2048
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: contradiction
É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: ¬b
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.
Réponse: L = 9
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 = 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: 53−1 mod 63 = 44
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·53 (mod 63).
Réponse: 9111 mod 16 = 9
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: C · O(n log n)
D'après le théorème maître (a = 2, b = 2, f(n) = n), T(n) = Θ(n log n).
Réponse: A · Un sommet est définitivement fixé lorsqu'il est extrait, mais une arête négative ultérieure pourrait encore lui donner un chemin plus court
L'étape gloutonne repose sur des poids positifs ou nuls pour que les distances extraites soient définitives ; on utilise Bellman-Ford quand les poids peuvent être négatifs.
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: B · Toutes les feuilles sont à la même profondeur
Les nœuds pleins se scindent vers le haut et l'arbre ne grandit que lorsque la racine se scinde, donc toutes les feuilles restent toujours au même niveau.
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 = 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: C · Pour accélérer les recherches et les jointures sur ces colonnes
Les index (souvent des arbres B) accélèrent les recherches, mais occupent de l'espace et ralentissent les insertions et mises à jour qui doivent les maintenir.
Réponse: C · Quand les attributs communs de R1 et R2 forment une super-clé de R1 ou de R2
Si les attributs partagés déterminent tous les attributs de R1 ou de R2, la jointure redonne exactement les lignes d'origine, sans tuples parasites.
Réponse: B · FIN
Chaque côté envoie FIN lorsqu'il n'a plus de données, et l'autre côté en accuse réception. SYN sert à ouvrir une connexion ; RST l'interrompt.
Réponse: C · 1500 octets
L'Ethernet standard transporte jusqu'à 1500 octets de charge utile ; les paquets IP plus grands doivent être fragmentés ou utiliser la découverte du MTU de chemin (Path MTU Discovery).
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 = 128
VLSM : chaque LAN reçoit le plus petit sous-réseau tel que 2ʰ − 2 ≥ son nombre d’hôtes, c’est-à-dire un préfixe 32 − h. Attribuer d’abord les plus grands sous-réseaux garde chaque bloc aligné sur un multiple de sa propre taille, donc les adresses réseau s’obtiennent en additionnant les tailles de bloc.
LAN B : 192.168.32.128/28.
ExamProblems · examproblems.com/courses/computer-science-fundamentals