Offre de th
Forum 'Emplois' - Sujet créé le 2014-02-03
Sujet : Somme coloration de graphes, résolution par solveur SAT.
Mots clés : Coloration de graphe, somme coloration, cliques, SAT.
Objectif du stage : Nous souhaitons étudier un problème de colora- tion de graphes, la somme coloration pondérée minimale. Le but sera non seulement d'étudier mais également de développer un algorithme per- mettant de résoudre le problème de la somme coloration de graphe par une modélisation sous forme de clauses SAT (solveur SAT).
Le problème de somme coloration pondérée minimale reprend les définitions et contraintes de la coloration basique, en ajoutant de nouvelles contraintes, de nouvelles données et en redéfinissant l'objectif. Il s'agit comme dans le problème basique de colorier les sommets du graphe en respectant les contraintes de voisinage. De plus, à chaque couleur i est associé un poids et
l'objectif est de définir une coloration dont la somme des poids est minimale. Ce problème généralisé de coloration peut être réduit en considérant que les poids associés aux couleurs c1,c2,···,ck sont respectivement les entiers consécutifs 1, 2, · · · , k. On parle alors de somme coloration minimale.
Le problème de somme coloration de graphe est un problème NP-difficile, et il existe différentes approches pour le résoudre. Nous souhaitons ici faire un lien entre le problème de somme coloration et le problème MinSAT. Pour MinSAT, il s'agit de déterminer une affectation des variables minimisant la somme des clauses satisfaites d'une formule propositionnelle sous forme normale conjonctive. Cette représentation permet de modéliser de façon na- turelle le problème de somme coloration. Le problème MinSAT est une extension du problème SAT, et le problème SAT est un problème central en informatique théorique, grâce à sa capacité de représentation des problèmes difficiles.
Modalités : Ce sujet de thèse est susceptible d'être financé par une allocation de recherche à partir de septembre 2014 pour une durée de 3 ans. Les dossiers de candidature sont à envoyer par mail au plus tôt à M. Chumin LI (chu-min.li@u-picardie.fr). Ils devront contenir une lettre de motivation, un CV détaillé, et les notes de Master I & II.
Mots clés : Coloration de graphe, somme coloration, cliques, SAT.
Objectif du stage : Nous souhaitons étudier un problème de colora- tion de graphes, la somme coloration pondérée minimale. Le but sera non seulement d'étudier mais également de développer un algorithme per- mettant de résoudre le problème de la somme coloration de graphe par une modélisation sous forme de clauses SAT (solveur SAT).
Le problème de somme coloration pondérée minimale reprend les définitions et contraintes de la coloration basique, en ajoutant de nouvelles contraintes, de nouvelles données et en redéfinissant l'objectif. Il s'agit comme dans le problème basique de colorier les sommets du graphe en respectant les contraintes de voisinage. De plus, à chaque couleur i est associé un poids et
l'objectif est de définir une coloration dont la somme des poids est minimale. Ce problème généralisé de coloration peut être réduit en considérant que les poids associés aux couleurs c1,c2,···,ck sont respectivement les entiers consécutifs 1, 2, · · · , k. On parle alors de somme coloration minimale.
Le problème de somme coloration de graphe est un problème NP-difficile, et il existe différentes approches pour le résoudre. Nous souhaitons ici faire un lien entre le problème de somme coloration et le problème MinSAT. Pour MinSAT, il s'agit de déterminer une affectation des variables minimisant la somme des clauses satisfaites d'une formule propositionnelle sous forme normale conjonctive. Cette représentation permet de modéliser de façon na- turelle le problème de somme coloration. Le problème MinSAT est une extension du problème SAT, et le problème SAT est un problème central en informatique théorique, grâce à sa capacité de représentation des problèmes difficiles.
Modalités : Ce sujet de thèse est susceptible d'être financé par une allocation de recherche à partir de septembre 2014 pour une durée de 3 ans. Les dossiers de candidature sont à envoyer par mail au plus tôt à M. Chumin LI (chu-min.li@u-picardie.fr). Ils devront contenir une lettre de motivation, un CV détaillé, et les notes de Master I & II.