Les maillages polygonaux sont des représentations géométriques de plus en plus utilisées pour encoder des formes dans un ordinateur, en raison de leur versatilité, et de leur compatibilité avec les dispositifs d'acquisition 3D. Dans le cadre de cette thèse d'habilitation, nous nous proposons d'étudier différentes maniérés de discrétiser des équations aux dérivées partielles sur ces maillages, ainsi que des applications aux domaines du plaquage de textures, de la conversion entre maillages et Splines, de la visualisation scientifique et de la simulation de la lumière.

Il existe de nombreuses approches développées par la communauté Implicit Computational Complexity (ICC) permettant d'analyser les ressources nécessaires à la bonne exécution des algorithmes. Dans cette thèse, nous nous intéressons plus particulièrement au contrôle des ressources à l'aide d'interprétations sémantiques. <br />Après avoir rappelé brièvement la notion de quasi-interprétation ainsi que les différentes propriétés et caractérisations qui en découlent, nous présentons les différentes avancées obtenues dans l'étude de cet outil : nous étudions le problème de la synthèse qui consiste à trouver une quasi-interprétation pour un programme donné, puis, nous abordons la question de la modularité des quasi-interprétations. La modularité permet de diminuer la complexité de la procédure de synthèse et de capturer un plus grand nombre d'algorithmes. Après avoir mentionné différentes extensions des quasi-interprétations à des langages de programmation réactif, bytecode ou d'ordre supérieur, nous introduisons la sup-interprétation. Cette notion généralise la quasi-interprétation et est utilisée dans des critères de contrôle des ressources afin d'étudier la complexité d'un plus grand nombre d'algorithmes dont des algorithmes sur des données infinies ou des algorithmes de type diviser pour régner. Nous combinons cette notion à différents critères de terminaison comme les ordres RPO, les paires de dépendance ou le size-change principle et nous la comparons à la notion de quasi-interprétation. En outre, après avoir caractérisé des petites classes de complexité parallèles, nous donnons quelques heuristiques permettant de synthétiser des sup-interprétations sans la propriété sous-terme, c'est à dire des sup-interprétations qui ne sont pas des quasi-interprétations. Enfin, dans un dernier chapitre, nous adaptons les sup-interprétations à des langages orientés-objet, obtenant ainsi différents critères pour contrôler les ressources d'un programme objet et de ses méthodes.

Les systèmes hybrides, systèmes combinant à la fois une dynamique continue et discrète, s'avèrent être un modèle mathématique utile pour différents phénomènes physiques, technologiques, biologiques ou économiques. Beaucoup d'efforts ont été consacrés à l'élaboration de méthodes automatiques d'analyse pour de tels systèmes, basées sur la vérification formelle. Néanmoins, l'applicabilité de ces méthodes est encore limitée aux systèmes de petite taille en raison de la complexité de l'analyse exhaustive. Le test est une autre approche de validation, qui peut être employée pour des systèmes beaucoup plus grands. En dépit de ses limitations comparées à la vérification algorithmique et déductive, le test reste l'outil standard dans l'industrie.<br />Nous proposons dans cette thèse une méthodologie formelle pour le test de conformité des systèmes hybrides, qui est définie selon la norme internationale pour le test formel de conformité (FMCT). Ensuite, nous abordons le problème de la définition de mesures de couverture de test. Pour cela, deux mesures de couverture sont proposées, qui sont non seulement utiles comme critère pour évaluer la qualité de test mais peuvent être aussi employées pour guider la génération de test vers une meilleur couverture. Des algorithmes de génération de test guidés par les mesures de couverture sont proposés. Ces algorithmes sont basés sur une combinaison des algorithmes de planification de trajectoires dans la robotique, de la théorie d'équidistribution, de la géométrie algorithmique et de la simulation numérique. L'outil HTG (Hybrid test generation) pour la génération de cas de test pour les systèmes hybrides implémente ces algorithmes, et a été appliqué avec succès pour traiter plusieurs études de cas provenant de différentes domaines (circuits analogiques et mixtes, systèmes de commande, etc.).

