MI - Projets maths, algorithmique et programmation

Le module s’articule en cours, travaux dirigés et pratiques (50%). Il s’agit de sensibiliser l’étudiant à la notion d’algorithme. Pour cela, on aborde la question de la complexité d’un algorithme qui demeure sous-jacente dans l’ensemble des développements ultérieurs. Nous présentons ensuite les résultats des principaux algorithmes de tris, les différentes structures de données depuis le simple tableau résidant en mémoire jusqu’aux arbres équilibrés et aux graphes. Ces structures mises en place, nous abordons, sur des cas simples, les grandes classes d’algorithmes de la théorie des graphes (résistance d’un réseau aux pannes, recherche de plus court chemin…).

Les travaux pratiques consistent à utiliser des structures de données (arbres, graphes) afin de tester les algorithmes les plus connus. Il s’agira notamment de prendre en main des langages de programmation modernes facilitant la visualisation (grâce à des bibliothèques de composants graphiques).

A la fin de ce module, les étudiants sauront définir les algorithmes de base (tris, graphes…) et reconnaître les différentes classes de complexité et d’algorithmes.

Savoir lire et comprendre le français.

Savoir écrire des programmes dans un langage impératif.

Contrôle continu: évaluation(s) écrite(s) et éventuelle évaluation des TPs pour 50% de la moyenne de l'EC et examen partiel final (épreuve écrite d’1h30) pour 50% de la moyenne de l'EC

Être capable d’estimer/de calculer le coût (complexité) d’un algorithme.

Être capable de décrire les différentes classes d’algorithme.

Être capable de manipuler différentes structures de données.

Être capable de décrire les algorithmes classiques (tris, recherche de chemin...).          

Être capable de programmer en langage Python.