Aucune, mais l'utilisation d'un ordinateur portable personnel est recommandée.

Cours de programmation en C++ de 1ère année (partie A, partie B fortement recommandée), ou, pour les admis sur titre ou en double diplôme, expérience d'un langage proche du C++, comme C ou java.

Programmation et algorithmique (6 séances)

Ce module aborde des aspects plus pointus de la programmation et de l'algorithmique que ceux vus en première année.

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 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 la compression d'image, la différenciation automatique et la recherche efficace de villes voisines à l'échelle d'un grand territoire (la France métropolitaine).

Contenu des séances :

1. Rappels de programmation C++ (types, fonctions, tableaux, classes, constructeurs, destructeur, surcharge d'opérateurs), pointeurs et mémoire.

2. Programmation avec templates, la Standard Template Library et son utilisation, foncteurs

3. Héritage et polymorphisme

4. Structures de données générales

5. Structure de données d'arbres pour le stockage et la recherche d'information efficaces

6. Ensembles, tableaux associatifs et hachage

Chaque séance se décompose en 1h à 1h30 de cours et en 1h30 à 2h de TP (suivant les séances), sauf la première qui comporte uniquement du cours. Les TP sont à terminer individuellement et à remettre en tant que devoir à la maison. 8h CM, 10h TD.

La validation se fait sur les rendus de TP, consistant en un programme C++ et un compte-rendu d'expérience.

Introducton to Algorithms. T. H. Cormen, Ch. E. Leiserson, R. L. Rivest, C. Stein. The MIT Press.

Algorithms in C++. R. Sedgewick. Addison-Wesley.

Algorithms. S. Dasgupta, C. Papadimitriou, U. Vazirani. McGraw-Hill.

10 Novembre 2025