💻Informatique

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)\).

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.

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.

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.

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.

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.

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.

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.

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.

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é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.

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.

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.

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).

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.

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.

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.

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.

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.

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.

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.

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.

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.

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.

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.

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.

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.

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.

C — Premiers pas

Écrire son premier programme C : la structure main/return, les types de base, printf et ses formats, les boucles for/while, et le piège n°1 — la division entière (7/2 vaut 3, pas 3,5) — chaque programme compilé et tracé, avec trois exercices corrigés.

C — Pointeurs et allocation dynamique

Le cœur du C : l'adresse et le pointeur, les opérateurs & et *, pourquoi il faut un pointeur pour modifier une variable (le passage par valeur), le lien tableaux/pointeurs, et malloc/free — chaque programme compilé et tracé, avec trois exercices corrigés.

OCaml — Premiers pas

Découvrir OCaml, le langage fonctionnel de MP2I : le let et le typage inféré, les fonctions, le piège des opérateurs pointés (+. pour les float), le if/then/else qui renvoie une valeur, et la récursivité let rec (factorielle déroulée) — avec trois exercices corrigés.

OCaml — Filtrage et listes

Les deux piliers d'OCaml : le filtrage (match ... with) et les listes récursives (:: et []), avec longueur et somme déroulées sur un exemple, les types somme et le type option (Some/None) — attention à l'ordre et à l'exhaustivité des cas, avec trois exercices corrigés.

C — Structures et listes chaînées

La première structure de données dynamique du programme : les struct, le maillon et l'opérateur flèche p->suivant, l'insertion en tête et le parcours d'une liste chaînée — construction de [3, 5, 8] tracée, avec les pièges (NULL, ordre inversé, fuite mémoire) et trois exercices corrigés.

C — Piles et files

Les deux structures linéaires fondamentales implémentées en C : la pile (LIFO, empiler/dépiler en tête) et la file (FIFO, avec un pointeur de queue pour enfiler en O(1)) — chaque opération compilée et tracée, avec trois exercices corrigés.

OCaml — Arbres binaires

L'arbre binaire comme type somme récursif OCaml (Vide | Noeud) : taille, hauteur et parcours infixe écrits par filtrage sur Vide / Noeud(g,x,d), déroulés à la main sur un petit arbre — chaque cas du type devient un cas du match, avec trois exercices corrigés.

OCaml — Fonctions d'ordre supérieur

Manipuler des fonctions comme des valeurs : les fonctions anonymes (fun x -> …) et les trois classiques des listes — map, filter, fold_left — déroulés sur des exemples, puis réécrits à la main pour les démystifier, avec trois exercices corrigés.

C — Tableaux et chaînes de caractères

La brique de base de presque tout le reste de l'année : les tableaux statiques (indice à partir de 0, taille fixe, débordement non contrôlé), les tableaux 2D, et les chaînes de caractères comme tableaux de char terminés par '\0' — chaque programme compilé, avec trois exercices corrigés.

C — Tris par insertion et par sélection

Les deux tris quadratiques écrits en C, triant un tableau en place : l'échange par variable temporaire (pas de swap de tuple), les invariants, les traces des échanges et décalages sur {5, 2, 4, 1}, et leurs complexités — chaque tri compilé, avec trois exercices corrigés.

OCaml — Arbres binaires de recherche

L'arbre binaire de recherche en OCaml : la propriété gauche < x < droite, la recherche et l'insertion récursives en O(hauteur), le fait que le parcours infixe d'un ABR est trié, et le piège de l'arbre qui dégénère en peigne — insertions tracées, avec trois exercices corrigés.

OCaml — n-uplets et enregistrements

Deux façons de regrouper des valeurs en OCaml : les n-uplets (accès par position — fst, snd, filtrage) et les enregistrements (accès par nom — p.x, et mise à jour fonctionnelle immuable { p with x = … }) — construction et accès tracés, avec trois exercices corrigés.

Dissertation « Les arcanes de la création » : sujets et une problématique corrigée

Gérer le stress des concours en prépa (mai-juillet)

Choisir son école d'ingénieur après les concours 2026 : la méthode des 5 critères et les grands duels

Réussir l'informatique en prépa : méthode, Python et algorithmique

Français-philo 2026-2027 : les arcanes de la création

Tier list des chapitres de spé : le rendement réel aux concours