Les couplages sont des algorithmes cryptographiques qui permettent de nouveaux protocoles de cryptographie à clé publique. Après une décennie de recherches sur des implémentations efficaces, ce qui permet maintenant d’exécuter un couplage en un temps raisonnable, nous nous sommes concentrés sur la sécurité de ces mêmes implémentations.Pour cela nous avons évalué la résistance des algorithmes de couplage contre les attaques en faute. Nous avons envoyé des impulsions électromagnétiques sur la puce calculant le couplage à des moments choisis. Cela nous a permis de remonter au secret cryptographique qu’est censé protéger l’algorithme de couplage. Cette étude fut à la fois théorique et pratique avec la mise en œuvre d’attaques en faute. Finalement, des contremesures ont été proposées pour pouvoir protéger l’algorithme dans le futur / Pairings are cryptographic algorithms allowing new protocols for public-key cryptography. After a decade of research which led to a dramatic improvement of the computation speed of pairings, we focused on the security of pairing implementations.For that purpose, we evaluated the resistance to fault attacks. We have sent electromagnetic pulses in the chip computing a pairing at a precise instant. It allowed us to recover the cryptographic secret which should be protected in the computation. Our study was both theoretical and practical; we did implement actual fault attacks. Finally, we proposed countermeasures in order to protect the algorithm in the future

Les premiers algorithmes exacts exponentiels pour résoudre des problèmes NP-difficiles datent des années soixante. Ces dernières années ont vu un intérêt croissant pour la conception de tels algorithmes tout comme pour l'amélioration de la précision de l'analyse de leur temps d'exécution. Ils sont motivés par les larges applications de problèmes réputés difficiles et qui, sous l'hypothèse P 6= NP, n'admettent pas d'algorithme polynomial en calculant une solution exacte. Dans cette thèse on s'intéresse au problème classique de la domination dans un graphe. On étudie également plusieurs variantes et généralisations de ce problème fondamental. Nous proposons des algorithmes exponentiels pour déterminer un ensemble dominant de taille minimum sur les graphes c-denses, cordaux, 4-cordaux, faiblement cordaux, cercles et bipartis. Puis, nous étudions le problème de la clique dominante qui demande de trouver un ensemble dominant qui soit aussi une clique du graphe. Nous proposons un algorithme Brancher & Réduire qui détermine une clique dominante de taille minimum. L'analyse du temps d'exécution est réalisée en utilisant la technique Mesurer pour Conquérir. Nous donnons ensuite un algorithme général pour énumérer tous les ensembles ( %)-dominants d'un graphe en temps O(cn), avec c < 2, sous certaines conditions sur les ensembles et %, et établissons une borne supérieure combinatoire sur leur nombre. Finalement, nous nous intéressons à un problème de domination partielle et obtenons un algorithme pour le problème de la domination romaine. Grâce à un algorithme basé sur le paradigme de la Programmation Dynamique, nous proposons un algorithme pour le problème de la domination avec des puissances variables / The first exact exponential-time algorithms solving NP-hard problems date back to the sixties. The last years have seen an increasing interest for designing such algorithms as well as analysing their running time. The existence of many applications of well known hard problems is one of the main motivations. Moreover, under the hypothesis P 6= NP, apolynomial time algorithm for these problems does not exist. In this thesis, we deal with the classical domination problem in graphs. We are also interested in some variants and generalizations of this fondamental problem. We give exponential-time algorithms for computing a minimum dominating set on c-dense graphs, chordal graphs, 4-chordal graphs, weakly chordal graphs, circle graphs and bipartite graphs. Then, we study the dominating clique problem requiring to find a minimum dominating set inducing a clique of the graph. We provide a Branch & Reduce algorithm computing a minimum dominating clique. The analysis of the running time is done by using the Measure and Conquer technique. Afterwards, we propose a general algorithm for enumerating all (%)-dominating sets of a graph in time O(cn), with c < 2, under some assumptions on the sets and %. Subsequently, we establish a combinatorial upper bound on the number of such sets in a graph. Finally, we consider a partial dominating set problem and we give an algorithm for solving the Roman domination problem. Using the dynamic programming paradigm, we obtain an algorithm for the domination problem with flexible powers

