Cette thèse est consacrée à l’étude de certains processus affines d’un point de vue théorique ainsi que appliqué par le biais d’applications en mathématiques actuarielles. Les processus affines sont des processus markoviens homogènes dont la transformée de Laplace du semi-groupe admet une structure exponentielle affine en son état initial. En vertu de leur riche structure, ces processus trouvent de nombreuses applications en biologie, physique et en mathématique de l’économie. Dans le chapitre 1, nous considérons les processus CBI (Continuous state Branching with Immigration) qui correspondent à un exemple de processus affines à valeurs dans la demi- droite réelle positive. Notre objectif dans ce chapitre consiste à étudier la transformée de Laplace du temps d’atteinte de ces processus à un niveau donné. Notre approche est basée sur un récent développement de Patie and Vigon [2015] concernant la théorie du potentiel pour la classe des processus de Markov complètement asymétriques à valeurs dans la droite réelle. Dans un premier temps, cette approche originale nous permet de donner une expression pour la transformée de Laplace du premier temps d’atteinte d’un niveau qui se trouve en dessous du point de départ du processus et ainsi de retrouver par une approche plus générale le résultat récemment obtenu par Duhalde et al. [2014]. Dans un deuxième temps, nous nous intéressons au cas où le niveau à atteindre se trouve au-dessus du point de départ du processus. Dans ce cadre, la situation est plus compliquée puisque le processus admet des sauts positifs. Néanmoins, nous sommes capable de donner une expression pour la transformée de Laplace de ce temps d’atteinte. Dans le chapitre 2, nous considérons les processus Wishart qui correspondent à un exemple de processus affines à valeurs dans le cône des matrices symétriques semi-définies positives. Plus précisément, nous considérons des processus de Wishart sans retour à la moyenne et nous étudions le problème de déterminer le plus petit instant tel que la transformée de Laplace du processus et/ou son intégrale devienne infinie. Le problème de déterminer le domaine maximal d’existence d’une transformée de Laplace est une préoccupation importante et cruciale, pas seulement d’un point de vue théorique, mais surtout pour des raisons pratiques liées à l’implémentation numérique. Sous une faible hypothèse de commutativité, nous obtenons le temps d’explosion de la transformée de Laplace jointe. Cette hypothèse disparaît lorsque l’on s’intéresse aux temps d’explosion de la transformée de Laplace de l’intégrale du processus ou du processus seul. De plus, nous expliquons le comportement du temps d’explosion en terme du rôle de la corrélation entre les facteurs positifs, ce qui va au-delà des résultats unidimensionnels que l’on peut retrouver dans la littérature. Dans le chapitre 3, nous considérons des modèles affines où une structure de dépendance entre les taux de mortalité et d’intérêt existe. Nous nous concentrons sur deux sortes de modèles. Le premier modèle suppose que les dynamiques de la mortalité et du processus de taux d’intérêt sont conduits par un processus de Cox-Ingersoll-Ross (CIR) multidimensionnel et le second par un processus de Wishart. Dans ce contexte, nos objectifs consistent à déterminer des formules pour les prix de certains contrats d’assurance tels que les options annuités garanties ainsi que d’étudier l’influence d’une structure de dépendance sur ces prix. En suivant la méthodologie introduite par Jalen and Mamon [2009], nous commençons par dériver une formule pour le prix de ces contrats. Ensuite, nous étudions la sensibilité du prix de ces contrats par rapport à la structure de dépendance entre les taux de mortalité et d’intérêt. Nous observons que dans un modèle affine général comme le modèle de Wishart qui permet de reproduire une structure de dépendance stochastique et plus riche entre les taux de mortalité et d’intérêt, plusieurs scénarios pour les prix peuvent être reproduits. / Doctorat en Sciences / info:eu-repo/semantics/nonPublished

