Algorithmique et C

L’objectif de cet enseignement est de fournir les premiers éléments relatifs à la notion de complexité et d’observer en pratique les résultats théoriques. La complexité est abordée tant en termes de ressources (temps ou mémoire) qu’en termes de structures de données (tableaux, listes, dictionnaire).

Les cours et travaux pratiques illustrent la complexité algorithmique en termes de nombre d’échanges et de comparaisons d’éléments dans le cas de tris classiques (bulle, sélection, insertion, rapide). On y met en particulier en évidence les situations idéales et critiques pour ces algorithmes. Des optimisations sont proposées. Ces dernières peuvent découler de propriétés des tris (en évitant les situations critiques par exemple), ou de la typologie des données (comme dans le cas du tri casier).