In this thesis, we consider the problem of having a mobile robot autonomously learn to perceive differences between terrains. The targeted application is for terrain identification. Robust terrain identification can be used to enhance the capabilities of mobile systems, both in terms of locomotion and navigation. For example, a legged amphibious robot that has learned to differentiate sand from water can automatically select its gait on a beach: walking for sand, and swimming for water. The same terrain information can also be used to guide a robot in order to avoid specific terrain types. The problem of autonomous terrain identification is decomposed into two sub-problems: a sensing sub-problem, and a learning sub-problem. In the sensing sub-problem, we look at extracting terrain information from existing sensors, and at the design of a new tactile probe. In particular, we show that inertial sensor measurements and actuator feedback information can be combined to enable terrain identification for a legged robot. In addition, we describe a novel tactile probe designed for improved terrain sensing. In the learning sub-problem, we discuss how temporal or spatial continuities can be exploited to perform the clustering of both time-series and images. Specifically, we present a new algorithm that can be used to train a number of classifiers in order to perform clustering when temporal or spatial dependencies between samples are present. We combine our sensing approach with this clustering technique, to obtain a computational architecture that can learn autonomously to differentiate terrains. This approach is validated experimentally using several different sensing modalities (proprioceptive and tactile) and with two different robotic platforms (on a legged robot named AQUA and a wheeled robot iRobot Create). Finally, we show that the same clustering technique, when combined with image information, can be used to define a new image segmentation algorithm. / Au travers de cette thèse, nous examinons la problématique entourant la perception des différences entre divers terrains, pour un robot mobile autonome. L'application visée par les résultats de nos recherches est l'identification des types de terrains. Cette identification, faite de manière robuste, permet d'augmenter les capacités de systèmes mobiles, tant au niveau de la locomotion que de la navigation. Par exemple, un robot amphibie à pattes qui aurait apprit à distinguer le sable et la mer pourra choisir de lui-même la démarche appropriée : marcher sur le sable, et nager dans l'eau. Cette même information sur le type de terrain peut aussi être utile pour guider un robot, lui permettant d'éviter des types de terrains spécifiques. Nous abordons la problématique d'identification des terrains autour de deux axes principaux: un problème de capture d'information (sensoriel), et un problème d'apprentissage. Dans le problème de la capture d'information, la question traitée est celle d'extraire l'information pertinente à l'identification du type de sol à partir de capteurs sur un robot, ou à l'aide d'une sonde tactile. En particulier, nous démontrons qu'en combinant l'information provenant d'une centrale inertielle avec celle provenant des actionneurs d'un robot à pattes, il est possible d'identifier certains types de sols. De plus, nous présentons une nouvelle sonde tactile possédant des caractéristiques améliorant la capture d'informations relatives aux terrains. Pour le problème de l'apprentissage, nous analysons comment il est possible d'exploiter les continuités spatiales et temporelles afin de séparer des séries temporelles ou des images en leurs classes constituantes (clustering). Nous présentons un nouvel algorithme de clustering basé sur ce principe. En combinant l'approche sensorielle et ce nouvel algorithme, nous obtenons une architecture permettant l'apprentissage, de façon autonome, des terrains. Cette approche est

