Heuristiques et conjectures à propos de la 2-dimension des ordres partiels / Kaoutar Ghazi ; sous la direction de Olivier Raynaud et de Laurent Beaudou

Date :

Type : Livre / Book

Type : Thèse / Thesis

Langue / Language : français / French

Catalogue Worldcat

Heuristique

Raynaud, Olivier (1971-....) (Directeur de thèse / thesis advisor)

Beaudou, Laurent (1982-....) (Directeur de thèse / thesis advisor)

Huchard, Marianne (Président du jury de soutenance / praeses)

Habib, Michel (19..-.... ; informaticien) (Rapporteur de la thèse / thesis reporter)

Crespelle, Christophe (Rapporteur de la thèse / thesis reporter)

Bendali-Mailfert, Fatiha (Membre du jury / opponent)

Nourine, Lhouari (Membre du jury / opponent)

Bertet, Karell (1972-....) (Membre du jury / opponent)

Université Clermont Auvergne (2017-2020) (Organisme de soutenance / degree-grantor)

École doctorale des sciences pour l'ingénieur (Clermont-Ferrand) (Ecole doctorale associée à la thèse / doctoral school)

Laboratoire d'Informatique, de Modélisation et d'Optimisation des Systèmes (Laboratoire associé à la thèse / thesis associated laboratory)

Résumé / Abstract : 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 et al. à 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.

Résumé / Abstract : The main question asked when manipulating partial orders (hierarchies), is how to represent them in computer. Among solutions proposed in literature, there is the bit-vector encoding. In this thesis, we consider the problem of computing a bit-vector encoding of orders with minimal size, which is also known as the problem of computing the2-dimension of orders that is NP-complete. We propose heuristics solutions of the problem for the general case and for some particular order classes. In addition, this thesis presents some results about conjectures on the 2-dimension of trees. Especially, the conjecture of Habib et al. about the 2-approximability of the 2-dimension of trees. We propose some ideas of a proof of this conjecture then give a reformulation of it that brings new perspectives on the problem that are finding efficient bits-vector encodings of orders of size less than their 2-dimension. We disprove two other conjectures.