Exercices d'algorithmique en Python — tris, dichotomie, récursivité
Les algorithmes au programme des CPGE scientifiques : tris, recherche dichotomique, récursivité, programmation dynamique, structures de données.
Le cœur de l'épreuve
C'est la partie la plus prévisible du programme, et donc la plus rentable. Un tri par insertion, une recherche dichotomique et un parcours d'arbre correctement écrits couvrent une part considérable de ce qui se demande, et se réécrivent de mémoire une fois qu'on les a compris plutôt que mémorisés.
Ce qu'il faut savoir écrire sans réfléchir
Les tris quadratiques (bulle, insertion, sélection) et leurs invariants ; les tris récursifs (fusion, rapide) et leur complexité ; la dichotomie sur un tableau trié — et sur une fonction monotone, ce qui est le même algorithme ; les structures linéaires (pile, file, liste chaînée) ; les arbres binaires et leurs parcours ; la programmation dynamique sur les schémas classiques : sac à dos, plus longue sous-séquence commune, distance d'édition.
La complexité se justifie, elle ne se récite pas
« Le tri fusion est en O(n log n) » ne vaut aucun point si tu ne sais pas d'où vient le log n. Prends l'habitude de compter : combien de fois la boucle interne tourne-t-elle pour une valeur donnée de la boucle externe ? Quelle est la profondeur de récursion ? La somme de ces deux réponses est ta justification.
L'invariant de boucle est ton outil de vérification
Avant d'écrire les bornes, écris ce qui est vrai après chaque passage. « Après le passage i, les i plus grands éléments sont à leur place définitive » te donne immédiatement range(n-1) et non range(n). Cette phrase, écrite en commentaire, rapporte souvent des points à elle seule.
Les exercices
Algorithmique classique 26 exercices
- Recherche Dichotomique Diviser pour mieux chercher
- Suite de Fibonacci Récursivité et mémoïsation
- Tri à Bulle (Bubble Sort) Échanges successifs — la bulle qui remonte
- Tri par Insertion Invariant de boucle et preuve
- Tri par Sélection Invariant et complexité quadratique
- Tri Fusion (Merge Sort) Diviser pour régner — O(n log n)
- Tri Rapide (Quicksort) Partition et pivot — cas moyen O(n log n)
- Exponentiation Rapide Calcul de aⁿ en O(log n)
- Recherche dans une Liste Chaînée Classe Maillon et parcours
- Pile et File Structures LIFO et FIFO avec listes
- Évaluation d'Expressions Postfixées Pile et notation polonaise inverse
- Algorithme de Boyer-Moore simplifié Recherche de motif dans un texte
- Algorithme glouton : rendu de monnaie Stratégie gloutonne et contre-exemples
- Sac à dos (Programmation Dynamique) Optimisation sous contrainte de poids
- Plus Longue Sous-séquence Commune (LCS) Programmation dynamique classique
- Détection de Cycle (Floyd) Algorithme du lièvre et de la tortue
- Arbres Binaires — Parcours et Hauteur Préfixe, infixe, postfixe, largeur
- Arbre Binaire de Recherche (ABR) Insertion, recherche, tri par parcours infixe
- Tri par Tas (Heap Sort) Structure de tas et tri en place en O(n log n)
- Algorithme de Kadane Sous-tableau de somme maximale en O(n)
- Chemins dans une Grille Programmation dynamique 2D — comptage de chemins
- Distance d'Édition (Levenshtein) Programmation dynamique 2D sur deux chaînes
- Rendu de Monnaie (DP) Programmation dynamique — quand le glouton échoue
- Problème des N-Reines Backtracking classique sur échiquier
- Traitement d'Image — Seuillage et Barycentre Niveaux de gris, masque binaire, centre de masse
- Algorithme de Bresenham Tracé de segment sur grille de pixels
Autres rubriques
- Exercices Python pour la prépa — CPGE scientifique et ECG
- Exercices SQL pour la prépa — bases de données en CPGE
- Exercices d'analyse numérique en Python — dichotomie, Newton, intégration
- Exercices sur les graphes en Python — BFS, DFS, Dijkstra
- Exercices Python pour la prépa ECG — probabilités, matrices, suites
- Exercices d'IA et d'apprentissage automatique en Python — CPGE
La correction commentee, les indices progressifs, l'execution du code dans le navigateur et la verification par l'IA sont reserves aux abonnes.