Le développement du logiciel actuel doit faire face de plus en plus à la complexité de programmes gigantesques, élaborés et maintenus par de grandes équipes réparties dans divers lieux. Dans ses tâches régulières, chaque intervenant peut avoir à répondre à des questions variées en tirant des informations de sources diverses. Pour améliorer le rendement global du développement, nous proposons d'intégrer dans un IDE populaire (Eclipse) notre nouvel outil de visualisation (VERSO) qui calcule, organise, affiche et permet de naviguer dans les informations de façon cohérente, efficace et intuitive, afin de bénéficier du système visuel humain dans l'exploration de données variées. Nous proposons une structuration des informations selon trois axes : (1) le contexte (qualité, contrôle de version, bogues, etc.) détermine le type des informations ; (2) le niveau de granularité (ligne de code, méthode, classe, paquetage) dérive les informations au niveau de détails adéquat ; et (3) l'évolution extrait les informations de la version du logiciel désirée. Chaque vue du logiciel correspond à une coordonnée discrète selon ces trois axes, et nous portons une attention toute particulière à la cohérence en naviguant entre des vues adjacentes seulement, et ce, afin de diminuer la charge cognitive de recherches pour répondre aux questions des utilisateurs. Deux expériences valident l'intérêt de notre approche intégrée dans des tâches représentatives. Elles permettent de croire qu'un accès à diverses informations présentées de façon graphique et cohérente devrait grandement aider le développement du logiciel contemporain. / Nowadays, software development has to deal more and more with huge complex programs, constructed and maintained by large teams working in different locations. During their daily tasks, each developer may have to answer varied questions using information coming from different sources. In order to improve global performance during software development, we propose to integrate into a popular integrated development environment (Eclipse) our new visualization tool (VERSO), which computes, organizes, displays and allows navigation through information in a coherent, effective, and intuitive way in order to benefit from the human visual system when exploring complex data. We propose to structure information along three axes: (1) context (quality, version control, etc.) determines the type of information; (2) granularity level (code line, method, class, and package) determines the appropriate level of detail; and (3) evolution extracts information from the desired software version. Each software view corresponds to a discrete coordinate according to these three axes. Coherence is maintained by navigating only between adjacent views, which reduces cognitive effort as users search information to answer their questions. Two experiments involving representative tasks have validated the utility of our integrated approach. The results lead us to believe that an access to varied information represented graphically and coherently should be highly beneficial to the development of modern software.

