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

• 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)