De nombreuses fonctions cellulaires sont réalisées grâce à l'interaction coordonnée de plusieurs gènes. Identifier le graphe de ces interactions, appelé réseau de régulation génétique, à partir de données d'expression de gènes est l'un des objectifs majeurs de la biologie des systèmes. Dans cette thèse, nous abordons ce problème en choisissant de modéliser les relations entre gènes par un réseau bayésien. Se pose alors la question de l'apprentissage de la structure de ce type de modèle à partir de données qui sont en général peu nombreuses. Pour résoudre ce problème, nous recherchons parmi tous les modèles possibles le modèle le plus simple, expliquant le mieux les données. Pour cela, nous introduisons et étudions différents types d'algorithmes génétiques permettant d'explorer l'espace des modèles. Nous nous intéressons plus particulièrement aux méthodes de spéciation. ces dernières, en favorisant la diversité des solutions candidates considérées, empêchent l'algorithme de converger trop rapidement vers des optima locaux. Ces algorithmes génétiques sont comparés avec différentes méthodes d'apprentissage de structure de réseaux bayésiens, classiquement utilisées dans la littérature. Nous mettons ainsi en avant la pertinence des approches evolutionnaires pour l'apprentissage de ces graphes d'interactions. Enfin, nous les comparons à une classe alternative d'algorithmes évolutionnaires qui s'avère particulièrement prometteuse : les algorithmes à estimation de distribution. Tous ces algorithmes sont testés et comparés sur un modèle du réseau de régulation de l'insuline de 35 noeuds dont nous tirons des jeux de données synthétiques de taille modeste. / Inferring gene regulatory networks from data requires the development of algorithms devoted to structure extraction. When only static data are available, gene interactions may be modelled by a bayesian network that represents the presence of direct interactions from regulators to regulees by conditional probability distributions. In this work, we used enhanced evolutionary algorithms to stochastically evolve a set of candidate bayesian network structures and found the model that best fits data without prior knowledge. We proposed various evolutionary strategies suitable for the task and tested our choices using simulated data drawn from a given bio-realistic network of 35 nodes, the so-called insulin network, which has been used in the literature for benchmarking. We introduced a niching strategy that reinforces diversity through the population and avoided trapping of the algorithm in one local minimum in the early steps of learning. We compared our best evolutionary approach with various well known learning algorithms (mcmc, k2, greedy search, tpda, mmhc) devoted to bayesian network structure learning. Then, we compared our best genetic algorithm with another class of evolutionary algorithms : estimation of distribution algorithms. We show that an evolutionary approach enhanced by niching outperforms classical structure learning methods in elucidating the original model. Finally, it appears that estimation of distribution algorithms are a promising approach to extend this work. These results were obtained for the learning of a bio-realistic network and, more importantly, on various small datasets.

Diss.--Mathematik--Chemnitz--Technischen universität, 2002.

Texte remanié de: Dissertation--Mainz, 2000. / Textes égyptiens, avec translittération et traduction allemande. Bibliogr. p. 367-382.

Thèse de doctorat : Informatique : Metz : 2006. / Thèse soutenue sur ensemble de travaux. Bibliogr. p. [131]-138. Index p. [125]. Liste des symboles p.[129]-130.

Thèse doctorat : Informatique : Villeurbanne, INSA : 2007. / Titre provenant de l'écran-titre. Bibliogr. p. [217]-221. Publications de l'auteur p. [215]-216.

Thèse de doctorat : Informatique : Lyon, École normale supérieure (sciences) : 2004. / Bibliogr. p. 101-104.

Reproduction de : Thèse de 3e cycle : informatique : Grenoble, INPG : 1984. / Titre provenant de l'écran-titre. Bibliogr. p. 165-172.

Habilitation à diriger des recherches : Informatique : Rennes 1 : 1996. / Bibliogr. p.15-21.