L’augmentation du nombre d’usagers de l’Internet a entraîné une croissance exponentielle dans les tables de routage. Cette taille prévoit l’atteinte d’un million de préfixes dans les prochaines années. De même, les routeurs au cœur de l’Internet peuvent facilement atteindre plusieurs centaines de connexions BGP simultanées avec des routeurs voisins. Dans une architecture classique des routeurs, le protocole BGP s’exécute comme une entité unique au sein du routeur. Cette architecture comporte deux inconvénients majeurs : l’extensibilité (scalabilité) et la fiabilité. D’un côté, la scalabilité de BGP est mesurable en termes de nombre de connexions et aussi par la taille maximale de la table de routage que l’interface de contrôle puisse supporter. De l’autre côté, la fiabilité est un sujet critique dans les routeurs au cœur de l’Internet. Si l’instance BGP s’arrête, toutes les connexions seront perdues et le nouvel état de la table de routage sera propagé tout au long de l’Internet dans un délai de convergence non trivial. Malgré la haute fiabilité des routeurs au cœur de l’Internet, leur résilience aux pannes est augmentée considérablement et celle-ci est implantée dans la majorité des cas via une redondance passive qui peut limiter la scalabilité du routeur. Dans cette thèse, on traite les deux inconvénients en proposant une nouvelle approche distribuée de BGP pour augmenter sa scalabilité ainsi que sa fiabilité sans changer la sémantique du protocole. L’architecture distribuée de BGP proposée dans la première contribution est faite pour satisfaire les deux contraintes : scalabilité et fiabilité. Ceci est accompli en exploitant adéquatement le parallélisme et la distribution des modules de BGP sur plusieurs cartes de contrôle. Dans cette contribution, les fonctionnalités de BGP sont divisées selon le paradigme « maître-esclave » et le RIB (Routing Information Base) est dupliqué sur plusieurs cartes de contrôle. Dans la deuxième contribution, on traite la tolérance aux pannes dans l’architecture élaborée dans la première contribution en proposant un mécanisme qui augmente la fiabilité. De plus, nous prouvons analytiquement dans cette contribution qu’en adoptant une telle architecture distribuée, la disponibilité de BGP sera augmentée considérablement versus une architecture monolithique. Dans la troisième contribution, on propose une méthode de partitionnement de la table de routage que nous avons appelé DRTP pour diviser la table de BGP sur plusieurs cartes de contrôle. Cette contribution vise à augmenter la scalabilité de la table de routage et la parallélisation de l’algorithme de recherche (Best Match Prefix) en partitionnant la table de routage sur plusieurs nœuds physiquement distribués. / The increasing number of end users has led to an exponential growth in the Internet routing table. The routing table is expected to reach a size of one million prefixes within the coming few years. Besides, current core routers may easily attain hundreds of connected BGP peers simultaneously. In classical monolithic architecture, the BGP protocol runs as a single entity inside the router. This architecture suffers from two drawbacks: scalability and reliability. BGP scalability can be measured in terms of the number of connected peers that can be handled and the size of the routing table. On the other hand, the reliability is a critical issue in core routers. If the BGP instance inside the router fails, all peers’ connections will shutdown and the new reachability state will be propagated across the Internet in a non trivial convergence delay. Although, in current core routers, the resiliency is increased considerably, it’s mainly implemented via a primary-backup redundancy scheme which limits the BGP scalability. In this thesis we address the two mentioned BGP drawbacks by proposing a novel distributed approach to increase both scalability and reliability of BGP without changing the semantic of the protocol. The BGP distributed architecture in the first paper is built to satisfy both requirements: scalability and reliability by adequately exploiting parallelism and module separation. In our model, BGP functionalities are split in a master-slave manner and the RIB (Routing Information Base) is replicated to multiple controller cards, to form a cluster of parallel computing entities. In the second paper, we address the fault tolerance of BGP within the distributed architecture presented in the first paper. We prove analytically that, by adopting the distributed architecture of BGP the availability of BGP will be increased considerably versus a monolithic architecture. In the third paper we propose a distributed parallel scheme called DRTP to partition the BGP routing table on multiple controller cards. DRTP aims at increasing the BGP scalability and the parallelization of the Best Match Prefix algorithm.

