Le ranking multipartite est un problème d'apprentissage statistique qui consiste à ordonner les observations qui appartiennent à un espace de grande dimension dans le même ordre que les labels, de sorte que les observations avec le label le plus élevé apparaissent en haut de la liste. Cette thèse vise à comprendre la nature probabiliste du problème de ranking multipartite afin d'obtenir des garanties théoriques pour les algorithmes de ranking. Dans ce cadre, la sortie d'un algorithme de ranking prend la forme d'une fonction de scoring, une fonction qui envoie l'espace des observations sur la droite réelle et l'ordre final est construit en utilisant l'ordre induit par la droite réelle. Les contributions de ce manuscrit sont les suivantes : d'abord, nous nous concentrons sur la caractérisation des solutions optimales de ranking multipartite. Une nouvelle condition sur les rapports de vraisemblance est introduite et jugée nécessaire et suffisante pour rendre le problème de ranking multipartite bien posé. Ensuite, nous examinons les critères pour évaluer la fonction de scoring et on propose d'utiliser une généralisation de la courbe ROC nommée la surface ROC pour cela ainsi que le volume induit par cette surface. Pour être utilisée dans les applications, la contrepartie empirique de la surface ROC est étudiée et les résultats sur sa consistance sont établis. Le deuxième thème de recherche est la conception d'algorithmes pour produire des fonctions de scoring. La première procédure est basée sur l'agrégation des fonctions de scoring apprises sur des sous-problèmes de ranking binaire. Dans le but d'agréger les ordres induits par les fonctions de scoring, nous utilisons une approche métrique basée sur le de Kendall pour trouver une fonction de scoring médiane. La deuxième procédure est une méthode récursive, inspirée par l'algorithme TreeRank qui peut être considéré comme une version pondérée de CART. Une simple modification est proposée pour obtenir une approximation de la surface ROC optimale en utilisant une fonction de scoring constante par morceaux. Ces procédures sont comparées aux algorithmes de l'état de l'art pour le ranking multipartite en utilisant des jeux de données réelles et simulées. Les performances mettent en évidence les cas où nos procédures sont bien adaptées, en particulier lorsque la dimension de l'espace des caractéristiques est beaucoup plus grand que le nombre d'étiquettes. Enfin, nous revenons au problème de ranking binaire afin d'établir des vitesses minimax adaptatives de convergence. Ces vitesses sont montrées pour des classes de distributions contrôlées par la complexité de la distribution a posteriori et une condition de faible bruit. La procédure qui permet d'atteindre ces taux est basée sur des estimateurs de type plug-in de la distribution a posteriori et une méthode d'agrégation utilisant des poids exponentiels.

L'intégration de diverses technologies, notamment celles de l'informatique et l'électronique, fait que les systèmes conçus de nos jours sont de plus en plus complexes. Ils ont des comportements plus élaborés et plus difficiles à prévoir, ont un nombre de constituants en interaction plus important et/ou réalisent des fonctions de plus haut niveau. Parallèlement à cette complexification des systèmes, la compétitivité du marché mondial impose aux développeurs de systèmes des contraintes de coût et de délais de plus en plus strictes. La même course s'opère concernant la qualité des systèmes, notamment lorsque ceux-ci mettent en jeu un risque en vies humaines ou un risque financier important. Ainsi, les développeurs sont contraints d'adopter une approche de conception rigoureuse pour répondre aux exigences du système souhaité et satisfaire les diverses contraintes (coût, délais, qualité, sûreté de fonctionnement,...). Plusieurs démarches méthodologiques visant à guider la conception de système sont définies par l'intermédiaire de normes d'Ingénierie Système. Notre travail s'appuie sur la norme EIA-632, qui est largement employée, en particulier dans les domaines aéronautique et militaire. Il consiste à améliorer les processus d'ingénierie système décrits par l'EIA-632, afin d'intégrer une prise en compte globale et explicite de la sûreté de fonctionnement. En effet, jusqu'à présent la sûreté de fonctionnement était obtenue par la réutilisation de modèles génériques après avoir étudié et développé chaque fonction indépendamment. Il n'y avait donc pas de prise en compte spécifique des risques liés à l'intégration de plusieurs technologies. Pour cette raison, nous proposons de nous intéresser aux exigences de Sûreté de Fonctionnement au niveau global et le plus tôt possible dans la phase de développement, pour ensuite les décliner aux niveaux inférieurs, ceci en s'appuyant sur les processus de la norme EIA-632 que nous étoffons. Nous proposons également une méthode original e de déclinaison d'exigences de sûreté de fonctionnement à base d'arbres de défaillances et d'AMDEC, ainsi qu'un modèle d'information basé sur SysML pour appuyer notre approche. Un exemple issu du monde aéronautique permet d'illustrer nos propositions.

