The dissertation consists of two parts. In the first part several asymptotic properties of random intersection graphs are studied. They include birth thresholds for small complete subgraphs in the binomial random intersection graph, the clique number in sparse random intersection graphs and the chromatic index of random uniform hypergraphs. Several new methods and theoretically and practically relevant algorithms are proposed. Some results are illustrated with data from real-world networks. The second part deals with asymptotic enumeration and properties of graphs from minor-closed classes in the case when the excluded minors are disjoint. The class of graphs without k+1 (vertex-)disjoint cycles and more general classes of graphs without k+1 disjoint excluded minors (satisfying a condition related to fans) are considered. Typical graphs in such classes are shown to have a simple “k apex vertex” structure. Other asymptotic properties (connectivity, number of components, chromatic number, vertex degrees) are also determined. Finally, it is shown that typical graphs without k+1 disjoint minors K4 have a more complicated “2k+1 apex vertex” structure, and properties of such graphs are investigated. Part of the results is proved in greater generality. A variety of methods from computer science, graph theory, combinatorics and the theory of generating functions are applied. / Disertacijoje yra dvi pagrindinės dalys. Pirmojoje dalyje gaunami keli nauji rezultatai uždaviniams, susijusiems su atsitiktiniais sankirtų grafais. Nagrinėjamas pilnojo pografio gimimo slenkstis binominiame atsitiktiniame sankirtų grafe, didžiausios klikos eilė atsitiktiniame retame sankirtų grafe ir chromatinio indekso eilė atsitiktiniame reguliariajame hipergrafe. Sprendimams pasiūloma keletas naujų metodų, taip pat pateikiami teoriškai ir praktiškai svarbūs algoritmai. Kai kurie rezultatai iliustruojami duomenimis iš realių tinklų. Antrojoje dalyje pristatomi rezultatai grafų su uždraustaisiais minorais tematikoje, nagrinėjamas atvejis kai uždraustieji minorai yra nejungūs. Čia tiriamas asimptotinis grafų, neturinčių k+1 nepriklausomų ciklų, skaičius, rezultatai apibendrinami grafų, neturinčių k+1 uždraustųjų minorų, tačiau tenkinančių tam tikrą „vėduoklės“ apribojimą, klasėms. Įrodoma, kad tipiniai tokių klasių grafai turi paprastą „k dydžio blokatoriaus“ struktūrą, nustatomos kitos tokių grafų asimptotinės savybės (jungumas, komponenčių skaičius, viršūnių laipsniai). Galiausiai parodoma, kad tipiniai grafai, neturintys k+1 nepriklausomų minorų K4 turi sudėtingesnę „2k+1 dydžio blokatoriaus“ struktūrą ir ištiriamos kitos jų savybės. Dalis šių rezultatų įrodoma daug bendresniu atveju. Darbe pasitelkiami įvairūs informatikos, kombinatorikos, grafų, tikimybių ir generuojančiųjų funkcijų teorijos metodai.

Le problème de la clique maximum (MCP) est un problème d'optimisation combinatoire important avec un large éventail d'applications pratiques dans de nombreux domaines, y compris la recherche d'information, l'analyse de la transmission du signal, la théorie de la classification, l'économie, la planification et l'ingénierie biomédicale. En outre, un certain nombre de problèmes d'optimisation combinatoire sont étroitement liés au MCP, tels que la coloration de graphe, la somme coloration, réglez détermination du gagnant emballage et optimale. Cette thèse est consacrée à l'élaboration d'approches heuristiques efficaces pour s'attaquer au problème de la clique maximum et ses généralisations. Pour atteindre cet objectif, nous avons développé une approche de recherche tabou adaptative multistart pour le problème de clique maximum classique, un algorithme recherche tabou multi-voisinage pour la clique maximum de sommets pondérés, et une méthode métaheuristique hybride pour le problème de la clique maximum d'arêtes pondérés. En outre, nous appliquons ces méthodes heuristiques développées pour résoudre ces problèmes difficiles qui sont étroitement liés au problème de la clique maximum. Tous les algorithmes sont mis en oeuvre et testés avec succès sur un certain nombre de cas de référence provenant de divers domaines d'application. Les méthodes proposées concurrencent favorablement les autres approches de l'état de l'art.

