Prérequis- Algorithmique (Licence)
ValidationCC+examen
EnseignantHervé Fournier et Bertrand Gentou
Horaires hebdomadaires 3 h CM , 4 h TD
Années M1 mathématiques (MFA) M1 Mathématiques et Informatique M1 Mathématiques et Informatique M1 Logos M1 MIC

Sommaire

Le cours est organisé en deux parties : Algorithmique et Complexité. Chaque partie fait l'objet d'une évaluation spécifique.

Algorithmique

  • Pratique algorithmique de base sur les tris, preuve d'algorithmes
  • Compréhension des enjeux de l'algorithmique, limites des méthodes par recherche exhaustive
  • Paradigmes classiques: programmation dynamique, diviser pour régner, algorithmes gloutons
  • Structures de données classiques: arbres, tas, tables de hachage
  • Algorithmes sur les graphes

Complexité

  • Machines de Turing, classes de complexité en temps, théorème de hiérachie
  • Réductions entre problèmes
  • La class NP et le théorème de Cook
  • Classes en espace
  • La complexité à paramètre
  • Algorithmes d'approximations: présentation de quelques techniques

Bibliographie

  • Arora, S., & Barak, B. (2009). Computational complexity: a modern approach. Cambridge University Press.
  • Cormen, T. H., Rivest, R., Leiserson, C. E., & Stein, C. (2009). Introduction to algorithms, MIT Press.