Traditionally, consistency is the only criterion for the quality of a theory in logic-based approaches to reasoning about actions. This work goes beyond that and contributes to the meta-theory of actions by investigating what other properties a good domain description should satisfy. Having Propositional Dynamic Logic (PDL) as background, we state some meta-theoretical postulates <br />concerning this sore spot. When all postulates are satisfied, we call the action theory modular. We point out the problems that arise when the postulates about modularity are violated, and propose algorithmic checks that can help the designer of an action theory to overcome them. Besides being easier to understand and more elaboration tolerant in McCarthy's sense, modular theories<br />have interesting computational properties. Moreover, we also propose a framework for updating domain descriptions and show the importance modularity has in action theory change.

Sécurisation du Contrôle d'Accès dans les Bases de Données

Cette thèse s'inscrit dans l'étude de familles de graphes infinis de présentation finie, de leurs propriétés structurelles, ainsi que des comparaisons entre ces familles. Étant donné un alphabet fini Σ, un graphe infini étiqueté par Σ peut être caractérisé par un ensemble fini de relations binaires (Ra )a∈Σ sur un domaine dénombrable V quelconque. De multiples caractérisations finies de tels ensembles de relations existent, soit de façon explicite grâce à des systèmes de réécriture ou à divers formalismes de la théorie des automates, soit de façon implicite. Après un survol des principaux résultats existants, nous nous intéressons plus particulièrement à trois problèmes. Dans un premier temps, nous définissons trois familles de systèmes de réécriture de termes dont nous démontrons que la rela- tion de dérivation peut être représentée de façon finie. De ces résultats découlent plusieurs questions sur les familles de graphes infinis correspondantes. Dans un se- cond temps, nous étudions deux familles de graphes dont les ensembles de traces forment la famille des langages contextuels, à savoir les graphes rationnels et les graphes linéairement bornés. Nous nous intéressons en particulier au cas des langages contextuels déterministes, ainsi qu'à la comparaison structurelle de ces deux familles. Enfin, d'un point de vue plus proche du domaine de la vérifica- tion, nous proposons un algorithme de calcul des prédécesseurs pour une famille d'automates à pile d'ordre supérieur.

Depuis plusieurs années, de nombreuses recherches ont été menées autour du diagnostic. Cependant, il est impératif de se préoccuper dès la phase de conception d'un système des objectifs de diagnostic à atteindre. Aussi, de nombreux travaux se sont intéressés à analyser et à caractériser les propriétés de la diagnosticabilité d'un système. La diagnosticabilité est la propriété d'un système garantissant qu'il génère des observations permettant de détecter et discriminer les fautes en temps fini après leur occurrence.Le sujet de cette thèse porte sur les méthodes permettant d'établir les propriétés de la diagnosticabilité des systèmes à événements discrets dans le cadre distribué, sans construction du modèle global du système. Ce cadre est de première importance pour les applications réelles : systèmes naturellement distribués, systèmes trop complexes pour traiter leur modèle global, confidentialité des modèles locaux les uns par rapport aux autres. L'analyse de la diagnosticabilité de tels systèmes distribués se fonde sur des opérations de synchronisation des modèles locaux, par les observations et les communications. D'abord, nous étudions comment optimiser cette analyse de la diagnosticabilité en faisant abstraction de l'information nécessaire et suffisante à partir des objets locaux pour décider la diagnosticabilité globale. L'efficacité de l'algorithme peut être grandement améliorée par la synchronisation des objets locaux et abstraits en comparaison avec celle des objets locaux et non abstraits.Ensuite, nous proposons, dans le cadre distribué, l'algorithme de la diagnosticabilité de motifs d'événements particuliers a priori inobservables dans les systèmes. Ces motifs peuvent être simplement l'occurrence, brutale ou graduelle, d'une faute permanente ou transitoire, plusieurs occurrences d'une faute, plusieurs fautes en cascade, etc. Dans le cadre distribué, la reconnaissance du motif d'événements s'effectue d'abord progressivement dans un sous-système et ensuite la diagnosticabilité de ce motif peut être déterminée par la méthode abstraite et distribuée. Nous prouvons la correction et l'efficacité de notre algorithme à la fois en théorie et en pratique par la mise en œuvre de l'implémentation sur des exemples.Finalement, nous étudions le problème de la diagnosticabilité dans les systèmes distribués avec composants autonomes, où l'information observable est distribuée au lieu d'être centralisée comme jusqu'alors. En d'autres termes, chaque composant ne peut appréhender que ses propres événements observables. Nous donnons la définition de la diagnosticabilité conjointe. Et puis nous discutons de l'indécidabilité de diagnosticabilité conjointe dans le cas général, c'est à dire, les événements de communication ne sont pas observables, avant de proposer un algorithme pour tester sa condition suffisante. De plus, nous obtenons également un résultat de décidabilité et de l'algorithme lorsque les communications sont observables.