Massively Multiplayer Online Games (MMOGs) can be treated as a database application. Players request actions concurrently to alter the state of objects in the game. Since the world state is the most valuable asset of MMOGs, it is extremely important to ensure its consistency. On the other hand, the defining feature of such games is their capacity to support thousands of clients playing simultaneously, thus requiring scalability. This thesis proposes a solution which leverages typical game semantics and architectures to design scalable transaction models for action handling while maintaining the required levels of consistency. These models vary in their levels of isolation and atomicity and offer different consistency guarantees that are suitable for actions of varying importance and complexity. Action handling protocols are then designed according to those models and optimized for scalability and efficiency. We also present a persistence architecture which is integrated with the transaction models mentioned above. We show how the different consistency guarantees of each transaction model can be maintained by the persistence structure. Concrete actions are then implemented and designed using various transaction models with persistence support. We then evaluate and compare the performance of the various implementations and discuss the trade-off between performance and consistency. / Les jeux en ligne massivement multijoueur (MMOGs) peuvent être considérés comme des applications base de données. Les joueurs initient des actions de façon concurrentielle pour modifier l'état du jeu. Puisque l'état du monde est le plus grand atout des MMOGs, il est extrêmement important d'assurer sa consistance. D'un autre côté, la caractéristique essentielle de ces jeux est leur capacité de supporter plusieurs milliers de clients simultanément, et donc l'habileté de gérer une charge grandissante. Cette thèse propose une solution qui est fondée sur des sémantiques et architectures typiques aux jeux pour concevoir des modèles de transaction extensibles à la charge pour la gestion des actions tout en maintenant les niveaux requis de consistance. Ces modèles varient dans leurs niveaux d'isolation et d'atomicité et offrent donc des garanties de consistance variées qui sont adaptées à des actions d'importance et de complexité différente. Des protocoles de gestion des actions optimisés sont alors conçus selon ces modèles. Nous présentons aussi une architecture pour la gestion de persistance des données qui est intégrée aux modèles de transaction mentionnés ci-dessus. Nous montrons comment les garanties de consistance de chaque modèle sont maintenues par la structure persistante. Des actions concrètes sont alors mises en oeuvre et conçues selon les divers modèles de transaction avec persistance. Nous évaluons et comparons la performance de chacune des implémentations et discutons du compromis entre la performance et la consistance.

The complexity of developing multiplayer games, along with their popularity, has grown tremendously in the recent years. The most complex of these, Massively Multiplayer Games (MMOGs), require developers to deal with many issues, such as scalability, reliability and cheat prevention. Although individual solutions to these problems exists, very little academic work has been done to address all these issues simultaneously. In addition, experimentation in these areas can require a significant implementation effort.In this work, we present Journey, a unified framework that address all these issues in a simple, modular and efficient architecture leveraging replicated objects. Scalability is addressed through the use of a dynamic cell load-balancing strategy while fault tolerance and cheat prevention are achieved by leveraging existing replicated objects in the system. The proposed framework is implemented using numerous enhancements not found in traditional replication, like obstacle-aware partitioning and remote procedure call systems.The efficiency of this framework is illustrated through the use of Mammoth, a massively multiplayer research framework. Using experimental data from human players, artificial players (NPC) were built and used to stress test and gather performance data. Analysis of this data demonstrated that load balancing provides important scalability benefits while very little overhead is incurred from the fault tolerance and cheat prevention systems. / Dans les dernières années, la popularité des jeux multi-joueurs a connu une croissance sans égale. Cette croissance a aussi provoqué une augmentation importante dans la complexité de développement, surtout pour les jeux en ligne massivement multi-joueurs (MMOGs). Ces jeux posent des problèmes sérieux, tel que la croissance de capacité, la fiabilité et la prévention de la tricherie. Quoiqu'il existe de nombreuses solutions pour chacun de ces problèmes, très peu de travail académique adresse tous ces problèmes ensembles. De plus, l'expérimentation dans ces domaines nécessite de grands efforts de développement.Ce document présente Journey, un cadre de librairies informatiques unifiées qui adresse tous ces problèmes avec une architecture simple, modulaire et efficace tirant parti de la technologie des objets répliqués. Journey utilise un système d'équilibrage de charge avec cellule dynamique pour pallier aux problèmes de capacité. De plus, les défis de tolérance des failles et la prévention de la tricherie peuvent être adressés à l'aide des objets déjà répliqués dans le système. L'outil proposé utilise plusieurs améliorations qui n'existe pas dans la réplication traditionnelle, tel que la division des espaces prenant compte des obstacles et l'exécution de méthode distantes.La performance de Journey est évaluée à l'aide de Mammoth, un outil de recherche pour les environnements massivement multi-joueurs. À l'aide de données expérimentales de joueurs humains, des joueurs artificiels on été construits pour mesurer la capacité et la performance de l'outil proposé. L'analyse de ses données démontre que l'équilibre des charges démontre une grande augmentation de capacité. De plus, les systèmes de tolérance de fautes et de prévention de la tricherie on très peu d'impact sur la performance du système.

