Tesis sobre el tema "[INFO:INFO_OH] Computer Science/Other"

Les récents outils dédiés aux Sciences de l'Information Géographique s'attachent principalement à visualiser, analyser voire interpréter une information dite quantitative, c'est-à-dire issue de données cartographiques. Malgré une utilisation exponentielle voire quotidienne de ces systèmes, ces derniers ne correspondent pas à la manière dont un individu perçoit l'espace. Le mécanisme de perception spatiale est en effet dépendant de nos propres connaissances, du contexte ou de la tâche à réaliser. Il entraîne une représentation cognitive de l'environnement qui est caractérisée par une absence de formalisation des concepts manipulés. Cette représentation n'est pas une reproduction fidèle de la réalité, mais un assemblage d'objets aux formes et aux échelles exagérées qui est structuré par des relations spatiales approximatives. Ce travail est né du paradoxe suivant : comment peut-on utiliser des systèmes informatiques dont les fondements reposent sur des données quantitatives, alors que la perception de l'espace et son expression par le langage naturel sont par définition absentes de toute formalisation, et ainsi très éloignées de la précision métrique recherchée par les outils géo-informatiques actuels ? L'objectif de cette thèse consiste à associer une représentation cognitive issue de la perception d'un environnement naturel, aux données quantitatives provenant d'une base de données géographiques. Le scénario associé à cette approche s'attache à identifier les positions géographiques d'un individu à partir de la description de ses environs : un randonneur ou un pêcheur perdu ne disposant pas d'outil de géo-positionnement, décrit de manière spontanée son environnement à un interlocuteur qui s'appuie sur les propositions d'un système informatique pour le localiser. Une modélisation de la description linguistique puis de la scène environnementale perçue est proposée. Cette "carte conceptuelle" est contrainte par quatre espaces de proximité et deux à quatre cônes directionnels qui ordonnent et orientent les objets perçus par rapport à la position fixe de l'individu. Une telle représentation ne permet cependant pas de distinguer les entités saillantes, des entités ne favorisant pas le géo-positionnement de l'observateur. Nous avons donc proposé deux critères de saillance linguistique et spatiale fondés sur un algorithme de renforcement mutuel. Les positions géographiques possibles de l'individu sont alors calculées à partir de l'interprétation de la configuration spatiale fournie par la carte conceptuelle. Les zones de visibilité des objets perçus sont calculées puis les relations spatiales sont interprétées sous la forme de contraintes spatiales. Chaque nouvelle contrainte réduit au fur et à mesure l'espace solution, et le résultat exploitable pour lancer les opérations de recherche de l'individu est fourni par l'intersection des différentes régions.

Les Systèmes Multi-Agents (SMA) forment un paradigme prometteur pour la conception de systèmes logiciel complexes. En effet, ce paradigme propose de nouvelles stratégies pour analyser, concevoir et implémenter de tels systèmes. Les systèmes multi-agents sont considérés comme des sociétés composées d'entités autonomes et indépendantes, appelées agents, qui interagissent en vue de résoudre un problème ou de réaliser collectivement une tâche. Nous nous plaçons dans un cadre d'ingénierie logicielle pour ce mémoire. Pour tout nouveau paradigme d'ingénierie logicielle pour pouvoir être pleinement appliqué et déployé il est nécessaire de disposer de nouveaux modèles et d'abstractions nouvelles. Ces abstractions servent de base à l'analyse et à la conception des SMA. De plus, toute méthodologie dédiée aux SMA doit prendre ces abstractions pour pouvoir développer des SMA de manière sys\-té\-ma\-ti\-que, sure, robuste et fiable. Les modèles à la base de tous les travaux dans ce mémoire sont composés de concepts organisationnels qui permettent de concevoir les SMA comme des sociétés d'individus, les agents, qui jouent des rôles dans des organisations. Ces concepts permettent également la description de structures organisationnelles complexes telles que les holarchies dans lesquelles les agents, désignés par le terme holons, peuvent être composés d'autres holons et définir une structure hiérarchique. La définition de ces concepts se fait au travers de méta-modèles exprimés avec une notation semi-formelle. Pour définir une sémantique non ambigüe et bénéficier d'outils de validation et de vérification nous proposons de spécifier des concepts au travers d'un langage formel. Aucun langage ne satisfaisant nos besoins nous avons composé deux langages existants : Object-Z et les statecharts. La syntaxe et la sémantique du langage formel OZS sont définies sur cette base. Des architectures d'agents sont étudiées en utilisant le modèle organisationnel et les outils formels. Ces études sont de deux types, définition complète d'une architecture et rétro-ingénierie afin de comprendre et analyser les éléments fondateurs d'architectures existantes pour pouvoir les réutiliser dans d'autres contextes. Deux méthodologies sont exploitant les concepts et la notation formelle sont proposées. La première est issue d'un travail initial concernant l'analyse et la conception de SMA Holoniques utilisant un cadre particulier. La deuxième est issue d'une collaboration avec Massimo Cossentino et est plus générale.