Ha Minh Lam et M. Morales ont introduit une classe d'idéaux binomiaux qui est une extension binomiale d'idéaux monomiaux libres de carrés.Étant donné I un idéal monomial quadratique de k[x] libre de carrés et J une somme d'idéaux de scroll de k[z] qui satisfont certaines conditions, nous définissons l'extension binomiale de I comme B=I+J. Le sujet de cette thèse est d'étudier le nombre p plus grand tel que les sizygies de B son linéaires jusqu'au pas p-1. Sous certaines conditions d'ordre imposées sur les facettes du complexe de Stanley-Reisner de I nous obtiendrons un ordre > pour les variables de l'anneau de polynomes k[z]. Ensuite nous prouvons pour un calcul des bases de Gröbner que l'idéal initial in(B), sous l'ordre lexicographique induit par l'ordre de variables >, est quadratique libre de carrés. Nous montrerons que B est régulier si et seulement si I est 2-régulier. Dans le cas géneral, lorsque I n'est pas 2-régulier nous trouverons une borne pour l'entier q maximal qui satisfait que les premier q-1 sizygies de B son linéaires. En outre, en supossant que J est un idéal torique et en imposant des conditions supplémentaires, nous trouveron une borne supérieure pour l'entier q maximal qui satisfait que les premier q-1 sizygies de B son linéaires. En imposant des conditions supplémentaires, nous prouverons que les deux bornes sont égaux. / Ha Minh Lam et M. Morales introduced a family of binomial ideals that are binomial extensions of square free monomial ideals. Let I be a square free monomial ideal of k[x] and J a sum of scroll ideals in k[z] with some extra conditions, we define the binomial extension of $I$ as $B=I+Jsubset sis$. The aim of this thesis is to study the biggest number p such that the syzygies of B are linear until the step p-1. Due to some order conditions given to the facets of the Stanley-Reisner complex of I we get an order > for the variables of the polynomial ring k[z]. By a calculation of the Gröbner basis of the ideal $B$ we obtain that the initial ideal in(B) is a square free monomial ideal. We will prove that B is 2-regular iff I is 2-regular. In the general case, wheter I is not 2-regular we will find a lower bound for the the maximal integer q which satisfies that the first q-1 sizygies of B are linear. On the other hand, wheter J is toric and supposing other conditions, we will find a upper bound for the integer q which satisfies that the first q-1 syzygies of B are linear. By given more conditions we will prove that the twobounds are equal.

Atmospheric nucleation is a process of phase transformation like liquid water transforming into solid or gas phase water, which serves as a significant impact on many atmospheric and technological processes. During the process of the atmospheric nucleation, certain 3D molecular models for atmospheric nucleation will be generated, which are main mixtures of water molecules and hexanol molecules. Analyzing these 3D molecular models can promote the understanding for the nucleation and growth of the particles and phases in a multi-component mixture, as well as for the changes in climate and weather. Therefore, the research for atmospheric nucleation can be transformed into the research for the 3D molecular visualizations and comparisons, which are the similarity calculations. Unfortunately, the research on understanding atmospheric nucleation processes is restricted due to the lack of efficient visual data exploration tools. In this paper, the issue of lacking efficient data visualization tools is tackled by implementing our own application to visualize the atmospheric nucleation. The similarity calculation for these 3D molecules is implemented in order to analyze and compare the atmospheric nucleation processes and molecular models. Admittedly, there are various 3D molecular similarity calculation algorithms, such as clique-detection algorithms and point matching, etc; however, these algorithms are specifically utilized in the fields of protein amino-acids and pharmacophore. Due to the large scale of the atmospheric nucleation data, GPU (Graphical Processing Units) is employed in order to significantly reduce the computation times. This is achieved by utilizing CUDA (Compute Uniform Device Architecture) technology which allows us to execute our algorithm in a parallel method. Furthermore, in this research, the knowledge of hypertree visualization is intended to be utilized to enhance the previously developed web-based visualization and analysis tool that allows remote users to effectively mine the wealth of particle-based nucleation simulation data. The research goal is to speed up knowledge discovery and improve users' productivity through effective data visualization technique and more friendly user interface design. Meanwhile, a feasible parallel computing solution is developed to overcome the slow response due to expensive large data pre-processing. The core research of my thesis is to calculate the similarity between the distinct 3D molecules.