La bioinformatique nécessite l'analyse de grandes quantités de données. Avec l'apparition de nouvelles technologies permettant un séquençage à haut débit à bas coût, la puissance de calcul requise pour traiter les données a énormément augmenté.. Cette thèse examine la possibilité d'utiliser les processeurs graphiques (GPU) pour des applications de bioinformatique. Dans un premier temps, ce travail s'intéresse au calcul des structures secondaires d'ARN. Ce problème est en général calculé par programmation dynamique, avec un algorithme qui pose de sérieux problèmes pour un code GPU. Nous introduisons une nouvelle implémentation tuilée qui fait apparaitre une bonne localité mémoire, permettant ainsi un programme GPU très efficace. Cette modification permet également de vectoriser le code CPU et donc de faire une comparaison honnête des performances entre GPU et CPU. Dans un deuxième temps, ce travail aborde le problème d'alignements de séquences. Nous présentons une parallélisation GPU d'une méthode utilisant une indexation par graines. L' implémentation sur GPU n'étant pas efficace, nous nous tournons vers le développement d'une version CPU. Notre contribution principale est le développement d'un nouvel algorithme éliminant rapidement les nombreux alignements potentiels, basé sur le précalcul de portions de la matrice de programmation dynamique. Ce nouvel algorithme a conduit au développement d'un nouveau programme d'alignement très efficace. Notre travail fournit l'exemple de deux problèmes différents dont seulement un a pu être efficacement parallélisé sur GPU. Ces deux expériences nous permettent d'évaluer l'efficacité des GPU et leur place en bioinformatique.

Ce travail de thèse s'est consacré à la comparaison de l'anatomie et de la fonction cardiaques à partir d'images médicales. Une première partie se concentre sur l'anatomie cardiaque avec une étude statistique de l'architecture des bres musculaires du c÷ur à partir d'IRM de tenseur de di usion. Dans la deuxième partie est proposée une comparaison la fonction cardiaque de di érents patients ou du même patient a di érents instants par le recalage spatiotemporel de séquences 4D CT. La complexe organisation des bres musculaires cardiaques a un rôle très important dans le comportement électrique et mécanique du c÷ur. Pour étudier cette architecture des bres, nous avons proposé de nouveaux outils algorithmiques d'analyse statistique d'IRM de tenseurs de di usion. La nouveauté de cette approche est de réaliser cette analyse statistique directement sur les tenseurs de di usion l'a où la plupart des études statistiques se font sur des vecteurs ou angles d'orientation décrivant les directions des bres et des feuillets. La variabilité de l'orientation des bres et des feuillets est ensuite directement donnée par la matrice de covariance des tenseurs de di usion de laquelle sont extraites les variabilités des vecteurs propres. L'application de ces outils a une base de données d'IRM de tenseur de di usion de c÷urs de chiens acquis ex vivo a permis d'obtenir un atlas de l'architecture des bres mais aussi de révééler une cohérence de l'orientation des bres et une plus grande variabilité de l'orientation des feuillets. Ensuite, nous avons comparé l'atlas de c÷urs de chien à un c÷ur humain et un modèle synthétique couramment utilisé pour des simulations électromé- caniques ou l'analyse d'images cardiaques. Le c÷ur humain s'est révélé plus proche des c÷urs de chien au niveau de l'orientation des bres que de celle des feuillets. Le modèle synthétique quant à lui s'est montré trop simple pour décrire en détails la complexité de l'architecture des bres. L'acquisition de séquences d'images cardiaques permet d'observer le mouvement cardiaque et donc sa fonction. Nous avons proposé un nouvel algorithme de recalage nonlin éaire spatiotemporel de séquences d'images qui permet de comparer cette fonction cardiaque. Le recalage temporel assure la mise en correspondance d'instants physiologiques similaires. Le recalage spatial quant à lui doit assure une cohérence entre le mouvement des points physiques intra-séquence et leur mise en correspondance inter-séquence. Cette cohérence est assurée par les contraintes de trajectoires liant les transformations intras équences décrivant le mouvement cardiaque aux transformations inter-séquences décrivant les di érences anatomiques au cours du temps. Sous ces contraintes de trajectoires, le recalage spatial 4D est simpli é en un recalage multicanal 3D résolu avec une nouvelle version des Demons Di eomorphes Multicanaux. Cette méthode de recalage spatiotemporel est appliquée au recalage inter-sujet de séquences 4D CT pour évaluation. Comparée a d'autres techniques existantes, cette technique de recalage s'est révélée le meilleur compromis en terme de précision, de régularité spatiale et temporelle, mais aussi de temps de calcul. Un exemple d'application possible du recalage spatiotemporal est proposé avec la comparaison de l'anatomie et de la fonction cardiaques avant et après thérapie.

