La complexité algorithmique est un pilier de la science informatique. Dans ce cours nous aborderons les premiers éléments de cette théorie, pour tendre vers la question : est-ce que P=NP ? En pratique nous apprendrons à utiliser un solveur pour la résolution de problèmes difficiles.
-
Rappels d'analyse de complexité (somme, produit et composition des polynômes).
-
Complexité dans le pire cas comme une fonction de la taille de l'entrée (attention au modèle RAM à taille de mot fixée, et au coût des instructions en pseudo-code).
-
Notion de problèmes (décision, recherche, dénombrement, énumération, optimisation).
-
Classes de complexité P, NP (vérificateur de certificats), coNP, PSPACE, EXP, distinctions connues (théorèmes de hiérarchie) et conjectures.
-
Exemples de problèmes, intuitions sur les bornes inférieures.
-
Utilisation d'un solver (modélisation SAT, CSP).
-
Remarque : sans machines de Turing, ni modèles non-déterministes.
