Algorithmique et complexité

Objectifs

· Calculer la complexité d’un algorithme, évaluer le temps nécessaire à sa terminaison

· Produire un algorithme en python

· Améliorer les algorithmes en termes de complexité

· Comprendre les structures de données couramment utilisées

· Apprendre la notion de classes de complexité

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’outil propre comme le théorème général. Nous abordons également la notion de classes de complexité et de NP-difficulté .

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