Nous étudions le comportement asymptotique des dérivées intrinsèques d'une courbe évoluant sous l'action d'un système dynamique aléatoire régulier. Etant donnée une courbe $c$ sur une variété riemannienne, nous désignons par "dérivées intrinsèques de la courbe $c$ en un point $m$", les dérivées à l'origine d'une paramétrisation normale de la courbe transportée sur l'espace tangent au point $m$, par l'application exponentielle. En utilisant le théorème ergodique multiplicatif d'Oseledets, nous obtenons une condition suffisante sur les deux premiers exposants de Lyapounov d'un système dynamique aléatoire régulier, réversible et ergodique, pour que les premières dérivées intrinsèques des images d'une courbe par ce système convergent. Si $\lambda_1$ et $\lambda_2$ sont les deux premiers exposants de Lyapounov du système, $\lambda_1$ étant supposé de multiplicité un, la condition "$\lambda_2-k\lambda_1<0$" assure la convergence des $k$ premières dérivées intrinsèques ; elle n'exclut donc pas les systèmes dynamiques aléatoires stables. La preuve proposée utilise un développement des dérivées intrinsèques à l'aide de diagrammes et donne un procédé récursif pour déterminer les limites des dérivées intrinsèques. Lorsque le premier exposant de Lyapounov est strictement positif, nous faisons le lien entre les limites des dérivées intrinsèques et les variétés instables associées à cet exposant. Nous vérifions ensuite "l'optimalité" de la condition $\lambda_2-2\lambda_1<0$ assurant la convergence de la courbure, en étudiant une classe particulière de systèmes dynamiques aléatoires : les flots browniens isotropes sur la sphère unité de $R^d$. Plus généralement, nous établissons que la norme au carré du vecteur courbure de l'image d'une courbe par un tel système dynamique aléatoire est une diffusion. L'étude du comportement asymptotique de cette diffusion en fonction de la valeur des deux premiers exposants de Lyapounov montre que, sauf si elle est presque sûrement constante, cette diffusion est récurrente positive si et seulement si $\lambda_2-2\lambda_1<0$.

