Algorithmique et complexité
Objectifs
Calculer la complexité d’un algorithme, identifier sa classe de complexité, évaluer le temps nécessaire à sa rnterminaison rn Produire un algorithme en python de complexité inférieure aboutissant au même résultat rn Appliquer les bonnes pratiques de programmation impérative rn Décrire les principaux composants d’un ordinateur rn
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 rnpuis ensuite dans le cas récursif. Si le cas non récursif consiste juste à compter le nombre d’opérations et nécessite rnuniquement des connaissances en arithmétique simple, le cas récursif est plus complexe et dispose d’outils propres rncomme le théorème général. rnDans un second temps nous étudierons différents formats de données et leur complexité pour différentes opérations rnélémentaires. Enfin nous verrons comment réduire la complexité d’une algorithme grâce à la programmation rndynamique. rn
Prérequis
Rudiment dans la programmation impérative