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 −46 en complément à deux sur 8 bits. Lu comme un nombre non signé, quelle est la valeur U du motif ?
Une image non compressée fait 1280 × 720 pixels avec 24 bits par pixel. Quelle mémoire M occupe-t-elle, en Kio (1 Kio = 1024 octets) ?
Vous voulez prouver ¬b → (c ∧ a) par contraposée. Quelle implication prouvez-vous à la place ? Cliquez dessus.
Les prémisses q → r; r → p sont données. Quelle conclusion en découle ? Cliquez dessus.
Utilisez le tableau de Karnaugh pour trouver la forme produit de sommes (POS) minimale de F(A, B, C, D) = Σm(0, 1, 3, 4, 6, 12, 13). Combien de termes somme (facteurs) N a-t-elle ?
Trouvez la forme SOP minimale de F(A, B, C, D) = Σm(4, 5, 6, 7, 8, 9, 11, 14) + d(0, 3, 15), où d marque les états indifférents. Combien de littéraux L contient-elle ?
Trouvez l’inverse de 4 modulo 27 : le nombre x avec 0 < x < 27 et 4·x ≡ 1 (mod 27).
Utilisez le carré répété pour trouver 763 mod 94.
La complexité temporelle de la version récursive naïve de Fibonacci (fib(n) = fib(n−1) + fib(n−2)) est :
Le tri topologique n'est possible que pour :
Pourquoi un tas binaire peut-il être stocké dans un tableau sans aucun pointeur ?
La structure union-find (ensembles disjoints) avec union par rang et compression de chemin a un coût amorti par opération de :
Combien de circuits hamiltoniens différents H le graphe complet K5 a-t-il ? Les circuits qui ne diffèrent que par le sommet de départ ou le sens comptent comme un seul.
Utilisez l’algorithme de Dijkstra pour trouver la longueur d(D) du plus court chemin de A à D dans le graphe pondéré.
Des étudiants peuvent suivre plusieurs cours et chaque cours a plusieurs étudiants. Comment modélise-t-on cela en tables ?
Que montre EXPLAIN (ou EXPLAIN ANALYZE dans PostgreSQL) pour une requête ?
Quel préfixe unique résume à la fois 192.168.0.0/24 et 192.168.1.0/24 ?
Les stations A et C atteignent toutes deux le point d'accès B mais ne s'entendent pas, si bien que leurs trames entrent en collision en B. Comment 802,11 aide-t-il ?
Un service a besoin de 1407 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.73.77/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 = 210
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: M = 2700 KiB
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: ¬(c ∧ a) → ¬¬b
É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).
La contraposée est équivalente à l’énoncé initial, donc la prouver prouve l’énoncé.
Réponse: q → p
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: 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é.
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.
Les plus grands groupes pouvant être formés de 1 et de X.
Réponse: 4−1 mod 27 = 7
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·4 (mod 27).
Réponse: 763 mod 94 = 53
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 · Exponentielle
L'arbre des appels croît à peu près comme φⁿ (environ 1,618ⁿ). La mémoïsation la réduit à O(n).
Réponse: A · Les graphes orientés acycliques (DAG)
Un ordre topologique existe si et seulement si le graphe orienté ne contient pas de cycle ; on peut le trouver en O(V + E) avec DFS ou l'algorithme de Kahn.
Réponse: B · C'est un arbre binaire complet, donc les positions suivent des formules d'indice simples
La complétude signifie qu'il n'y a pas de trous, donc les enfants de l'indice i sont toujours en 2i + 1 et 2i + 2.
Réponse: A · O(α(n)), l'inverse de la fonction d'Ackermann, pratiquement constant
Avec les deux optimisations, les opérations prennent un temps amorti O(α(n)) ; α(n) ≤ 4 pour tout n réaliste.
Réponse: H = 12
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(D) = 18
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: A · Avec une table d'association contenant des clés étrangères vers les étudiants et vers les cours
Une association plusieurs-à-plusieurs nécessite une table d'association (de jonction), par exemple enrolment(student_id, course_id), souvent avec une clé primaire composée.
Réponse: B · Le plan d'exécution choisi par l'optimiseur, comme les parcours et les méthodes de jointure
EXPLAIN affiche le plan (parcours d'index ou séquentiels, algorithmes de jointure, coûts estimés) ; EXPLAIN ANALYZE exécute aussi la requête et indique les temps réels.
Réponse: A · 192.168.0.0/23
0 et 1 partagent tous les bits du troisième octet sauf le dernier ; un préfixe raccourci d'un bit (/23) commençant à 192.168.0.0 couvre donc exactement les deux.
Réponse: D · Par des échanges RTS/CTS facultatifs : le CTS du point d'accès indique à toutes les stations proches d'attendre
Une station envoie un Request to Send ; le point d'accès répond par un Clear to Send que toutes les stations de sa portée entendent, de sorte que les stations cachées diffèrent leur émission pendant la durée réservée.
Réponse: p = 21
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 = 78
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