La recherche d'information est confrontée à une variété de plus en plus importante tant en termes d'usagers, de tâches à remplir, d'outils.... Face à cette hétérogénéité de nombreux travaux, s'attachent à améliorer la recherche d'information par le biais d'approches adaptatives, de systèmes de recommandation... Mes travaux s'inscrivent dans ce cadre et apportent un éclairage essentiellement porté sur l'usager et ses activités et plus particulièrement sur la recherche d'information. Les résultats correspondent à 3 angles d'investigation nous permettant d'aborder cette problématique de l'hétérogénéité en Recherche d'Information.

Dans les simulations centrées individu, la variété et la cohérence du comportement des agents sont des critères importants pour le réalisme et la validité de la simulation. Dans ce travail, nous nous sommes intéressés à la prise en compte simultanée de ces deux éléments. Nous proposons un modèle de différenciation comportementale, qui se décline en un outil dont les principaux apports sont d'être générique, non-intrusif, et de permettre une conception en dehors de l'agent. Le modèle s'articule selon trois axes. Tout d'abord, il décrit les comportements des agents par des normes. Celles-ci fournissent un profil comportemental à la conception, et un contrôle de la conformité à l'exécution. Ensuite, le processus de génération des comportements permet d'autoriser la création d'agents déviants ou en violation. Il inlfue pour cela sur le déterminisme du mécanisme. Enfin, les normes peuvent être inférées à partir de simulations enregistrées ou de situations réelles, afin d'analyser les résultats des expérimentations et d'automatiser la configuration du modèle. Nous avons appliqué cet outil à la simulation de trafic dans SCANeR, l'application développée et utilisée par Renault pour ses simulateurs de conduite. Les développements réalisés au cours de la thèse introduisent dans le trafic des styles de conduite spécifiés sous forme de normes, par exemple des conducteurs prudents ou agressifs. Ils permettent ensuite de peupler l'environnement de manière automatisée. Au delà de l'amélioration subjective du réalisme, les expérimentations réalisées démontrent les apports de l'outil sur la variété et la représentativité des comportements obtenus.

Wavelet analysis is a powerful mathematical tool commonly used in signal processing applications, such as image analysis, image compression, image edge detection, and communications systems. Unlike traditional Fourier analysis, wavelet analysis allows for multiple resolutions in the time and frequency domains; it can preserve time information while decomposing a signal spectrum over a range of frequencies. Wavelet analysis is also more suitable for detecting numerous transitory characteristics, such as drift, trends, abrupt changes, and beginnings and ends of events. These characteristics are often the most important and critical part of some non-stationary signals, such as physiological signals. The thesis focuses on a formal analysis of using wavelet transform for noise filtering. The performance of the wavelet analysis is simulated on a variety of patient samples of Arterial Blood Pressure (ABP 14 sets) and Electrocardiography (ECG 14 sets) from the Mayo Clinic at Jacksonville. The performance of the Fourier analysis is also simulated on the same patient samples for comparison purpose. Additive white Gaussian noise (AWGN) is generated and added to the samples for studying the AWGN effect on physiological signals and both analysis methods. The algorithms of finding the optimal level of approximation and calculating the threshold value of filtering are created and different ways of adding the details back to the approximation are studied. Wavelet analysis has the ability to add or remove certain frequency bands with threshold selectivity from the original signal. It can effectively preserve the spikes and humps, which are the information that is intended to be kept, while de-noising physiological signals. The simulation results show that the wavelet analysis has a better performance than Fourier analysis in preserving the transitory information of the physiological signals.

