💻 28 chapitres publiés
Fiches Informatique MPSI
Un parcours de révision par chapitre : commence par les fondamentaux, puis consolide les méthodes et démonstrations avant ton prochain DS ou ta prochaine colle.
Dernière mise à jour du parcours : 2026-08-02
Chapitres à réviser
Étape 1
Recherche par dichotomie
La recherche dichotomique dans un tableau trié, expliquée ligne par ligne : code Python commenté, exécution pas à pas, preuve de terminaison et de correction (variant \(d-g\), invariant de boucle), version récursive et complexité \(O(\log n)\).
Réviser ce chapitre →
Étape 2
Variables, types et affectations
Les briques de base de Python pour bien démarrer la prépa : affectation, types int/float/bool/str, conversions, opérateurs (/ // %), f-strings — avec les pièges classiques et deux exercices corrigés.
Réviser ce chapitre →
Étape 3
Conditions et booléens
Faire choisir un programme : booléens, comparaisons, if / elif / else, rôle de l'indentation, et combinaison de conditions avec and / or / not — avec pièges et exercices corrigés.
Réviser ce chapitre →
Étape 4
Boucles for et while
Répéter une action : boucle for avec range, boucle while qui termine, et le motif de l'accumulateur (somme, compteur) — avec table de trace, pièges et exercices corrigés.
Réviser ce chapitre →
Étape 5
Fonctions : paramètres et valeurs de retour
Définir et appeler une fonction, comprendre paramètres et valeur de retour, et surtout ne jamais confondre return (renvoie) et print (affiche) — avec pièges et exercices corrigés.
Réviser ce chapitre →
Étape 6
Listes et chaînes de caractères
Créer, indexer, parcourir et découper des listes et des chaînes ; comprendre qu'une liste est modifiable et une chaîne non — avec les pièges d'indices et deux exercices corrigés.
Réviser ce chapitre →
Étape 7
Manipuler les listes
Créer et modifier une liste, ajouter et retirer des éléments, trier avec sort et sorted, découper au slicing et découvrir les compréhensions — avec le piège de l'alias et deux exercices corrigés.
Réviser ce chapitre →
Étape 8
Chaînes de caractères
Indexer, découper et parcourir une chaîne, utiliser les méthodes essentielles (upper, count, replace, split, join) et comprendre qu'une chaîne est immuable — avec le test du palindrome et deux exercices corrigés.
Réviser ce chapitre →
Étape 9
Lire, tester et corriger un programme
Dérouler un programme à la main, reconnaître les patrons max / min / comptage / recherche, et tester un code sur ses cas limites — avec le piège du maximum initialisé à 0 et deux exercices corrigés.
Réviser ce chapitre →
Étape 10
Patrons d'algorithmes classiques
Écrire de tête les algorithmes classiques sur une liste — somme, moyenne, maximum, minimum, comptage, recherche — grâce au motif de l'accumulateur, avec le piège du maximum initialisé à zéro et deux exercices corrigés.
Réviser ce chapitre →
Étape 11
Récursivité
La récursivité pas à pas : cas de base et cas récursif, pile d'appels déroulée (descente puis remontée), preuve de terminaison par le variant, et le piège du coût exponentiel de Fibonacci — avec trois exercices corrigés.
Réviser ce chapitre →
Étape 12
Correction et terminaison d'un programme
Prouver un programme, pas seulement le tester : préconditions/postconditions, assertions, invariant (correction) et variant (terminaison), avec une preuve complète déroulée et trois exercices corrigés.
Réviser ce chapitre →
Étape 13
Piles et files
Piles (LIFO) et files (FIFO) : empiler/dépiler, enfiler/défiler, implémentation en liste Python et leur coût (le piège de pop(0) en O(n)), avec l'application phare du parenthésage et trois exercices corrigés.
Réviser ce chapitre →
Étape 14
Dictionnaires
Le type dict pas à pas : créer, accéder (d[k], get, KeyError), modifier, parcourir (keys/values/items), le réflexe O(1) contre O(n) d'une liste, et l'algorithme reine du comptage d'occurrences — avec trois exercices corrigés (élément le plus fréquent, anagrammes).
Réviser ce chapitre →
Étape 15
Complexité temporelle
Lire la complexité d'un code à l'œil : la notation grand-O, la table des ordres de grandeur, meilleur cas contre pire cas sur la recherche séquentielle, et la méthode boucle→O(n) / imbriquée→O(n²) / division par 2→O(log n) — avec la preuve du coût logarithmique de la dichotomie et trois exercices corrigés.
Réviser ce chapitre →
Étape 16
Tri par insertion et par sélection
Les deux tris quadratiques du programme, tracés à la main sur [5, 2, 4, 1] : sélection (toujours n(n-1)/2 comparaisons) contre insertion (rapide sur une liste presque triée), leurs invariants, les notions de tri en place et stable, et l'ouverture vers le tri fusion — avec trois exercices corrigés.
Réviser ce chapitre →
Étape 17
Graphes : vocabulaire et représentations
Le socle des graphes avant les parcours : tout le vocabulaire (sommet, arête vs arc, degré, chemin, cycle, connexité), les deux représentations codées et décryptées (listes d'adjacence et matrice d'adjacence), leurs coûts comparés, et le lemme des poignées de main démontré — avec trois exercices corrigés.
Réviser ce chapitre →
Étape 18
Parcours de graphes : BFS et DFS
BFS et DFS, le même squelette à une structure près : la file (largeur) contre la pile ou la récursion (profondeur), tracés pas à pas sur un graphe où les deux ordres diffèrent, le plus court chemin « gratuit » du BFS démontré, et les applications (connexité, accessibilité) — avec trois exercices corrigés.
Réviser ce chapitre →
Étape 19
Plus court chemin : Dijkstra
Le plus court chemin pondéré expliqué pas à pas : distances provisoires, sommet finalisé, relâchement d'arête, la boucle de Dijkstra codée et tracée sur un graphe concret, la preuve de l'optimalité de la finalisation et le contre-exemple qui montre pourquoi les poids négatifs cassent tout — avec trois exercices corrigés.
Réviser ce chapitre →
Étape 20
Tableaux à deux dimensions et images
Les tableaux 2D sans le piège : listes de listes, le danger d'aliasing de [[0]*c]*l démonté et tracé, le parcours par double boucle, et les images comme matrices de pixels (négatif, seuillage) — avec trois exercices corrigés.
Réviser ce chapitre →
Étape 21
Algorithmes gloutons
Le paradigme glouton et sa limite : le rendu de monnaie euro tracé pas à pas, le contre-exemple [1,3,4] pour 6 (glouton 3 pièces contre optimum 2) qui prouve qu'un glouton n'est pas toujours optimal, et la sélection d'activités où il l'est — avec trois exercices corrigés.
Réviser ce chapitre →
Étape 22
Représentation des entiers et des flottants
Comment la machine code les nombres : les entiers en base 2 et le complément à deux, le débordement (absent en Python), et surtout les flottants — pourquoi 0.1 + 0.2 ne vaut pas 0.3 et pourquoi on ne compare jamais deux flottants avec == mais avec abs(a-b) < epsilon — avec trois exercices corrigés.
Réviser ce chapitre →
Étape 23
Bases de données : le modèle relationnel
Tout le vocabulaire des bases de données avant d'écrire une requête : relation, attribut, tuple, domaine, schéma, et surtout clé primaire vs clé étrangère et l'intégrité référentielle — illustré sur un schéma Eleve/Note concret, avec trois exercices corrigés.
Réviser ce chapitre →
Étape 24
Bases de données : requêtes SQL
Les huit briques de SQL et surtout leur ordre d'évaluation (FROM → WHERE → GROUP BY → HAVING → SELECT → ORDER BY) : projection, sélection, jointure, agrégats, GROUP BY vs HAVING — chaque requête décryptée et son résultat tracé sur une base d'exemple, avec trois exercices corrigés.
Réviser ce chapitre →
Étape 25
Programmation dynamique
Le paradigme qui bat le glouton : mémoïser les sous-problèmes chevauchants pour ne jamais recalculer. Fibonacci mémoïsé (exponentiel → linéaire) et le rendu de monnaie optimal par tableau dp, qui trouve 2 pièces là où le glouton en donnait 3 — avec trois exercices corrigés.
Réviser ce chapitre →
Étape 26
k plus proches voisins et matrice de confusion
Classer par ressemblance : la distance euclidienne, l'algorithme k-NN (calculer les distances, garder les k plus proches, voter la classe majoritaire) tracé sur un exemple, le choix de k, et la matrice de confusion pour évaluer un classifieur (précision, taux d'erreur) — avec trois exercices corrigés.
Réviser ce chapitre →
Étape 27
k-moyennes (k-means)
Faire émerger des groupes sans étiquettes : l'algorithme des k-moyennes en deux phases (affectation au centre le plus proche, puis mise à jour par le barycentre) tracé sur un exemple 2D, la convergence vers un minimum local dépendant de l'initialisation, et la différence avec le k-NN — avec trois exercices corrigés.
Réviser ce chapitre →
Étape 28
Algorithme minimax
Jouer optimalement contre un adversaire optimal : l'arbre de jeu, les joueurs MAX et MIN, et l'algorithme minimax récursif qui remonte les valeurs des feuilles vers la racine — tracé sur un petit arbre, avec l'idée de l'élagage alpha-bêta et trois exercices corrigés.
Réviser ce chapitre →