Contenu
L'objectif de ce module 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.
|