Le succès commercial des jeux vidéo nous montre qu’ils sont devenus une alternative non négligeable en matière de loisir et de divertissement. En observant les tendances, on constate que les concepteurs de jeux vidéo cherchent à transposer ou adapter les loisirs comme la danse, l’interprétation de la musique ou la pratique d’un sport dans le contexte de jeux vidéo (l’univers virtuel) et ceci est devenu encore plus évident depuis l’apparition des nouvelles technologies intégrant le mouvement comme mode d'interaction. En rapport aux activités dont les jeux vidéo s’inspirent, ces tendances entraînent des changements considérables sur l’aspect formel de l’activité ludique et notamment l’interaction. Dans le cas particulier du tennis de table, ou ping-pong dans le langage courant, il semble y avoir des différences en terme de plaisir lors de la pratique de ce loisir de façon traditionnelle ou en mode virtuel dans ses différentes adaptations. Le but de cette recherche est de mettre en évidence les différences entre l’appréciation de l’interaction avec le contrôleur multifonctionnel Wiimote et une raquette traditionnelle de ping-pong et de découvrir les implications sur l’expérience du plaisir de la transposition du jeu ping-pong traditionnel comparé aux adaptations sur la console Wii. Ainsi, en regard du CLASSIC GAME MODEL de Juul (2005) et du modèle THE FOUR FUN KEYS de Lazzaro (2008) nous comparons les deux modes d’interaction, jeu traditionnel avec le jeu virtuel, sur le plan formel du jeu et sur les dimensions du plaisir que chacun procure. Les résultats obtenus par l’observation des tests de jeu et l’entremise des autres outils permettent de souligner le rôle déterminant des interfaces dans l’engagement des joueurs et de montrer les limites des interfaces digitales par rapport à celle des jeux traditionnels. / The market success of Video games shows us that they have become a significant alternative for leisure and entertainment. While observing the trends one can realize that game designers tend to transpose or adapt leisure activities such as dance, playing music or sports to the context of video games which has become even more obvious with the appearance of input devices incorporating physical movement as a mode of interaction. Inspired by these different forms of leisure, video game user interfaces have considerably changed the formal aspect of play, especially in terms of interaction. In the particular case of table tennis, also known as ping-pong, there are significant differences with respect to pleasure when playing a traditional game or its virtual adaptations in form of video games. The purpose of this research is to highlight the difference in appreciation of the interaction with the Wiimote controller and a traditional ping-pong racket and discover the implications on the fun experiences of traditional table tennis and its adaptations for the Wii console. Thus, based on Juul's CLASSIC GAME MODEL (2005) and Lazzaro' model of THE FOUR FUN KEYS (2008) we compare both interaction modes, traditional game with the virtual game, in terms of formal level of the game and the notion of fun that each provides. The results obtained through observation and testing through other tools allow us to highlight the importance of interfaces and their role in the players' commitment as well as to show the limit of video games compared to their traditional counterpart.

La rapide progression des technologies sans fil au cours de ces dernières années a vu naître de nouveaux systèmes de communication dont les réseaux véhiculaires. Ces réseaux visent à intégrer les nouvelles technologies de l’information et de la communication dans le domaine automobile en vue d’améliorer la sécurité et le confort sur le réseau routier. Offrir un accès Internet aux véhicules et à leurs occupants peut sans doute aider à anticiper certains dangers sur la route tout en rendant plus agréables les déplacements à bord des véhicules. Le déploiement de ce service nécessite que des messages soient échangés entre les véhicules. Le routage constitue un élément crucial dans un réseau, car définissant la façon dont les différentes entités échangent des messages. Le routage dans les VANETS constitue un grand défi car ces derniers sont caractérisés par une forte mobilité entraînant une topologie très dynamique. Des protocoles ont été proposés pour étendre Internet aux réseaux véhiculaires. Toutefois, la plupart d’entre eux nécessitent un coût élevé de messages de contrôle pour l’établissement et le maintien des communications. Ceci a pour conséquence la saturation de la bande passante entrainant ainsi une baisse de performance du réseau. Nous proposons dans ce mémoire, un protocole de routage qui s’appuie sur des passerelles mobiles pour étendre Internet aux réseaux véhiculaires. Le protocole prend en compte la mobilité des véhicules et la charge du réseau pour l’établissement et le maintien des routes. / The fast progression of wireless technologies has motivated the emergence of new communications system called VANETS (Vehicular Adhoc Networks). VANETS enable vehicles on the roadway to communicate with each other and with road infrastructure using wireless capabilities. The applications of VANETS include improving safety and comfort on the road. For example, by providing Internet to vehicles, traveling can be safer and more comfortable. To provide Internet connectivity, messages need to be exchanged between the vehicles. However, it is hard to design an efficient routing protocol for connecting vehicles to Internet with a reasonable cost due to high mobility in VANETS. Although, several existing routing protocols have been proposed in the open literature to extend Internet to VANETS, they generate considerable overhead. This leads to unfairly consumption of bandwidth decreasing network performance. We design a routing protocol to connect vehicles to Internet through mobile gateways with the objective to make efficient use of the network bandwidth. Indeed, the protocol significantly reduces the communication overhead required to establish and maintain the routes relying on the mobility of the gateways and the network’s load.

