Cette thèse étudie d'un point de vue algorithmique diverses méthodes de consensus portant sur des collections d'objets étiquetés. Les problèmes étudiés impliquent des objets étiquetés sans répétition d'étiquettes ; ces objets peuvent être des arbres enracinés ou des séquences, avec des applications à la bioinformatique. Ainsi, les problèmes sur les arbres considérés dans cette thèse peuvent trouver des applications pour l'estimation de congruence entre phylogénies, pour la construction de superarbres, et pour l'identification de transferts horizontaux de gènes. Pour leur part, les problèmes sur les séquences considérés dans cette thèse ont des applications potentielles pour le calcul de distance génomique basé sur les ordres de gènes. De manière générale, ce travail met à profit les théories de la complexité paramétrique et de l'approximabilité pour obtenir des algorithmes et des résultats de difficulté pour les problèmes étudiés.

La miniaturisation de circuits intégrés, les hautes fréquences de fonctionnement, la baisse des potentiels d'alimentation, les fortes densités d'intégration rendent les signaux numériques propagés sur les interconnexions très susceptibles à la dégradation voire à la corruption. En vue d’évaluer la compatibilité électromagnétique et l’intégrité du signal il est nécessaire de disposer dès les premières phases de développement de modèles précis de ces interconnexions pour les insérer dans les simulateurs temporels. Nos travaux s'inscrivent dans ce contexte et concernent plus particulièrement la modélisation comportementale des buffers et drivers de ligne de transmission. Ils ont abouti à une approche originale de modélisation notamment basée sur les séries de Volterra-Laguerre. Les modèles boites noires développés disposent d’une implémentation SPICE assez simple autorisant ainsi une très bonne portabilité. Ils sont faciles à identifier et disposent d’une complexité paramétrique permettant un gain important de temps de simulation vis-à-vis des modèles transistors des drivers. En outre les méthodes développées permettent une modélisation dynamique non linéaire plus précise du port de sortie, et une gestion plus générale des entrées autorisant notamment une très bonne prise en compte du régime de sur-cadencement ce que par exemple ne fait pas le standard IBIS. / Integrated circuits miniaturization, high operating frequencies, lower supply voltages, high-density integration make digital signals propagating on interconnects highly vulnerable to degradation. Assessing EMC and signal integrity in the early stages of the design flow requires accurate interconnect models allowing for efficient time-domain simulations. In this context, our work addressed the issue of behavioral modeling of transmission line buffers, and particularly that of drivers. The main result is an original modeling approach partially based on Volterra-Laguerre series. The black box models we developed have a fairly simple implementation in SPICE thus allowing a very good portability. They are easy to identify and have a parametric complexity allowing a large gain in simulation time with respect to transistor driver models. In addition, the developed methods allow a more accurate output port nonlinear dynamics modeling, and a more general management of inputs. A very good reproduction of driver behaviour in overclocking conditions provides a significant advantage over standard IBIS models.

Le formalisme des états graphes consiste à modéliser des états quantiques par des graphes. Ce formalisme permet l'utilisation des notions et des outils de théorie des graphes (e.g. flot, domination, méthodes probabilistes) dans le domaine du traitement de l'information quantique. Ces dernières années, cette modélisation combinatoire a permis plusieurs avancées décisives, notamment (i) dans la compréhension des propriétés de l'intrication quantique (ii) dans l'étude des modèles de calcul particulièrement prometteurs en terme d'implémentation physique, et (iii) dans l'analyse et la construction de protocoles de cryptographie quantique. L'objectif de cette thèse est d'étudier les propriétés graphiques émergeant des problématiques d'informatique quantique, notamment pour la simulation quantique. En particulier, l'étude des propriétés de causalité et de localité des états graphes, en étendant par exemple la notion existante de flot de causalité à une notion intégrant des contraintes de localité, permettrait d'ouvrir de nouvelles perspectives pour la simulation de systèmes quantiques à l'aide d'états graphes. Des connections formelles avec les automates cellulaires quantiques bruités pourront également émerger de cette étude. / Graph States formalism consist in using graphs to model quantum states. This formalism allows us to use notion and tools of graph theory (e.g. flow, domination, probabilistic methods) in quantum information processing. Last years, this combinatorial modelisation had lead to many decisiv breakthroughs, in particular (i) in the comprehension of the quantum entranglement properties (ii) in very promising in term of physical implementation quantum calculus model, and (iii) in the analysis and construction of quantum cryptography protocols. The goal of this thesis is to study the graphic properties emerging of those quantum information processing problematics, especially for quantum simulation. In particular, the properties of causality and locality in graph states, by extanding for exemple the existing notion of causality flows to a notion integring the locality constraints, would allow new perspectives for the quantum system simulation using graphs states. Formal connections with noisy quantum cellular automata would emerge from this study.