MI-Algorithmique et programmation S5

Le but de ce cours est d’appréhender des éléments d’algorithmiques plus avancés en abordant deux aspects : d’une part, les notions de complexité et d’autre part, des structures de données avancées.
Nous abordons les notions de complexité en comparant différentes vitesses d’exécution pour différents algorithmes de tris. Les notions de complexité sous linéaire, linéaire, log linéaire, quadratique sont abordée ainsi que les notions de complexité dans le pire cas et les notions de complexité moyenne.
Nous abordons aussi les notions de complexité exponentielle sur un certain nombre de problèmes classique (“subset sum” par exemple) et abordons aussi les techniques qui permettent de parcourir l’ensemble des solutions d’un tel problème.
Enfin dans un troisième temps, nous abordons des structures de données avancées telles que les tas, les tables de hachage, et enfin les structures d’arbres.

Programme :

• Algorithme de tris comparaison de complexité
• Problème avec complexité exponentielle
• Manipulation de données avancées

Évaluation en session 1 pour les étudiants inscrits en formule standard de contrôle de connaissances : des épreuves de contrôle continu pendant le semestre (50% de la note) et un examen terminal écrit de 2h (50% de la note).

Évaluation en session 1 pour les étudiants inscrits en formule dérogatoire de contrôle de connaissances : un examen terminal écrit de 2h (100% de la note).

Évaluation en session 2 : un examen terminal écrit de 2h (100% de la note).

• Connaitre les concepts liés à la complexité.
• Savoir ce que signifient une complexité linéaire, sous linéaire quadratique et plus généralement polynomiale.
• Appréhender les problèmes avec un nombre exponentiel de solutions.
• Connaitre des structures de données complexes.

• Initiation à l'algorithmique et à la programmation en C, Remi Malgouyres, Rita Zrour, Fabien Feschet. Edition Dunod
• Algorithmique, Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest Clifford Stein, Edition Dunod