Title: Baseball modifications for kids and their comparison Objectives: The goal of this project is to compare, via a two tier method, modified version of baseball for kids, T-ball and Coachpitch. First goal is a comparison of a course of a T-ball and a Coachpitch game - analysis and evaluation of games and their respective scorecards , with the aim of extracting information about the course and the character of the game in both of these modifications. Second goal is an analysis of a cinematic footage of a baseball swing and analysis of differences in mechanics between hitting against a Coachpitch delivery and hitting off a tee in T-ball. On the data extracted from the first two steps, evaluation of benefits of each of these baseball modifications follows. Methods: This research is a case study of a descriptive character in which a large amount of data from 11 individuals is collected. Video footage of 11 research subjects was created for swing motion in both baseball modifications. Video footage was thereafter evaluated via computer programme Dartfish. Extracted data was afterwards analysed via a one-way analysis of variance method. In the second part of the thesis, evaluation of the modified scorecards and subsequent transfer of these scorecards into statistical data is used. Results: Thesis...

This dissertation studies the pricing of Outside barrier call options, when their activation starts at a hitting time. The pricing of Outside barrier options when their activation starts at time zero, and the pricing of standard barrier options when their activation starts at a hitting time of a pre speci ed barrier level, have been studied previously (see [21], [24]). The new work that this dissertation will do is to price Outside barrier call options, where they will be activated when the triggering asset crosses or hits a pre speci ed barrier level, and also the pricing of Outside barrier call options where they will be activated when the triggering asset crosses or hits a sequence of two pre specifed barrier levels. Closed form solutions are derived using Girsanov's theorem and the re ection principle. Existing results are derived from the new results, and properties of the new results are illustrated numerically and discussed. / Mathematical Sciences / M. Sc. (Applied Mathematics)

Dans cette thèse, nous étudions des problèmes de transversaux d'un point de vue tant algorithmique que combinatoire. Etant donné un hypergraphe, un transversal est un ensemble de sommets qui touche toutes les hyperarêtes. Un packing est un ensemble d'hyperarêtes deux à deux disjointes. Alors que la taille minimale d'un transversal est au moins égale à la taille maximale d'un packing on ne peut pas dans le cas général borner la taille minimale d'un transversal par une fonction du packing maximal. Dans un premier temps, un état de l'art rappelle les différentes conditions qui assurent l'existence de bornes supérieures sur la taille des transversaux, en particulier en fonction de la taille d'un packing. La plupart d'entre elles sont valables lorsque la VC-dimension de Vapnik-Chervonenkis de l'hypergraphe, est bornée. L'originalité de la thèse consiste à utiliser ces outils d'hypergraphes pour obtenir des résultats sur des problèmes de graphes. Nous prouvons notamment une conjecture de coloration de Scott dans le cas des graphes sans-triangle maximaux; ensuite, nous généralisons un résultat de Chepoi, Estellon et Vaxès traitant de domination à grande distance; enfin nous nous attaquons à une conjecture de Yannakakis sur la séparation des cliques et des stables d'un graphe.Dans un second temps, nous étudions les transversaux d'un point de vue algorithmique. On se concentre plus particulièrement sur les problèmes de séparation de graphe où on cherche des transversaux à un ensemble de chemin. En combinant des outils de connexité, les séparateurs importants et le théorème de Dilworth, nous obtenons un algorithme FPT pour le problème Multicut paramétré par la taille de la solution. / In this manuscript we study hitting sets both from a combinatorial and from an algorithmic point of view. A hitting set is a subset of vertices of a hypergraph which intersects all the hyperedges. A packing is a subset of pairwise disjoint hyperedges. In the general case, there is no function linking the minimum size of a hitting set and a maximum size of a packing.The first part of this thesis is devoted to present upper bounds on the size of hitting sets, in particular this upper bounds are expressed in the size of the maximum packing. Most of them are satisfied when the dimension of Vapnik-Chervonenkis of the hypergraph is bounded. The originality of this thesis consists in using these hypergraph tools in order to obtain several results on graph problems. First we prove that a conjecture of Scott holds for maximal triangle-free graphs. Then we generalize a result of Chepoi, Estellon and Vaxès on dominating sets at large distance. We finally study a conjecture of Yannakakis and prove that it holds for several graph subclasses using VC-dimension.The second part of this thesis explores algorithmic aspects of hitting sets. More precisely we focus on parameterized complexity of graph separation problems where we are looking for hitting sets of a set of paths. Combining connectivity tools, important separator technique and Dilworth's theorem, we design an FPT algorithm for the Multicut problem parameterized by the size of the solution.

