La révolution technologique que connaît le secteur automobile avec la multiplication des<br />systèmes électroniques et informatiques embarqués n'est pas près de s'essouffler. Il est<br />manifeste que la complexité croissante et la spécificité des systèmes embarqués justifieront de<br />plus en plus le besoin de structurer l'ensemble des activités de développement. Vérification,<br />validation, conception et bien entendu sûreté de fonctionnement font partie intégrante d'un<br />même processus. Nous cherchons tout d'abord à définir un formalisme de modélisation<br />fonctionnelle et comportementale, support de la méthodologie, et en cohérence avec les<br />spécificités des systèmes mécatroniques. En particulier, les aspects hybrides et temps réel<br />doivent pouvoir être représentés. Ensuite, sur le plan de la vérification et de la validation,<br />nous proposons d'exploiter les méthodes formelles, telles que le model-checking, en<br />complément des tests et des simulations habituellement utilisées dans l'industrie. Enfin nous<br />attachons une importance centrale à la sûreté de fonctionnement. Afin de pallier aux<br />insuffisances et aux limites des méthodes habituellement utilisées, nous proposons une<br />approche basée sur la construction d'un graphe de Markov agrégé. L'originalité tient dans sa<br />capacité de répondre à un problème de représentation et d'évaluation de la fiabilité des<br />systèmes dynamiques hybrides. Les principales étapes consistent à découpler la dynamique du<br />système et la dynamique du processus de défaillance grâce à la théorie des perturbations<br />singulières, puis d'identifier et estimer les grandeurs du système influençant la dynamique des<br />défaillances. Ces grandeurs sont évaluées par de simples simulations dans le but de pouvoir<br />traiter des systèmes complexes. Ceux-ci sont alors intégrés dans le graphe agrégé.

Cette thèse s'inscrit dans le cadre de la théorie des systèmes linéaires dans les dioïdes. Cette théorie concerne la sous-classe des systèmes à événements discrets modélisables par les Graphes d'Événements Temporisés (GET). La dynamique de ces graphes peut être représentée par des équations récurrentes linéaires sur des structures algébriques particulières telles que l'algèbre (max,+) ou l'algèbre (min,+).Ce mémoire est consacré à l'analyse de performances des systèmes dynamiques qui peuvent être modélisés graphiquement par des Graphes d'Événements Temporisés Généralisés (GETG). Ces derniers, contrairement au GET, n'admettent pas une représentation linéaire dans l'algèbre (min,+). Pour pallier à ce problème de non linéarité, nous avons utilisé une approche de modélisation définie sur un dioïde d'opérateurs muni de deux lois internes : loi additive correspondant à l'opération (min), et loi multiplicative équivalente à la loi de composition usuelle. Le modèle d'état obtenu, est utilisé pour évaluer les performances des GETG. Pour cela, nous avons proposé une nouvelle méthode qui a pour but de linéariser le modèle mathématique régissant l'évolution dynamique du modèle graphique, dans le but d'obtenir un modèle (min,+) linéaire. La deuxième partie de cette thèse est consacrée au problème qui consiste à déterminer les ressources à utiliser dans une ligne de production, en vue d'atteindre des performances souhaitée. Ceci est équivalent à déterminer le marquage initial de la partie commande du GETG.

