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 ; Décrire les principaux composants d’un ordinateur
Plan
Différents types de complexité des algorithmes et des problèmes ; La notation grand-O, grand-Omega et grand-Thêta ; Algorithmes itératifs et analyse de complexité par sommation ; Algorithmes récursifs et analyse de complexité par récurrence ; La stratégie « diviser pour régner »; Structures de données telles que tableaux, listes chaînées, piles, files et tables de hachage ; Techniques de preuve comme l’induction, le raisonnement par l’absurde, et le théorème maître ; Programmation dynamique.
Prérequis
Rudiment dans la programmation impérative
