Le thème de la thèse est la compilation de connaissances, une approche pour la résolution de problèmes difficiles à résoudre du point de vue du calcul et qui vise à réduire cette complexité en pré-traitant une partie des informations décrivant le problème, qui sont connues à l’avance. Le travail de thèse a pour objectif le développement de nouvelles approches pour la compilation de connaissances, à base de concepts issus de la théorie de la complexité paramétrée, de l’approximation et de la complexité à grain fin. Il s’agira d’étendre les résultats connus, focalisés sur la complexité dans le pire des cas, à des situations plus générales dans laquelle des paramètres seront pris en compte et / ou l’exigence sur la qualité des solutions obtenues pourra être quelque peu relâchée.