Habilitation à diriger des recherches : Informatique : Rennes 1 : 2003. / Bibliogr. p.68-73.

Cette thèse est composée de trois chapitres indépendants ayant pour thématique commune la théorie des trajectoires rugueuses. Introduite en 1998 par Terry Lyons, cette approche trajectorielle des équations différentielles stochastiques (EDS) permet l'étude d'EDS dirigées par des processus n'ayant pas la propriété de semi-martingale nécessaire à l'application du cadre de l'intégration d'Itô. C'est par exemple le cas du mouvement brownien fractionnaire pour un indice de Hurst différent d'un demi. Le premier chapitre porte sur les liens entre la théorie des trajectoires rugueuses et celle des structures de régularité qui a été récemment introduite par Martin Hairer pour résoudre une large classe d'équations aux dérivées partielles stochastiques. Nous exposons, avec les outils de cette nouvelle théorie, la définition de l'intégrale rugueuse et de la signature d'une trajectoire irrégulière, ce qui nous mène à la résolution d'équations différentielles rugueuses (EDR). Dans le second chapitre, nous nous intéressons à la construction de flots d'EDR à partir de leurs approximations en temps petit, appelées presque flots. Nous montrons que sous des conditions faibles de régularité du presque flot, bien que l'unicité des solutions de l'EDR associée ne soit plus assurée, il est possible de sélectionner un flot mesurable. Notre cadre général unifie les précédentes approches par flot dues à I. Bailleul, A. M. Davie, P. Friz et N. Victoir. Le dernier chapitre s'attache à l'étude d'une inclusion différentielle perturbée par une trajectoire rugueuse, c'est-à-dire d'une EDR dont la dérive est une fonction multivaluée. Nous démontrons, sans hypothèse de convexité et avec différentes conditions de régularité sur la dérive, l'existence de solution. / This thesis consists of three independent chapters in the theme of rough path theory. Introduced in 1998 by Terry Lyons, this pathwise approach to stochastic differential equations (SDE) allows one to study SDE driven by processes that do not have the semi-martingale property which is required to apply the framework of the Itô integral. This is for example the case of the fractional Brownian motion for a Hurst index different from one-half. The first chapter deals with the links between rough path and regularity structure theories. The latter was recently introduced by Martin Hairer to solve a large class of stochastic partial differential equations. With the tools of this new theory, we show how to build the rough integral and the signature of an irregular path, which leads to solve a rough differential equation (RDE). In the second chapter, we focus on building RDE flows from their approximations at small scale, called almost flows. We show that under weak conditions on regularity of almost flows, although the uniqueness of the associated RDE solutions does not hold, we are able to select a measurable flow. Our general framework unifies the previous approaches by flow due to I. Bailleul, A. M. Davie, P. Friz and N. Victoir. In the last chapter, we study of a differential inclusion perturbed by a rough path, i.e. a RDE whose drift is a multivalued function. We prove, without convexity hypothesis and several conditions on the regularity of the drift, the existence of a solution.

