Algorithmique

About This Course

Ce cours pose les fondements de la conception et de l'analyse d'algorithmes efficaces. L'objectif central est de résoudre des problèmes de manière rigoureuse en maîtrisant le coût des solutions proposées.

La complexité algorithmique, notation grand O,  est l'outil universel d'évaluation. Elle mesure la croissance du temps d'exécution ou de la mémoire en fonction de la taille de l'entrée n. Distinguer O(1), O(log n), O(n), O(n log n), O(n²) et O(2ⁿ) est essentiel pour choisir la bonne approche : un algorithme quadratique devient impraticable dès n > 10⁵.

Les structures de données : tableaux, listes, piles, files, arbres binaires de recherche, tas, tables de hachage — sont les briques de base. Leur choix impacte directement la complexité des opérations d'insertion, recherche et suppression. Les algorithmes de tri illustrent ce principe : le tri fusion et le tri rapide atteignent O(n log n) grâce à la stratégie diviser pour régner, vérifiée par la relation de récurrence T(n) = 2T(n/2) + O(n).

La théorie des graphes introduit les parcours BFS et DFS, les plus courts chemins (Dijkstra, Bellman-Ford) et les arbres couvrants minimaux (Kruskal, Prim). La programmation dynamique optimise les sous-problèmes chevauchants. Enfin, la théorie de la NP-complétude trace la frontière entre problèmes traitables et intrinsèquement difficiles.