This thesis presents a particular set of spheres as new representation of the shape of a 3D solid. The spheres considered are maximal inscribed spheres in the solid and their centres are chosen in such a way that at most one sphere centre lies in a cubic region of space.The shape representation proposed is a discretization of the medial surface transform of a solid. Part I of this thesis presents algorithms for the computation of this representation given a boundary representation of a solid by approximating its medial surface transform. Properties of those medial spheres that are not detected by our algorithm in 3D are described and a complete characterization of those medial circles that are not detected by a 2D version of our algorithm is given. In Part II, recent results from differential geometry are used to compute principal curvatures and principal curvature directions on the boundary of the smooth solid represented using the union of medial spheres. This computation is performed using only the medial sphere centres and a pair of points on each medial sphere that lies on the surface of the solid being modeled. It is shown how the union of medial spheres allows a part-based description of the solid, with a significance measure associated with each part. In Part III, it is shown that our shape representation can offer a tight volumetric fit to a polyhedron, using a small number of spheres. The spheres used in our representation can be quickly updated as the solid undergoes a certain class of deformations. It is shown how our set of medial spheres allows efficient and accurate proximity queries between polyhedra. / Cette thèse présente une nouvelle représentation de la forme de solides 3D, décrite par un ensemble spécifique de sphères. Les sphères de cette représentation sont des sphères inscrites maximalement dans le solide et leur centre est choisi de telle manière que tout au plus un seul centre de sphère occupe une région cubique de l'espace. La représentation de forme proposée est une discrétisation de la surface médiane d'un solide. La première partie de cette thèse présente des algorithmes pour le calcul de cette représentation à partir d'une description de la frontière d'un solide, en approximant sa surface médiane. Certaines propriétés des sphères médianes qui ne sont pas détectées par notre algorithme en 3D sont décrits, ainsi qu'une caractérisation complète des cercles médians qui ne sont pas détectés par une version 2D de l'algorithme.En deuxième partie, des résultats récents en géométrie différentielle sont utilisés pour calculer les courbures principales et les directions principales de courbure sur la surface d'un solide lisse représenté par une union de sphères médianes. Ce calcul est effectué en utilisant seulement le centre et une paire de points relatifs à chaque sphère médiane qui se trouve sur la surface du solide. Il est aussi démontré comment l'union des sphères médianes permet une description par partie du solide, tout en donnant une mesure de l'importance associée à chaque partie.En troisième partie, il est démontré que notre représentation de forme peut servir à l'ajustement volumétrique serré d'un polyèdre, tout en utilisant un nombre restreint de sphères. Les sphères utilisées dans notre représentation peuvent être rapidement adaptées au solide lorsqu'il est sujet à une certaine classe de déformations. Notre ensemble de sphères médianes permet d'effectuer des requêtes de proximité efficaces et précises entre des polyèdres.

The intuition that the amount of classical correlations between two systems be bounded by their size does not hold true in general for quantum states. In the setting of information locking, measurements on a pair of quantum systems that appear to be completely uncorrelated can become maximally correlated with a small increment in the size of one of the systems. A new information locking scheme based on generic unitary channels is presented and a strengthened definition of locking based on a measure of indistinguishability is used. The new definition demonstrates that classical information can be kept arbitrarily low until it can be completely decoded. Unlike previous locking results, non-uniform input messages are allowed and shared entanglement between the pair of quantum systems is considered. Whereas past locking results relied on schemes with an explicit "key" register, this requirement is eliminated in favor of an arbitrary quantum subsystem. Furthermore, past results considered only projective measurements at the receiver. Here locking effects can be shown even in the case where the receiver is armed with the most general type of measurement. The locking effect is found to be generic and finds applications in entropic security and models for black hole evaporation. / L'intuition que le montant des corrélations classiques entre deux systèmes sont limités par leur taille est incorrect en général pour les états quantiques. En cas de verrouillage, des mesures sur une paire de systèmes quantiques qui semblent être totalement décorrélées peuvent devenir corrélées au maximum avec une minuscule augmentation de la taille d'un des systèmes. Une nouvelle forme de verrouillage utilisant des canaux unitaire génériques est introduite et la définition de verrouillage est renforcée a base d'une mesure d'indiscernabilité. La nouvelle définition montre que l'information classique peut être arbitrairement bas jusqu'à ce qu'elle puisse être complètement décodée. Aux contraire des résultats précédents, des messages non-uniforme et l'intrication entre la paire de systèmes sont considérés. Auparavant, il était nécessaire d'avoir un registre explicite pour une "clé", cette nécessité est supprimée en faveure d'un sous-système quantique arbitraire. De plus, les résultats précédent considéraient que les mesures projective mais nous démontrons des effets de verrouillage même dans le cas où le récepteur est armé avec les mesures les plus générales. Nous trouvons l'effet de verrouillage générique et montrons des applications pour la sécurité entropique et pour un modèl d'évaporation des trous noirs.

