IP4003 - Complexité des algorithmes

Objectifs

Objectif général :

Savoir calculer les complexités temporelle et spatiale d'algorithmes séquentiels.
Être capable d'appliquer la technique de programmation dynamique pour optimiser les formulations
récursives.
Savoir comparer des algorithmes et choisir le plus adapté en fonction du problème.

Objectifs détaillés :

Maîtriser les notions de complexités temporelle et spatiale en pire cas d’un algorithme séquentiel.
Savoir calculer et comparer les expressions asymptotiques d'algorithmes itératifs et récursifs.
Savoir transformer certains algorithmes récursifs en algorithme itératif à l’aide de la programmation
dynamique.
Comprendre la notion d’algorithme optimal.
Connaître les classes de complexité de problèmes NP, P, NPC et NP-difficile.
Savoir comparer des algorithmes et choisir le plus adapté pour résoudre un problème donné en fonction
du contexte.