Une coloration des sommets de G s'appelle une b-coloration si chaque classe de couleur contient au moins un sommet qui a un voisin dans toutes les autres classes de couleur. Le nombre b-chromatique b(G) de G est le plus grand entier k pour lequel G a une b-coloration avec k couleurs. Ces notions ont été introduites par Irving et Manlove en 1999. Elles permettent d'évaluer les performances de certains algorithmes de coloration. Irving et Manlove ont montré que le calcul du nombre b-chromatique d'un graphe est un problème NP-difficile et qu'il peut être résolu en temps polynomial pour les arbres. Une question qui se pose naturellement est donc d'enquêter sur les graphes qui ont une structure proche des arbres: cactus, graphes triangulés, graphes série-parallèles, "block" graphes, etc. Dans cette thèse, nous généralisons le résultat d'Irving et Manlove pour les cactus dont le "m-degré" est au moins 7 et pour les graphes planaires extérieurs dont la maille est au moins 8. (Le m-degré m(G) est le plus grand entier d tel que G a au moins d sommets de degré au moins d −1.) Nous démontrons un résultat semblable pour le produit cartésien d'un arbre par une chaîne, un cycle ou une étoile. Pour ce qui concerne les graphes dont les blocs sont des cliques, nous montrons que le problème avec un nombre de couleurs fixé peut être résolu en temps polynomial et nous présentons des cas où le problème de décision peut être résolu. Toutefois, nous avons constaté que la différence m(G)−b(G) peut être arbitrairement grande pour les graphes blocs, ce qui montre qu'avoir une structure arborescence n'est pas suffisant pour que le graphe satisfasse b(G)>= m(G) − 1.