In der klassischen Komplexitätstheorie werden worst-case Laufzeiten von Algorithmen typischerweise einzig abhängig von der Eingabegröße angegeben. In dem Kontext der parametrisierten Komplexitätstheorie versucht man die Analyse der Laufzeit dahingehend zu verfeinern, dass man zusätzlich zu der Eingabengröße noch einen Parameter berücksichtigt, welcher angibt, wie strukturiert die Eingabe bezüglich einer gewissen Eigenschaft ist. Ein parametrisierter Algorithmus nutzt dann diese beschriebene Struktur aus und erreicht so eine Laufzeit, welche schneller ist als die eines besten unparametrisierten Algorithmus, falls der Parameter klein ist. Der erste Hauptteil dieser Arbeit führt die Forschung in diese Richtung weiter aus und untersucht den Einfluss von verschieden Parametern auf die Laufzeit von bekannten effizient lösbaren Problemen. Einige vorgestellte Algorithmen sind dabei adaptive Algorithmen, was bedeutet, dass die Laufzeit von diesen Algorithmen mit der Laufzeit des besten unparametrisierten Algorithm für den größtmöglichen Parameterwert übereinstimmt und damit theoretisch niemals schlechter als die besten unparametrisierten Algorithmen und übertreffen diese bereits für leicht nichttriviale Parameterwerte. Motiviert durch den allgemeinen Erfolg und der Vielzahl solcher parametrisierten Algorithmen, welche eine vielzahl verschiedener Strukturen ausnutzen, untersuchen wir im zweiten Hauptteil dieser Arbeit, wie man solche unterschiedliche homogene Strukturen zu mehr heterogenen Strukturen vereinen kann. Ausgehend von algebraischen Ausdrücken, welche benutzt werden können, um von Parametern beschriebene Strukturen zu definieren, charakterisieren wir klar und robust heterogene Strukturen und zeigen exemplarisch, wie sich die Parameter tree-depth und modular-width heterogen verbinden lassen. Wir beschreiben dazu effiziente Algorithmen auf heterogenen Strukturen mit Laufzeiten, welche im Spezialfall mit den homogenen Algorithmen übereinstimmen. / In classical complexity theory, the worst-case running times of algorithms depend solely on the size of the input. In parameterized complexity the goal is to refine the analysis of the running time of an algorithm by additionally considering a parameter that measures some kind of structure in the input. A parameterized algorithm then utilizes the structure described by the parameter and achieves a running time that is faster than the best general (unparameterized) algorithm for instances of low parameter value. In the first part of this thesis, we carry forward in this direction and investigate the influence of several parameters on the running times of well-known tractable problems. Several presented algorithms are adaptive algorithms, meaning that they match the running time of a best unparameterized algorithm for worst-case parameter values. Thus, an adaptive parameterized algorithm is asymptotically never worse than the best unparameterized algorithm, while it outperforms the best general algorithm already for slightly non-trivial parameter values. As illustrated in the first part of this thesis, for many problems there exist efficient parameterized algorithms regarding multiple parameters, each describing a different kind of structure. In the second part of this thesis, we explore how to combine such homogeneous structures to more general and heterogeneous structures. Using algebraic expressions, we define new combined graph classes of heterogeneous structure in a clean and robust way, and we showcase this for the heterogeneous merge of the parameters tree-depth and modular-width, by presenting parameterized algorithms on such heterogeneous graph classes and getting running times that match the homogeneous cases throughout.

