Nos tutelles

CNRS

Nos partenaires


Accueil > Publications > Thèses

GHAZI Kaoutar


Heuristiques et Conjectures à propos de la 2-dimension des ordres partiels

Vendredi 29 Septembre 2017 - 10h00 - Amphi Bruno Garcia - ISIMA

Dés qu’on manipule des ordres partiels (des hiérarchies), il est naturel
de se demander comment les représenter dans un système informatique. Parmi
les solutions proposées dans la littérature, on retrouve le codage par vecteur de
bits. Dans cette thèse, nous nous intéressons au problème de calcul d’un codage
des ordres par vecteur de bits de taille minimale, aussi connu par le problème de
calcul de la 2-dimension des ordres, qui est NP-complet. Nous proposons des solutions
du problème de nature heuristique, pour le cas général et pour des classes
d’ordres particulières.
Cette thèse présente également des résultats sur des conjectures autour de
la 2-dimension des arbres. Notamment celle de Habib, Nourine, Raynaud et Thierry à propos de la 2-approximabilité de la 2-dimension des arbres. Nous proposons quelques pistes de preuve de cette conjecture puis une reformulation, permettant d’apporter un nouveau regard sur le problème en question et d’espérer trouver des codages des ordres par vecteur de bits efficaces et de taille inférieure à leur 2-dimension. Nous apportons une réponse négative à deux autres conjectures.

Jury

Rapporteurs :
M. Michel Habib, Professeur, Université Paris Diderot
M. Christophe Crespelle, MCF-HDR, Université Claude Bernard Lyon 1

Examinateurs :
Mme. Fatiha Bendali-Mailfert, MCF-HDR, Université Clermont Auvergne
Mme. Karell Bertet, MCF-HDR, Université de La Rochelle
Mme. Marianne Huchard, Professeur, Université de Montpellier
M. Lhouari Nourine, Professeur, Université Clermont Auvergne
M. Eric Thierry, MCF, Université de Lyon

Directeurs :
M. Laurent Beaudou, MCF, Université Clermont Auvergne
M. Olivier Raynaud, MCF-HDR, Université Clermont Auvergne.