Formulaires, étapes clés de la méthode pour chaque thème et 20 exercices, avec les corrigés complets à la fin.
Écris −111 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 ?
Positionnez les bits sur le résultat sur 8 bits de 0011 1100 >> 2. Quelle est la valeur R du résultat en décimal ?
Quelle formule est logiquement équivalente à p ↔ r ? Cliquez dessus.
Combien des 16 lignes de la table de vérité rendent ((r ∨ s) ∧ (¬s ∧ r)) → (¬p ∧ (p ∨ q)) vraie ? Appelez ce nombre N.
Utilisez le tableau de Karnaugh pour trouver la forme somme de produits (SOP) minimale de F(A, B, C, D) = Σm(1, 2, 4, 5, 6, 15). Combien de termes produits N a-t-elle ?
Trouvez la forme SOP minimale de F(A, B, C, D) = Σm(0, 7, 10, 12, 13) + d(2, 3, 4), où d marque les états indifférents. Combien de littéraux L contient-elle ?
Trouvez l’inverse de 15 modulo 43 : le nombre x avec 0 < x < 43 et 15·x ≡ 1 (mod 43).
Utilisez le carré répété pour trouver 5755 mod 62.
Quel algorithme de tri est stable ?
Quelle est la complexité temporelle de : pour i = 1 à n : pour (j = i ; j ≤ n ; j = j + i) faire un travail O(1) ?
Vous avez une référence vers un nœud au milieu d'une liste. Dans quelle liste pouvez-vous le supprimer en O(1) ?
Quel est le temps d'exécution d'un parcours en largeur sur un graphe à V sommets stocké sous forme de matrice d'adjacence ?
Un graphe connexe a 12 sommets et 14 arêtes. Combien d’arêtes k faut-il retirer pour obtenir un arbre couvrant ?
L’algorithme de Kruskal construit un arbre couvrant minimal. Cliquez sur l’arête qu’il ajoute en numéro 3 ; les arêtes sautées ne comptent pas.
Une vue (view) en SQL est :
Les scores sont 90, 90 et 80. Quelles valeurs RANK() OVER (ORDER BY score DESC) donne-t-il ?
À quelle couche OSI un commutateur (switch) fonctionne-t-il normalement ?
La phase de « slow start » du contrôle de congestion TCP :
Un sous-réseau utilise le masque 255.255.255.128. Combien d’adresses d’hôte utilisables H possède-t-il ?
Un routeur a des routes vers ces réseaux : 10.82.44.0/24, 10.82.45.0/24, 10.82.46.0/24, 10.82.47.0/24. Quelle est la plus grande longueur de préfixe p d’une route résumée unique qui les couvre tous ?
Réponse: U = 145
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: R = 15
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 à droite de 2 déplace chaque bit de 2 positions vers la droite ; les bits qui sortent à l’extrémité droite sont perdus et des zéros entrent à gauche.
Réponse: (p → r) ∧ (r → p)
É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: N = 13
Tables de vérité : une formule à n variables distinctes a 2ⁿ lignes, une pour chaque combinaison de valeurs de vérité (1 = vrai, 0 = faux). Travaillez de l’intérieur vers l’extérieur et donnez à chaque sous-formule sa propre colonne. ¬a inverse la valeur ; a ∧ b vaut 1 seulement quand les deux valent 1 ; a ∨ b vaut 0 seulement quand les deux valent 0 ; a → b vaut 0 seulement quand a = 1 et b = 0 ; a ↔ b vaut 1 quand les deux côtés sont égaux.
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.
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: L = 12
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: 15−1 mod 43 = 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·15 (mod 43).
Réponse: 5755 mod 62 = 57
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: D · Tri fusion
Le tri fusion est stable si, en cas d'égalité, la fusion prend d'abord dans la moitié gauche. Le tri rapide en place, le tri par tas et le tri par sélection ne sont généralement pas stables.
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: C · Une liste doublement chaînée
Un nœud doublement chaîné connaît son prédécesseur, on peut donc relier directement prev et next ; une liste simplement chaînée doit rechercher le prédécesseur.
Réponse: B · O(V²)
Chacun des V sommets parcourt une ligne de V cases, ce qui donne O(V²) ; avec des listes d'adjacence, le BFS est en O(V + E).
Réponse: k = 3
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: arête CE
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 · Une requête enregistrée qui se comporte comme une table virtuelle
Une vue enregistre une instruction SELECT ; l'interroger exécute la requête sous-jacente (les vues matérialisées stockent le résultat).
Réponse: B · 1, 1, 3
RANK donne le même rang aux lignes ex æquo et saute les numéros suivants (1, 1, 3) ; DENSE_RANK donnerait 1, 1, 2.
Réponse: D · Liaison de données (couche 2)
Un commutateur standard apprend les adresses MAC et transmet les trames en couche 2. Les commutateurs de couche 3 effectuent aussi du routage.
Réponse: C · Augmente la fenêtre de congestion de façon exponentielle jusqu'à un seuil ou une perte
Le slow start fait croître la fenêtre de congestion de façon exponentielle ; après le seuil, l'évitement de congestion la fait croître linéairement, et une perte la réduit.
Réponse: H = 126
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: p = 22
Résumé de routes : une route résumée a.b.c.0/p couvre tous les réseaux dont les p premiers bits correspondent. Écrivez en binaire l’octet qui diffère pour le premier et le dernier réseau ; le nombre de bits de tête communs, plus les bits des octets qui le précèdent, donne le plus long préfixe de résumé.
Route résumée : 10.82.44.0/22
ExamProblems · examproblems.com/courses/computer-science-fundamentals