Mobility is quickly becoming the normal usage pattern for application developers. How a user accesses a given application changes depending on present circumstances. User applications can exist on the local machine, on a web server, in a cloud infrastructure, or on a mobile phone. Deciding which platforms to support can be the difference between a successful application and one that doesn't get off the ground. The W12 Window System is an attempt at solving the mobility problem. Each platform shares one ubiquitous piece of software: the web browser. When a new platform is developed, typically a web browser is among the first fully-formed applications released. W12 leverages HTML5 web browsers as thin-client computing terminals to display an application that can be running anywhere over the network. Windows are drawn into the browser and events can be sent back to the application for processing. / Les utilisateurs d'applications informatiques ne sont plus restreints à leurs ordinateurs comme avant. Le mode d'utilisation d'une application peut changer selon les circonstances de l'usager. L'application peut être exécutée sur un ordinateur local, sur un serveur Web, dans un environnement d'infonuagique ou sur un téléphone mobile. La décision de la plateforme informatique sur laquelle une nouvelle application sera développée peut, à elle seule, décider du succès ou de l'échec du projet. Le système W12, un environnement graphique en réseau, vise à régler les problèmes reliés aux multiples plateformes informatiques. Chacune des plateformes mentionnées partage un aspect en particulier : le navigateur Web. Le navigateur Web est souvent une des premières applications développées pour le lancement d'une nouvelle plateforme informatique. Le système W12 utilise la nouvelle standard Web HTML5 pour transformer un navigateur Web en un client léger pour permettre l'affichage d'une application peu importe où elle est exécutée. Le navigateur Web affiche le rendu de l'application et les évènements, tels ceux générés par le clavier et la souris, sont acheminés à l'application.