Tous les problèmes définissables en logique du second ordre monadique peuvent être résolus en temps polynomial dans les classes de graphes qui ont une largeur de clique bornée. La largeur de clique est un paramètre de graphe défini de manière algébrique, c'est-à-dire, à partir d'opérations de composition de graphes. La largeur de rang, définie de manière combinatoire, est une notion équivalente à la largeur de clique des graphes non orientés. Nous donnons une caractérisation algébrique de la largeur de rang et nous montrons qu'elle est linéairement bornée par la largeur arborescente. Nous proposons également une notion de largeur de rang pour les graphes orientés et une relation de vertex-minor pour les graphes orientés. Nous montrons que les graphes orientés qui ont une largeur de rang bornée sont caractérisés par une liste finie de graphes orientés à exclure comme vertex-minor. Beaucoup de classes de graphes n'ont pas une largeur de rang bornée, par exemple, les graphes planaires. Nous nous intéressons aux systèmes d'étiquetage dans ces classes de graphes. Un système d'étiquetage pour une propriété P dans un graphe G, consiste à assigner une étiquette, aussi petite que possible, à chaque sommet de telle sorte que l'on puisse vérifier si G satisfait P en n'utilisant que les étiquettes des sommets. Nous montrons que si P est une propriété définissable en logique du premier ordre alors, certaines classes de graphes de largeur de clique localement bornée admettent un système d'étiquetage pour P avec des étiquettes de taille logarithmique. Parmi ces classes on peut citer les classes de graphes de degré borné, les graphes planaires et plus généralement les classes de graphes qui excluent un apex comme mineur et, les graphes d'intervalle unitaire. Si x et y sont deux sommets, X un ensemble de sommets et F un ensemble d'arêtes, nous notons Conn(x,y,X,F) la propriété qui vérifie dans un graphe donné si x et y sont connectés par un chemin, qui ne passe par aucun sommet de X si aucune arête de F. Cette propriété n'est pas définissable en logique du premier ordre. Nous montrons qu'elle admet un système d'étiquetage avec des étiquettes de taille logarithmique dans les graphes planaires. Nous montrons enfin que Conn(x,y,X,0) admet également un système d'étiquetage avec des étiquettes de taille logarithmique dans des classes de graphes qui sont définies comme des combinaisons de graphes qui ont une petite largeur de clique et telles que le graphe d'intersection de ces derniers est planaire et est de degré borné. / Every property definable in onadic second order logic can be checked in polynomial-time on graph classes of bounded clique-width. Clique-width is a graph parameter defined in an algebraical way, i.e., with operations ``concatenating graphs'' and that generalize concatenation of words.Rank-width, defined in a combinatorial way, is equivalent to the clique-width of undirected graphs. We give an algebraic characterization of rank-width and we show that rank-width is linearly bounded in term of tree-width. We also propose a notion of ``rank-width'' of directed graphs and a vertex-minor inclusion for directed graphs. We show that directed graphs of bounded ``rank-width'' are characterized by a finite list of finite directed graphs to exclude as vertex-minor. Many graph classes do not have bounded rank-width, e.g., planar graphs. We are interested in labeling schemes on these graph classes. A labeling scheme for a property P in a graph G consists in assigning a label, as short as possible, to each vertex of G and such that we can verify if G satisfies P by just looking at the labels. We show that every property definable in first order logic admit labeling schemes with labels of logarithmic size on certain graph classes that have bounded local clique-width. Bounded degree graph classes, minor closed classes of graphs that exclude an apex graph as a minor have bounded local clique-width. If x and y are two vertices and X is a subset of the set of vertices and Y is a subset of the set of edges, we let Conn(x,y,X,Y) be the graph property x and y are connected by a path that avoids the vertices in X and the edges in Y. This property is not definable by a first order formula. We show that it admits a labeling scheme with labels of logarithmic size on planar graphs. We also show that Conn(x,y,X,0) admits short labeling schemes with labels of logarithmic size on graph classes that are ``planar gluings'' of graphs of small clique-width and with limited overlaps.

