Algorithmique appliquée
L'Algorithmique appliquée distingue un candidat capable d'écrire du code de celui qui sait pourquoi une solution est meilleure. On y évalue la décomposition d'un problème, le choix des structures de données, la correction et la complexité.
Les bases incontournables
- Structures de contrôle : alternative, boucle bornée (for) vs non bornée (while) avec sa condition d'arrêt garantie.
- Structures de données : tableau (accès O(1), insertion coûteuse), liste chaînée, pile (LIFO), file (FIFO), dictionnaire (accès en moyenne O(1)), arbre, graphe.
- Algorithmes classiques : parcours linéaire O(n) ; recherche dichotomique O(log n) sur un tableau trié ; tris en O(n²) (insertion, sélection) et en O(n log n) (fusion, rapide en moyenne) ; parcours de graphe en largeur (BFS, avec une file) et en profondeur (DFS, avec une pile ou la récursion).
Exemple raisonné : recherche dichotomique
Tableau trié de 16 entiers, on cherche 42. On compare à l'élément médian : l'intervalle est divisé par deux à chaque étape, les bornes gauche et droite étant mises à jour. Nombre maximal de comparaisons : ⌈log₂ 16⌉ = 4, contre jusqu'à 16 en recherche linéaire. La condition de boucle est while gauche <= droite et non <, sinon l'élément situé sur la dernière case survolée n'est jamais testé. La dichotomie exige un tableau trié : l'oublier est l'erreur classique.
Écrire un algorithme propre
Une fonction a un rôle unique, un nom explicite, des paramètres typés, et gère les cas limites (tableau vide, valeur absente → renvoyer −1 ou lever une exception, selon le contrat annoncé). La récursion exige un cas de base atteint à coup sûr, sinon débordement de pile.
Les pièges qui coûtent des points
Confondre = (affectation) et == (comparaison) ; oublier d'incrémenter un compteur (boucle infinie) ; erreur d'indice (le dernier indice d'un tableau de n cases est n−1) ; croire qu'un tableau passé en argument est copié ; annoncer O(log n) pour un parcours complet ; décrire un tri sans préciser s'il est en place ni stable.