Soutenance de thèse : Mikhael Carmona
Début
Le 20 décembre 2024 à 10h30Fin
Le 20 décembre 2024 à 12h30Lieu
Campus Saint Charles, 3 Place Victor Hugo, 13003 Marseille
Monsieur Mikhael Carmona est autorisé à présenter ses travaux en vue de l'obtention du diplôme national de Doctorat délivré par Centrale Méditerranée.
Titre : Les dissimilarités de Robinson : algorithmes de reconnaissance et extensions
École doctorale : ED 184 - Mathématiques et Informatique de Marseille
Spécialité : Informatique
Lieu : Salle , Campus saint Charles 3 Pl. Victor Hugo, 13003 Marseille
Rapporteurs :
- Monsieur Jean Diatta, Laboratoire d'Informatique et de Mathématiques
- Madame Pascale Kuntz-Cosperec, Laboratoire des Sciences du Numérique de Nantes
Membres du jury :
- Monsieur Pascal Prea, Aix Marseille Université (Directeur de thèse)
- Monsieur Guyslain Naves, LIS (Co-encadrant de thèse)
- Monsieur Victor Chepoi, LIS (Co-directeur de thèse)
- Monsieur Nicolas Nisse, Université Côte d'azur (Président)
- Monsieur Patrice Bertrand, Université Paris Dauphine
- Monsieur Christopher Thraves Caro, Universidad de Concepción
Résumé
En français
Une dissimilarité $d$ sur un ensemble $X$ de taille $n$ est dite de Robinson si sa matrice peut être permutée symétriquement de telle sorte à ce que ses éléments soient rangés dans l'ordre croissant en partant de la diagonale pour toute ligne ou colonne.
Ces dissimilarités sont largement utilisés en sériation et en classification. Elles jouent également un rôle important pour le problème du voyageur de commerce (TSP). Cette thèse porte sur la reconnaissance de ces dissimilarités.
Dans un premier temps, nous donnons deux algorithmes pour reconnaître les dissimilarités Robinson, inspirés par {sf{Quicksort}}, avec des complexités de $O(n^2log n)$ pour le premier et $O(n^3)$ dans le pire des cas, et $O(n^2)$ en moyenne, pour le second.
Ensuite, nous introduisons le concept de emph{module métrique } (emph{mmodule}) dans un espace de Robinson, qui sont des sous-ensembles indiscernables depuis l'extérieur ainsi que les copoints, qui sont des mmodules maximaux ne contenant pas un point donné.
Nous présentons un nouvel algorithme de reconnaissance, utilisant la structure des mmodules et des partitions de copoints qui atteint une reconnaissance optimale en $O(n^2)$.
Nous appliquons enfin ces mmodules à la sériation circulaire stricte. Cela nous a permis d'obtenir un algorithme simple et optimal en$O(n^2)$.
Mots-clés : Robinson, expérimentation, algorithmes.
En anglais
A dissimilarity $d$ on a set $X$ of size $n$ is said to be Robinson if its matrix can be symmetrically permuted so that its elements are arranged in increasing order from the diagonal in every row and column.
These dissimilarities are widely used in seriation and classification and play an important role in the Traveling Salesman Problem (TSP). This thesis focuses on the recognition of these dissimilarities.
Firstly, we present two algorithms to recognize Robinson dissimilarities, inspired by {sf{Quicksort}}, with complexities of $O(n^2log n)$ for the first and $O(n^3)$ in the worst case, and $O(n^2)$ on average, for the second.
Next, we introduce the concept of a emph{metric module} (emph{mmodule}) in a Robinson space, which are subsets that are indistinguishable from the outside, along with copoints, which are maximal mmodules not containing a given point.
We present a new divide-and-conquer algorithm,using the structure of mmodules and copoint partitions to achieve optimal recognition in $O(n^2)$ time.Finally, we apply these mmodules to strict circular seriation. This has led us to develop a simple and optimal algorithm in $O(n^2)$.
Keywords: Robinson, experimentation, algorithms.