Despite the popularity of Java, problems may arise from potential data-race conditionsduring execution of a Java program. Data-races are considered errors in concurrent pro-gramming languages and greatly complicate both programming and runtime optimizationefforts. A race-free version of Java is therefore desirable as a way of avoiding this com-plexity and simplifying the programming model.This thesis is part of work trying to build a race-free version of Java. It implements andoptimizes thread-local accesses and comes up with a new semantics for this language. Animportant part of implementing a language without races is to distinguish thread-local datafrom shared data because these two groups of data need to be treated differently. This iscomplex in Java because in the current Java semantics all objects are allocated on a singleheap and implicitly shared by multiple threads. Furthermore, while Java does provide amechanism for thread-local storage, it is awkward to use and inefficient.Many of the new concurrent programming languages, such as OpenMP, UPC, and D,use "sharing directives" to distinguish shared data from thread-local data, and have fea-tures that make heavy use of thread-local data. Our goal here is to apply some of theselanguage ideas to a Java context in order to provide a simpler and less error-prone pro-gramming model. When porting such features as part of a language extension to Java,however, performance can suffer due to the simple, map-based implementation of Java'sbuilt-in ThreadLocal class. We implement an optimized mechanism based on program-mer annotations that can efficiently ensure class and instance variables are only accessed bytheir owner thread. Both class and instance variables inherit values from the parent threadthrough deep copying, allowing all the reachable objects of child threads to have localcopies if syntactically specified. In particular, class variable access involves direct accessto thread-local variables through a localized heap, which is faster and easier than the defaultmap mechanism defined for ThreadLocal objects. Our design improves performance sig-nificantly over the traditional thread-local access method for class variables and providesa simplified and more appealing syntax for doing so. We further evaluate our approach bymodifying non-trivial, existing benchmarks to make better use of thread-local features, il-lustrating feasibility and allowing us to measure the performance in realistic contexts. Thiswork is intended to bring us closer to designs for a complete race-free version of Java, aswell as show how improved support for use of thread-local data could be implemented inother languages. / Malgré la popularité de JAVA, de potentiels accès concurrents aux données peuvent causer des problèmes à l'exécution d'un programme. Les accès concurrents aux données sont considérés comme des erreur par les langages de programmation et compliquent grandement le processus de programmation et d'optimisation. Une version de JAVA sans accès concurrents serait la bienvenue et simplifierait ce processus. Cette thèse n'est qu'une partie d'une recherche plus importante visant à établir une version de JAVA sans accès concurrents. Elle implémente et optimise les accès en thread local et introduit une nouvelle sémantique pour ce langage. Une part importante de l'implémentation d'un langage sans concurrence est de distinguer les données locales de thread des données partagées car ces 2 types de données doivent être traitées différemment. Ceci est complexe en JAVA, car avec la sémantique actuelle, tous les objets sont alloués en un seul tas (heap) et implicitement partagés entre plusieurs threads. De plus, le mécanisme de stockage en thread local de Java est étrange et inefficace. Plusieurs des nouveaux langages concurrents, comme OpenMP, UPC et D, utilisent des "directives de partage" pour distinguer les données partagées des données locales de thread, et ont des structures faisant un usage avancé des données locales de thread. Notre but ici est d'appliquer certaines idées de ces langages dans un contexte JAVA dans le but de fournir un modéle de programmation plus simple et plus fiable. Cependant, apporter ces fonctionnalités sous forme d'extension a JAVA peut en affecter les performance du fait de la structure de la classe ThreadLocal de JAVA. Nous implémentons donc un mécanisme qui garantit efficacement que seul le processus propriétaire accède aux classes et variables d'instances. Aussi bien les classes que les variables d'instances héritent des valeurs du processus parent par copie, ce qui permet aux objets de processus enfants d'avoir des copies locales si précisé dans la syntaxe. En particulier, l'accès à des variables de classe utilise un accès direct aux variables du processus local via un tas local, ce qui est plus rapide et facile que le mécanisme par défaut de mappage défini pour les objet ThreadLocal. Notre conception améliore le performance de faon significative comparé à la méthode d'accès au processus local traditionnelle pour les variables de classe et fournit une syntaxe simplifiée et plus attrayante. Nous évaluons ensuite notre approche en modifiant des outils de test (benchmarks) complexes existants pour faire un meilleur usage de leurs fonctionnalités en processus local, ceci illustrant la faisabilité et nous permettant de mesurer les performances dans un contexte réaliste. Ce travail a pour but de nous rapprocher de la conception d'une version JAVA sans concurrence aussi bien que de montrer comment un support amélioré des données en thread local pourrait être implémenté dans d'autres langages.

Application programing interfaces promote reuse by facilitating interaction between software components and/or software libraries. API code templates are parameterized API scenarios that can be quickly instantiated by copy-and-pasting or through support from integrated development environments. They provide the skeletal structure of an API coding scenario and let developers simply "fill in the blanks" with the details of their coding task. Unfortunately, creating relevant API code templates requires time and experience with the API. To address these problems we present a technique that mines API usage patterns and transforms them into API code templates. Our intuition is that API usage patterns are a solid basis for code templates because they are grounded by actual API usage. We evaluate our approach performing retroactive study on the Mammoth, ArgoUML, and Eclipse projects to see if API code templates created from earlier versions could have been helpful to developers in later versions. Our results show that, on average, each API code template our technique mined could have helped developers with creating six, nine, and twelve new methods in Mammoth, ArgoUML, and Eclipse, respectively. In our evaluation, we mined many API code templates from the three test projects that provide evidence that our technique could have helped developers learn and use an API faster in many opportunities. / Les interfaces de programmation (API) encouragent la réutilisation de code en facilitant l'interaction entre les composantes du logiciel et ses librairies. Les "templates" d'API sont des scénarios d'utilisation de l'API paramétrées pour êtres rapidement instanciés par copier-coller ou par le soutien intégré des environnements de développement. Ils fournissent le squelette d'un scénario d'utilisation de l'API et laissent au développeurs la simple tâche de "remplir les espace". Malheureusement, afin de créer des "templates" pertinents, du temps et de l'expérience avec l'API sont nécessaires. Pour résoudre ces problèmes, nous présentons une technique par laquelle les "templates" d'API sont découverts en analysant des scénarios d'utilisation existants. Notre intuition est que de tels scénarios sont une base valide pour la découverte de "templates" car ils sont une représentation existante de l'API en action. Nous évaluons notre méthode en effectuant une étude rétroactive sur les projets Mammoth, ArgoUML, et Eclipse pour voir si les modèles créés à partir de versions antérieures auraient été utiles aux développeurs dans les versions ultérieures. Nos résultats illustrent que, en moyenne, chaque "template" d'API créé par notre technique aurait permis aux développeurs de créer six, neuf et douze nouvelles méthodes dans les projets Mammoth, ArgoUML, et Eclipse, respectivement. De plus, dans notre évaluation, de nombreux modèles de code API ont été créé à partir des ces trois projets, ainsi prouvant que notre technique pourrait avoir aidée les développeurs à apprendre et utiliser une API plus rapidement dans de nombreuses occasions.