Un circuit arithmétique dont les entrées sont des entiers ou une variable x et dont les portes calculent la somme ou le produit représente un polynôme univarié. On assimile la complexité de représentation d'un polynôme par un circuit arithmétique au nombre de portes multiplicatives minimal requis pour cette modélisation. Et l'on cherche à obtenir une borne inférieure à cette complexité, et cela en fonction du degré d du polynôme. A une chaîne additive pour d, correspond un circuit arithmétique pour le monôme de degré d. La conjecture de Strassen prétend que le nombre minimal de portes multiplicatives requis pour représenter un polynôme de degré d est au moins la longueur minimale d'une chaîne additive pour d. La conjecture de Strassen généralisée correspondrait à la même proposition lorsque les portes du circuit arithmétique ont degré entrant g au lieu de 2. Le mémoire consiste d'une part en une généralisation du concept de chaînes additives, et une étude approfondie de leur construction. On s'y intéresse d'autre part aux polynômes qui peuvent être représentés avec très peu de portes multiplicatives (les d-gems). On combine enfin les deux études en lien avec la conjecture de Strassen. On obtient en particulier de nouveaux cas de circuits vérifiant la conjecture. / An arithmetic circuit with inputs among x and the integers which has product gates and addition gates represents a univariate polynomial. We define the complexity of the representation of a polynomial by an arithmetic circuit as the minimal number of product gates required for this modelization. And we seek a lower bound to this complexity, with respect to the degree d of the polynomial. An addition chain for d corresponds to an arithmetic circuit computing the monomial of degree d. Strassen's conjecture states that the minimal number of product gates required to represent a polynomial of degree d is at least the minimal length of an addition chain for d. The generalized Strassen conjecture corresponds to the same statement where the indegree of the gates of the arithmetic circuit is g instead of 2. The thesis consists, on the one hand, of the generalization of the concept of addition chains, and a study of the subject. On the other hand, it is concerned with polynomials which can be represented with very few product gates (d-gems). Both studies related to Strassen's conjecture are combined. In particular, we get new classes of circuits verifying the conjecture.

La conception de systèmes hétérogènes exige deux étapes importantes, à savoir : la modélisation et la simulation. Habituellement, des simulateurs sont reliés et synchronisés en employant un bus de co-simulation. Les approches courantes ont beaucoup d’inconvénients : elles ne sont pas toujours adaptées aux environnements distribués, le temps d’exécution de simulation peut être très décevant, et chaque simulateur a son propre noyau de simulation. Nous proposons une nouvelle approche qui consiste au développement d’un simulateur compilé multi-langage où chaque modèle peut être décrit en employant différents langages de modélisation tel que SystemC, ESyS.Net ou autres. Chaque modèle contient généralement des modules et des moyens de communications entre eux. Les modules décrivent des fonctionnalités propres à un système souhaité. Leur description est réalisée en utilisant la programmation orientée objet et peut être décrite en utilisant une syntaxe que l’utilisateur aura choisie. Nous proposons ainsi une séparation entre le langage de modélisation et la simulation. Les modèles sont transformés en une même représentation interne qui pourrait être vue comme ensemble d’objets. Notre environnement compile les objets internes en produisant un code unifié au lieu d’utiliser plusieurs langages de modélisation qui ajoutent beaucoup de mécanismes de communications et des informations supplémentaires. Les optimisations peuvent inclure différents mécanismes tels que le regroupement des processus en un seul processus séquentiel tout en respectant la sémantique des modèles. Nous utiliserons deux niveaux d’abstraction soit le « register transfer level » (RTL) et le « transaction level modeling » (TLM). Le RTL permet une modélisation à bas niveau d’abstraction et la communication entre les modules se fait à l’aide de signaux et des signalisations. Le TLM est une modélisation d’une communication transactionnelle à un plus haut niveau d’abstraction. Notre objectif est de supporter ces deux types de simulation, mais en laissant à l’usager le choix du langage de modélisation. De même, nous proposons d’utiliser un seul noyau au lieu de plusieurs et d’enlever le bus de co-simulation pour accélérer le temps de simulation. / The design of heterogeneous systems requires two main steps, modeling and simulation. Usually, simulators are connected and synchronized by using a cosimulation bus. These current approaches have many disadvantages: they are not always adapted to the distributed environments, the execution time can be very disappointing, and each simulator has its own core of simulation. We propose a new approach which consists in developing a multi-language compiled simulator where each model can be described by employing various modeling languages such as SystemC, ESyS.Net or others. Each model contains modules and communication links between them. These modules describe functionalities for a desired system. Their description is realized by using the programming object and can be described by using a syntax that a user will have chosen. We thus propose a separation between the language of modeling and simulation. The models are transformed into the same internal representation which could be seen like unique objects. Our environment compiles these internal objects by producing a unified code instead of using several languages of modeling which add many mechanisms of communications and extra informations. Optimizations can include various mechanisms such as merging processes into only one sequential process while respecting the semantics of the models. We will use two abstraction levels, the “register transfer level”(RTL) and the “transaction-level modeling”(TLM). RTL allows a low level abstraction for modeling and the communication between the modules is done with signals. The TLM is a modeling for transactional communication with a higher abstraction level than RTL. Our aim is to support these two types of simulation, but the user can choose the language of modeling. In the same way, we propose to use a single core and to remove the cosimulation bus to accelerate the simulation time.

