Les systèmes de vélos en libre-service ont connu ces dernières années un développement sans précédent. Bien que les premières tentatives de mise en place remontent aux années 60, l'arrivée de technologies permettant un suivi des différents véhicules mis à la disposition du grand public et de l'état des bornes de stationnement en temps réel a rendu ces systèmes plus attractifs. Plus de 200 villes disposent de tels systèmes et cette tendance se poursuit avec l'entrée en fonctionnement du système de New York prévue pour l'été 2012. La fin de l'année 2011 a été marquée par l'arrivée d'un nouvel avatar de ce type de transport avec la mise en place d'Autolib à Paris. L'objectif de cette thèse est de proposer des algorithmes d'aide à la décision pour l'optimisation de réseaux de transport en libre-service. L'exploitation de ces systèmes, qui fleurissent actuellement un peu partout dans le monde, pose en effet de nombreux problèmes, l'un des plus cruciaux étant celui de la régulation. Cette dernière a pour objectif de maintenir dans chaque station un nombre de vélos ni trop faible, ni trop élevé, afin de satisfaire au mieux la demande. Cette régulation se fait souvent par le biais de camions qui effectuent des tournées sur le réseau. Il apparaît rapidement que la question d'une régulation optimale à l'aide d'une flotte fixée de camions est une question difficile. La thèse est divisée en deux parties. Dans la première partie, le cas "statique" est considéré. Les déplacements de véhicules dus aux usagers sont négligés. Cela traduit la situation la nuit ou lorsque le système est fermé à la location. L'opérateur doit redistribuer les véhicules afin que ceux-ci soient disposés selon une répartition définie. Les problèmes de rééquilibrage avec un ou plusieurs camions sont traités. Pour chacun des deux cas, un algorithme est proposé et utilisé pour résoudre des instances de tailles variées. La seconde partie traite du cas "dynamique" dans lequel les utilisateurs interagissent avec le système. Afin d'étudier ce système complexe, un simulateur a été développé. Il est utilisé pour comparer différentes stratégies de redistribution des véhicules. Certaines utilisent des camions se déplaçant dans la ville pendant la journée. D'autres tentent d'organiser une régulation intrinsèque du système par le biais d'une politique d'incitation : des prix mis à jour régulièrement encouragent les usagers à rendre leur véhicule dans certaines stations. Enfin, si on choisit de ne pas utiliser de camion durant la journée, la question de la détermination du nombre optimal de véhicules à disposer à chaque station se pose. Deux méthodes de recherche locale visant à minimiser le temps total perdu par les usagers sont présentées. Les résultats obtenus peuvent servir pour la définition des répartitions cibles de la première partie.

Nous abordons les automates cellulaires (AC) en cherchant à dégager des informations quantitatives et en particulier à préciser les comportements répandus. Nous étudions en guise de prélude des AC présentant une forte symétrie de la règle locale (AC dits multi-ensemblistes). Les règles locales qui les définissent ont la propriété de pouvoir être utilisées facilement pour différente tailles de voisinage, et nous exhibons des règles, pour chaque dimension, qui sont universelles pour une infinité de tailles. Nous formalisons ensuite la notion de densité d'une propriété parmi l'ensemble des AC. En remarquant que les propriétés répandues sont liées aux propriétés des objets aléatoires au sens de Kolmogorov, et en utilisant divers outils combinatoires nous montrons la négligeabilité (au sens quantitatif) de propriétés non seulement syntaxiques (injectivité, surjectivité, présence d'états persistants ou envahissants), mais aussi dynamiques (nilpotence, certaines contraintes sur l'ensemble limite...). Et nous montrons à l'opposé que l'universalité intrinsèque , propriété qui semble à priori exigeante, est pour de nombreuses sous-familles une propriété très répandue. En ce qui concerne le comportement typique à long terme d'un AC fixé, la mu-nipotence, que nous introduisons à partir de la notion d'ensembles mu-limites, permet de caractériser les AC convergeant presque toujours vers une configuration unique. Nous montrons que celle-ci n'est ni récursivement énumérable ni co-récursivement énumérable. Ceci montre que la difficulté calculatoire de la prédiction du comportement à long terme des AC n'est pas due à des ensembles de configurations négligeables. Nous exhibons aussi des ensembles mu-limites aux langages non récursifs. Enfin nous montrons des résultats d'existence et de non-existence d'AC universels pour la relation de simulation dite surjective parmi certaines sous-familles.