Des charrettes de la civilisation ancienne au Véhicule Utilitaire Sportif (VUS) actuels, la dépendance de l'homme pour les véhicules reste incontournable. Les avancements rapides des infrastructures de transport aujourd'hui, couplé au désir de voyager de plus en plus rapidement, conduisent à de graves problèmes de transport: accidents, pollution et embouteillages. Afin de réduire ces problèmes et augmenter la capacité de l'infrastructure actuelle, plusieurs approches ont été proposées. Les résultats se présentent, d'une part, sous forme de panneau à message variable qui affiche la situation du trafic aux conducteurs sur la route ; d' autre part, sous forme de dos d'âne pour la prévention des accidents en réduisant la vitesse des conducteurs dans les zones urbaines ; et enfin sous forme de décisions gouvernementale permettant de lutter contre la pollution en interdisant, les jours de forte pollution, l'accès au centre-ville pour les véhicules avec des numéros immatriculés pair ou impair. A la fin du XXe siècle, des efforts considérables sont apparus pour introduire l'intelligence dans les systèmes de transport. Afin de s'adapter à la complexité du système de transport, cela constitue un des facteurs déterminants pour une action durable et plus efficace. Au début, les initiatives se sont limitées au niveau de la télésurveillance sur les incidents de la circulation à l'aide de caméras pour en informer les utilisateurs via des panneaux à messages. Peu après, avec l'avènement de la communication sans fil, le monde a ouvert ses portes en direction de la recherche sur la communication inter-véhiculaires. Plus précisément, en permettant aux véhicules de détecter et de communiquer automatiquement sur les incidents de trafic avec d'autres véhicules on peut atteindre une connaissance étendue sur la situation de la circulation locale autour du conducteur. C'est un facteur très important pour l'installation efficace du Système des Transports Intelligent (STI). A l'heure actuelle, le principal défi est d'exploiter et utiliser efficacement la communication entre les véhicules afin de réduire, sinon éliminer complètement, les problèmes précités: accidents - par le biais de la sécurité active ; la pollution et les embouteillages - grâce à la fluidité du trafic et en guidant les conducteurs des transports à emprunter des itinéraires qui permettent d'économiser la consommation d'énergie et réduire les émissions. Cette thèse présente un élément important qui réalise le déploiement d'une STI à grande échelle: la communication entre les véhicules sur la route. Ce manuscrit est consacré au développement d'un algorithme de diffusion "Multi-Hop Vehicular Broadcast"(MHVB), en utilisant la localisation de véhicules pour permettre la communication entre les véhicules.