Programmation avancée et algorithmique

Niveau M1

"Ce module aborde des aspects pointus de la programmation et de l'algorithmique.

Pour la programmation, le langage C++ est utilisé car il représente un bon équilibre entre la possibilité de programmation à un haut niveau d'abstraction, mais expose aussi aux considérations bas niveau comme la gestion de la mémoire. L'héritage et le polymorphisme, aspects essentiels de la programmation objet, sont introduits et discutés ; ce sont les clés de voûte d'une programmation haut niveau. Mais ces concepts ne peuvent ignorer la question de leur efficacité, qui repose sur la gestion de la mémoire et en particulier la notion cruciale de pointeur.

Pour ce qui concerne l'algorithmique, sont présentées d'une part des méthodes de résolution de problèmes combinatoires (aspects pratiques et implémentations efficaces de la programmation dynamique) et d'autres part des structures données adaptées au stockage et à la recherche d'information efficaces : arbres binaires, graphes acycliques orientés, quadtrees, ensembles, tableaux associatifs et tables de hachage. Ces notions d'optimisation et de structures de données sont centrales dans le développement de logiciels. Elles sont illustrées par des TP variés tels que le calcul de la distance d'édition entre chaînes de caractères, la compression d'image, et la recherche efficace de villes voisines à l'échelle d'un grand territoire (la France métropolitaine)."