Abstract (FR)

Cette thèse s'inscrit dans le domaine de l'étude des problèmes de NPO (problèmes d'optimisation dont la version décision est dans NP), et plus particulièrement dans la théorie de l'approximation polynomiale de ces problèmes. Il s'agit d'étudier la possibilité de fournir efficacement des solutions réalisables ayant une certaine qualité, qualité que nous mesurons tantôt par le rapport standard, tantôt par le rapport différentiel. Deux aspects principaux se dégagent dans notre travail : - La structure des classes d'approximation : il s'agit de structurer les classes classiques par l'introduction de réductions qui préservent certains types d'approximation et qui induisent des notions de complétude. - L'approximation polynomiale de problèmes de NPO : nous avons étudié les problèmes de la coloration pondérée, de la coloration probabiliste et de la couverture d'ensemble quadratique selon le rapport standard, ainsi que des problèmes de satisfiabilité selon le rapport différentiel.