Almost every theory of mathematics has its discrete counterpart that makes it conceptually easier to understand and practically easier to use in the modeling process of real world problems. For instance, one can take the "difference" of any function, from 1st order up to the n-th order with discrete calculus. However, it is also possible to extend this theory by means of discrete fractional calculus and make n- any real number such that the ½-th order difference is well defined. This thesis is comprised of five chapters that demonstrate some basic definitions and properties of discrete fractional calculus while developing the simplest discrete fractional variational theory. Some applications of the theory to tumor growth are also studied. The first chapter is a brief introduction to discrete fractional calculus that presents some important mathematical functions widely used in the theory. The second chapter shows the main fractional difference and sum operators as well as their important properties. In the third chapter, a new proof for Leibniz formula is given and summation by parts for discrete fractional calculus is stated and proved. The simplest variational problem in discrete calculus and the related Euler-Lagrange equation are developed in the fourth chapter. In the fifth chapter, the fractional Gompertz difference equation is introduced. First, the existence and uniqueness of the solution is shown and then the equation is solved by the method of successive approximation. Finally, applications of the theory to tumor and bacterial growth are presented.

<p>Interactions between combinatorics and statistical mechanics have provided many fruitful insights in both fields. A compelling example is Kuperberg’s solution to the alternating sign matrix conjecture, and its following generalisations. In this thesis we investigate two models from statistical mechanics which have received attention in recent years.</p><p>The first is the fully packed loop model. A conjecture from 2001 by Razumov and Stroganov opened the field for a large ongoing investigation of the O(1) loop model and its connections to a refinement of the fully packed loop model. We apply a combinatorial bijection originally found by de Gier to an older conjecture made by Propp.</p><p>The second model is the hard particle model. Recent discoveries by Fendley et al. and results by Jonsson suggests that the hard square model with cylindrical boundary conditions possess some beautiful combinatorial properties. We apply both topological and purely combinatorial methods to related independence complexes to try and gain a better understanding of this model.</p>

Dans cette thèse, nous considérons des questions relatives aux homomorphismes de quatre types distincts de graphes : les graphes orientés, les graphes orientables, les graphes 2-arête colorés et les graphes signés. Pour chacun des ces quatre types, nous cherchons à déterminer le nombre chromatique, le nombre de clique relatif et le nombre de clique absolu pour différentes familles de graphes planaires : les graphes planaires extérieurs, les graphes planaires extérieurs de maille fixée, les graphes planaires et les graphes planaires de maille fixée. Nous étudions également les étiquetages "2-dipath" et "L(p,q)" des graphes orientés et considérons les catégories des graphes orientables et des graphes signés. Nous étudions enfin les différentes relations pouvant exister entre ces quatre types d'homomorphismes de graphes.

Ce manuscrit d'Habilitation à diriger des recherches décrit mes travaux de recherche récents en théorie des graphes et en théorie des jeux combinatoires. Une première partie est consacrée à l'étude de paramètres de graphes en s'intéressant particulièrement aux contraintes structurelles qui permettent d'améliorer les bornes connues. Dans cette partie, nous traitons notamment la paire-domination, la domination indépendante mais aussi les partitions en cographes et les colorations quasi propres. Une deuxième partie traite de la domination de puissance, une forme itérative de la domination au sujet de laquelle nous proposons un début de synthèse des résultats existants. Enfin, une troisème partie parle de jeux. Nous y traitons d'abord le travail réalisé sur quelques conjectures portant sur un jeu de domino, puis au sujet des jeux en version misère. Nous y parlons enfin du jeu de domination, qui est à l'interface entre le paramètre de graphe et le jeu combinatoire.

Cette HDR présente mes travaux récents en combinatoire (énumérative et algébrique) autour du groupe symétrique, et répartis sur trois axes principaux : les co-quasi-invariants polynomiaux, les matrices à signes alternants et les tableaux boisés.