The minimum set cover problem is, without question, among the most ubiquitous and well-studied problems in computer science. Its theoretical hardness has been fully characterized--logarithmic approximability has been established, and no sublogarithmic approximation exists unless P=NP. However, the gap between real-world instances and the theoretical worst case is often immense--many covering problems of practical relevance admit much better approximations, or even solvability in polynomial time. Simple combinatorial or geometric structure can often be exploited to obtain improved algorithms on a problem-by-problem basis, but there is no general method of determining the extent to which this is possible. In this thesis, we aim to shed light on the relationship between the structure and the hardness of covering problems. We discuss several measures of structural complexity of set cover instances and prove new algorithmic and hardness results linking the approximability of a set cover problem to its underlying structure. In particular, we provide: - An APX-hardness proof for a wide family of problems that encode a simple covering problem known as Special-3SC. - A class of polynomial dynamic programming algorithms for a group of weighted geometric set cover problems having simple structure. - A simplified quasi-uniform sampling algorithm that yields improved approximations for weighted covering problems having low cell complexity or geometric union complexity. - Applications of the above to various capacitated covering problems via linear programming strengthening and rounding. In total, we obtain new results for dozens of covering problems exhibiting geometric or combinatorial structure. We tabulate these problems and classify them according to their approximability.

In this manuscript we study hitting sets both from a combinatorial and from an algorithmic point of view. A hitting set is a subset of vertices of a hypergraph which intersects all the hyperedges. A packing is a subset of pairwise disjoint hyperedges. In the general case, there is no function linking the minimum size of a hitting set and a maximum size of a packing.The first part of this thesis is devoted to present upper bounds on the size of hitting sets, in particular this upper bounds are expressed in the size of the maximum packing. Most of them are satisfied when the dimension of Vapnik-Chervonenkis of the hypergraph is bounded. The originality of this thesis consists in using these hypergraph tools in order to obtain several results on graph problems. First we prove that a conjecture of Scott holds for maximal triangle-free graphs. Then we generalize a result of Chepoi, Estellon and Vaxès on dominating sets at large distance. We finally study a conjecture of Yannakakis and prove that it holds for several graph subclasses using VC-dimension.The second part of this thesis explores algorithmic aspects of hitting sets. More precisely we focus on parameterized complexity of graph separation problems where we are looking for hitting sets of a set of paths. Combining connectivity tools, important separator technique and Dilworth's theorem, we design an FPT algorithm for the Multicut problem parameterized by the size of the solution.

The minimum set cover problem is, without question, among the most ubiquitous and well-studied problems in computer science. Its theoretical hardness has been fully characterized--logarithmic approximability has been established, and no sublogarithmic approximation exists unless P=NP. However, the gap between real-world instances and the theoretical worst case is often immense--many covering problems of practical relevance admit much better approximations, or even solvability in polynomial time. Simple combinatorial or geometric structure can often be exploited to obtain improved algorithms on a problem-by-problem basis, but there is no general method of determining the extent to which this is possible. In this thesis, we aim to shed light on the relationship between the structure and the hardness of covering problems. We discuss several measures of structural complexity of set cover instances and prove new algorithmic and hardness results linking the approximability of a set cover problem to its underlying structure. In particular, we provide: - An APX-hardness proof for a wide family of problems that encode a simple covering problem known as Special-3SC. - A class of polynomial dynamic programming algorithms for a group of weighted geometric set cover problems having simple structure. - A simplified quasi-uniform sampling algorithm that yields improved approximations for weighted covering problems having low cell complexity or geometric union complexity. - Applications of the above to various capacitated covering problems via linear programming strengthening and rounding. In total, we obtain new results for dozens of covering problems exhibiting geometric or combinatorial structure. We tabulate these problems and classify them according to their approximability.

This dissertation studies the pricing of Outside barrier call options, when their activation starts at a hitting time. The pricing of Outside barrier options when their activation starts at time zero, and the pricing of standard barrier options when their activation starts at a hitting time of a pre speci ed barrier level, have been studied previously (see [21], [24]). The new work that this dissertation will do is to price Outside barrier call options, where they will be activated when the triggering asset crosses or hits a pre speci ed barrier level, and also the pricing of Outside barrier call options where they will be activated when the triggering asset crosses or hits a sequence of two pre specifed barrier levels. Closed form solutions are derived using Girsanov's theorem and the re ection principle. Existing results are derived from the new results, and properties of the new results are illustrated numerically and discussed. / Mathematical Sciences / M. Sc. (Applied Mathematics)

