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

Cours Introduction à la programmation de 1ère année, ou expérience d'un langage proche du C++, comme C ou java.

Programmation et algorithmique (7 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 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).

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. Programmation dynamique : aspects pratiques et implémentation efficace

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 à 1h 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.

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.

Adresse web du site du module