E. Kounalis, PR

Algorithmique 1

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.

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

  • 2 CC à 30%
  • 1 CT à 40%

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)