Cette page utilise des feuilles de style en cascade. Si vous arrivez à lire ce message, c'est que CSS ou javascript ne sont pas activés. L'affichage de la page sera donc différent de ce qui est prévu.

Thèmes de recherche


quelques mots clés concernant mes recherches actuelles :


au cours de mon doctorat :

D'octobre 2004 à décembre 2007, j'ai préparé une thése en informatique dont le sujet était "Algorithmes exacts et exponentiels pour les problèmes NP-difficiles", sous la direction de Dieter Kratsch, professeur à l'université de Metz.

L'objectif de ces recherches est de trouver des algorithmes exacts pour des problèmes NP-complets. Puisqu'il semble qu'on ne puisse pas espérer obtenir un algorithme s'exécutant en temps polynomial pour ces problèmes, le but est de parvenir à des algorithmes dont le temps d'exécution est exponentiel. Typiquement, on cherche des algorithmes dont le temps d'exécution est en c^n, avec c une constante la plus proche possible de 1.
Quelques références concernant mes travaux sont disponibles ici.


durant mon année de DEA :

Ma formation m'a conduit à suivre le DEA (Diplôme d'Etudes Approfondies, équivalent maintenant à un Master Recherche) "Informatique de Lorraine". Ce diplôme, co-habilité par l'université de Nancy 1, de Nancy 2, Institut National Polytechnique de Lorraine, et l'université de Metz, compte quatre filières de formation: L'année de DEA est composé de deux semestres. Un premier semestre d'enseignement, et le second consacré exclusivement à un stage de recherche.

Mon stage de recherche s'est déroulé au LITA (Laboratoire d'Informatique Théorique et Appliquée de l'université de Metz) et j'ai été encadré par Dieter Kratsch, professeur à l'université de Metz.

L'objet de mon stage fut l'étude du problème de la Domination Romaine. Il s'agit en fait d'une variante du problème de la domination dans un graphe. Ce problème, ayant alors été démontré comme étant NP-complet, l'objectif était de se restreindre à certaines classes de graphes pour vérifier si le problème restait NP-complet ou s'il était possible d'obtenir des algorithmes polynomiaux pour le résoudre. De plus, nous avons chercher à obtenir des résultats (similaires à celui du problème de la domination) concernant la complexité à paramètre fixé ainsi qu'un algorithme exact exponentiel.


durant mon année de maîtrise :

Dans le cadre d'un Travail d'Etude et de Recherche, encadré par Dieter Kratsch, je me suis intéressé à la NP-complétude. Ce sujet n'étant jusqu'alors que peu, voire pas du tout, traité dans mon cursus universitaire, cela m'a permis de me familiariser avec cette notion importante.

Un nombre impressionnant de problèmes théoriques et pratiques sont dits NP-complets. Qu'est-ce qui caractérise un tel problème ? Comment montrer qu'un problème est NP-complet ? En m'appuyant essentiellement sur l'étude de quelques chapitres du livre de M.R. Garey et D.S. Johnson (Computers and Intractability : A Guide to the Theory of NP-Completeness), mais également celui de C. Papadimitriou (Computational Complexity), j'ai pu acquérir quelques connaissances sur ce sujet. En particulier, cela m'a permis d'appréhender les techniques de preuves de NP-complétude par l'intermédiaire des réductions en temps polynomial.