Révisions d'Informatique, Passage MPSI → MP

Révisions d'Informatique en prépa MPSI : 30 exercices corrigés avec rappels de cours, de la sup à la spé. Gratuit sur MonProf+.

Les 6 chapitres de la fiche

À maîtriser :

Distinguer type et valeur d'une variable (int, float, str, bool, list) et connaître les conversions implicites/explicites.
Écrire une fonction avec paramètres, valeur de retour explicite (return), et docstring d'une ligne.
Maîtriser les boucles for (parcours d'un itérable, range) et while (condition, risque de boucle infinie), et savoir choisir entre les deux.
Manipuler les chaînes de caractères par slicing (s[i:j:k]), concaténation, et parcours caractère par caractère.
Distinguer division entière (//), reste (%) et division flottante (/), et anticiper les erreurs d'indices.

5 exercices corrigés dans ce chapitre.

À maîtriser :

Parcourir une liste avec for élément in liste, ou avec for i in range(len(liste)) quand l'indice est nécessaire.
Calculer min, max, somme à la main par accumulation, sans les fonctions prédéfinies quand elles sont interdites.
Programmer une recherche linéaire et connaître son coût dans le pire cas, en O(n).
Programmer la recherche dichotomique itérative sur une liste triée, avec des bornes gauche/droite qui se resserrent.
Manipuler des matrices comme des listes de listes (accès m[i][j], parcours par lignes ou par colonnes).

5 exercices corrigés dans ce chapitre.

À maîtriser :

Identifier dans une fonction récursive le ou les cas de base (arrêt) et le cas récursif (appel sur une instance plus petite du problème).
Justifier la terminaison à l'aide d'un variant entier naturel qui décroît strictement à chaque appel récursif.
Écrire et dérouler à la main les exemples classiques : factorielle, puissance rapide, dichotomie récursive.
Comprendre la pile d'appels (empilement des appels en attente, dépilement au retour) et le risque de dépassement de pile.
Comparer le coût d'une version récursive naïve à celui d'une version optimisée (puissance rapide contre puissance naïve, mémoïsation contre récursion naïve).

5 exercices corrigés dans ce chapitre.

À maîtriser :

Écrire de mémoire le tri par sélection (recherche du minimum restant, échange) et le tri par insertion (insertion à la bonne place dans la partie déjà triée).
Compter le nombre de comparaisons ou d'échanges de chaque tri dans le pire cas, et les exprimer en O(n^2).
Distinguer les classes de complexité O(n), O(n^2), O(n log n), et savoir situer un algorithme donné dans l'une de ces classes.
Écrire l'invariant de boucle qui prouve la correction d'un tri, par exemple l[0:i] trié et contenant les i plus petits éléments.
Comparer un tri en place (espace O(1)) à un tri nécessitant un espace supplémentaire, comme le tri fusion.

5 exercices corrigés dans ce chapitre.

À maîtriser :

Tout entier naturel k de [0, 2^n - 1] s'écrit de façon unique en base 2 sur n bits : k = somme des b_i 2^i, obtenue par l'algorithme des divisions successives par 2 (bit de poids faible en premier).
Complément à deux sur n bits : un entier relatif x est représentable si et seulement si x appartient à [-2^(n-1), 2^(n-1) - 1] ; codage par x mod 2^n si x < 0, décodage par valeur non signée moins 2^n si le bit de poids fort vaut 1.
Un flottant est stocké en signe, mantisse et exposant (norme IEEE 754) ; l'epsilon machine (environ 2,22.10^-16 en double précision) mesure la plus petite différence relative représentable, d'où 0.1 + 0.2 != 0.3 en Python.
Comparer deux flottants exige une tolérance absolue et/ou relative, jamais l'égalité stricte == ; les erreurs d'arrondi s'accumulent sur une somme longue (sommation naïve), et des méthodes compensées (sommation de Kahan, math.fsum) limitent cette dérive.
Opérateurs Python sur les entiers : bin(n) donne l'écriture préfixée par '0b', int(s, 2) convertit une chaîne binaire en entier, n >> k réalise une division entière par 2^k, n << k une multiplication par 2^k, et n & 1 teste la parité de n par masquage bit à bit.

5 exercices corrigés dans ce chapitre.

À maîtriser :

Une pile respecte l'ordre LIFO (dernier entré, premier sorti) : empiler avec list.append(x), dépiler avec list.pop(), et tester la pile vide avec not pile.
Une file respecte l'ordre FIFO (premier entré, premier sorti) : utiliser collections.deque, enfiler avec append(x) et défiler avec popleft(), en évitant list.pop(0) qui coûte O(n) par décalage de tous les éléments.
Recherche dichotomique dans une liste triée : invariant « si x est présent dans l, il est dans l[gauche:droite+1] », variant droite - gauche strictement décroissant, complexité en O(log n).
Algorithme glouton : effectuer à chaque étape le choix localement optimal sans jamais revenir en arrière ; optimal pour le choix d'activités (tri par date de fin) mais pas pour tout système de rendu de monnaie.
Un dictionnaire Python (dict) offre un accès et une insertion en O(1) amorti par clé, utile pour la mémoïsation, le comptage d'occurrences ou la modélisation d'un système de pièces sous la forme {valeur: quantité}.

5 exercices corrigés dans ce chapitre.

30 exercices corrigés avec indice et rappel de cours, en accès libre.