Les travaux de cette thèse s’inscrivent dans le cadre du planning de traitements minimalement invasifs des lésions des artères coronaires. Le cardiologue réalise un examen coronarographique, puis dans la continuité, une angioplastie transluminale. L’angiographie rotationnelle à rayons X permet de visualiser sous différentes incidences 2D la lumière des artères coronaires sur plusieurs cycles cardiaques et aussi d’obtenir une reconstruction 3D+T des arbres coronaires. A partir de cette séquence, notre objectif est de déterminer automatiquement une incidence optimale 2D du segment sténosé compatible avec les angles du C-arm afin d’aider le cardiologue lors de l’intervention.Différentes étapes sont considérées pour calculer la position angulaire optimale du C-arm. Afin de suivre la zone de lésion durant le cycle cardiaque, une première méthode est proposée pour mettre en correspondance tous les arbres de la séquence 3D+T. Tout d’abord, un appariement deux à deux des arbres successifs est réalisé afin de construire un arbre d’union. Ces derniers sont ensuite fusionnés afin d’obtenir un arbre mosaïque représentant l’arbre le plus complet de la séquence. L’utilisation de mesures de similarités géométriques et hiérarchiques ainsi que l’insertion de nœuds artificiels permet de prendre en compte les différents mouvements non-rigides des artères coronaires subits au cours du cycle cardiaque et les variations topologiques dû à leurs extractions. Cet appariement nous permet de proposer une deuxième méthode afin d’obtenir une vue angiographique 2D optimale de la zone de lésion tout le long du cycle cardiaque. Cette incidence est proposée spécifiquement pour trois types de région d’intérêt (segment unique, segment multiple ou bifurcation) et est calculée à partir de quatre critères (raccourcissement, chevauchement interne et externe ou angle d’ouverture de bifurcation). Une vue 2D déployée du segment projeté avec le moins de superposition avec les structures vasculaires avoisinantes est obtenue. Nous donnons également la possibilité au cardiologue d’avoir une incidence optimale privilégiant soit le déploiement du stent ou soit le guidage d’outils de la racine de l’arbre à la zone sténosée. Nos différents algorithmes ont été évalués sur une séquence réelle de 10 phases segmentées à partir d’un CT et de 41 séquences simulées. / The thesis work deals with the planning of minimally invasive surgery of coronary artery lesions. The physician performs a coronarography following by a percutaneous transluminal angioplasty. The X-ray rotational angiography permits to visualize the lumen artery under different projection angles in several cardiac cycles. From these 2D projections, a 3D+T reconstruction of coronary arteries can be obtained. Our goal is to determine automatically from this 3D+T sequence, the optimal angiographic viewing angle of the stenotic segment. Several steps are proposed to compute the optimal angular position of the C-arm. Firstly, a mosaic-based tree matching algorithm of the 3D+T sequence is proposed to follow the stenotic lesion in the whole cardiac cycle. A pair-wise inexact tree matching is performed to build a tree union between successive trees. Next, these union trees are merged to obtain the mosaic tree which represents the most complete tree of the sequence. To take into account the non-rigid movement of coronary arteries during the cardiac cycle and their topology variations due to the 3D reconstruction or segmentation, similarity measures based on hierarchical and geometrical features are used. Artificial nodes are also inserted. With this global tree sequence matching, we propose secondly a new method to determine the optimal viewing angle of the stenotic lesion throughout the cardiac cycle. This 2D angiographic view which is proposed for three regions of interest (single segment, multiple segment or bifurcation) is computed from four criteria: the foreshortening, the external and internal overlap and the bifurcation opening angle rates. The optimal view shows the segment in its most extended and unobstructed dimension. This 2D view can be optimal either for the deployment of the stent or for the catheter guidance (from the root to the lesion). Our different algorithms are evaluated on real sequence (CT segmentation) and 41 simulated sequences.

