En Terminale, tu vas dépasser la simple écriture de scripts pour aborder la conception d'algorithmes efficaces et élégants. Cette partie du programme est fondamentale, car elle structure ta pensée logique et te prépare aux études supérieures, quelle que soit ta future orientation.
Objectifs du chapitre
- •Comprendre et implémenter des algorithmes de recherche et de tri classiques
- •Maîtriser la récursivité et en évaluer l'efficacité
- •Analyser la complexité d'un algorithme pour choisir la meilleure solution
1La récursivité : une fonction qui s'appelle elle-même
Un algorithme récursif résout un problème en se rappelant lui-même sur un problème plus petit. C'est une technique puissante, surtout pour les structures qui se décomposent naturellement (comme les arbres). Pour qu'elle fonctionne, il faut absolument définir un cas de base, une condition simple qui arrête les appels, sans quoi tu auras une boucle infinie. La pile d'exécution gère tous les appels en attente, ce qui consomme de la mémoire. Tu dois toujours vérifier que tes appels récursifs se font sur un problème strictement plus petit, pour converger vers le cas de base.
Le calcul de la factorielle : n! = n * (n-1)!, avec le cas de base 0! = 1. En Python : `def factorielle(n): if n == 0: return 1 else: return n * factorielle(n-1)`
Pour comprendre la récursivité, trace l'exécution à la main sur un petit exemple (n=3). Vois comment les appels s'empilent puis se dépilent.
2Diviser pour régner : la stratégie des grands problèmes
Cette approche géniale consiste à découper un problème complexe en sous-problèmes plus petits et indépendants, à les résoudre récursivement, puis à fusionner leurs solutions pour obtenir le résultat final. C'est plus qu'une simple récursivité : c'est une philosophie de conception. Elle est à la base des algorithmes les plus efficaces. L'enjeu est de bien choisir comment diviser et comment fusionner, car c'est là que se gagne l'efficacité. On l'utilise quand le problème peut être séparé en parties qui ne se chevauchent pas.
Le tri fusion (merge sort) : tu divises la liste en deux moitiés, tu tries récursivement chaque moitié, puis tu fusionnes les deux listes triées en une seule liste triée. La fusion de deux listes triées est une opération très rapide.
Dessine l'arbre de décomposition du problème. Chaque niveau correspond à une division. Cela t'aide à visualiser le cheminement de l'algorithme.
3Complexité algorithmique : l'art de mesurer l'efficacité
Ce n'est pas assez qu'un algorithme donne le bon résultat ; il doit être efficace en temps et en mémoire. La complexité en temps, souvent notée avec un grand O (comme O(n) ou O(n²)), évalue comment le temps d'exécution évolue quand la taille des données (n) augmente. C'est une estimation du pire des cas, qui permet de comparer deux algorithmes de façon théorique, indépendamment de l'ordinateur utilisé. Une complexité exponentielle (O(2^n)) devient rapidement ingérable, alors qu'une complexité logarithmique (O(log n)) est excellente. En Terminale, tu dois savoir analyser des boucles imbriquées pour en déduire la complexité.
Parcourir une liste de n éléments avec une seule boucle `for` a une complexité linéaire O(n). Parcourir cette même liste avec deux boucles `for` imbriquées (comme dans un tri par sélection) a une complexité quadratique O(n²). Pour n=1000, O(n) c'est environ 1000 opérations, O(n²) c'est 1 000 000 !
Concentre-toi sur la boucle la plus imbriquée dans ton code. Le nombre de fois où elle s'exécute donne souvent l'ordre de grandeur de la complexité.
4Algorithmes de recherche et de tri fondamentaux
Savoir rechercher un élément dans une collection ou trier cette collection sont des opérations de base en informatique. Tu dois connaître plusieurs méthodes pour pouvoir choisir la plus adaptée au contexte. Une recherche dichotomique est bien plus rapide qu'une recherche séquentielle, mais elle exige que la liste soit déjà triée. Pour le tri, le tri par insertion est simple et efficace sur de petites listes, tandis que le tri fusion (diviser pour régner) est optimal pour de grandes listes. Comprendre leur mécanisme te permet de saisir les compromis entre simplicité et performance.
Recherche dichotomique dans une liste triée : on compare l'élément du milieu avec la cible. S'il est égal, c'est trouvé. Sinon, on élimine la moitié de la liste où l'élément ne peut pas être et on recommence sur l'autre moitié. On divise la taille du problème par 2 à chaque étape.
Pour mémoriser les algorithmes de tri, code-les toi-même plusieurs fois jusqu'à ce que tu puisses les écrire sans aide. C'est le meilleur moyen de les comprendre en profondeur.
5Parcours de graphes : explorer des réseaux
Un graphe est un ensemble de sommets reliés par des arêtes, modélisant un réseau (social, routier, etc.). Le parcours en profondeur (DFS) explore un chemin le plus loin possible avant de revenir en arrière, comme dans un labyrinthe. Le parcours en largeur (BFS) explore tous les voisins d'un sommet avant de passer aux voisins des voisins, utile pour trouver le plus court chemin dans un graphe non pondéré. Ces algorithmes sont la base pour résoudre une foule de problèmes, comme vérifier la connexité d'un réseau ou trouver une sortie.
Avec le DFS, si tu es sur un sommet, tu vas explorer récursivement son premier voisin non visité, puis le premier voisin de ce voisin, etc. Avec le BFS, tu utilises une file (FIFO) : tu traites les sommets dans l'ordre où tu les as découverts, ce qui assure de visiter par couches successives.
Associe DFS à une pile (explicite ou via la récursivité) et BFS à une file. Dessine un petit graphe et trace les deux parcours avec des couleurs différentes pour bien voir la différence.