Un graphe est un ensemble de noeuds, ensemble de liens reliant des paires de noeuds. Avec la quantité accumulée de données collectées, il existe un intérêt croissant pour la compréhension des structures et du comportement de très grands graphes. Néanmoins, l’augmentation rapide de la taille des grands graphes rend l’étude de tous les graphes de moins en moins efficace. Ainsi, il existe une demande impérieuse pour des méthodes plus efficaces pour étudier de grands graphes sans nécessiter la connaissance de tous les graphes. Une méthode prometteuse pour comprendre le comportement de grands graphes consiste à exploiter des propriétés spécifiques de structures locales, telles que la taille des grappes ou la présence locale d’un motif spécifique, c’est-à-dire un graphe donné (généralement petit). Un exemple classique de la théorie des graphes (cas avérés de la conjecture d'Erdos-Hajnal) est que, si un graphe de grande taille ne contient pas de motif spécifique, il doit alors avoir un ensemble de noeuds liés par paires ou non liés, de taille exponentiellement plus grande que prévue. Cette thèse abordera certains aspects de deux questions fondamentales de la théorie des graphes concernant la présence, en abondance ou à peine, d’un motif donné dans un grand graphe : - Le grand graphe peut-il être partitionné en copies du motif ? - Le grand graphe contient-il une copie du motif ? Nous discuterons de certaines des conjectures les plus connues de la théorie des graphes sur ce sujet: les conjectures de Tutte sur les flots dans les graphes et la conjecture d'Erdos-Hajnal mentionnée ci-dessus, et présenterons des preuves pour plusieurs conjectures connexes - y compris la conjecture de Barát-Thomassen, une conjecture de Haggkvist et Krissell, un cas particulier de la conjecture de Jaeger-Linial-Payan-Tarsi, une conjecture de Berger et al, et une autre d'Albouker et al. / A graph is a set of nodes, together links connecting pairs of nodes. With the accumulating amount of data collected, there is a growing interest in understanding the structures and behavior of very large graphs. Nevertheless, the rapid increasing in size of large graphs makes studying the entire graphs becomes less and less efficient. Thus, there is a compelling demand for more effective methods to study large graphs without requiring the knowledge of the graphs in whole. One promising method to understand the behavior of large graphs is via exploiting specific properties of local structures, such as the size of clusters or the presence locally of some specific pattern, i.e. a given (usually small) graph. A classical example from Graph Theory (proven cases of the Erdos-Hajnal conjecture) is that if a large graph does not contain some specific pattern, then it must have a set of nodes pairwise linked or not linked of size exponentially larger than expected. This thesis will address some aspects of two fundamental questions in Graph Theory about the presence, abundantly or scarcely, of a given pattern in some large graph: - Can the large graph be partitioned into copies of the pattern? - Does the large graph contain any copy of the pattern?We will discuss some of the most well-known conjectures in Graph Theory on this topic: the Tutte's flow conjectures on flows in graphs and the Erdos-Hajnal conjecture mentioned above, and present proofs for several related conjectures -- including the Barát-Thomassen conjecture, a conjecture of Haggkvist and Krissell, a special case of Jaeger-Linial-Payan-Tarsi's conjecture, a conjecture of Berger et al, and another one by Albouker et al.

La première partie de cette thèse exploite et développe la relation entre approximation diophantienne homogène à une variable dans un corps de nombre et la dynamique du flot des chambres de Weyl dans la variété de Hilbert associée.<br />La deuxième partie s'intéresse au problème des cibles réctricissantes sur une variété hyperbolique.<br />Dans la troisième partie, on démontre des résultats de répartition des orbites de l'action de réseaux de groupes de Lie sur certains espaces homogènes, dans la veine de résultats antérieurs de Ledrappier.

Pour permettre une plus grande capacité de calcul les concepteurs de systèmes embarqués se tournent aujourd'hui vers les MPSoC. Malheureusement, ces systèmes sont difficiles à programmer. Un des problèmes durs est l'expression et l'optimisation des réorganisations de données au sein d'un programme. Dans cette thèse nous souhaitons proposer une chaîne de compilation qui : 1) propose une syntaxe simple et haut-niveau pour exprimer le découpage et la réorganisation des données d'un programme parallèle ; 2) définisse une exécution déterministe du programme (critique dans le cadre des systèmes embarqués) ; 3) optimise et adapte les programmes aux contraintes de l'architecture. Pour répondre au point 1) nous proposons un langage haut-niveau, SLICES, qui permet de décrire les réorganisation de données à travers des découpages multidimensionnels. Pour répondre au point 2) nous montrons qu'il est possible de compiler SLICES vers un langage de flots de données, SJD, qui s'inscrit dans le modèle des Cyclostatic Data-Flow et donc admet une exécution déterministe. Pour répondre au point 3) nous définissons un ensemble de transformations qui préservent la sémantique des programmes SJD. Nous montrons qu'il existe un sous-ensemble de ces transformations qui génère un espace de programmes équivalents fini. Nous proposons une heuristique pour explorer cet espace de manière à choisir la variante la plus adaptée à notre architecture. Enfin nous évaluons cette méthode sur deux problèmes classiques : la réduction de la mémoire consommée et la réduction des communications d'une application parallèle.