Durant ces dernières décennies, d'importants efforts et beaucoup de café ont été dépensés en vue de caractériser les instances faciles des problèmes NP-difficiles. Dans ce domaine de recherche, une approche s'avère être redoutablement efficace : la théorie de la complexité paramétrée introduite par Downey et Fellows dans les années 90.Dans cette théorie, la complexité d'un problème n'est plus mesurée uniquement en fonction de la taille de l'instance, mais aussi en fonction d'un paramètre .Dans cette boite à outils, la largeur arborescente est sans nul doute un des paramètres de graphe les plus étudiés.Ce paramètre mesure à quel point un graphe est proche de la structure topologique d'un arbre.La largeur arborescente a de nombreuses propriétés algorithmiques et structurelles.Néanmoins, malgré l'immense intérêt suscité par la largeur arborescente, seules les classes de graphes peu denses peuvent avoir une largeur arborescente bornée.Mais, de nombreux problèmes NP-difficiles s'avèrent faciles dans des classes de graphes denses.La plupart du temps, cela peut s'expliquer par l'aptitude de ces graphes à se décomposer récursivement en bipartitions de sommets $(A,B)$ où le voisinage entre $A$ et $B$ possède une structure simple.De nombreux paramètres -- appelés largeurs -- ont été introduits pour caractériser cette aptitude, les plus remarquables sont certainement la largeur de clique , la largeur de rang , la largeur booléenne et la largeur de couplage induit .Dans cette thèse, nous étudions les propriétés algorithmiques de ces largeurs.Nous proposons une méthode qui généralise et simplifie les outils développés pour la largeur arborescente et les problèmes admettant une contrainte d'acyclicité ou de connexité tel que Couverture Connexe , Dominant Connexe , Coupe Cycle , etc.Pour tous ces problèmes, nous obtenons des algorithmes s'exécutant en temps $2^{O(k)}\cdot n^{O(1)}$, $2^{O(k \log(k))}\cdot n^{O(1)}$, $2^{O(k^2)}\cdot n^{O(1)}$ et $n^{O(k)}$ avec $k$ étant, respectivement, la largeur de clique, la largeur de Q-rang, la larguer de rang et la largueur de couplage induit.On prouve aussi qu'il existe un algorithme pour Cycle Hamiltonien s'exécutant en temps $n^{O(k)}$ quand une décomposition de largeur de clique $k$ est donné en entrée.Finalement, nous prouvons qu'on peut compter en temps polynomial le nombre de transversaux minimaux d'hypergraphes $\beta$-acyclique ainsi que le nombre de dominants minimaux de graphes fortement triangulés.Tous ces résultats offrent des pistes prometteuses en vue d'une généralisation des largeurs et de leurs applications algorithmiques. / In the last decades, considerable efforts have been spent to characterize what makes NP-hard problems tractable. A successful approach in this line of research is the theory of parameterized complexity introduced by Downey and Fellows in the nineties.In this framework, the complexity of a problem is not measured only in terms of the input size, but also in terms of a parameter on the input.One of the most well-studied parameters is tree-width, a graph parameter which measures how close a graph is to the topological structure of a tree.It appears that tree-width has numerous structural properties and algorithmic applications.However, only sparse graph classes can have bounded tree-width.But, many NP-hard problems are tractable on dense graph classes.Most of the time, this tractability can be explained by the ability of these graphs to be recursively decomposable along vertex bipartitions $(A,B)$ where the adjacency between $A$ and $B$ is simple to describe.A lot of graph parameters -- called width measures -- have been defined to characterize this ability, the most remarkable ones are certainly clique-width, rank-width, and mim-width.In this thesis, we study the algorithmic properties of these width measures.We provide a framework that generalizes and simplifies the tools developed for tree-width and for problems with a constraint of acyclicity or connectivity such as Connected Vertex Cover, Connected Dominating Set, Feedback Vertex Set, etc.For all these problems, we obtain $2^{O(k)}\cdot n^{O(1)}$, $2^{O(k \log(k))}\cdot n^{O(1)}$, $2^{O(k^2)}\cdot n^{O(1)}$ and $n^{O(k)}$ time algorithms parameterized respectively by clique-width, Q-rank-width, rank-width and mim-width.We also prove that there exists an algorithm solving Hamiltonian Cycle in time $n^{O(k)}$, when a clique-width decomposition of width $k$ is given.Finally, we prove that we can count in polynomial time the minimal transversals of $\beta$-acyclic hypergraphs and the minimal dominating sets of strongly chordal graphs.All these results offer promising perspectives towards a generalization of width measures and their algorithmic applications.

