B2-M3 Introduction à la complexité de programme¶
Objectifs du module¶
Introduire la notion de complexité d'un algorithme et de grand O(). Illustrer ces concepts sur des petits programmes Python.
Sommaire¶
1. Efficacité d'un algorithme et d'un programme
2. Approche pragmatique
3. Approche analytique
4. La notion de grand O
5. Calcul du grand O
6. Applications des règles de calcul du grand O
7. Complexité des tris simples
8. Complexité des manipulations des séquences de données python
Prérequis¶
- Savoir programmer en Python
- Avoir les bases de la programmation impérative Python vous sont acquises. La matière correspond au contenu du MOOC "Apprendre à coder avec Python".
Temps d'apprentissage :¶
- 4 à 6 heures
- Ce temps est donné à titre indicatif. Il peut varier en fonction des participants.
Texte Complémentaire¶
- Référence:
Thomas Cormen, Charles Leiserson, Ronald Rivest, Clifford Stein - Algorithmique - 3ème édition - Cours avec 957 exercices et 158 problèmes, Dunod, 2010, ISBN: 978-2-10-054526-1
Enseignant¶
Thierry Massart¶
Thierry Massart est professeur à l'Université Libre de Bruxelles (ULB) où, depuis plus de 25 ans, il enseigne la programmation principalement aux étudiants de Sciences Informatique et de l'école Polytechnique de l'ULB..