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 devoirs.

Partiel : Mercredi 29 Octobre — 10h45-12h45

Examen Session 1 : Mercredi 17 Décembre — 10h45-12h45

Examen Session 2 : Mercrdi 21 Janvier — 10h45-12h45

Documents pour le module
- Transparents de cours.
- Enoncés de TD-TME.
- Annales.
- Devoirs et Projets.

 
Documents utiles
EnonceExamenSession1.pdf
CorrigeExamenSession1.pdf