L'objectif de cette thèse est d'instrumentaliser des moyens, centrés utilisateur, de représentation, d'acquisition, d'enrichissement et d'exploitation des métadonnées décrivant des documents multimédias socio-personnels. Afin d'atteindre cet objectif, nous avons proposé un modèle d'annotation, appelé SeMAT avec une nouvelle vision du contexte de prise de vue. Nous avons proposé d'utiliser des ressources sémantiques externes telles que GeoNames , et Wikipédia pour enrichir automatiquement les annotations partant des éléments de contexte capturés. Afin d'accentuer l'aspect sémantique des annotations, nous avons modélisé la notion de profil social avec des outils du web sémantique en focalisant plus particulièrement sur la notion de liens sociaux et un mécanisme de raisonnement permettant d'inférer de nouveaux liens sociaux non explicités. Le modèle proposé, appelé SocialSphere, construit un moyen de personnalisation des annotations suivant la personne qui consulte les documents (le consultateur). Des exemples d'annotations personnalisées peuvent être des objets utilisateurs (e.g. maison, travail) ou des dimensions sociales (e.g. ma mère, le cousin de mon mari). Dans ce cadre, nous avons proposé un algorithme, appelé SQO, permettant de suggérer au consultateur des dimensions sociales selon son profil pour décrire les acteurs d'un document multimédia. Dans la perspective de suggérer à l'utilisateur des évènements décrivant les documents multimédias, nous avons réutilisé son expérience et l'expérience de son réseau de connaissances en produisant des règles d'association. Dans une dernière partie, nous avons abordé le problème de correspondance (ou appariement) entre requête et graphe social. Nous avons proposé de ramener le problème de recherche de correspondance à un problème d'isomorphisme de sous-graphe partiel. Nous avons proposé un algorithme, appelé h-Pruning, permettant de faire une correspondance rapprochée entre les nœuds des deux graphes : motif (représentant la requête) et social. Pour la mise en œuvre, nous avons réalisé un prototype à deux composantes : web et mobile. La composante mobile a pour objectif de capturer les éléments de contexte lors de la création des documents multimédias socio-personnels. Quant à la composante web, elle est dédiée à l'assistance de l'utilisateur lors de son annotation ou consultation des documents multimédias socio-personnels. L'évaluation a été effectuée en se servant d'une collection de test construite à partir du service de médias sociaux Flickr. Les tests ont prouvé : (i) l'efficacité de notre approche de recherche dans le graphe social en termes de temps d'exécution ; (ii) l'efficacité de notre approche de suggestion des événements (en effet, nous avons prouvé notre hypothèse en démontrant l'existence d'une cooccurrence entre le contexte spatio-temporel et les événements) ; (iii) l'efficacité de notre approche de suggestion des dimensions sociales en termes de temps d'exécution.

Une mosaïque aléatoire est une partition aléatoire de l'espace euclidien en des polytopes appelés cellules. Ce type de structure apparaît dans divers domaines tels que la biologie cellulaire, les télécommunications et la segmentation d'images. Beaucoup de travail a déjà été effectué sur la cellule typique c'est-à-dire sur une cellule "choisie uniformément". Cependant, ces travaux ne tiennent pas compte de l'irrégularité de la mosaïque et d'éventuelles cellules pathologiques (par exemple, celles qui sont anormalement allongées ou anormalement grandes). Dans cette thèse, on étudie les mosaïques aléatoires par une approche inédite: celle des valeurs extrêmes. En pratique, on observe la mosaïque aléatoire dans une fenêtre et on considère une certaine caractéristique géométrique (comme le volume, le nombre de sommets ou le diamètre des cellules). Le problème de base est d'étudier le comportement du maximum et du minimum, voire des statistiques d'ordre, de cette caractéristique pour toutes les cellules de la fenêtre lorsque la taille de celle-ci tend vers l'infini. Une telle approche permet non seulement de mieux comprendre la régularité de la mosaïque mais aussi d'étudier la qualité d'une approximation discrète d'un ensemble par des cellules d'une mosaïque aléatoire. Cette approche pourrait également fournir une piste inédite pour discriminer les processus ponctuels. Les résultats de cette thèse portent principalement sur des théorèmes limites des extrêmes et des statistiques d'ordre pour diverses caractéristiques géométriques et diverses mosaïques aléatoires. En particulier, on obtient des vitesses de convergence en établissant de fines estimations géométriques. On déduit de l'étude du maximum des diamètres une majoration de la distance de Hausdorff entre un ensemble et son approximation dite de Poisson-Voronoï. On traite, notamment, de plusieurs aspects géométriques comme les problèmes de bord et la forme des cellules optimisantes. Enfin, dans le but de savoir comment se répartissent les cellules excédentes (celles dont la caractéristique est grande), on s'intéresse à la convergence de processus ponctuels associés et à la taille moyenne d'un cluster d'excédents. Les outils utilisés sont issus à la fois de la géométrie aléatoire (mesure de Palm, probabilités de recouvrement, formule de Slivnyak) et de la théorie des valeurs extrêmes (graphes de dépendance, méthode de Chen-Stein, indice extrême).

