S. Julia & M. Pelleau

Algorithmique 1

Complexité et méthodes générales

Le but du cours est d'introduire l’étudiant à l’algorithmique, en mettant l'accent sur les stratégies de conception d'un algorithme efficace.

L2 6 ECTS 24h CM, 36h TD S4 S. Julia, M. Pelleau

Description

Le but du cours est d’introduire l’étudiant à l’algorithmique, en mettant l’accent sur les stratégies de conception d’un algorithme efficace.

Cours

  1. Complexité des algorithmes: temps et espace
  2. Complexité des problèmes: classes de complexité,NP-complétude
  3. Resumé des algorithmes de tri et des structures de données
  4. Revue des stratégies fondamentales de l’algorithmique :
    1. diviser-pour-régner
    2. gloutonne
    3. programmation dynamique

Modalités de contrôle des connaissances

  • 1 CC à 50%
  • 1 CT à 50%

Ressources

  1. Sanjoy Dasgupta, Christos Papadimitriou, Umesh Vazirani, Algorithms /2008.
  2. Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest et Clifford Stein, Intro-duction to Algorithms, 3rd edition, MIT Press, 2009
  3. Tim Roughgarden-Algorithms Illuminated_ Part 1_ The Basics-Soundlikeyourself Publ. (2017)