Dans cette thèse nous étudions des équations différentielles stochastiques sur quelques graphes simples dont les solutions sont des flots de noyaux au sens de Le Jan et Raimond. Dans une première partie, nous définissons une extension de l'équation de Tanaka sur un nombre fini de demi-droites orientées et issues de l'origine. Utilisant certaines propriétés de régularité du flot associé au mouvement brownien biaisé, nous donnons une description complète de toutes les solutions. S'appuyant sur une transformation discrète introduite par Csaki et Vincze, nous donnons dans un cas d'orientation particulière (qui couvre déjà l'équation de Tanaka usuelle) une approche discrète à quelques solutions. La dernière partie de ce travail est effectuée avec O. Raimond. Par une méthode de couplage des flots, nous classifions les solutions de l'équation de Tanaka sur le cercle. Nous établissons aussi que ces flots sont coalescents.

Extraction de séquences fréquentes : des bases de données statiques aux flots de données Il est reconnu aujourd'hui que l'être humain est généralement noyé sous une profusion d'informations et que sa capacité d'analyse n'est plus capable de faire face au volume sans cesse croissant de données. C'est dans ce contexte qu'est né le processus d'Extraction de Connaissance dans les bases de Données. Un des buts de ce processus est de passer d'un grand volume d'informations à un petit ensemble de connaissances à fortes valeurs ajoutées pour l'analyste ou le décideur. De plus, le processus d'ECD n'est pas un processus monolithique et univoque au cours duquel il s'agirait d'appliquer un principe général à tous les types de données stockées ou récupérées. Ainsi, une des étapes de ce processus qu'est la fouille de données peut se dériver sous plusieurs formes tels que : le clustering, la classification, l'extraction d'itemset et de règles d'associations, l'extraction de structures plus complexes tels que les épisodes, les graphes ou comme dans le cadre de cette thèse l'extraction de motifs séquentiels. Malheureusement, dans un monde sans cesse en évolution, le contexte dans lequel les travaux d'ECD ont été définis ces dernières années considérait que les données, sur lesquelles la fouille était réalisée, étaient disponibles dans des bases de données statiques. Aujourd'hui, suite au développement de nouvelles technologies et applications associées, nous devons faire face à de nouveaux modèles dans lesquels les données sont disponibles sous la forme de flots. Une question se pose alors : quid des approches d'extraction de connaissances traditionnelles ? Dans ce mémoire, nous présentons un ensemble de résultat sur les motifs séquentiels dans les bases de données d'un point de vue des représentations condensées et des méthodes d'échantillonnage puis nous étendons nos différentes approches afin de prendre en compte le nouveau modèle des flots de données. Nous présentons des algorithmes permettant ainsi l'extraction de motifs séquentiels (classiques et multidimensionnels) sur les flots. Des expérimentations menées sur des données synthétiques et sur des données réelles sont rapportées et montrent l'intérêt de nos propositions.

L'étude des cycles, flots et chemins des graphes est intimement liée au développement de l'optimisation combinatoire. Dans l'introduction nous mettons en parallèle ces concepts à partir de résultats classiques, et les deux autres parties de la thèse développent les nouveaux résultats dans deux directions différentes. La première porte sur les problèmes d'existence de multiflots entiers. Plusieurs paramètres naturels s'appliquent à ces problèmes, générant plus d'une centaine de cas. Après un rappel des résultats de la littérature sous une forme synthétique, nous résolvons plusieurs problèmes ouverts. En particulier, nous montrons que trouver deux flots disjoints dans les graphes planaires est un problème NP-complet. Nous donnons aussi un algorithme polynomial pour router les digraphes planaires acycliques eulériens, lorsque le nombre de classes d'arcs de demande est fixé. Ensuite, nous nous intéressons au problème consistant à trouver une plus courte marche fermée passant par tous les sommets d'un graphe. Spéciquement, nous cherchons à caractériser les graphes pour lesquels une bonne caractérisation est donnée par des empilements d'ensembles éclatants. Nous présentons quelques résultats de nature polyédrale, puis étudions le cas des cographes et des graphes d'intervalles.

Les systèmes temps-réel critiques sont de plus en plus complexes, et les exigences fonctionnelles et non-fonctionnelles ne cessent plus de croître. Le flot de conception de tels systèmes doit assurer, parmi d'autres propriétés, le déterminisme fonctionnel et la prévisibilité temporelle. Le déterminisme fonctionnel est inhérent aux modèles de calcul flot de données (ex. KPN, SDF, etc.) ; c'est pour cela qu'ils sont largement utilisés pour modéliser les systèmes embarqués de traitement de flux. Un effort considérable a été accompli pour résoudre le problème d'ordonnancement statique périodique et à mémoire de communication bornée des graphes flots de données. Cependant, les systèmes embarqués temps-réel optent de plus en plus pour l'utilisation de systèmes d'exploitation temps-réel et de stratégies d'ordonnancement dynamique pour gérer les tâches et les ressources critiques. Cette thèse aborde le problème d'ordonnancement temps-réel dynamique des graphes flots de données ; ce problème consiste à assigner chaque acteur dans un graphe à une tâche temps-réel périodique (i.e. calcul des périodes, des phases, etc.) de façon à : (1) assurer l'ordonnançabilité des tâches sur une architecture et pour une stratégie d'ordonnancement (ex. RM, EDF) données ; (2) exclure statiquement les exceptions d'overflow et d'underflow sur les buffers de communication ; et (3) optimiser les performances du système (ex. maximisation du débit, minimisation des tailles des buffers).

In dimension one, optimal transportation is rather straightforward. The easiness with which a solution can be obtained in that setting has recently been used to tackle more general situations, each time thanks to the same method. First, disintegrate your problem to go back to the unidimensional case, and apply the available 1D methods to get a first result; then, improve it gradually using some evolution process.This dissertation explores that direction more thoroughly. Looking back at two problems only partially solved this way, I show how this viewpoint in fact allows to go even further.The first of these two problems concerns the computation of Yann Brenier's optimal map. Guillaume Carlier, Alfred Galichon, and Filippo Santambrogio found a new way to obtain it, thanks to an differential equation for which an initial condition is given by the Knothe--Rosenblatt rearrangement. (The latter is precisely defined by a series of unidimensional transformations.) However, they only dealt with discrete target measures; I~generalize their approach to a continuous setting. By differentiation, the Monge--Ampère equation readily gives a PDE satisfied by the Kantorovich potential; but to get a proper initial condition, it is necessary to use the Nash--Moser version of the implicit function theorem.The basics of optimal transport are recalled in the first chapter, and the Nash--Moser theory is exposed in chapter 2. My results are presented in chapter 3, and numerical experiments in chapter 4.The last chapter deals with the IDT algorithm, devised by François Pitié, Anil C. Kokaram, and Rozenn Dahyot. It builds a transport map that seems close enough to the optimal map for most applications. A complete mathematical understanding of the procedure is, however, still lacking. An interpretation as a gradient flow in the space of probability measures is proposed, with the sliced Wasserstein distance as the functional. I also prove the equivalence between the sliced and usual Wasserstein distances.

Les langages synchrones sont apparus autour des années quatre-vingt, en réponse à un besoin d’avoir un modèle mathématique simple pour implémenter des systèmes temps réel critiques. Dans ce modèle, le temps est découpé en instants discrets durant lesquels tous les composants du système reçoivent et produisent une donnée. Cette modélisation permet des raisonnements beaucoup plus simples en évitant de devoir prendre en compte le temps de calcul de chaque opération. Dans le monde du logiciel critique, la fiabilité du matériel et de son fonctionnement sont primordiaux, et on accepte d’être plus lent si on devient plus sûr. Afin d’augmenter cette fiabilité, plutôt que de concevoir manuellement tout le système, on utilise des machines qui synthétisent automatiquement le système souhaité à partir d’une description la plus concise possible. Dans le cas du logiciel, ce mécanisme s’appelle la compilation, et évite des erreurs introduites par l’homme par inadvertance. Elle ne garantit cependant pas la bonne correspondance entre le système produit et la description donnée. Des travaux récents menés par une équipe INRIA dirigée par Xavier Leroy ont abouti en 2008 au compilateur CompCert d’un sous-ensemble large de C vers l’assembleur PowerPC pour lequel il a été prouvé dans l’assistant de preuve Coq que le code assembleur produit correspond bien à la description en C du programme source. Un tel compilateur offre des garanties fortes de bonne correspondance entre le système synthétisé et la description donnée. De plus, avec les compilateurs utilisés pour le temps réel critique, la plupart des optimisations sont désactivées afin d’éviter les erreurs qui y sont liées. Dans CompCert, des optimisations elles aussi prouvées sont proposées, ce qui pourrait permettre ces passes dans la production de systèmes temps réel critiques sans en compromettre la fiabilité. Le but de cette thèse est d’avoir une approche similaire mais spécifique à un langage synchrone, donc plus approprié à la description de systèmes temps réel critiques que ne l’est le C. Un langage synchrone flots de données semblable à Lustre, nommé Ls, et un langage impératif semblable au langage C, nommé Obc y sont proposés ainsi que leur sémantique formelle et une chaîne de compilation avec des preuves de préservation de sémantique le long de cette chaîne. / Synchronous languages first appeared during the 80’s, in order to provide a mathematical model for safety-critical systems. In this model, time is discrete. At each instant, all components of the system simultaneously receive and produce some data. This model allows simpler reasonning on the behaviour of the system, as it does not involve the time required for each of the operations for every component. In safety-critical systems, safety is the rule, so a poor performance behaviour can be allowed if it improves safety. In order to improve safety, rather than conceiving directly the system, machines are used to automatically design the system from a given concise description. In the case of software, this machine is called a compiler, and avoids issues due to some human inadvertence. But it does not ensure that the produced system and the description specification really show the same behaviour. Some recent work from an INRIA team lead by Xavier Leroy achieved in 2008 the realisation of the CompCert compiler from a large subset of C to PowerPC assembly, for which it was proven inside of the Coq proof assistant that the produced system fits its source description. Such a compiler offers strong guarantees that the produced system and its given description by the programmer really fit. Furthermore, most current compiler’s optimizations are disabled when dealing with safety-critical systems in order to avoid tedious compilation errors that optimizations may introduce. Proofs for optimizations may allow their use in this domain without affecting the faith we could place in the compiler. The aim of this thesis is to follow a similar path, but this one on a language which would be more suited for safety-critical systems than the C programming language. Some dataflow synchronous programming language very similar to Lustre, called Ls is described with its formal semantics, as well as an imperative programming language similar to a subset of C called Obc. Furthermore some compilation process is described as well as some proofs that the semantics is preserved during the compilation process.

Les applications de gestion de flux sont responsables de la majorité des calculs des systèmes embarqués (vidéo conférence, vision par ordinateur). Leurs exigences de haute performance rendent leur mise en œuvre parallèle nécessaire. Par conséquent, il est de plus en plus courant que les systèmes embarqués modernes incluent des processeurs multi-cœurs qui permettent un parallélisme massif. La mise en œuvre des applications de gestion de flux sur des multi-cœurs est difficile à cause de leur complexité, qui tend à augmenter, et de leurs exigences strictes à la fois qualitatives (robustesse, fiabilité) et quantitatives (débit, consommation d'énergie). Ceci est observé dans l'évolution de codecs vidéo qui ne cessent d'augmenter en complexité, tandis que leurs exigences de performance demeurent les mêmes. Les modèles de calcul (MdC) flot de données ont été développés pour faciliter la conception de ces applications qui sont typiquement composées de filtres qui échangent des flux de données via des liens de communication. Ces modèles fournissent une représentation intuitive des applications de gestion de flux, tout en exposant le parallélisme de tâches de l'application. En outre, ils fournissent des analyses statiques pour la vivacité et l'exécution en mémoire bornée. Cependant, les applications de gestion de flux modernes comportent des filtres qui échangent des quantités de données variables, et des liens de communication qui peuvent être activés / désactivés. Dans cette thèse, nous présentons un nouveau MdC flot de données, le Boolean Parametric Data Flow (BPDF), qui permet le paramétrage de la quantité de données échangées entre les filtres en utilisant des paramètres entiers et l'activation et la désactivation de liens de communication en utilisant des paramètres booléens. De cette manière, BPDF est capable de exprimer des applications plus complexes, comme les décodeurs vidéo modernes. Malgré l'augmentation de l'expressivité, les applications BPDF restent statiquement analysables pour la vivacité et l'exécution en mémoire bornée. Cependant, l'expressivité accrue complique grandement la mise en œuvre. Les paramètres entiers entraînent des dépendances de données de type paramétrique et les paramètres booléens peuvent désactiver des liens de communication et ainsi éliminer des dépendances de données. Pour cette raison, nous proposons un cadre d'ordonnancement qui produit des ordonnancements de type ``aussi tôt que possible'' (ASAP) pour un placement statique donné. Il utilise des contraintes d'ordonnancement, soit issues de l'application (dépendance de données) ou de l'utilisateur (optimisations d'ordonnancement). Les contraintes sont analysées pour la vivacité et, si possible, simplifiées. De cette façon, notre cadre permet une grande variété de politiques d'ordonnancement, tout en garantissant la vivacité de l'application. Enfin, le calcul du débit d'une application est important tant avant que pendant l'exécution. Il permet de vérifier que l'application satisfait ses exigences de performance et il permet de prendre des décisions d'ordonnancement à l'exécution qui peuvent améliorer la performance ou la consommation d'énergie. Nous traitons ce problème en trouvant des expressions paramétriques pour le débit maximum d'un sous-ensemble de BPDF. Enfin, nous proposons un algorithme qui calcule une taille des buffers suffisante pour que l'application BPDF ait un débit maximum. / Streaming applications are responsible for the majority of the computation load in many embedded systems (video conferencing, computer vision etc). Their high performance requirements make parallel implementations a necessity. Hence, more and more modern embedded systems include many-core processors that allow massive parallelism. Parallel implementation of streaming applications on many-core platforms is challenging because of their complexity, which tends to increase, and their strict requirements both qualitative (e.g., robustness, reliability) and quantitative (e.g., throughput, power consumption). This is observed in the evolution of video codecs that keep increasing in complexity, while their performance requirements remain the same or even increase. Data flow models of computation (MoCs) have been developed to facilitate the design process of such applications, which are typically composed of filters exchanging streams of data via communication links. Data flow MoCs provide an intuitive representation of streaming applications, while exposing the available parallelism of the application. Moreover, they provide static analyses for liveness and boundedness. However, modern streaming applications feature filters that exchange variable amounts of data, and communication links that are not always active. In this thesis, we present a new data flow MoC, the Boolean Parametric Data Flow (BPDF), that allows parametrization of the amount of data exchanged between the filters using integer parameters and the enabling and disabling of communication links using boolean parameters. In this way, BPDF is able to capture more complex streaming applications, like video decoders. Despite the increase in expressiveness, BPDF applications remain statically analyzable for liveness and boundedness. However, increased expressiveness greatly complicates implementation. Integer parameters result in parametric data dependencies and the boolean parameters disable communication links, effectively removing data dependencies. We propose a scheduling framework that facilitates the scheduling of BPDF applications. Our scheduling framework produces as soon as possible schedules for a given static mapping. It takes us input scheduling constraints that derive either from the application (data dependencies) or from the user (schedule optimizations). The constraints are analyzed for liveness and, if possible, simplified. In this way, our framework provides flexibility, while guaranteeing the liveness of the application. Finally, calculation of the throughput of an application is important both at compile-time and at run-time. It allows to verify at compile-time that the application meets its performance requirements and it allows to take scheduling decisions at run-time that can improve performance or power consumption. We approach this problem by finding parametric throughput expressions for the maximum throughput of a subset of BPDF graphs. Finally, we provide an algorithm that calculates sufficient buffer sizes for the BPDF graph to operate at maximum throughput.

On étudie des flots géométriques d'ordre quatre sur des variétés riemanniennes compactes, qui apparaissent naturellement comme flots de gradient de fonctionnelles quadratiques en la courbure. Lorsque la constante de Yamabe reste minorée par une constante strictement positive le long du flot, on montre que la variété ne s'effondre pas, et qu'une suite de métriques dilatées au voisinage d'un temps singulier converge vers une variété complète qui modélise la singularité. En particulier, en dimension quatre, cette hypothèse est vérifiée pour une certaine classe de flots de gradients, du moment que l'énergie initiale est inférieure à une constante explicite. Les singularités de ces flots sont alors modélisées par des variétés complètes et non compactes, dont le tenseur de Bach et la courbure scalaire s'annulent. En combinant une formule de Weitzenböck avec l'inégalité de Sobolev induite par la positivité de la constante de Yamabe, on montre une série de résultats de rigidité pour des métriques dont la courbure est intégralement pincée. En particulier, on prouve un théorème de rigidité pour les variétés de dimension quatre à tenseur de Bach et à courbure scalaire nuls, qui implique que les singularités de notre classe de flots de gradient ne peuvent exister que si l'énergie initiale est supérieure à une certaine constante. Dans le cas contraire, ces flots existent pour tous temps positifs et convergent vers une métrique à courbure sectionnelle constante et positive. On retrouve ainsi un "théorème de la sphère" pour les variétés compactes de dimension quatre dont la courbure est intégralement pincée. En appliquant cette même méthode aux formes harmoniques d'une variété à courbure intégralement pincée, on démontre une version intégrale du théorème de Bochner-Weitzenböck. On en déduit l'annulation des nombres de Betti sous diverses conditions de pincement intégral, et on caractérise les cas d'égalité. / We study fourth-order geometric flows on compact Riemannian manifolds, which naturally appear as gradient flows of quadratic curvature functionals. When the Yamabe constant remains bounded from below by a positive constant along the flow, we show that the manifold doesn't collapse, and that a sequence of dilated metrics near a singular time converges to a singularity model. In particular, in dimension four, this assumption is satisfied by a class of gradient flows, provided that the initial energy is less than an explicit constant. The singularities of these flows are then modeled by complete non-compact manifolds, which are Bach-flat and scalar-flat. By combining a Weitzenböck formula with the Sobolev inequality induced by the positivity of the Yamabe constant, we prove several rigidity results for metrics with integral pinched curvature. In particular, we prove a rigidity result for Bach-flat and scalar-flat manifolds in dimension four, which implies that the singularities of our gradient flows can only exist when the initial energy is bigger than a given constant. When this is not the case, these flows exist for all time, and converge to a metric with constant positive curvature. It provides a proof of a "sphere theorem" for closed four-dimensional manifolds with integral pinched curvature. Applying the same method to harmonic forms on an integral pinched manifold, we prove an integral version of the Bochner-Weitzenböck theorem. As a corollary, we obtain the vanishing of Betti numbers under various integral pinching conditions, and we characterize the equality cases.

Le flot de Ricci, introduit par Hamilton au début des années 80, a montré sa valeur pour étudier la topologie et la géométrie des variétés riemanniennes lisses. Il a ainsi permis de démontrer la conjecture de Poincaré (Perelman, 2003) et le théorème de la sphère différentiable (Brendle et Schoen, 2008). Cette thèse s'intéresse aux applications du flot de Ricci à des espaces métriques à courbure minorée peu lisses. On définit en particulier ce que signifie pour un flot de Ricci d'avoir pour condition initiale un espace métrique. Dans le Chapitre 2, on présente certains travaux de Simon permettant de construire un flot de Ricci pour certains espaces métriques de dimension 3. On démontre aussi deux applications de cette construction : un théorème de finitude en dimension 3 et une preuve alternative d'un théorème de Cheeger et Colding en dimension 3. Dans le Chapitre 3, on s'intéresse à la dimension 2. On montre que pour les surfaces singulières à courbure minorée (au sens d'Alexandrov), on peut définir un flot de Ricci et que celui-ci est unique. Ceci permet de montrer que l'application qui à une surface associe son flot de Ricci est continue par rapport aux perturbations Gromov-Hausdorff de la condition initiale. Le Chapitre 4 généralise une partie de ces méthodes en dimension quelconque. On doit y considérer des conditions de courbure autres que les usuelles minorations de la courbure de Ricci ou de la courbure sectionnelle. Les méthodes mises en place permettent de construire un flot de Ricci pour certains espaces métriques non effondrés limites de variétés dont l'opérateur de courbure est minoré. On montre aussi que sous certaines hypothèses de non-effondrement, les variétés à opérateur de courbure presque positif portent une métrique à opérateur de courbure positif ou nul. / The Ricci flow was introduced by Hamilton in the beginning of the 90's. It has been a valuable tool to study the topology and the geometry of smooth Riemannian manifolds. For example, it was essential in the of the Poincaré conjecture (Perelman, 2003) and of the differentiable sphere theorem (Brendle and Schoen, 2008). In this thesis, we are interested in the applications of Ricci flow to metric spaces with curvature bounded from below which are not smooth. We define what it means for a Ricci flow to admit a metric space as initial condition. In Chapter 2, we present some works of Simon which allow to build a Ricci flow for some metric spaces of dimension 3. We also give two applications of this result : a finiteness theorem in dimension 3 and an alternative of a theorem of Cheeger and Colding in dimension 3. In Chapter 3, we treat the special case of dimension 2. We show that for singular surfaces whose curvature is boded from below (in the sense of Alexandrov), we can define a Ricci and it is unique. This allow to show that for surfaces with curvature bounded from below, the application which maps a surface to its Ricci flow is continuous with respect to Gromov-Hausdorff perturbations of the initial condition. Chapter 4 generalizes some of these methods in higher dimension. Here one needs to consider other conditions on the curvature than the usual "Ricci curvature bounded from below" and "sectional curvature bounded from below". The methods used there allow us to build a Ricci flow for some non-collapsed metric spaces which are limits of manifolds whose curvature operator is bounded from below. We also show that under some non-collapsing assumptions manifolds with almost non-negative curvature operator admit metrics with non-negative curvature operator.