Les peuplements forestiers mélangés subissent moins de dégâts d’insectes herbivores que les peuplements purs, du fait d’une diminution de l’accessibilité à la ressource ou/et d’une amélioration des conditions de survie de leurs ennemis naturels. Pour vérifier ces hypothèses, nous avons étudié un insecte ravageur, la processionnaire du pin (Thaumetopoea pityocampa), et ses insectes parasitoïdes dans le contexte de monoculture de pin maritime (Pinus pinaster) de la forêt des Landes de Gascogne, où persistent localement des zones de milieu ouvert (parefeux, coupes rases) et des boisements d’essences feuillues (haies en bordure de peuplement de pin, ripisylves, îlots). Nous avons pu démontrer que :(1) La colonisation des parcelles de pin par la processionnaire est limitée parla présence de haies de feuillus en lisière de parcelle. En effet, les feuillus jouent un rôle de barrière physique, entravant la détection visuelle des pins par la femelle de processionnaire lorsqu’elle recherche un site d’oviposition.(2) La longévité des principaux parasitoïdes, spécialiste et généraliste, des oeufs de processionnaire est favorisée par la consommation de miel lat produit pardes pucerons du chêne. Cela permet notamment à l’espèce généraliste, qui émergedeux mois avant la processionnaire, de prolonger sa présence dans le milieu et doncd’augmenter sa probabilité de parasiter des pontes de processionnaire.(3) Les chrysalides de processionnaire du pin survivent mieux dans le sol desmilieux ouverts que sous couvert forestier (de pin ou de feuillus), du fait d’unetempérature et d’une humidité plus élevées. L’association de pins et de milieuxouverts favorise la processionnaire par complémentation des habitats, tandis que laprésence de feuillus peut représenter un piège écologique pour les chenilles aumoment de l’enfouissement.(4) À l’échelle du paysage, les peuplements de pin maritime au centre depaysages hétérogènes sont moins infestés que dans les paysages de monoculture.De plus, les niveaux d’infestation de la processionnaire diminuent lorsque laproportion de feuillus dans le paysage environnant augmente.Ces résultats sont interprétés en fonction des mécanismes écologiquesexpliquant la relation entre diversité et herbivorie. Des possibilités de transfert vers lagestion forestière de la forêt des Landes de Gascogne sont proposées, ainsi que desperspectives en termes de recherche scientifique. / Mixed forests are less prone to insect damage than pure forests because ofreduced host accessibility and/or improved control by natural enemies. To test thesehypotheses, we have studied the ecology of the pine processionary moth (PPM)(Thaumetopoea pityocampa) and its parasitoid, in a monoculture of maritime pine(Pinus pinaster) plantations, the Landes de Gascogne forest. There, open areas(firebreaks, clear cuts) and patches of broadleaved woodlands (hedgerows, riparianforest, natural forest remnants) still persist locally. In this study we have shown that:(1) Pine stand colonization by PPM was limited by the presence ofbroadleaved hedgerows at stand edge. Broadleaved trees formed physical barriersdisrupting the visual detection of pine trees by PPM females when searching for anoviposition site.(2) The longevity of the two main PPM egg parasitoids increased whenspecimen were fed with honeydew produced by oak aphids. The generalist species,which emerges two months before PPM, could benefit from this longer lifespan tooverlap its host emergence.(3) PPM pupae survived better in the soil of open areas than under forestcovers (pine or broadleaved trees), because of higher temperature and humidity. Theassociation between pine stands and open areas benefits PPM through habitatcomplementation, whereas the presence of broadleaved trees may act as anecological trap for PPM caterpillars.(4) Maritime pine stands within heterogeneous landscapes exhibited lowerPPM infestations than similar stands within pine monocultures. PPM infestation levelsdecreased with increasing percent broadleaved area in the surrounding landscape.These results are discussed according to the ecological mechanisms whichmay explain the relationship between insect herbivory and tree species diversity.Perspectives for improved PPM management in the Landes de Gascogne forest, andfor further scientific research are proposed.

Nous étudions le déterminant du laplacien sur les fibrés vectoriels sur les graphes et l'utilisons, en lien avec des techniques d'analyse complexe discrète, pour comprendre des modèles de physique statistique. Nous calculons certaines constantes de réseaux, construisons des limites d'échelles d'excursions de la marche aléatoire à boucles effacées sur les surfaces, et étudions certains champs gaussiens et processus déterminantaux. / We study the determinant of the Laplacian on vector bundles on graphs and use it, combined with discrete complex analysis, to study models of statistical physics. We compute exact lattice constants, construct scaling limits for excursions of the loop-erased random walk on surfaces, and study some Gaussian fields and determinantal processes.

