Algorithmique Avancée
algav

L’objectif du module MI015 ALGAV est de donner un panorama de structures et de méthodes phares dans divers domaines d’applications algorithmiques : codage, géométrie, réseaux, compilation. On insiste sur l’importance d’analyser et de comparer les performances de différentes solutions algorithmiques.

Les thèmes traités sont les suivants : Organisation de l’information : Arbres-B versus Hachage extensible. Représentation de files de priorités : des tas aux files de Fibonacci. Géométrie algorithmique : enveloppe convexe triangulation de Delaunay. Graphes : composantes connexes et fortement connexes. Chemins minimaux et flots maximaux dans les graphes. NP-complétude et réduction entre problèmes.

Bibliographie
- T. Cormen, C. Leiserson, R. Rivest, C. Stein - Introduction à l’algorithmique
- C. Froidevaux, M-C. Gaudel, M. Soria - Types de données et algorithmes
- D. Beauquier, J. Berstel, P. Chrétienne - Eléments d’algorithmique

Contrôle des connaissances
- La note de module est formée à 60% par l’examen final et à 40% par la note de contrôle continu.
- La note du CC comprend la note du partiel et les notes des TME.

Documents pour le module
- Transparents de cours
- Sujets de TD
- Sujets de TME