Mes travaux ont portés successivement sur:<br />- les flots d'Anosov en dimension 3,<br />- l'étude des (G,X)-structures, avec en premier plan les structures affines plates,<br />- la géométrie lorentzienne en courbure constante et leus aspects causaux.<br />Ce long mémoire recouvre tous ces sujets, en mettant en évidence leurs interconnexions.

dans cette thèse, je m'intéresse au problème de classification des flots d'Anosov de décomposition lisse. Sous certaines conditions géométriques supplémentaires, j'ai obtenu une serie de résultats de classification, et mon point de départ est une idée appellée ``aller et retour''. Une des corollaires de mes résultats de classification est la suivante: Soit \Phi le feuilletage orbital du flot géodésique d'une variété hyperbolique fermée de dimension au moins 3. Soit \Psi un autre feuilletage de dimension un. Si ces deux feuilletages sont C^1 conjugués, alors ils sont forcément C^\infty conjugués.

Les travaux de cette thèse portent sur la cryptanalyse d'un système de chiffrement simple, mais important : le registre filtré. Ils concernent les deux principales familles d'attaques que sont les attaques algébriques et les attaques probabilistes. Pour les attaques algébriques, il est important de pouvoir calculer efficacement l'immunité algèbrique de la fonction booléenne par laquelle le registre est filtré. Cette quantité est intimement liée au comportement des codes de Reed-Muller sur le canal à effacements et son étude a permis la découverte de plusieurs résultats qui s'expriment naturellement dans le cadre de la théorie des codes correcteurs. Nous avons ainsi construit une nouvelle borne sur la probabilité de pouvoir compenser un nombre d'effacements fixé. Cette borne montre que l'immunité algébrique d'une fonction booléenne aléatoire est presque toujours maximale. Nous avons également explicité une méthode de décodage fondée sur des algorithmes d'algèbre linéaire creuse (comme l'algorithme de Wiedemann) qui donne un des algorithmes les plus efficace pour calculer l'immunité algébrique. Pour les attaques probabilistes, un outil très important est de parvenir à trouver efficacement de nombreux multiples de poids faible du registre à décalage du système. Un nouvel algorithme fondé sur les logarithmes discrets à été proposé. Il est particulièrement interessant pour les multiples de poids 4, améliorant dans de nombreux cas pratiques le meilleur algorithme connu. Ce travail s'est poursuivi par une nouvelle cryptanalyse probabiliste du registre filtré qui utilise ces multiples de poids faible pour reconnaître les entrées nulles de la fonction de filtrage. Cette attaque est l'une des plus efficaces connue à l'heure actuelle.

L'explosion du volume de données disponibles due au développement des technologies de l'information et de la communication a démocratisé les flots qui peuvent être définis comme des séquences non bornées de données très précises et circulant à grande vitesse. Les stocker intégralement est par définition impossible. Il est alors essentiel de proposer des techniques de résumé permettant une analyse a posteriori de cet historique. En outre, un grand nombre de flots de données présentent un caractère multidimensionnel et multiniveaux que très peu d'approches existantes exploitent. Ainsi, l'objectif de ces travaux est de proposer des méthodes de résumé exploitant ces spécificités multidimensionnelles et applicables dans un contexte dynamique. Nous nous intéressons à l'adaptation des techniques OLAP (On Line Analytical Processing ) et plus particulièrement, à l'exploitation des hiérarchies de données pour réaliser cette tâche. Pour aborder cette problématique, nous avons mis en place trois angles d'attaque. Tout d'abord, après avoir discuté et mis en évidence le manque de solutions satisfaisantes, nous proposons deux approches permettant de construire un cube de données alimenté par un flot. Le deuxième angle d'attaque concerne le couplage des approches d'extractions de motifs fréquents (itemsets et séquences) et l'utilisation des hiérarchies pour produire un résumé conservant les tendances d'un flot. Enfin, les catégories de hiérarchies existantes ne permettent pas d'exploiter les connaissances expertes dans le processus de généralisation. Nous pallions ce manque en définissant une nouvelle catégorie de hiérarchies, dites contextuelles, et en proposant une modélisation conceptuelle, graphique et logique d'un entrepôt de données intégrant ces hiérarchies contextuelles. Cette thèse s'inscrivant dans un projet ANR (MIDAS), une plateforme de démonstration intégrant les principales approches de résumé a été mise au point. En outre, la présence de partenaires industriels tels que Orange Labs ou EDF RD dans le projet a permis de confronter nos approches à des jeux de données réelles. / Due to the rapid increase of information and communication technologies, the amount of generated and available data exploded and a new kind of data, the stream data, appeared. One possible and common definition of data stream is an unbounded sequence of very precise data incoming at an high rate. Thus, it is impossible to store such a stream to perform a posteriori analysis. Moreover, more and more data streams concern multidimensional and multilevel data and very few approaches tackle these specificities. Thus, in this work, we proposed some practical and efficient solutions to deal with such particular data in a dynamic context. More specifically, we were interested in adapting OLAP (On Line Analytical Processing ) and hierarchy techniques to build relevant summaries of the data. First, after describing and discussing existent similar approaches, we have proposed two solutions to build more efficiently data cube on stream data. Second, we were interested in combining frequent patterns and the use of hierarchies to build a summary based on the main trends of the stream. Third, even if it exists a lot of types of hierarchies in the literature, none of them integrates the expert knowledge during the generalization phase. However, such an integration could be very relevant to build semantically richer summaries. We tackled this issue and have proposed a new type of hierarchies, namely the contextual hierarchies. We provide with this new type of hierarchies a new conceptual, graphical and logical data warehouse model, namely the contextual data warehouse. Finally, since this work was founded by the ANR through the MIDAS project and thus, we had evaluated our approaches on real datasets provided by the industrial partners of this project (e.g., Orange Labs or EDF R&D).

Dans le cadre de cette thèse, nous nous intéressons à la vérification de systèmes réactifs critiques et temps réel développés a l'aide de langages flots de données synchrones. Plus particulièrement nous avons considéré les propriétés de sureté pour les applications réalisées dans un des deux langages, saga produit de Merlin Gerin/ses, ou lustre crée au LGI. La méthode de vérification, pour laquelle un prototype a été réalise, est l'évaluation de propriétés sur un modèle des programmes. Un langage de spécification adapte au contexte des systèmes réactifs temps réel, avec sa sémantique formelle, est défini; ce langage comprend plusieurs opérateurs temporels. Le désir d'automatiser la vérification a nécessité la définition de la sémantique formelle de saga. Plusieurs modèles pour les programmes ont alors été étudiés: les arbres des exécutions comme base d'expression commune des sémantiques, les graphes d'états et automates de contrôle pour la mise en œuvre de la vérification. L'utilisation de moyens existants de vérification, fondée sur l'évaluation de propriétés sur un modèle des programmes, a été étudiée et évaluée. Ces moyens sont relatifs a des logiques temporelles arborescentes et des mu-calculs propositionnels. Une nouvelle approche pour la spécification et la vérification de propriétés de sureté, mettant en œuvre les caractéristiques du langage lustre, est développée. Elle s'appuie sur l'utilisation de lustre lui-même comme langage de spécification et présente les avantages suivants: formalisme commun pour la programmation et la spécification, utilisation du compilateur pour la vérification, possibilité de preuves modulaires