L’objet de cette thèse est l’étude de problèmes d’évaluation d’options dans les modèles à volatilité stochastique. La première partie est centrée sur les options américaines dans le modèle de Heston. Nous donnons d’abord une caractérisation analytique de la fonction de valeur d’une option américaine comme l’unique solution du problème d’obstacle parabolique dégénéré associé. Notre approche est basée sur des inéquations variationelles dans des espaces de Sobolev avec poids étendant les résultats récents de Daskalopoulos et Feehan (2011, 2016) et Feehan et Pop (2015). On étudie aussi les propriétés de la fonction de valeur d’une option américaine. En particulier, nous prouvons que, sous des hypothèses convenables sur le payoff, la fonction de valeur est décroissante par rapport à la volatilité. Ensuite nous nous concentrons sur le put américaine et nous étendons quelques résultats qui sont bien connus dans le monde Black-Scholes. En particulier nous prouvons la convexité stricte de la fonction de valeur dans la région de continuation, quelques propriétés de la frontière libre, la formule de Prime d’Exercice Anticipée et une forme faible de la propriété du smooth fit. Les techniques utilisées sont de type probabiliste. Dans la deuxième partie nous abordons le problème du calcul numérique du prix des options européennes et américaines dans des modèles à volatilité stochastiques et avec sauts. Nous étudions d’abord le modèle de Bates-Hull-White, c’est-à-dire le modèle de Bates avec un taux d’intérêt stochastique. On considère un algorithme hybride rétrograde qui utilise une approximation par chaîne de Markov (notamment un arbre “avec sauts multiples”) dans la direction de la volatilité et du taux d’intérêt et une approche (déterministe) par différence finie pour traiter le processus de prix d’actif. De plus, nous fournissons une procédure de simulation pour des évaluations Monte Carlo. Les résultats numériques montrent la fiabilité et l’efficacité de ces méthodes. Finalement, nous analysons le taux de convergence de l’algorithme hybride appliqué à des modèles généraux de diffusion avec sauts. Nous étudions d’abord la convergence faible au premier ordre de chaînes de Markov vers la diffusion sous des hypothèses assez générales. Ensuite nous prouvons la convergence de l’algorithme: nous étudions la stabilité et la consistance de la méthode hybride par une technique qui exploite les caractéristiques probabilistes de l’approximation par chaîne de Markov / We study option pricing problems in stochastic volatility models. In the first part of this thesis we focus on American options in the Heston model. We first give an analytical characterization of the value function of an American option as the unique solution of the associated (degenerate) parabolic obstacle problem. Our approach is based on variational inequalities in suitable weighted Sobolev spaces and extends recent results of Daskalopoulos and Feehan (2011, 2016) and Feehan and Pop (2015). We also investigate the properties of the American value function. In particular, we prove that, under suitable assumptions on the payoff, the value function is nondecreasing with respect to the volatility variable. Then, we focus on an American put option and we extend some results which are well known in the Black and Scholes world. In particular, we prove the strict convexity of the value function in the continuation region, some properties of the free boundary function, the Early Exercise Price formula and a weak form of the smooth fit principle. This is done mostly by using probabilistic techniques.In the second part we deal with the numerical computation of European and American option prices in jump-diffusion stochastic volatility models. We first focus on the Bates-Hull-White model, i.e. the Bates model with a stochastic interest rate. We consider a backward hybrid algorithm which uses a Markov chain approximation (in particular, a “multiple jumps” tree) in the direction of the volatility and the interest rate and a (deterministic) finite-difference approach in order to handle the underlying asset price process. Moreover, we provide a simulation scheme to be used for Monte Carlo evaluations. Numerical results show the reliability and the efficiency of the proposed methods.Finally, we analyze the rate of convergence of the hybrid algorithm applied to general jump-diffusion models. We study first order weak convergence of Markov chains to diffusions under quite general assumptions. Then, we prove the convergence of the algorithm, by studying the stability and the consistency of the hybrid scheme, in a sense that allows us to exploit the probabilistic features of the Markov chain approximation

Dans cette thèse, nous abordons des problèmes NP-difficiles à l'aide de techniques combinatoires, en se focalisant sur le domaine de la complexité paramétrée. Les principaux problèmes que nous considérons sont les problèmes de Multicoupe et d'Arbre Orienté Couvrant avec Beaucoup de Feuilles. La Multicoupe est une généralisation naturelle du très classique problème de coupe, et consiste à séparer un ensemble donné de paires de sommets en supprimant le moins d'arêtes possible dans un graphe. Le problème d'Arbre Orienté Couvrant avec Beaucoup de Feuilles consiste à trouver un arbre couvrant avec le plus de feuilles possible dans un graphe dirigé. Les résultats principaux de cette thèse sont les suivants. Nous montrons que le problème de Multicoupe paramétré par la taille de la solution est FPT (soluble à paramètre fixé), c'est-à-dire que l'existence d'une multicoupe de taille $k$ dans un graphe à $n$ sommets peut être décidée en temps $f(k)*poly(n)$. Nous montrons que Multicoupe dans les arbres admet un noyau polynomial, c'est-à-dire est réductible aux instances de taille polynomiale en $k$. Nous donnons un algorithme en temps $O^*(3.72^k)$ pour le problème d'Arbre Orienté Couvrant avec Beaucoup de Feuilles et le premier algorithme exponentiel exact non trivial (c'est-à-dire meilleur que $2^n$). Nous fournissons aussi un noyau quadratique et une approximation à facteur constant. Ces résultats algorithmiques sont basés sur des résultats combinatoires et des propriétés structurelles qui concernent, entre autres, les décompositions arborescentes, les mineurs, des règles de réduction et les $s-t$ numberings. Nous présentons des résultats combinatoires hors du domaine de la complexité paramétrée: une caractérisation des graphes de cercle Helly comme les graphes de cercle sans diamant induit, et une caractérisation partielle des classes de graphes 2-bel-ordonnées. / This thesis tackles NP-hard problems with combinatorial techniques, focusing on the framework of Fixed-Parameter Tractability. The main problems considered here are Multicut and Maximum Leaf Out-branching. Multicut is a natural generalisation of the cut problem, and consists in simultaneously separating prescribed pairs of vertices by removing as few edges as possible in a graph. Maximum Leaf Out-branching consists in finding a spanning directed tree with as many leaves as possible in a directed graph. The main results of this thesis are the following. We show that Multicut is FPT when parameterized by the solution size, i.e. deciding the existence of a multicut of size $k$ in a graph with $n$ vertices can be done in time $f(k)*poly(n)$. We show that Multicut In Trees admits a polynomial kernel, i.e. can be reduced to instances of size polynomial in $k$. We give an $O^*(3.72^k)$ algorithm for Maximum Leaf Out-branching and the first non-trivial (better than $2^n$) exact algorithm. We also provide a quadratic kernel and a constant factor approximation algorithm. These algorithmic results are based on combinatorial results and structural properties, involving tree decompositions, minors, reduction rules and $s-t$ numberings, among others. We present results obtained with combinatorial techniques outside the scope of parameterized complexity: a characterization of Helly circle graphs as the diamond-free circle graphs, and a partial characterisation of 2-well-quasi-ordered classes of graphs.