La première partie de notre travail, menée en collaboration étroite avec V. BOUCHITTE et M. HABIB, porte sur l'étude de quelques invariants comme le nombre de sauts et la dimension sur les ensembles ordonnés finis. Nous reproduisons ici intégralement les deux articles N-free posets as generalizations of series-parallel posets M. HABIB, R. JEGOU Sorne results on the greedy dimension V. BOUCHITTE~ M. HABIB, R. JEGOU à paraître respectivement dans Discrete Applied Mathematics et dans Order. Le nombre de sauts a fait l'objet de nombreux travaux parmi lesquels ceux de G. CHATY, M. CHEIN, O. COGIS, U. FAIGLE, G. GIERZ, M. HABIB, P. MARTIN, G. PETOLLA, W. POGUNTKE, W.R. PULLEYBLANK, I. RIVAL, M.M. SYSLO ..., et reste d'actua1ité comme en témoigne le congrès GRAPHS and OROER (Banff 1984). Cette notion définie originellement sur les graphes sans circuit comme étant le nombre minimum d'arcs à ajouter à un tel graphe pour obtenir un graphe sans circuit ayant un chemin hamiltonien, est étudiée ici sur les ordres sans N. Nous mettons en évidence une construction récursive de ces ordres en généralisant celle des ordres série parallèles(SP) introduits par E.L. LAWLER et étudiés notamment par J. VALDES, R.E. TARJAN et E.L. LAWLER. Les ordres sans N, ou quasi-série-parallè1es(QSP), peuvent donc se définir à 1 'aide de deux opérations simples à partir de l'ordre réduit à un élément. Cette construction permet en particulier d'obtenir un algorithme linéaire (en fonction du nombre de sommets et du nombre d'arcs du graphe de Hasse) de reconnaissance et de décomposition qui calcule le nombre de sauts.

Dans ce mémoire de thèse, nous nous intéressons à l'affectation des vols aux avions dans une compagnie aérienne. Notre objectif est de proposer des plannings de vols qui prennent en compte des contraintes de maintenance, en utilisant des algorithmes efficaces. Au cours de nos recherches, nous avons ramené le problème de rotation des avions à des cas particuliers du problème de partitionnement d'un graphe orienté acyclique par des chemins disjoints. Nous avons fait des études de complexité pour différents cas et nous avons proposé des algorithmes de liste, un recuit simulé et une approche heuristique basée sur la génération de colonnes. Nous avons finalement comparé la performance de ces méthodes sur différentes instances.

Les entreprises aéronautiques ont un besoin continu de générer de grands et complexes modèles de simulation, en particulier pour simuler le comportement structurel de sous-systèmes de leurs produits. Actuellement, le pré-traitement des modèles de Conception Assistée par Ordinateur (CAO) issus des maquettes numériques de ces sous-systèmes en Modèles Eléments Finis (MEF), est une tâche qui demande de longues heures de travail de la part des ingénieurs de simulation, surtout lorsque des idéalisations géométriques sont nécessaires. L'objectif de ce travail de thèse consiste à définir les principes et les opérateurs constituant la chaîne numérique qui permettra, à partir de maquettes numériques complexes, de produire des géométries directement utilisables pour la génération de maillages éléments finis d'une simulation mécanique. A partir d'une maquette numérique enrichie d'information sur les interfaces géométriques entre composants et d'information sur les propriétés fonctionnelles de l'assemblage, l'approche proposée dans ce manuscrit est d'ajouter un niveau supplémentaire d'enrichissement en fournissant une représentation structurelle de haut niveau de la forme des composants CAO. Le principe de cet enrichissement est d'extraire un graphe de construction de modèles CAO B-Rep de sorte que les processus de génération de forme correspondants fournissent des primitives volumiques directement adaptées à un processus d'idéalisation. Ces primitives constituent la base d'une analyse morphologique qui identifie dans les formes des composants à la fois des sous-domaines candidats à l'idéalisation mais également les interfaces géométriques qui leurs sont associées. Ainsi, les modèles de composants et leurs représentations géométriques sont structurés. Ils sont intégrés dans la maquette numérique enrichie qui est ainsi contextualisée pour la simulation par EF. De cette maquette numérique enrichie, les objectifs de simulation peuvent être utilisés pour spécifier les opérateurs géométriques adaptant les composants et leurs interfaces lors de processus automatiques de préparation d'assemblages. Ainsi, un nouveau procédé d'idéalisation de composant unitaire est proposé. Il bénéficie de l'analyse morphologique faite sur le composant lui fournissant une décomposition en sous-domaines idéalisables et en interfaces. Cette décomposition est utilisée pour générer les modèles idéalisés de ces sous-domaines et les connecter à partir de l'analyse de leurs interfaces, ce qui conduit à l'idéalisation complète du composant. Enfin, le processus d'idéalisation est étendu au niveau de l'assemblage et évolue vers une méthodologie de pré-traitement automatique de maquettes numériques. Cette méthodologie vise à exploiter l'information fonctionnelle de l'assemblage et les informations morphologiques des composants afin de transformer à la fois des groupes de composants associés à une même fonction ainsi que de traiter les transformations d'idéalisation de l'assemblage. Pour démontrer la validité de la méthodologie, des opérateurs géométriques sont développés et testés sur des cas d'application industriels.

