Algorithmique et complexité
Objectifs
Calculer la complexité d’un algorithme, identifier sa classe de complexité, évaluer le temps nécessaire à sa terminaison ; Produire un algorithme en python de complexité inférieure aboutissant au même résultat ; Appliquer les bonnes pratiques de programmation impérative ; Décrire les principaux composants d’un ordinateur
Plan
La première partie du cours se concentre sur le calcul de la complexité d’un algorithme, d’abord dans le cas non récursif puis ensuite dans le cas récursif. Si le cas non récursif consiste juste à compter le nombre d’opérations et nécessite uniquement des connaissances en arithmétique simple, le cas récursif est plus complexe et dispose d’outils propres comme le théorème général. Dans un second temps nous étudierons différents formats de données et leur complexité pour différentes opérations élémentaires. Enfin nous verrons comment réduire la complexité d’une algorithme grâce à la programmation dynamique.
Prérequis
Rudiment dans la programmation impérative