Cette thèse se divise en 2 grandes parties indépendantes ; la première traitant des nombres de Jacobi-Stirling, la seconde abordant les nombres d’Entringer. La première partie introduit les nombres de Jacobi-Stirling de seconde et de première espèce comme coefficients algébriques dans des relations polynomiales. Nous donnons des interprétations combinatoires de ces nombres, en termes de partitions d’ensembles et de quasi-permutations pour les nombres de seconde espèce, et en termes de permutations pour les nombres de première espèce. Nous étudions également les fonctions génératrices diagonales de ces familles de nombres, ainsi qu’une de leur généralisation sur le modèle des r-nombres de Stirling. La seconde partie introduit les nombres d’Entringer à l’aide de leur interprétation en termes de permutations alternantes. Nous étudions les différentes formules de récurrence vérifiées par ces nombres et généralisons ces résultats à l’aide d’un q-analogue utilisant la statistique d’inversion. Nous verrons également que ces résultats peuvent être étendus à des permutations de forme donnée quelconque. Enfin, nous définissons la notion de famille d’Entringer, et établissons des bijections entre certaines de ces familles. En particulier, nous établissons une bijection reliant les permutations alternantes de premier terme fixé, aux arbres binaires croissants dont l’extrémité du chemin minimal est fixée. / This thesis is constructed in two main independant parts ; the first one dealing with the numbers of Jacobi-Stirling, the second one tackling the numbers of Entringer. The first part introduces the numbers of Jacobi-Stirling of the second kind and of the first kind, as algebraic coefficients in some polynomial relations. We give some combinatorial interpretations of these numbers, in terms of set partitions and quasi-permutations for the numbers of the second kind, and in terms of permutations for the numbers of the first kind. We also study the diagonal generating functions of these sequences of numbers, and one of their generalization based on the model of r-Stirling numbers. The second part introduces the numbers of Entringer with their interpretation in terms of alternating permutations. We study the different recurrences formulas satisfied by these numbers, and refine these results with a q-analogue using the inversion statistic. We also note that these results can be extend to permutations with any fixed shape. Finally, we define the notion of Entringer family, and provide bijections between some of these families. In particular, we establish a bijection between the alternating permutations with fixed given value, and the binary increasing trees such that the end-point of the minimal path is fixed.