Ces dernières années, les technologies sans fil ont connu un essor fulgurant. Elles ont permis la mise en place de réseaux sans fil à hautes performances. Les réseaux maillées sans fil (RMSF) sont une nouvelle génération de réseaux sans fil qui offrent des débits élevés par rapport aux réseaux Wi-Fi (Wireless Fidelity) classiques et aux réseaux ad-hoc. Ils présentent de nombreux avantages telles que leur forte tolérance aux pannes, leur robustesse, leur faible coût etc. Les routeurs des RMSF peuvent disposer de plusieurs interfaces radio et chaque interface peut opérer sur plusieurs canaux distincts, c’est des RMSF multiples-radios, multiples-canaux. Ce type de réseau peut accroître de manière considérable les performances des RMSF. Cependant plusieurs problèmes subsistent et doivent être résolus notamment celui du routage. Le routage dans les RMSF demeure un défi majeur. Le but des protocoles de routage est de trouver les meilleures routes i.e. des routes qui maximisent les débits et minimisent les délais, lors de l’acheminement du trafic. La qualité des routes dans les RMSF peut être fortement affectée par les interférences, les collisions, les congestions etc. Alors les protocoles doivent être en mesure de détecter ces problèmes pour pouvoir en tenir compte lors de la sélection des routes. Plusieurs études ont été dédiées aux métriques et aux protocoles de routage dans les RMSF afin de maximiser les performances de celles ci. Mais la plupart ne prennent pas en considération toutes les contraintes telles que les interférences, le problème des stations cachées etc. Ce mémoire propose une nouvelle métrique de routage pour RMSF. Nous avons mis en place une nouvelle métrique de routage pour RMSF appelée MBP (Metric Based on Probabilities). Cette métrique est destinée aux RMSF mono-radio ou multiples-radios. Elle permet d’éviter les routes à forte ii interférence. Les résultats des simulations ont montré que MBP présente des améliorations par rapport à certaines métriques : ETT, WCETT et iAWARE qui sont connues dans le domaine. / In recent years, wireless technologies have developed sharply. They allow the establishment of high performance wireless networks. Wireless Mesh Networks (WMNs) is a new generation of wireless networks that offer high throughput compared to classical Wi-Fi (Wireless Fidelity) or ad-hoc networks. WMNs have attracted significant research due to their features that include dynamic self organization, self configuration, easy maintenance and low cost. WMNs nodes can be equipped with multiples-radios and multiples-channels. This type of network can increase significantly the performance of WMNs. However, several problems must be solved including routing in WMNs. Routing in WMNs is a great challenge. The main goal of routing protocols is to find best paths i.e. paths that maximize throughputs and minimize delays when transmitting packets. Route quality can be strongly affected by interference, collisions, congestions etc. Then protocols should be able to detect these problems and take them into account during route selection. We propose a new routing metric for WMNs, called MBP that captures the impact of intra-flow and inter-flow interference in multi-radio, multi-channel networks. Results show that MBP has better performances than some existing and popular metrics like ETT, WCETT and iAWARE.