La technique de paramétrisation est très prometteuse pour la conception radio logicielle. La radio logicielle consiste à concevoir des systèmes multi-standards qui tirent bénéfice des possibilités de programmation ou de reconfiguration offertes par les composants de traitement la constituant. Cette thèse étudie la technique de paramétrisation par opérateurs communs. Les opérateurs communs sont des unités de traitements communes à plusieurs opérations qu'effectue un équipement, quelle que soit la couche du modèle OSI à laquelle elles appartiennent. La méthode proposée repose sur une approche théorique afin de résoudre le problème de conception d'un équipement multi-standards. Elle consiste en une optimisation d'un hypergraphe. La conception de l'équipement est représentée par des opérateurs à différents niveaux de granularité dans un graphe acyclique orienté. Le niveau le plus élevé représente une approche de conception d'équipements multi-standards de type Velcro. Plus les opérateurs sont bas dans le graphe, plus leur coût est faible en termes de complexité, mais plus il faut faire appel de fois à eux pour effectuer des opérations de différentes sortes. Nous décrivons ensuite en tant qu'exemples des conception basées sur les opérateurs DMFFT (dual mode FFT), LFSR (linear feedback shift register) et le cas du FRMFB (frequency response masking filter bank). Les solutions basées sur les opérateurs communs proposées dans cette thèse peuvent contribuer à optimiser la conception des futurs équipements multi-standards de radio logicielle qui devront supporter de nombreux standards de communication sans fil.

Orienter un graphe c'est remplacer chaque arête par un arc de mêmes extrémités. On s'intéresse à la connexité du graphe orienté ainsi obtenu. L'orientation avec des contraintes d'arc-connexité est maintenant comprise en profondeur mais très peu de résultats sont connus en terme de sommet-connexité. La conjecture de Thomassen avance que les graphes suffisament sommet-connexes ont une orientation k-sommet-connexe. De plus, la conjecture de Frank propose une caractérisation des graphes qui admettent une telle orientation. Les résultats de cette thèse s'articulent autour des notions d'orientation, de packing, de connexité et de matroïde. D'abord, nous infirmons une conjecture de Recski sur la décomposition d'un graphe en arbres ayant des orientations avec degrés entrants prescrits. Nous prouvons également un nouveau résultat sur le packing d'arborescences enracinées avec contraintes de matroïdes. Ceci généralise un résultat fondamental d'Edmonds. Enfin, nous démontrons un nouveau théorème de packing sur les bases des matroïdes de dénombrement qui nous permet d'améliorez le seul résultat connu sur la conjecture de Thomassen. D'autre part, nous donnons une construction et un théorème d'augmentation pour une famille de graphes liée à la conjecture de Frank. En conclusion, nous réfutons la conjecture de Frank et prouvons que, pour tout entier k >= 3, décider si un graphe a une orientation k-sommet-connexe est un problème NP-complet.

Le contourage des ventricules cardiaques sur IRM est nécessaire à la détermination de la fonction contractile du cœur. Cette tâche est difficile, en particulier pour le ventricule droit (VD), due au flou aux frontières des cavités, aux irrégularités des intensités et à sa forme complexe et variable. Peu de travaux ont cependant été réalisés afin de résoudre cette problématique de segmentation. Dans ce but, nous avons proposé et développé deux méthodes de segmentation basées sur la méthode des coupes de graphe (GC), à laquelle nous avons incorporé des a priori de forme. La première méthode, semi-automatique, repose sur une carte d'a priori statistique créée à base d'Analyses en Composantes Principales et intégrée à la méthode des GC binaires. La seconde, automatique, permet la segmentation d'un ensemble d'objets par GC multi-labels à partir d'un modèle de forme probabiliste basé sur le recalage et la fusion d'atlas. Ces méthodes ont été évaluées sur une base importante d'IRM cardiaques, composée de 48 patients. Une comparaison aux méthodes de l'état de l'art pour cette application à travers le challenge de segmentation du VD MICCAI'12, que nous avons organisé, montre l'efficacité de nos méthodes.