Dans la nature les plantes sont sans cesse soumises à des sollicitations mécaniques qui affectent et modifient leur croissance. Un aspect remarquable de cette réponse est qu’elle n’est pas seulement locale mais non-locale : la flexion d’une tige ou d’une branche inhibe rapidement la croissance loin de la zone sollicitée. Cette observation suggère l'existence d'un signal pouvant se propager à travers toute la plante. Parmi les différentes hypothèses, il a été suggéré que ce signal pouvait être purement mécanique, et provenir d’un couplage hydro/mécanique entre la déformation du tissu et la pression de l’eau contenue dans le système vasculaire de la plante. L’objectif de cette thèse est de comprendre l’origine physique de ce couplage par une approche biomimétique. Pour cela, nous avons développé des branches artificielles micro-fluidiques possédant des caractéristiques mécaniques et hydrauliques similaires à celles d'une branche d'arbre. Nous avons montré que la flexion de ces branches génère une surpression globale non-nulle dans le système, qui varie comme le carré de la déformation longitudinale. Un modèle simple basé sur un mécanisme analogue à l’ovalisation des tubes permet de prédire cette réponse poroélastique non-linéaire et d’identifier le paramètre physique clé pilotant cette réponse en pression : le module de compressibilité de la branche. A la lumière de ces résultats, des expériences sur des branches d'arbre ont ensuite été conduites et des signaux similaires sont obtenus et comparés au modèle théorique. La similitude suggère le caractère générique du mécanisme physique identifié pour la génération de signaux hydraulique dans les plantes. / Plants are constantly subjected to external mechanical loads such as wind or touch and respond to these stimuli by modifying their growth and development. A fascinating feature of this mechanical-induced-growth response is that it is not only local, but also non-local: bending locally a stem or a branch can induce a very rapid modification of the growth far away from the stimulated area, suggesting the existence of a signal that propagates across the whole plant. The nature and origin of this signal is still not understood, but it has been suggested recently that it could be purely mechanical and originate from the coupling between the local deformation of the tissues and the water pressure in the vascular system. The objective of this work is to understand the origin of this hydro/mechanical coupling using a biomimetic approach. Artificial microfluidic branches have been developed, that incorporate the mechanical and hydraulic key features of natural ones. We show that the bending of these branches generates a steady overpressure in the whole system, which varies quadratically with the bending deformation. A simple model based on a mechanism analogue to tube ovalization enables us to predict this non-linear poroelastic response, and identify the key physical parameter at play, namely the elastic bulk modulus of the branch. Further experiments conducted on natural tree branches reveal the same phenomenology. Once rescaled by the model prediction, both the biomimetic and natural branches falls on the same master curve, showing the universality of the identified mechanism for the generation of hydraulic signals in plants.

La problématique de la reconnaissance de formes manuscrites est particulièrement riche et complexe. Il existe en effet un grand nombre de problèmes différents à traiter dans lesquels les formes à reconnaître sont nombreuses, soumises à une variabilité importante et donc sources de confusions. De plus, les contraintes applicatives, et notamment celles résultant de la volonté de diffusion des moyens informatiques au travers de l'informatique nomade (PDA, smart phone...), font que la conception et l'adaptation de systèmes de reconnaissance à des contextes précis d'utilisation sont particulièrement délicats.<br /><br />Pour faciliter cette mise au point nous proposons une méthodologie de classification visant à réunir un ensemble de propriétés rarement satisfaites dans une même approche : performances, généricité, fiabilité, robustesse, compacité et interprétabilité. Ce dernier point est particulièrement important puisqu'il permet au concepteur d'adapter, de maintenir et d'optimiser le système plus facilement. L'approche proposée, centrée sur la notion de connaissances dans un classifieur, est entièrement guidée par les données. L'originalité réside notamment dans l'exploitation conjointe de connaissances intrinsèques et discriminantes extraites automatiquement et organisées sur deux niveaux pour bénéficier au mieux de leur complémentarité. Le premier niveaux modélise les classes de façon explicite par des prototypes flous. Ceux-ci sont notamment utilisés pour décomposer le problème initial en sous-problèmes dans lesquels les formes possèdant des propriétés intrinsèques similaires sont regroupées. Le second niveau effectue ensuite une discrimination ciblée sur ces sous-problèmes par des arbres de décision flous. L'ensemble est formalisé de façon homogène par des systèmes d'inférence floue qui sont combinés pour la classification.<br /><br />Cette approche a conduit à la réalisation du système Mélidis qui a été validé sur plusieurs benchmarks dont des problèmes de reconnaissance de caractères manuscrits en ligne.