Les systèmes multi-agents (SMA) permettent à ce jour de simuler des phénomènes impliquant des entités en interactions. Ces entités peuvent représenter des experts et doivent alors utilisent des processus cognitifs de haut niveau (perception, prise de décision, raisonnement, stockage de l'information en mémoire). Depuis longtemps, la psychologie cognitive étudie ces processus cognitifs et a proposé des modèles conceptuels de la cognition humaine. L'approche « Naturalistic Decision Making » (prise de décision naturelle) et plus particulièrement RPD (Recognition-Primed-Decision), modélise la prise de décisions efficaces par des individus dans des situations complexes en fonction de leur expérience et du contexte. L'objectif de cette thèse est d'intégrer au sein d'un SMA, via l'approche Agent-Groupe-Rôle, le modèle RPD pour simuler les comportements d'experts. L'expérience des individus est stockée à l'aide d'une base de patrons. Un patron associe à une situation prototypique une décision générique. Le modèle de prise de décision qui en découle : DBP (Décision à Base de Patrons) est décomposé en quatre phases. La première ; la perception de la situation courante est basée sur des sous-ensembles flous. Ils sont employés pour transformer des données quantitatives en données qualitatives. Une phase d'appariement de la situation courante à une ou plusieurs situations prototypiques est alors lancée. Puis, le patron optimal, en fonction de critères spécifiques au profil de chaque agent, est retenu. Finalement, la décision est traduite en une action. DBP est validé par une extension du simulateur TRANS (Tractable Role Agent prototype for concurrent Navigation Systems) afin de reproduire le comportement d'experts maritimes. L'extension créée ; CogTRANS (cognitive TRANS) porte plus particulièrement sur les décisions des chefs de quart à bord de ferries et de cargos. CogTRANS permet de simuler les évitements de collisions de façon réaliste. Il offre ainsi de bonnes perspectives pour une meilleure compréhension des risques maritimes et l'amélioration d'outils pédagogiques pour l'apprentissage de la navigation.

The foundation of term rewriting is equational logic but for the sake of efficiency, the equations are oriented and become the rules of a term rewriting system. Term rewriting form a model of computation on algebraic data structures (terms). Term rewriting systems play an important role in various domains of computer science such as automated theorem proving, functional programming, code generation, problem formalization (security of cryptographic protocols). Rewriting starts with a ground term, and consists of repeatedly replacing a redex (an instance of a left-hand side) by its contractum (the corresponding right-handside after applying the substitution). Rewriting may eventually yield a term in normal form which is a term containing no redex. Natural questions in term rewriting are: * is the system terminating" (i.e. there are no infinite rewrite sequences)? * "is the system confluent" (if a term rewrites independently to two terms t1 and t2 , there exists a term s such that both t1 and t2 rewrite to s)? We are interested in systems which can be used as programs so we want to allow non-terminating computations. Confluence implies unicity of normal forms but does not imply termination. Confluent systems form a good framework for deterministic programming. They have the power of Turing machines. However confluence is not a decidable property for term rewriting systems. Orthogonal systems (i.e. linear and non-overlapping left-hand sides) which are always confluent form the framework of all this work, although some results may apply to the more general class of left-linear systems (linear left-hand sides). The first point we want to address is "how to compute the normal form?" and not end up in an infinite computation when the normal form exists. The second is "how to do that efficiently?". The following theorem of Huet and Levy [HL91] forms the basis of all result on optimal normalizing rewrite strategies for orthogonal term rewrite systems: "Every reducible term contains a needed redex, i.e., a redex which is contracted in every rewrite sequence to normal form, and repeated contraction of needed redexes results in a normal form, if the term under consideration has a normal form". Unfortunately, needed redexes are not computable in general. Hence, in order to obtain a computable optimal rewrite strategy, we are left to find (1) decidable approximations of neededness and (2) decidable properties of rewrite systems which ensure that every reducible term has a needed redex identi-fied by (1). Starting with the seminal work of Huet and Levy [HL91] on strong sequentiality, these issues have been extensively investigated in the literature [Com00, Jac96b, JS95, KM91, NST95, Oya93, Toy92]. In all these works Huet and Levy's notions of index, omega-reduction, and sequentiality figure prominently. We present here our contributions to this domain.

L'informatique et en particulier l'Internet jouent un rôle grandissant dans notre société. Un grand nombre d'applications critiques d'un point de vue de leur sécurité sont déployées dans divers domaines comme le domaine militaire, la santé, le commerce électronique, etc. La sécurité des systèmes informatiques devient alors une problématique essentielle tant pour les individus que pour les entreprises ou les états. Il est donc important de définir une politique de sécurité pour ces systèmes et de veiller à son respect. Néanmoins les mécanismes de sécurité préventifs mis en place ne sont pas incontournables. Il est nécessaire de mettre en œuvre des outils permettant de détecter toute violation de la politique de sécurité, c'est-à-dire toute intrusion. Ces outils sont appelés des systèmes de détection d'intrusions ou IDS. Souvent en collaboration avec les IDS, il est possible de mettre en place des outils et techniques de tolérance aux intrusions. Ces outils et techniques ont pour objectif que les intrusions affectant un composant du système n'entrainent pas de violations de la politique de sécurité du système global.
Notre travail s'inscrit dans le domaine de la détection d'intrusions, de manière essentielle, et permet une certaine tolérance aux intrusions. Contrairement aux méthodes de détection classiques en détection comportementale pour lesquelles il est nécessaire de définir et construire un modèle de référence du comportement de l'entité surveillée, nous avons suivi une méthode issue de la sureté de fonctionnement fondée sur la programmation N-versions pour laquelle le modèle de référence est implicite et est constitué par les autres logiciels constituant l'architecture. Nous proposons l'utilisation de COTS en remplacement des versions spécifiquement développées car développer N-versions est couteux et est réservé à des systèmes critiques du point de vue de la sécurité-innocuité. D'autres travaux et projets ont proposé des architectures fondées sur ces idées. Nos contributions se situent à différents niveaux. Nous avons pris en compte dans notre modèle général de détection d'intrusions les spécificités liées à l'utilisation de COTS en lieu et place de versions spécifiquement développées et proposé deux solutions pour parer aux problèmes induits par ces spécificités. Nous avons proposé deux approches de détection d'intrusions fondées sur cette architecture : l'une suivant une approche de type boite noire et l'autre suivant une approche de type boite grise. Notre méthode de type boite grise peut, en outre, aider l'administrateur de sécurité à effectuer un premier diagnostic des alertes. Nous avons réalisé une implémentation de ces deux approches dans le cadre des serveurs web et avons évalué pratiquement la pertinence et de la fiabilité de ces deux IDS.

Nous nous intéressons à la multilinguïsation, ou « portage linguistique » (plus simple que la localisation) des services de gestion de contenu traitant des énoncés spontanés en langue naturelle, souvent bruités, mais contraints par la situation, et constituant toujours un « sous-langage » plus ou moins restreint. Un service de ce type (soit App) utilise une représentation du contenu spécifique (RC-App) sur laquelle travaille le noyau fonctionnel. Le plus souvent, cette représentation est produite à partir de la langue « native » L1 par un extracteur de contenu (EC-App). Nous avons dégagé trois méthodes de portage possibles, et les avons illustrées par le portage en français d'une partie de CATS, un système de traitement de petites annonces en SMS (en arabe) déployé à Amman, ainsi que sur IMRS, un système de recherche de morceaux de musique dont l'interface native est en japonais et dont seule la RC est accessible. Il s'agit de : (1) localisation « interne », i. E. Adaptation à L2 de l'EC donnant EC-App-L2 ; (2) localisation « externe », i. E. Adaptation d'un EC existant pour L2 au domaine et à la représentation de contenu de App (EC-X-L2-App); (3) traduction des énoncés de L2 vers L1. Le choix de la stratégie est contraint par la situation traductionnelle : types et niveau d'accès possibles (accès complet au code source, accès limité à la représentation interne, accès limité au dictionnaire, et aucun accès), ressources disponibles (dictionnaires, corpus), compétences langagières et linguistiques des personnes intervenant dans la multilinguïsation des applications. Les trois méthodes ont donné de bons résultats sur le portage d'arabe en français de la partie de CATS concernant l'occasion automobile. En localisation interne, la partie grammaticale a été très faiblement modifiée, ce qui prouve que, malgré la grande distance entre l'arabe et le français, ces deux sous-langages sont très proches l'un de l'autre, une nouvelle illustration de l'analyse de R. Kittredge. La localisation externe a été expérimentée sur CATS et sur IMRS en adaptant au nouveau domaine considéré l'extracteur de contenu du français écrit initialement par H. Blanchon pour le domaine du tourisme (projet CSTAR/Nespole!), puis en changeant de langue pour IMRS (anglais). Enfin, le portage par TA statistique a également donné de très bonnes performances, et cela avec un corpus d'apprentissage très petit (moins de 10. 000 mots) et un dictionnaire complet. Cela prouve que, dans le cas de sous-langages très petits, la TA statistique peut être de qualité suffisante en partant de corpus 100 à 500 fois moins grands que pour de la langue générale
We are interested in the multilinguization, or “linguistic porting” (simpler than localization) of management content services processing spontaneous utterances in natural language, often noisy, but constrained by the situation and constituting a restricted “sublangage”. Any service of this type (App) uses a specific content representation (CR-App) on which the functionnal kernel operates. Most often, this representation is produced from the “native” language L1 by a content extractor (CE-App). We identified three possible methods of porting and have illustrated them by porting to French a part of CATS, a system handling small ads in SMS (in Arabic), deployed in Amman, as well as IMRS, a music retrieval system, where the native natural language interface is in Japanese and only the CR is accessible. These are: (1) “internal localisation”, i. E. Adaptation to L2 of the CE, giving CE-App-L2; (2)”external” localization , i. E. Adaptation of an existing CE for L2 to the domain and to the App content representation (CE-X-L2-App); (3) translation of utterances from L2 to L1. The choice of the strategy is constrained by the translational situation: type and level of possible access (complete access to the source code, access limited to the internal representation, access limited to the dictionary, and no access), available resources (dictionaries, corpus), competences in languages and linguistics of persons taking part in the multilinguisation of application. The three methods gave good results on the Arabic to French porting of the CARS part of CATS. For internal localization, the grammatical part was very little modified, which proves that, despite the great distance between Arabic and French, these two sub-languages are very near one to another. This is a new illustration of R. Kittredge’s analysis. The external localization was experimented with CATS and with IMRS by adapting to the new domain the French content extractor written initially by H. Blanchon for the tourism domain (CSTAR/Nespole! project), and then by changing the language for IMRS (English). Finally, porting by statistical MT gave also a very good performance, and that with a very small training corpus (less than 10 000 words) and a complete dictionary. This proves that, in the case of very small sub-languages, statistical MT may be of sufficient quality, starting from a corpus 100 to 500 smaller than for the general language

Nous nous intéressons à la multilinguïsation, ou « portage linguistique » (plus simple que la localisation) des services de gestion de contenu traitant des énoncés spontanés en langue naturelle, souvent bruités, mais contraints par la situation, et constituant toujours un « sous-langage » plus ou moins restreint.
Un service de ce type (soit App) utilise une représentation du contenu spécifique (RC-App) sur laquelle travaille le noyau fonctionnel. Le plus souvent, cette représentation est produite à partir de la langue « native » L1 par un extracteur de contenu (EC-App). Nous avons dégagé trois méthodes de portage possibles, et les avons illustrées par le portage en français d'une partie de CATS, un système de traitement de petites annonces en SMS (en arabe) déployé à Amman, ainsi que sur IMRS, un système de recherche de morceaux de musique dont l'interface native est en japonais et dont seule la RC est accessible. Il s'agit de : (1) localisation « interne », i.e. adaptation à L2 de l'EC donnant EC-App-L2 ; (2) localisation « externe », i.e. adaptation d'un EC existant pour L2 au domaine et à la représentation de contenu de App (EC-X-L2-App); (3) traduction des énoncés de L2 vers L1.
Le choix de la stratégie est contraint par la situation traductionnelle : types et niveau d'accès possibles (accès complet au code source, accès limité à la représentation interne, accès limité au dictionnaire, et aucun accès), ressources disponibles (dictionnaires, corpus), compétences langagières et linguistiques des personnes intervenant dans la multilinguïsation des applications.
Les trois méthodes ont donné de bons résultats sur le portage d'arabe en français de la partie de CATS concernant l'occasion automobile. En localisation interne, la partie grammaticale a été très faiblement modifiée, ce qui prouve que, malgré la grande distance entre l'arabe et le français, ces deux sous-langages sont très proches l'un de l'autre, une nouvelle illustration de l'analyse de R. Kittredge. La localisation externe a été expérimentée sur CATS et sur IMRS en adaptant au nouveau domaine considéré l'extracteur de contenu du français écrit initialement par H. Blanchon pour le domaine du tourisme (projet CSTAR/Nespole!), puis en changeant de langue pour IMRS (anglais).
Enfin, le portage par TA statistique a également donné de très bonnes performances, et cela avec un corpus d'apprentissage très petit (moins de 10.000 mots) et un dictionnaire complet. Cela prouve que, dans le cas de sous-langages très petits, la TA statistique peut être de qualité suffisante en partant de corpus 100 à 500 fois moins grands que pour de la langue générale.

Cette thèse traite des langages reconnaissables de mots indexés par des ordinaux. Plusieurs classes d'automates qui reconnaissent de tels mots ont été introduites par Büchi. Elles diffèrent par la longueur des mots reconnus par les automates. Nous en utilisons quatre: la classe pour les mots de longueur , celle pour les mots de longueur inférieure à , où n est un entier naturel, celle pour les mots de longueur dénombrable, et celle pour les mots de longueur quelconque. Nous y ajoutons la classe des automates de Kleene traditionnelle, sur les mots finis. Nous remontrons que ces différentes définitions d'automates sont équivalentes, c'est-à-dire que données deux de ces classes et un automate d'une des deux, la restriction du langage reconnu par l'automate aux mots du domaine le plus petit des deux classes est la restriction du langage reconnu par un automate de l'autre classe au même domaine. Nous donnons également une présentation unifiée de la déterminisation pour chacune des classes qui reconnaît au plus des mots de longueur dénombrable. Les semigroupes finis sont un formalisme équivalent aux automates pour définir des ensembles de mots finis. Perrin, Pin et Wilke ont introduits des structures algébriques adaptées à l'étude des langages de mots de longueur , qui, quand elles sont finies, sont équivalentes aux automates. Nous généralisons l'approche algébrique de la théorie des langages reconnaissables de mots de longueur aux mots de longueur inférieure à , puis aux mots de longueur dénombrable. Pour cela, nous définissons deux structures algébriques, les -semigroupes et les -semigroupes, qui, quand elles sont finies, sont équivalentes respectivement aux automates pour les mots de longueur inférieure à et aux automates pour les mots de longueur dénombrable. Comme pour le cas des mots de longueur , une algèbre syntaxique peut être canoniquement associée à chaque langage reconnaissable. Nous définissons le produit de Schützenberger et le produit en couronne sur les -semigroupes. Nous étendons également le théorème des variétés d'Eilenberg aux mots de longueur dénombrable. Finalement, nous remontrons l'équivalence entre langages reconnus par automates et langages définis par énoncés de logique monadique du second ordre quand on s'intéresse aux mots de longueur dénombrable. Le théorème d'équivalence de Schützenberger entre langages sans étoile et semigroupes finis apériodiques est étendu aux mots de longueur inférieure à , et le théorème d'équivalence entre langages sans étoile et langages définis par énoncés de logique du premier ordre de l'ordre linéaire de McNaughton et Papert est étendu aux mots de longueur quelconque.

L'objectif de cette thèse est d'examiner comment les technologies orientées-objet peuvent apporter aux applications scientifiques tout ce qu'elles ont apporté dans la programmation des machines séquentielles: une meilleure réutilisabilité et pérennité des codes, des démarches méthodologiques de conception et de réalisation claires... La contrainte du calcul scientifique parallèle de ne pas sacrifier les performances devant être respectée.

Après une revue des moyens de programmation parallèle et des
concepts objets, la conception et la réalisation d'une bibliothèque parallèle d'algèbre linéaire orientée-objet sont présentées. Nous étudions deux moyens de programmation parallèle, le premier, C++//, est un LAO parallèle à objets actifs dérivé de C++, le second est l'utilisation de MPI au travers d'une surcouche objet minimale.
Ces deux approches objets posent des problèmes soit de performances soit de réutilisabilité séquentielle/parallèle qui sont présentés et résolus.

Nous proposons notamment un mécanisme simple de partage en lecture pour les modèles à objets actifs, en montrant son utilité en terme de performances de nos applications. Suite à la seconde approche nous définissons les notions de formes de matrices et de matrices avec forme qui permettent d'atteindre nos objectifs de réutilisabilité séquentielle/parallèle.

Au final, la conception et la réalisation permettent d'instancier, à partir du même code [séquentiel] d'algèbre linéaire, une version séquentielle et parallèle offrant des performances satisfaisantes.

Cette thèse s'inscrit dans le domaine de l'optimisation combinatoire. Elle utilise l'approche polyèdrale pour résoudre des problèmes combinatoires qui se posent dans le contexte des réseaux de télécommunications. Nous introduisons et étudions le problème de synthèse de réseaux à composantes connexes unicycliques. Après avoir rappelé que le problème est facile à résoudre en absence d'autres contraintes, nous étudions de nouvelles variantes en intégrant de nouvelles contraintes techniques. Nous commençons par une contrainte portant sur la taille des cycles. Nous souhaitons interdire tous les cycles contenant au plus p sommets. Le problème est alors NP-Difficile. Des inégalités valides sont alors proposées pour ce problème. On montre sous des conditions bien précises que ces inégalités peuvent être des facettes. Plusieurs algorithmes polynomiaux ont été proposés pour la séparation des inégalités valides. Ces algorithme sont mis en oeuvre et des résultats numériques sont donnés. Nous nous focalisons par la suite sur un nouveau problème dit de Steiner consistant à partitionner un réseau en composantes unicycliques tout en imposant que certains sommets soient sur les cycles. On montre alors que ce problème est facile au sens de la complexité algorithmique en proposant un algorithme polynomial et une formulation étendue du problème. On présente également une description partielle de l'enveloppe convexe des vecteurs d'incidence de ces réseaux. La séparation des inégalités est également étudiée. Nous proposons notamment une généralisation de l'algorithme de Padberg-Rao pour séparer les inégalités Blossom. D'autres contraintes techniques sont prises en compte : contraintes de degrés, contrainte sur le nombre de composantes connexes, appartenance de certains sommets à une même composante connexe et enfin la séparation de certains sommets qui doivent être sur des composantes différentes. Enfin, nous faisons une étude spectrale de deux classes spécifiques de graphes unicycliques
In this thesis, we use the polyhedral approach to solve combinatorial problems in telecommunications context. First, we introduce the problem of network design with unicyclic connected components. We recall that without other constraints, our problem is easy to solve, and we propose a study with new technical constraints. We start our study by adding constraints on the size of cycles. We aim to obtain unicyclic components such that the size of each cycle is not lower than a certain p. This problem is NP-Hard. We describe some valid inequalities for the design of unicyclic graphs with girth constraints. The faces induced by these valid inequalities are also studied. Some of them can be separated in polynomial time. A cutting plane algorithm based on these inequalities is implemented to solve the problem. Furthermore, we focus on a Steiner type problem, which consists in partitioning the graph to unicyclic components, such that some given vertices belong to a cycle. We prove then that our problem is easy to solve, and we propose an exact extended formulation and a partial description of the convex hull of the incidence vectors of our Steiner network problem. Polynomial time separation algorithms are described. One of them is a generalization of the Padberg&Rao algorithm to separate blossom inequalities. Other technical constraints are proposed such as degree constraints, a bound of the number of unicyclic components, constraints related to whether some given pairs of vertices belong to the same component or to different components. Finally, we study the spectra of two specified classes of unicyclic graphs

Cette thèse traite de la segmentation d'IRM cérébrales multimodales par des méthodes de coupe de graphe. Dans un premier temps, nous proposons une méthode qui utilise trois modalités IRM en les fusionnant. L'information de frontière, donnée par le gradient spectral, est alors mis en balance avec une information de région, donnée par des graines sélectionnées par l'utilisateur, par un algorithme de coupe de graphe. Dans un second temps, nous proposons trois variantes de cette méthode. La première consiste à trouver un espace spectral optimal car le gradient spectral est basé sur les images naturelles donc inadapté aux images médicales multimodales. Cela donne naissance à une méthode de segmentation par apprentissage. Nous explorons ensuite l'automatisation de notre méthode. Ici, les informations d'ordinaire données par l'utilisateur sont déduites par un algorithme robuste d'espérance-maximisation. Nous montrons les performances de ces deux variantes sur la segmentation de lésions de sclérose en plaques. Enn, nous intégrons l'utilisation d'atlas pour la segmentation automatique de structures profondes du cerveau. Ces trois nouvelles techniques montrent l'adaptabilité de notre méthode à divers problèmes. Nos différentes méthodes de segmentation se montrent meilleures que la plupart de celles actuellement utilisés, aussi bien en terme de temps de calcul qu'en précision de segmentation.

L'innovation thérapeutique progresse traditionnellement par la combinaison du criblage expérimental et de la modélisation moléculaire. En pratique, cette dernière approche est souvent limitée par la pénurie de données expérimentales, particulièrement les informations structurales et biologiques. Aujourd'hui, la situation a complètement changé avec le séquençage à haut débit du génome humain et les avancées réalisées dans la détermination des structures tridimensionnelles des protéines. Cette détermination permet d'avoir accès à une grande quantité de données pouvant servir à la recherche de nouveaux traitements pour un grand nombre de maladies. À cet égard, les approches informatiques permettant de développer des programmes de criblage virtuel à haut débit offrent une alternative ou un complément aux méthodes expérimentales qui font gagner du temps et de l'argent dans la découverte de nouveaux traitements. Appliqué aux grandes bases de données moléculaires, le criblage virtuel à haut débit permet de limiter le criblage expérimental en fournissant, pour chaque cible biologique visée, des molécules potentiellement intéressantes au moyen de méthodes informatiques adaptées. Cependant, la plupart de ces approches souffrent des mêmes limitations. Le coût et la durée des temps de calcul pour évaluer la fixation d'une collection de molécules à une cible, qui est considérable dans le contexte du haut débit, ainsi que la précision des résultats obtenus sont les défis les plus évidents dans le domaine. Le besoin de gérer une grande quantité de données hétérogènes est aussi particulièrement crucial. Pour surmonter les limitations actuelles du criblage virtuel à haut débit et ainsi optimiser les premières étapes du processus de découverte de nouveaux médicaments, j'ai mis en place une méthodologie innovante permettant, d'une part, de gérer une masse importante de données hétérogènes et d'en extraire des connaissances et, d'autre part, de distribuer les calculs nécessaires sur les grilles de calcul comportant plusieurs milliers de processeurs, le tout intégré à un protocole de criblage virtuel en plusieurs étapes. L'objectif est la prise en compte, sous forme de contraintes, des connaissances sur le problème posé afin d'optimiser la précision des résultats et les coûts en termes de temps et d'argent du criblage virtuel. Les approches méthodologiques développées ont été appliquées avec succès à une étude concernant le problème de résistance du VIH aux antiviraux, projet soutenu par la fondation Bill et Melinda Gates dans le cadre d'un projet de collaboration avec le CIRCB au Cameroun.

Le dilemme itéré du prisonnier est une représentation mathématique de la coopération entre agents. Ce modèle est issu de la théorie des jeux dont le but initial est d'étudier les situations de conflits d'intérêts entre individus. La pauvreté des résultats qu'elle implique dans le cas du dilemme du prisonnier rend son utilisation assez inefficace. Une nouvelle approche évolutionniste basée en grande partie sur des simulations informatiques a été initiée par Robert Axelrod. Les agents sont caractérisés par leur comportement, ou stratégie. Axelrod a mis en évidence quatre propriétés qu'une stratégie doit posséder pour être efficace, et propose la stratégie donnant_donnant comme exemple.

Notre travail consiste à étudier et approfondir ce type de simulations. Nous adaptons le modèle afin de prendre en compte l'aspect discret des calculs. Cette adaptation nous permet de faire un grand nombre de simulations confirmant en majeure partie les résultats obtenus dans le cas continu. Ceci remet cependant en cause une des propriétés avancées par Axelrod : la simplicité. Nous illustrons ceci par la présentation de stratégies meilleures que donnant_donnant et à complexité plus importante. Les évaluations sont faites grâce à des simulations impliquant un très grand nombre de stratégies construites de manière objective via une approche génétique.

Ces simulations permettent de mettre en évidence une nouvelle propriété : la faculté d'adaptation du comportement. Cette nouvelle propriété renforce l'idée de complexité croissante dans les comportements coopératifs entre agents.

Nous débutons également l'étude d'un dilemme du prisonnier particulier dont seule l'itération diffère du modèle classique et qui permet de modéliser deux niveaux de coopération : le dilemme de l'ascenseur. Cette étude théorique et expérimentale nous permet de montrer qu'avec cette nouvelle représentation les comportements purement déterministes ne peuvent être efficaces.

Cette thèse s'inscrit dans le domaine de l'optimisation combinatoire. Elle utilise l'approche polyèdrale pour résoudre des problèmes combinatoires qui se posent dans le contexte des réseaux de télécommunications. Nous introduisons et étudions le problème de synthèse de réseaux à composantes connexes unicycliques. Après avoir rappelé que le problème est facile à résoudre en absence d'autres contraintes, nous étudions de nouvelles variantes en intégrant de nouvelles contraintes techniques. Nous commençons par une contrainte portant sur la taille des cycles. Nous souhaitons interdire tous les cycles contenant au plus p sommets. Le problème est alors NP-Difficile. Des inégalités valides sont alors proposées pour ce problème. On montre sous des conditions bien précises que ces inégalités peuvent être des facettes. Plusieurs algorithmes polynomiaux ont été proposés pour la séparation des inégalités valides. Ces algorithme sont mis en oeuvre et des résultats numériques sont donnés. Nous nous focalisons par la suite sur un nouveau problème dit de Steiner consistant à partitionner un réseau en composantes unicycliques tout en imposant que certains sommets soient sur les cycles. On montre alors que ce problème est facile au sens de la complexité algorithmique en proposant un algorithme polynomial et une formulation étendue du problème. On présente également une description partielle de l'enveloppe convexe des vecteurs d'incidence de ces réseaux. La séparation des inégalités est également étudiée. Nous proposons notamment une généralisation de l'algorithme de Padberg-Rao pour séparer les inégalités Blossom. D'autres contraintes techniques sont prises en compte : contraintes de degrés, contrainte sur le nombre de composantes connexes, appartenance de certains sommets à une même composante connexe et enfin la séparation de certains sommets qui doivent être sur des composantes différentes. Enfin, nous faisons une étude spectrale de deux classes spécifiques de graphes unicycliques. Mots clés : Optimisation Combinatoire, Polyèdres, Algorithme à Plans Coupants, Graphes

Mes travaux de recherche ont pour sujet unificateur : les déplacements et les réseaux de transport ; et ils ont été traités par une approche unique, la modélisation physico-économique à caractère mathématique et algorithmique.
Une telle modélisation comporte quatre aspects : un contenu sémantique, à caractère physique ou économique ; une formulation mathématique ; un solveur technique ; un aspect empirique (métrologie, statistique, économétrie).
Les disciplines mises en œuvre sont variées : théorie des réseaux, optimisation, informatique algorithmique, probabilités et statistiques, et aussi économie, socio-économie et physique du trafic. Mes contributions théoriques concernent la théorie des réseaux, l'économie du transport et la physique du trafic.
Mes travaux se répartissent en quatre thèmes :
A. La mesure et la modélisation du trafic. Au niveau local d'une route, j'ai analysé la relation entre flux et vitesse en mettant en cohérence l'analyse désagrégée, probabiliste au niveau du mobile individuel ; et l'analyse macroscopique en termes de flux et de distribution statistique des temps.
B. La modélisation des réseaux et des cheminements. L'équilibre entre offre de transport et demande de déplacement conjugue une dimension spatiale - topologique, une dimension temporelle, et une dimension comportementale - économique. Les enjeux de modélisation concernent : la représentation de l'offre et la demande ; la formulation et les propriétés d'existence – unicité – stabilité ; les algorithmes. Je me suis intéressé à la diversité des comportements ; et à la modélisation fine de l'offre et à la dimension temporelle.
C. L'analyse socio-économique des déplacements. Je me suis intéressé à l'usage de divers moyens de transport et à la prospection de leur clientèle potentielle ; au choix d'horaire de déplacement ; aux caractéristiques à la fois économiques et dynamiques de la congestion.
D. La distribution spatiale des déplacements et des activités. Je me suis intéressé d'une part à l'observation des flux par relation origine-destination (O-D) et à l'inférence statistique des matrices O-D ; et d'autre part, à la justification microéconomique des déplacements en raison de la localisation et de l'utilité des activités.

Cette étude est une classification générale des constructions verbales et une description des propriétés syntaxico-sémantiques des verbes à complément essentiel introduit par la postposition e en coréen. Ce travail a pour modèle théorique le lexique-grammaire, qui a été élaboré par M. Gross (1975), sur la base des principes de Z. S. Harris (1968). Dans cette étude, nous avons examiné les propriétés syntaxico-sémantiques des 3000 verbes demandant ce complément et nous les avons regroupés en 8 classes. Ces propriétés constitueront des informations syntaxiques qui servent à l'analyse de structure d'une phrase et au traitement automatique des textes en coréen.

Les avancées technologiques dans le domaine du multimédia, associées à la généralisation de leur utilisation dans de nombreuses applications (archivages télévisuelles, vidéosurveillances, etc..), ont rendu possible le stockage des grandes collections de documents vidéo dans des systèmes informatiques. Pour permettre une exploitation efficace de ces collections, il est nécessaire de mettre en place des outils facilitant l'accès à leurs documents et la manipulation de ceux-ci. Une indexation par mots-clés (issus de la transcription de la parole et ou de sous-titre dans le document vidéo) est parfois possible. Cependant, l'utilisation de concepts peut améliorer les résultats de processus d'indexation et de recherche d'information parce qu'elle enlève les ambiguïtés entre les sens des mots-clés dus à la synonymie et l'homonymie. La précision de la description sera encore meilleure si, en plus des concepts non ambigus, des relations entre ces concepts sont indexées.
Les documents vidéo ont un caractère multimédia qui fait que la recherche par le contenu dans ceux-ci présente un certain nombre de spécificités. Par exemple, un concept donné (personne, objet...) peut être interprété de différentes manières : il peut être vu, il peut être entendu ou il peut être mentionné. Des combinaisons de ces cas peuvent également se produire. Naturellement, ces distinctions sont importantes pour l'utilisateur. Des requêtes impliquant le concept C comme par exemple : « rechercher les segments vidéos montrant une image de C » ou comme : « rechercher les segments vidéos dans lesquels on parle de C » sont susceptibles de produire des réponses tout à fait différentes. Dans le premier cas, on rechercherait C dans le contenu visuel tandis que dans le second, on rechercherait dans le contenu audio un segment dans la transcription duquel C est mentionné.
Cette étude s'inscrit dans un contexte de modélisation, indexation et recherche d'information multimédia. Au niveau théorique, notre contribution consiste à la proposition d'un modèle pour la représentation du contenu sémantique des documents vidéo. Ce modèle permet la prise en compte synthétique et intégrée des éléments d'informations issus de chacune des modalités (image, texte, son). L'instanciation de ce modèle est réalisée à l'aide du formalisme des graphes conceptuels. Le choix de ce formalisme est justifié par son expressivité et son adéquation au contexte d'indexation et de recherche d'information par le contenu.
Notre contribution au niveau expérimental consiste à l'implémentation (en partie) du prototype CLOVIS . Nous avons intégré le modèle proposé dans d'un système d'indexation et de recherche vidéo par le contenu pour évaluer ses apports en termes d'efficacité et de précision.
Mots-clés : Recherche d'information multimédia, indexation conceptuel, document vidéo, graphe conceptuel, ontologie.