Analyser le code permet de vérifier ses fonctionnalités, détecter des bogues ou améliorer sa performance. L’analyse du code peut être statique ou dynamique. Des approches combinants les deux analyses sont plus appropriées pour les applications de taille industrielle où l’utilisation individuelle de chaque approche ne peut fournir les résultats souhaités. Les approches combinées appliquent l’analyse dynamique pour déterminer les portions à problèmes dans le code et effectuent par la suite une analyse statique concentrée sur les parties identifiées. Toutefois les outils d’analyse dynamique existants génèrent des données imprécises ou incomplètes, ou aboutissent en un ralentissement inacceptable du temps d’exécution. Lors de ce travail, nous nous intéressons à la génération de graphes d’appels dynamiques complets ainsi que d’autres informations nécessaires à la détection des portions à problèmes dans le code. Pour ceci, nous faisons usage de la technique d’instrumentation dynamique du bytecode Java pour extraire l’information sur les sites d’appels, les sites de création d’objets et construire le graphe d’appel dynamique du programme. Nous démontrons qu’il est possible de profiler dynamiquement une exécution complète d’une application à temps d’exécution non triviale, et d’extraire la totalité de l’information à un coup raisonnable. Des mesures de performance de notre profileur sur trois séries de benchmarks à charges de travail diverses nous ont permis de constater que la moyenne du coût de profilage se situe entre 2.01 et 6.42. Notre outil de génération de graphes dynamiques complets, nommé dyko, constitue également une plateforme extensible pour l’ajout de nouvelles approches d’instrumentation. Nous avons testé une nouvelle technique d’instrumentation des sites de création d’objets qui consiste à adapter les modifications apportées par l’instrumentation au bytecode de chaque méthode. Nous avons aussi testé l’impact de la résolution des sites d’appels sur la performance générale du profileur. / Code analysis is used to verify code functionality, detect bugs or improve its performance. Analyzing the code can be done either statically or dynamically. Approaches combining both analysis techniques are most appropriate for industrial-scale applications where each one individually cannot provide the desired results. Blended analysis, for example, first applies dynamic analysis to identify problematic code regions and then performs a focused static analysis on these regions. However, the existing dynamic analysis tools generate inaccurate or incomplete data, or result in an unacceptably slow execution times. In this work, we focus on the generation of complete dynamic call graphs with additional information required for blended analysis. We make use of dynamic instrumentation techniques of Java bytecode to extract information about call sites and object creation sites, and to build the dynamic call graph of the program. We demonstrate that it is possible to profile real-world applications to efficiently extract complete and accurate information. Performance measurement of our profiler on three sets of benchmarks with various workloads places the overhead of our profiler between 2.01 and 6.42. Our profiling tool generating complete dynamic graphs, named dyko, is also an extensible platform for evaluating new instrumentation approaches. We tested a new adaptive instrumentation technique for object creation sites which accommodates instrumentation to the bytecode of each method. We also tested the impact of call sites resolution on the overall performance of the profiler.