Dans cette thèse, nous explorons de nouvelles méthodes d'analyse d'images pour la détection précoce des changements métaboliques cérébraux causés par la maladie d'Alzheimer (MA). Nous introduisons deux apports méthodologiques que nous appliquons à un ensemble de données réelles. Le premier est basé sur l'apprentissage automatique pour créer une carte des informations de classification pertinente dans un ensemble d'images. Pour cela nous échantillonnons des blocs de voxels de l'image selon un algorithme de Monte-Carlo. La mise en oeuvre d'une classification basée sur ces patchs 3D a pour conséquence importante la réduction significative du volume de patchs à traiter, et l'extraction de caractéristiques dont l'importance est statistiquement quantifiable. Cette méthode s'applique à différentes caractéristiques de l'image et donc est adaptée à des types d'images très variés. La résolution des cartes produites par cette méthode peut être affinée à volonté et leur contenu informatif est cohérent avec les résultats antérieurs basés sur les statistiques sur les voxels obtenus dans la littérature. Le second apport méthodologique porte sur la conception d'un nouvel algorithme de décomposition de tenseur d'ordre important, adapté à notre application. Cet algorithme permet de réduire considérablement la consommation de mémoire et donc évite la surcharge de la mémoire. Il autorise la décomposition rapide de tenseurs, y compris ceux de dimensions très déséquilibrées. Nous appliquons cet algorithme en tant que méthode d'extraction de caractéristiques dans une situation où le clinicien doit diagnostiquer des stades MA précoce ou MCI (Mild Cognitive Impairment) en utilisant la TEP FDG seule. Les taux de classification obtenus sont souvent au-dessus des niveaux de l'état de l'art. Dans le cadre de ces tâches d'analyse d'images, nous présentons notre source de données, les scans de patients retenus et les pré-traitements réalisés. Les principaux aspects que nous voulons prendre en compte sont la nature volumétrique des données, l'information a priori disponible sur la localisation des changements métaboliques et comment l'identification des zones de changements métaboliques participe à la réduction de la quantité de données à analyser et d'extraire des caractéristiques discriminantes. Les méthodes présentées fournissent des informations précises sur la localisation de ces changements métaboliques. Les taux de classification allant jusqu'à 92,6% pour MA et 83,8% pour MCI. En outre, nous sommes capables de séparer les patients MCI stables des MCI patients évoluant vers la MA dans les 2 ans après l'acquisition du PET-scan avec un taux de classification de 84.7%. Ce sont des étapes importantes vers une détection fiable et précoce de la MA.

This thesis studies a problem that has been proposed as a novel way to disrupt communication networks: the load maximization problem. The load on a member of a network represents the amount of communication that the member is forced to be involved in. By maximizing the load on an important member of the network, we hope to increase that member's visibility and susceptibility to capture. In this thesis we characterize load as a combinatorial property of graphs and expose possible connections between load and spectral graph theory. We specifically describe the load and how it changes in several canonical classes of graphs and determine the range of values that the load can take on. We also consider a connection between load and liquid paint flow and use this connection to build a heuristic solver for the load maximization problem. We conclude with a detailed discussion of open questions for future work.

In this workshop, we present a model of problem that we call Research Situation for the Classroom (RSC). The aim of a RSC is to put students in a role close to a mathematical researcher in order to make them work on mathematical thinking/skills. A RSC has some characteristics : the problem is close to a research one, the statement is an easy understandable question, school knowledge are elementary, there is no end, a solved question postponed to new questions... The most important characteristic of a RSC is that students can manage their research by fixing themselves some variable of the problem. So, a RSC is completely different from a problem that students usually do in France. For short : there is no final answer, students can try to resolve their own questions : a RSC is a large open field where many sub-problems exist; the goal for the students is not to apply a technique: the goal is, as for a researcher, to search. These type of situations are particularly interesting to develop problem solving skills and mathematical thinking. They can also let students discover that mathematics are “alive” and “realistic”. This workshop will be split into two parts. First, we propose to put people in the situation of solving a RSC to make them discover practically what is it. After, we present the model of a RSC and some results of our experimentations.