En biologie structurale, il est couramment admit que la structure tridimensionnelle d'une protéine détermine sa fonction. Ce paradigme permet de supposer que deux protéines possédant des structures tridimensionnelles similaires peuvent partager un ancêtre commun et donc posséder des fonctions similaires. Déterminer la similarité entre deux structures de protéines est une tâche importante qui a été largement étudiée. Parmi toutes les méthodes proposées, nous nous intéressons à la mesure de similarité appelée “maximisation du recouvrement de cartes de contacts” (ou CMO), principalement parce qu'elle fournit des scores de similarité pouvant être utilisés pour obtenir de bonnes classifications automatiques des structures de protéines. Dans cette thèse, la comparaison de deux structures de protéines est modélisée comme une recherche de sous-graphe dans des graphes k-partis spécifiques appelés graphes d'alignements, et nous montrons que cette tâche peut être efficacement réalisée en utilisant des techniques avancées issues de l'optimisation combinatoire. Dans la seconde partie de cette thèse, nous modélisons CMO comme une recherche de sousgraphe maximum induit par les arêtes dans des graphes d'alignements, problème pour lequel nous proposons un solveur exact qui surpasse les autres algorithmes de la littérature. Même si nous avons réussi à accélérer CMO, la procédure d'alignement requière encore trop de temps de calculs pour envisager des comparaisons à grande échelle. La troisième partie de cette thèse est consacrée à l'accélération de CMO en utilisant des connaissances issues de la biologie structurale. Nous proposons une approche hiérarchique pour résoudre CMO qui est basée sur les structures secondaires des protéines. Enfin, bien que CMO soit une très bonne mesure de similarité, les alignements qu'elle fournit possèdent souvent de fortes valeurs de déviation (root mean squared deviation, ou RMSD). Pour palier à cette faiblesse, dans la dernière partie de cette thèse, nous proposons une nouvelle méthode de comparaison de structures de protéines basée sur les distances internes que nous appelons DAST (pour Distance-based Alignment Search Tool). Elle est modélisée comme une recherche de clique maximum dans des graphes d'alignements, pour laquelle nous présentons un solveur dédié montrant de très bonnes performances.

Cette thèse est consacrée à l'évaluation de requêtes logiques du point de vue de l'énumération. Nous étudions quatre classes de requêtes. En premier lieu, nous nous intéressons aux formules conjonctives acycliques avec inégalités pour lesquelles nous améliorons un résultat de Papadimitriou et Yannakakis en montrant que de telles requêtes logiques peuvent être évaluées à délai linéaire en la taille de la structure. Nous exhibons ensuite la sous-classe des formules connexe-acycliques pour lesquelles l'évaluation de requêtes s'effectue à délai constant après prétraitement linéaire. Nous montrons que cette classe est maximale pour ce résultat dans le sens suivant: si le produit de matrices booléennes ne peut pas être calculé en temps linéaire alors toute requête conjonctive acyclique est évaluable à délai constant après prétra itement linéaire si et seulement si elle est connexe-acyclique. En second lieu, nous démontrons que toute requête MSO sur une classe de structures de largeur arborescente bornée peut être évaluée à délai linéaire en la taille de chaque solution produite après un prétraitement linéaire en la taille de la structure. En troisième lieu, nous montrons que, pour chaque requête en logique du premier ordre sur des structures de degré borné, il est possible de trouver en temps constant la j-ème solution dans un certain ordre après un prétraitement linéraire. Enfin, nous établissons que les graphes d'intervalles unitaires ont une largeur de clique localement bornée. D'où nous déduisons que tout énoncé du premier ordre sur ces graphes est décidable en temps linéaire; là encore, nous démontrons une certaine maximalité de ce résultat.