Les gènes sont les parties du génome qui codent pour les protéines. Les gènes d’une ou plusieurs espèces peuvent être regroupés en "familles", en fonction de leur similarité de séquence. Cependant, pour connaître les relations fonctionnelles entre ces copies de gènes, la similarité de séquence ne suffit pas. Pour cela, il est important d’étudier l’évolution d’une famille par duplications et pertes afin de pouvoir distinguer entre gènes orthologues, des copies ayant évolué par spéciation et susceptibles d’avoir conservé une fonction commune, et gènes paralogues, des copies ayant évolué par duplication qui ont probablement développé des nouvelles fonctions. Étant donnée une famille de gènes présents dans n espèces différentes, un arbre de gènes (obtenu par une méthode phylogénétique classique), et un arbre phylogénétique pour les n espèces, la "réconciliation" est l’approche la plus courante permettant d’inférer une histoire d’évolution de cette famille par duplications, spéciations et pertes. Le degré de confiance accordé à l’histoire inférée est directement relié au degré de confiance accordé à l’arbre de gènes lui-même. Il est donc important de disposer d’une méthode préliminaire de correction d’arbres de gènes. Ce travail introduit une méthodologie permettant de "corriger" un arbre de gènes : supprimer le minimum de feuilles "mal placées" afin d’obtenir un arbre dont les sommets de duplications (inférés par la réconciliation) sont tous des sommets de "duplications apparentes" et obtenir ainsi un arbre de gènes en "accord" avec la phylogénie des espèces. J’introduis un algorithme exact pour des arbres d’une certaine classe, et une heuristique pour le cas général. / Genes are segments of genomes that code for proteins. Genes of one or more species can be grouped into gene families based on their sequence similarity. In order to determine functional relationships among these multiple gene copies of a family, sequence homology is insufficient as no direct information on the evolution of the gene family by duplication, speciation and loss can be inferred directly from a family of homologous genes. And it is precisely this information that allows us to distinguish between orthologous gene copies, that have evolved by speciation and are more likely to preserve the same function and paralogous gene copies that have evolved by duplication and usually acquire new functions. For a given gene family contained within n species, a gene tree (inferred by typical phylogenetic methods) and a phylogenetic tree of the considered species, reconciliation between the gene tree and the species tree is the most commonly used approach to infer a duplication, speciation and loss history for the gene family. The main criticism towards reconciliation methods is that the inferred duplication and loss history for a gene family is strongly dependent on the gene tree considered for this family. Indeed, just a few misplaced leaves in the gene tree can lead to a completely different history, possibly with significantly more duplications and losses. It is therefore important to have a preliminary method for "correcting” the gene tree, i.e. removing potentially misplaced branches. N. El-Mabrouk and C. Chauve introduced "non-apparent duplications" as nodes that are likely to result from the misplacement of one leaf in the gene tree. Simply put, such a node indicates that one or more triplets contradict the phylogeny given by the species tree. In this work, the problem of eliminating non-apparent duplications from a given gene tree by a minimum number of leaf removals is considered. Depending on the disposition of this type of nodes in the gene tree, the algorithm introduced leads to an O(nlogn) performance and an optimal solution in a best case scenario . The general case however is solved using an heuristic method.

Les logiciels de correction grammaticale commettent parfois des détections illégitimes (fausses alertes), que nous appelons ici surdétections. La présente étude décrit les expériences de mise au point d’un système créé pour identifier et mettre en sourdine les surdétections produites par le correcteur du français conçu par la société Druide informatique. Plusieurs classificateurs ont été entraînés de manière supervisée sur 14 types de détections faites par le correcteur, en employant des traits couvrant di-verses informations linguistiques (dépendances et catégories syntaxiques, exploration du contexte des mots, etc.) extraites de phrases avec et sans surdétections. Huit des 14 classificateurs développés sont maintenant intégrés à la nouvelle version d’un correcteur commercial très populaire. Nos expériences ont aussi montré que les modèles de langue probabilistes, les SVM et la désambiguïsation sémantique améliorent la qualité de ces classificateurs. Ce travail est un exemple réussi de déploiement d’une approche d’apprentissage machine au service d’une application langagière grand public robuste. / Grammar checking software sometimes erroneously flags a correct word sequence as an error, a problem we call overdetection in the present study. We describe the devel-opment of a system for identifying and filtering out the overdetections produced by the French grammar checker designed by the firm Druide Informatique. Various fami-lies of classifiers have been trained in a supervised way for 14 types of detections flagged by the grammar checker, using features that capture diverse linguistic phe-nomena (syntactic dependency links, POS tags, word context exploration, etc.), extracted from sentences with and without overdetections. Eight of the 14 classifiers we trained are now part of the latest version of a very popular commercial grammar checker. Moreover, our experiments have shown that statistical language models, SVMs and word sense disambiguation can all contribute to the improvement of these classifiers. This project is a striking illustration of a machine learning component suc-cessfully integrated within a robust, commercial natural language processing application.