In this thesis we address the problem of recommendation in domains where items have strong dependency constraints. We apply our work on the academic courses domain, where dependencies between items are present as explicit prerequisite constraints, implicit ordering patterns, and general course consumption restrictions. We propose a new recommendation approach that combines both ordering patterns of items learned from data and estimated user interests in providing a personalized sequence of recommendations that take into account item inter-dependencies. Our approach is based on modeling the recommendation problem as a Markov Decision Process (MDP), in which the goal is to find a plan with the maximum total reward. We have developed an implementation of our approach as a web-based course recommender system, which recommends academic course course plans to students for a number of subsequent terms. Experiments on real data collected from students of McGill University demonstrate that our approach has better performance compared to other simpler models which rely exclusively on student interests or on course co-occurrence patterns. / Dans cette thèse, nous abordons le problème de recommandation dans les domaines où les éléments ont des fortes contraintes de dépendance. Nous appliquons notre travail sur le domaine des cours académiques où les dépendances entre les éléments sont présentes comme contraintes de condition préalable explicites, pattern de l'arrangement implicite, et restrictions générale de la consomption de cours. Nous proposons une nouvelle approche au problème de recommandation qui combine l'arrangement des articles appris à partir des données et les intérêts de l'utilisateur, estimés pour fournir une séquence personnalisée des recommandations, qui prend en compte les interdépendances des éléments. Notre approche est basée sur la modélisation du problème de recommandation comme processus de décision Markovien (MDP) dont le but est de trouver un plan à profit totale maximale. Nous avons implémenté notre approche sur le Web en tant qu'un système qui propose des plans de cours aux étudiants pour un certain nombre de périodes subséquentes. Nos expériences sur des données réelles recueillies auprès des élèves de l'Université McGill démontrent que notre approche est plus performant comparativement aux modèles qui ne considèrent que les intérêts d'étudiant ou les patterns de co-occurrence de cours.

