Algorithmique
Ce domaine porte sur la conception, la correction et l'évaluation d'algorithmes : parcours de tableaux, recherche, tri, récursivité et complexité. L'examen demande de lire un algorithme, d'en suivre l'exécution pas à pas et de justifier sa terminaison ou son coût.
Règles et concepts
- Un algorithme doit être correct et terminer. Sa complexité décrit l'évolution du nombre d'opérations quand la taille des données augmente.
- La recherche linéaire examine les éléments un par un : coût O(n) dans le pire cas.
- La recherche dichotomique s'applique à un tableau trié ; elle compare l'élément cherché au milieu et divise l'intervalle de recherche par deux : coût O(log n).
- Les tris par sélection, insertion ou bulles ont un coût quadratique dans le pire cas, O(n^2). Un tri par fusion a un coût O(n log n).
- Une fonction récursive s'appelle elle-même et doit posséder un cas de base qui arrête les appels.
- Un invariant de boucle est une propriété vraie avant et après chaque itération ; il aide à prouver la correction.
Exemple travaillé
Soit t = [2, 4, 7, 9, 11] et x = 9. On pose g = 0 et d = 4. Le milieu vaut m = 2 : t[2] = 7, donc 7 < 9 et l'on pose g = 3. Le nouveau milieu vaut m = 4 : t[4] = 11, donc 11 > 9 et l'on pose d = 3. Le milieu vaut m = 3 : t[3] = 9, on renvoie 3. En trois comparaisons, l'intervalle est réduit de moitié à chaque étape, ce qui illustre le coût logarithmique.
Pièges fréquents
Appliquer la recherche dichotomique à un tableau non trié ; écrire while g < d au lieu de g <= d et manquer le dernier élément ; calculer m par (g + d) / 2 au lieu d'une division entière ; oublier le cas où x est absent ; confondre O(n) et O(log n) ; oublier le cas de base d'une récursion ; affirmer qu'un algorithme est correct sans preuve ni test des bords.
À retenir
- Recherche linéaire : O(n) ; recherche dichotomique : O(log n), tableau trié obligatoire.
- Les tris simples sont souvent O(n^2).
- Une récursion exige un cas de base.
- Un invariant aide à justifier une boucle.
- Suivre les indices et les bornes évite les erreurs de terminaison.