Orientador: Prof. Dr. Luiz Carlos da Silva Rozante / Dissertação (mestrado) - Universidade Federal do ABC, Programa de Pós-Graduação em Ciência da Computação, 2015. / A inferência de redes de regulação gênica é um dos problemas cruciais no campo de Biologia de Sistemas. É ainda um problema em aberto, principalmente devido à alta dimensionalidade (milhares de genes) com um número limitado de amostras (dezenas), tornando difícil estimar dependências entre genes. Além do problema de estimação, outro obstáculo é a inerente complexidade computacional dos métodos de inferência de GRNs. Este trabalho teve como foco contornar problemas de desempenho de uma técnica baseada em perturbação de sinais para inferir dependências entre genes. Um dos passos principais consiste em resolver o problema da Transversal Mínima (do Inglês Hitting Set, ou HSP), o qual é NPDifícil. Existem diversas propostas para se obter soluções aproximadas ou exatas para esse problema. Uma dessas propostas consiste em um algoritmo baseado em GPU (Graphical Processing Unit) para se obter as soluções exatas do HSP. Entretanto, tal método não é escalável para GRNs de tamanho real. Foi proposto nesse trabalho, portanto, uma extensão desse algoritmo para resolver o HSP, que é capaz de lidar com conjuntos de entrada contendomilhares de variáveis, pela introdução de inovações nas estruturas de dados e um mecanismo de ordenação que permite um descarte eficiente de candidatos que não são solução do HSP. Foi provida uma implementação em CPU multi-core e em clusters de GPU. Os resultados experimentais mostraram que o uso do mecanismo de ordenação fornece speedups de até 3,5 na implementação em CPU. Além disso, utilizando uma única GPU, foi obtido um speedup adicional de até 4,7, em comparação com uma implementação multithreaded em CPU. Porfim, o uso de oito GPUs de um cluster de GPU forneceu um speedup adicional de até 6,6. Combinando todas as técnicas, foram obtidos speedups acima de 60 para a parte paralela do algoritmo. / Gene regulatory networks inference is one of the crucial problems of the Systems Biology field. It is still an open problem, mainly because of its high dimensionality (thousands of genes) with a limited number of samples (dozens), making it difficult to estimate dependenciesamong genes. Besides the estimation problem, another important hindrance is the inherent computational complexity of GRN inference methods. In this work, we focus on circumventing performance issues of a technique based on signal perturbations to infer gene dependencies. One of its main steps consists in solving the Hitting Set problem (HSP), which is NP-Hard. There are many proposals to obtain approximate or exact solutions to this problem. One of these proposals consists of a Graphical Processing Unit (GPU) based algorithm to obtain exact solutions to the HSP. However, such method is not scalable for real size GRNs. We propose an extension of the HSP algorithm to deal with input sets containing thousands of variables by introducing innovations in the data structures and a sorting scheme to allow efficient discarding of Hitting Set non-solution candidates. We provide an implementation for multi-core CPUs and GPU clusters. Our experimental results show that the usage of the sorting scheme brings speedups of up to 3.5 in the CPU implementation. Moreover, using a single GPU, we could obtain an additional speedup of up to 4.7, in comparison with the multithreaded CPU implementation. Finally, usage of eight GPUs from a GPU cluster brought an additional speedup of up to 6.6. Combining all techniques, speedups above 60 were obtained for the parallel part of the algorithm.

In this work, we study return and hitting times in measure-preserving dy- namical systems. We consider a special type of skew-products of two Bernoulli schemes, called a random walk in random scenery. For these systems, the limit distribution of normalized hitting times for cylinders of increasing length is proved to be exponential under the assumption of finite variance of the first order dis- tribution of the Bernoulli scheme representing the walk, and provided the drift is non-zero or the scenery alphabet is finite. Mixing properties of the skew-products are discussed in order to relate our work with some known results on rescaled hitting times for strongly-mixing systems. 1