Understanding the organization of protein-protein interactions (PPIs) as a complex network is one of the main pursuits in proteomics today. With the help of high-throughput experimental techniques, a large amount of PPI data has become available, providing us a rough picture of how proteins interact in biological systems. One of the leading technologies for identifying protein interactions is affinity-purification followed by mass spectrometry (AP-MS). While the AP-MS method provides the ability to detect protein interactions at biologically reasonable expression levels, this technique still suffers from poor accuracy as well as lack of sound approach to interpret the obtained interaction data.In this thesis, we look for sources of systematic errors and limitations of the data from AP-MS experiments, and propose several approaches for improvements. In particular, we identify various problems that arise within the experimental pipeline, and propose combinatorial algorithms developed using the theory of approximationalgorithms and discrete mathematics. The first part of the thesis deals with quantification of proteins from MS-based experiments. Existing approaches for protein quantification often use each detected peptide as an indicator for the originating protein. These approaches ignore peptides that belong to more than one protein family. We attack this problem of protein quantification by taking these shared peptides into consideration, and propose a framework for estimating protein abundance via linear programming.In AP-MS data, the identified protein interactions contain a large number of indirect interactions as artifacts from a series of simultaneous physical interactions. The second part of this thesis studies the problem of distinguishing direct physical interactions from indirect interactions. To do this, we first propose a probabilistic graph model for the PPI data, and design a combinatorial algorithm suited for graphs with underlying structure that is evident in PPI networks.While the traditional model for PPI networks is a binary graph representing pairwise interactions, a large number of interactions involve more than two interaction partners. Such collections of proteins interacting concertedly are known as protein complexes, and various approaches have been proposed to identify the complexes in the network. When these complexes are overlapping, however, the existing complex detection methods often fail to identify the constituent complexes. Taking one step further on this line of research, the last part of this thesis discusses the problem of modelling PPI networks as hypergraphs by studying the clique cover problem on sparse networks. For each problem discussed throughout the thesis, we obtain either an exact algorithm, an algorithm with provably good guarantee on the output quality, or a heuristic with efficient running time. Furthermore, each of the proposed algorithms is empirically tested against biological data as well as simulated data, in order to validate both computational efficiency and biological soundness. / Comprendre l'organisation des interactions protéine-protéine (IPP) en tant que réseau complexe est un des plus grands problèmes de la protéomique moderne. Avec l'aide de techniques expérimentales à haut débit, une grand quantité de données de IPP est devenue disponible, nous procurant ainsi une image approximative du fonctionnement des interactions entre protéines dans des systèmes biologiques. Une des technologies de fine pointe pour identifier des interactions protéiques est la purification d'affinité suivie de la spectrométrie de masse (PA-SM). Même si la méthode de PA-SM nous permet de détecter des interactions de protéines à des niveaux d'expression raisonnables biologiquement, cette technique souffre encore d'une précision déficiente et d'un manque d'une approche saine pour interpréter les résultats d'interactions obtenus par celle-ci.Dans cette thèse, nous cherchons des sources d'erreurs systématiques et des limites des données provenant d'expériences PA-SM et nous proposons plusieurs approches amenant des améliorations. En particulier, nous identifions divers problèmes présents dans la procédure expérimentale et proposons des algorithmes combinatoires développés en utilisant la théorie des algorithmes d'approximation et des mathématiques discrètes. La première partie de la thèse étudie la quantification des protéines provenant d'une expérience basée sur la spectrométrie de masse. Les approches existantes pour la quantification de protéines utilisent souvent chaque peptide détecté comme un indicateur de la protéine d'origine. Ces approches ignorent les peptides qui appartiennent à plus d'une protéines. Nous attaquons ce problème de quantification de protéines en prenant ces peptides partagés en considération et proposons un cadre de travail pour estimer l'abondance des protéines via la programmation linéaire.Les interactions de protéines identifiées dans les données de PA-SM contiennent un grand nombre d'interactions indirectes qui sont des artéfacts d'une série d'interactions physiques simultanées. La seconde partie de cette thèse étudie le problème de distinction des interactions physiques directes de celles qui sont indirectes. Pour ce faire, nous proposons premièrement un modèle d'un graphe probabiliste pour les données de IPPs et concevons un algorithme combinatoire adapté aux graphes ayant des propriétés observées dans de vrais réseaux de IPPs.Malgré le fait que le modèle traditionnel des réseaux de IPPs est un graphe binaire représentant les interactions par paires, un grand nombre d'interactions impliquent plus de deux partenaires d'interaction. De tels groupes de protéines interagissant de concert se nomment des complexes de protéines. Plusieurs approches ont déjà été proposées afin d'identifier les complexes dans un réseau. Cependant, lorsque ces complexes se chevauchent, les méthodes existantes échouent. La dernière partie de cette thèse discute du problème de modélisation des réseaux de IPPs comme des hypergraphes en étudiant le problème de couverture par cliques sur des réseaux clairsemés.Pour chaque problème discuté au cours de cette thèse, nous obtenons un algorithme exact, un algorithme avec de bonnes garanties prouvables sur la qualité de la sortie, ou une heuristique avec un temps d'exécution efficient. De plus, chaque algorithme proposé est testé empiriquement avec des données biologiques et simulées dans le but de valider l'efficience computationnelle et la signification biologique.