ED Mathématiques et Informatique
Résultats d'impossibilité pour les graphes universels
par Amaury JACQUES (LaBRI - Laboratoire Bordelais de Recherche en Informatique)
Cette soutenance a lieu à 14h30 - Amphithéâtre 351 Cours de la libération, LaBRI, Université de Bordeaux, 33405 Talence
devant le jury composé de
- Cyril GAVOILLE - Professeur des universités - Université de Bordeaux - Directeur de these
- Nicolas NISSE - Directeur de recherche - Centre Inria d'Université Côte d'Azur - Rapporteur
- Édouard BONNET - Chargé de recherche - LIP, ENS de Lyon, CNRS - Rapporteur
- Arnaud LABOUREL - Maître de conférences - LIS, Aix-Marseille Université - Examinateur
- Caroline BROSSE - Maîtresse de conférences - LIFO, Université d'Orléans - Examinateur
- François PELLEGRINI - Professeur des universités - Université de Bordeaux - Examinateur
Dans cette thèse, nous nous sommes intéressés à la représentation des graphes à travers le problème de graphes universels. Un graphe est une abstraction permettant de représenter les interconnexions entre différents objets, ces objets sont appelés sommets et leurs connexions sont elles des arrêtes. Il est classique de représenter les graphes sous forme de tableau ou sous forme de liste d'adjacences des sommets. Ces représentations classiques sont à la base de l'algorithmique des graphes, essentielle dans de nombreux domaines comme les télécommunications, l'électronique ou l'informatique. Cependant, dans certains contextes particuliers tels que l'algorithmique distribuée, des contraintes d'espace et de nombre de communications poussent à utiliser des représentations plus compactes et dites implicites. Les schémas d'étiquetage répondent à cette problématique. Un schéma d'étiquetage d'adjacence est, pour une famille de graphes, une assignation d'étiquettes aux sommets des graphes de la famille de sorte que, à partir d'une paire de celles-ci, et sans aucune autre information, il soit possible de déterminer si les sommets correspondants sont adjacents ou non. L'objectif est alors de minimiser la taille de ces étiquettes. Nous nous sommes intéressés à ce problème plus particulièrement à travers un problème correspondant qui est celui des graphes universels induits et de leur nombre minimal de sommets. Un graphe universel induit pour une famille de graphes contient comme sous-graphes induit, c'est-à-dire, en sélectionnant uniquement un sous-ensemble de sommets du graphes et toutes les arêtes qui les connectent, l'ensemble des graphes de la famille. Les principaux résultats de cette thèse portent sur l'impossibilité de construire des graphes universels induits pour certaines familles de graphes en utilisant moins qu'un certain nombre de sommets. Ces résultats assez généraux permettent de donner des bornes inférieures pour les familles à partir de leur caractéristiques telles que le nombre de graphes de la famille ou la présence d'unions de graphes complets d'une certaine taille dans la famille. Nous avons également étudié le nombre de graphes nécessaires pour améliorer ces bornes inférieures, cela a été réalisé à l'aide d'une construction de graphe universel induit pour des petites familles de graphes, en particulier les sous-familles de graphes closes par mineur tels que les graphes planaires. Nous présentons également des constructions de graphes universels induits pour différentes familles comme les forêts d'étoiles, et les unions de graphes complets. Pour ces derniers, la construction que nous proposons est optimale en nombre de sommets. Finalement, nous présentons des résultats de complexité pour les graphes universels induits de taille minimale et nous généralisons ces résultats à d'autres types de graphes universels
ED Sciences Physiques et de l'Ingénieur
Simulations numériques du mouvement brownien dans des environnements complexes
par Juliette LACHEREZ (Laboratoire Ondes et Matière d'Aquitaine)
Cette soutenance a lieu à 14h15 - Salle A Université de Bordeaux, Bâtiment A29, 351 cours de la Libération, 33400 Talence
devant le jury composé de
- Thomas SALEZ - Directeur de recherche - Université de Bordeaux - Directeur de these
- Chantal VALERIANI - Professeure associée - Universidad Complutense de Madrid - Rapporteur
- Demian LEVIS - Professeur associé - Universitat de Barcelona - Rapporteur
- Christine GRAUBY-HEYWANG - Professeure des universités - Université de Bordeaux - Examinateur
- Marco ELLERO - Professeur - Basque center for Applied Mathematics - Examinateur
Il est des phénomènes en physique que l'on retrouve dans de nombreux systèmes, mais dont la description formelle et exacte n'est jamais vraiment atteinte. Le mouvement brownien, processus par lequel les petites particules explorent l'espace qui leur est disponible sous l'effet de l'agitation thermique des molécules du fluide environnant, compte parmi ces notions. Depuis son observation en 1827, puis sa formalisation théorique et sa confirmation expérimentale dans un cas idéal très simple au début des années 1900, la communauté scientifique n'a cessé d'approfondir la compréhension des interactions entre processus browniens et confinement, qu'il soit rigide ou déformable. S'y ajoutent les écoulements visqueux, l'activité propre de la particule dans le cas d'un organisme vivant, ou encore les interactions hydrodynamiques entre particules. Chacun de ces cas d'étude présente toutefois des limitations : le couplage entre mobilité confinée et déformabilité de l'interface reste mal quantifié, l'effet conjoint de l'encombrement et de la proximité d'un mur sur la diffusion est rarement traité dans son ensemble, et l'extension des théories de dispersion classiques aux solutés actifs restait jusqu'ici largement ouverte. Mes travaux de thèse mobilisent l'outil numérique pour avancer sur ces trois fronts. Je présente une étude théorique et numérique du mouvement brownien à proximité d'une interface molle et fluctuante, l'analyse de la modification de la diffusion par la présence d'autres colloïdes et d'un mur à proximité immédiate du colloïde d'intérêt, et l'extension de la théorie de Taylor-Aris sur la dispersion d'un soluté en écoulement aux solutés actifs. Ces développements permettent d'appréhender plus finement le comportement de systèmes microbiologiques où le confinement, parfois lui-même fluctuant, modifie drastiquement la mobilité, où l'activité est inhérente, et où l'encombrement perturbe la dynamique. Ayant isolé les effets propres à chacun de ces éléments, leur couplage devient envisageable pour étudier, par comparaison, des systèmes réels.