Cette thèse est une contribution à un problème classique de la géométrie algorithmique et combinatoire : l’étude des k-sets d’un ensemble V de n points du plan. Nous introduisons d’abord la notion de chaîne d’inclusion de convexes qui est un ordonnancement des points de V tel qu’aucun point n’appartient à l’enveloppe convexe de ceux qui le précèdent. Tout k-set d’une sous-suite commençante de la chaîne est appelé un k-set de la chaîne. Nous montrons que le nombre de ces k-sets est un invariant de V et qu’il est égal au nombre de régions du diagramme de Voronoï d’ordre k de V. Nous en déduisons un algorithme en ligne pour construire les k-sets des sommets d’une ligne polygonale simple dont chaque sommet est à l’extérieur de l’enveloppe convexe des sommets qui le précèdent sur la ligne. Si c est le nombre total de k-sets construits, la complexité de notrealgorithme est en O(n log n+c log^2 k) et est équivalente, par k-set construit, à celle du meilleur algorithme connu. Nous montrons ensuite que la méthode algorithmique classique de division-fusion peut être adaptée à la construction des k-sets de V. L’algorithme qui en résulte a une complexité enO(n log n+c log^2 k log(n/k)), où c est le nombre maximum de k-sets d’un ensemble de n points.Nous prouvons enfin que les centres de gravité des k-sets d’une chaîne d’inclusion de convexes sont les sommets d’une triangulation qui appartient à la même famille de triangulations, dites centroïdes, que le dual du diagramme de Voronoï d’ordre k. Nous en d´déduisons un algorithme qui construit des triangulations centroïdes particulières en temps O(n log n+k(n-k) log^2 k), ce qui est plus efficace que les algorithmes connus jusque là. / This thesis is a contribution to a classical problem in computational and combinatorial geometry: the study of the k-sets of a set V of n points in the plane. First we introduce the notion of convex inclusion chain that is an ordering of the points of V such that no point is inside the convex hull of the points that precede it. Every k-set of an initial sub-sequence of the chain is called a k-set of the chain. We prove that the number of these k-sets is an invariant of V and is equal to the number of regions in the order-k Voronoi diagram of V. We then deduce an online algorithm for the construction of the k-sets of the vertices of a simple polygonal line such that every vertex of this line is outside the convex hull of all its preceding vertices on the line. If c is the total number of k-sets built with this algorithm, the complexity of our algorithm is in O(n log n + c log^2k) and is equal, per constructed k-set, to the complexity of the best algorithm known. Afterward, we prove that the classical divide and conquer algorithmic method can be adapted to the construction of the k-sets of V. The algorithm has a complexity of O(n log n + c log^2k log(n/k)), where c is the maximum number of k-sets of a set of n points. We finally prove that the centers of gravity of the k-sets of a convex inclusion chain are the vertices of a triangulation belonging to the family of so-called centroid triangulations. This family notably contains the dual of the order-k Voronoi diagram. We give an algorithm that builds particular centroid triangulations in O(n log n + k(n- k) log^2 k) time, which is more efficient than all the currently known algorithms.

Cette thèse de doctorat étudie trois problèmes à l'aide des outils de la mécanique statistique. Nous montrons l'existence du phénomène d'universalité critique pour la transition de phases dynamique de certains algorithmes de recherche combinatoire. Nous donnons les valeurs exactes des exposants critiques et une formule analytique pour une fonction d'échelle. Nous développons un formalisme qui nous permet de calculer un développement perturbatif systématique, en grandes dimensions d'espace, de la fonction de grandes déviations de l'état métastable du processus de contact. Il peut resservir entre autres pour d'autres modèles de biologie des populations. Nous introduisons enfin deux modèles bidimensionnels exactement solubles pour la statique des milieux granulaires. Ils reproduisent la transition de jamming et permettent de discuter les différentes échelles de longueurs de ces milieux et de mettre en défaut l'hypothèse d'Edwards dans un cas réaliste.

Dans cette thèse, nous définissons des méthodes efficaces et génériques<br /> dans le but de résoudre les problèmes de robustesse que pose la géométrie algorithmique,<br /> en se concentrant principalement sur l'évaluation exacte des prédicats<br /> géométriques.<br /> Nous avons exploré des méthodes basées sur l'arithmétique<br /> modulaire, ce qui nous a conduits à mettre au point des algorithmes simples<br /> et efficaces de reconstruction du signe dans cette représentation des<br /> nombres.<br /> Nous avons également mis au point de nouveaux types de filtres<br /> arithmétiques qui permettent d'accélérer<br /> le calcul des prédicats exacts, en contournant le coût des solutions<br /> traditionnelles basées sur des calculs multi-précision génériques.<br /> Nos méthodes sont basées sur l'utilisation de l'arithmétique<br /> d'intervalles, qui permet une<br /> utilisation souple et efficace, combinée à un outil de génération<br /> automatique de code des prédicats.<br /> Ces solutions sont maintenant disponibles dans la bibliothèque<br /> d'algorithmes géométriques CGAL.

Cette thèse aborde différents aspects de la conception d'un réseau de télécommunications. Un tel réseau utilise des technologies hétérogènes : liens antennes-satellites, radio, fibres optiques ou bien encore réseaux embarqués dans un satellite. Les problématiques varient en fonction de la partie du réseau considérée, du type de requêtes et de l'objectif. Le cas des requêtes de type paquets est abordé dans le cadre des réseaux en forme de grille, mais le thème principal est le routage de requêtes de type connections (unicast et multicast). Les objectifs considérés sont : la conception d'un réseau embarqué dans un satellite de télécommunication, de taille minimum et tolérant des pannes de composants; le dimensionnement des liens d'un réseau afin qu'il supporte des pannes corrélées ou qu'il offre une bonne qualité de service, ou s'il autorise des connections {\em multicast}; le dimensionnement de la taille des buffers d'un réseau d'accés radio; et l'optimisation de l'utilisation des ressources d'un réseau dynamique orienté connections. Dans tous ces cas la problématique du routage de connections est centrale. Mon approche consiste à utiliser la complémentarité de techniques algorithmique et d'optimisation combinatoire ainsi que d'outils issus de la théorie des graphes tels la pathwidth et des notions reliées -process number, jeux de captures et treewidth-, différents types de coloration -impropre et pondérée, proportionnelle, directed star colouring-, les graphes d'expansion et des techniques de partitions telle la quasi partition.

Les travaux effectués lors de cette thèse concernent principalement la triangulation de Delaunay. On montre que la complexité en moyenne - en termes de sites inachevés - du processus de fusion multidimensionnelle dans l'hypothèse de distribution quasi-uniforme dans un hypercube est linéaire en moyenne. Ce résultat général est appliqué au cas du plan et permet d'analyser de nouveaux algorithmes de triangulation de Delaunay plus performants que ceux connus à ce jour. Le principe sous-jacent est de diviser le domaine selon des arbres bidimensionnels (quadtree, 2d-tree, bucket-tree. . . ) puis de fusionner les cellules obtenues selon deux directions. On étudie actuellement la prise en compte de contraintes directement pendant la phase de triangulation avec des algorithmes de ce type. De nouveaux algorithmes pratiques de localisation dans une triangulation sont proposés, basés sur la randomisation à partir d'un arbre binaire de recherche dynamique de type AVL, dont l'un est plus rapide que l'algorithme optimal de Kirkpatrick, au moins jusqu'à 12 millions de sites K Nous travaillons actuellement sur l'analyse rigoureuse de leur complexité en moyenne. Ce nouvel algorithme est utilisé pour construire " en-ligne " une triangulation de Delaunay qui est parmi les plus performantes des méthodes " en-ligne " connues à ce jour.

La récente réforme des lycées en France de 2009 s'est accompagnée d'un changement de programmes en mathématiques. Relativement à la classe de seconde, deux sujets nous questionnent : d'une part, la nouvelle place de l'algèbre, désormais plongée dans le domaine fonctionnel, lui conférant un rôle essentiellement d'outil, et d'autre part l'introduction d'une familiarisation avec l'algorithmique. De par l'intérêt de lier ces deux sujets, ce travail de thèse propose une étude didactique de la reprise de l'algèbre élémentaire en classe de seconde, et plus particulièrement des objets gravitant autour du concept d'équation, objets dont nous cherchons à affiner le sens par le détour de l'algorithmique. Nous situant dans le cadre de la théorie anthropologique du didactique de Chevallard, nous étudions les conditions et les contraintes de cette reprise. Au travers d'une ingénierie didactique mise en place avec la collaboration de trois enseignants de lycée, nous montrons comment la reprise de concepts d'algèbre élémentaire par le biais de l'algorithmique induit pour les élèves un geste de généralisation, tout en réalisant une certaine matérialisation des objets algébriques, en les manipulant au sein d'un programme informatique. Pour les enseignants, cette ingénierie provoque un questionnement sur les praxéologies de leur enseignement de l'algèbre, suscité par des tâches non routinières de catégorisation et de modélisation des équations. Enfin, nous mettons en évidence la question de l'intégration du domaine de l'algorithmique dans la discipline des mathématiques et le besoin d'une formation des professeurs pour assurer la viabilité de cet enseignement.

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.

Cette thèse s'intéresse à la conception et le développement des techniques de bioinfor- matique qui peuvent faciliter l'utilisation de l'approche metabarcoding pour mesurer la diversité d'espèces. Le metabarcoding peut être utilisé avec le séquencage haut débit pour l'identification d'espèces multiples à partir d'un seul échantillon environnemental. La véritable force du metabarcoding réside dans l'utilisation de barcode marqueurs choisi pour une étude particulière et l'identification d'espèces ou des taxons peut être réalisé avec des marqueurs soigneusement conçu. Avec l'avancement des techniques haut débit de séquençage, une énorme quantité des données de séquences est produit qui contient un nombres substantiel des mutations. Ces mutations posent un grand problème pour les estimations correctes de la biodiversité et pour le d'assignation de taxon. Les trois problèmes majeurs dans le domaine de la bioinformatique que j'ai abordés dans cette thèse sont: i) évaluer la qualité d'une barcode marker , ii) concevoir des nouveaux région barcode et iii) d'analyser les données de séquençage pour traiter les erreurs et éliminer le bruit en séquences. Pour évaluer la qualité d'un barcode marker, on a développé deux mesures quantita- tive,formelle: la couverture (Bc) et la spécificité (Bs). La couverture donne une mesure de universalité d'une pairs de primer pour amplifier un large nombre de taxa, alors que la spécificité donne une mesure de capacité à discriminer entre les différents taxons. Ces mesures sont très utiles pour le classement des barcode marker et pour sélectionner les meilleurs markers. Pour trouver des nouveaux région barcode notamment pour les applications metabarcod- ing, j'ai développé un logiciel, ecoPrimers3. Basé sur ces deux mesures de qualité et de l'information taxinomique intégré, ecoPrimers nous permet de concevoir barcode markers pour n'importe quel niveau taxonomique . En plus, avec un grand nombre de paramètres réglables il nous permet de contrôler les propriétés des amorces. Enfin, grâce a des algorithmes efficaces et programmé en langage C, ecoPrimers est suffisamment efficace pour traiter des grosses bases de données, y compris génomes bactériens entièrement séquencés. Enfin pour traiter des erreurs présentes dans les données de séquencage , nous avons analysé un ensemble simple d'échantillons de PCR obtenus à partir de l'analyse du régime alimentaire de Snow Leopard. En mesurant les corrélations entre les différents paramètres des erreurs, nous avons observé que la plupart des erreurs sont produites pendant l'amplification par PCR. Pour détecter ces erreurs, nous avons développé un algorithme utilisant les graphes, qui peuvent différencier les vrai séquences des erreurs induites par PCR. Les résultats obtenus à partir de cet algorithme a montré que les données de-bruitée a donnent une estimation réaliste de la diversité des espèces étudiées dans les Alpes françaises.

Nous nous intéressons aux aspects algorithmiques de la théorie des représentations modulo p de groupes de Galois p-adiques. À cet effet, l'un des outils introduits par Fontaine est la théorie de ϕ-modules : un ϕ-module sur un corps K de caractéristique p est la donnée d'un espace vectoriel de dimension finie sur K muni d'un endomorphisme ϕ, semi-linéaire par rapport au morphisme de Frobenius sur K. Les représentations à coefficients dans un corps fini du groupe de Galois absolu de K forment une catégorie équivalente à la catégorie des ϕ-modules dits " étales " sur K. Le but des travaux rassemblés ici est donner des algorithmes pour décrire le plus complètement possible la représentation associée à un ϕ-module donné. Nous étudions en préambule les ϕ-modules sur les corps finis, ce qui nous permet d'obtenir de nouveaux résultats décrivant les polynômes tordus sur un corps fini, qui sont des ob jets utilisés notamment en théorie des codes correcteurs. Cela nous permet d'améliorer en partie l'algorithme dû à Giesbrecht pour la factorisation de ces polynômes. Nous nous intéressons ensuite à la catégorie des ϕ-modules sur un corps de séries formelles de caractéristique p. Nous donnons une classification des ob jets simples de cette catégorie lorsque le corps résiduel est algébrique- ment clos, et décrivons un algorithme efficace pour décomposer un ϕ-module en ϕ-modules " isoclines ". Nous donnons des applications à l'étude algorithmique des représentations de p-torsion de groupes de Galois p-adiques.

Selon la méthode utilisée pour construire un modèle structural en trois dimensions et selon l'application à laquelle il est destiné, son maillage, en d'autres termes sa représentation informatique, doit être adapté afin de respecter des critères de type, de nombre et de qualité de ses éléments. Les méthodes de maillage développées dans d'autres domaines que la géomodélisation ne permettent pas de modifier le modèle d'entrée. Ceci est souhaitable en géomodélisation afin de mieux contrôler le nombre d'éléments du maillage et leur qualité. L'objectif de cette thèse est de développer des méthodes de maillage permettant de remplir ces objectifs afin de gérer la complexité géométrique des modèles structuraux définis par frontières. Premièrement, une analyse des sources de complexité géométrique dans ces modèles est proposée. Les mesures développées constituent une première étape dans la définition d'outils permettant la comparaison objective de différents modèles et aident à caractériser précisément les zones plus compliquées à mailler dans un modèle. Ensuite, des méthodes originales de remaillage surfacique et de maillage volumique fondées sur l'utilisation des diagrammes de Voronoï sont proposées. Les fondements de ces deux méthodes sont identiques : (1) une optimisation de type Voronoï barycentrique est utilisée pour globalement obtenir un nombre contrôlé d'éléments de bonne qualité et (2) des considérations combinatoires permettant de construire localement le maillage final, éventuellement en modifiant le modèle initial. La méthode de remaillage surfacique est automatique et permet de simplifier un modèle à une résolution donnée. L'originalité de la méthode de maillage volumique est que les éléments générés sont de types différents. Des prismes et pyramides sont utilisés pour remplir les zones très fines du modèle, tandis que le reste du modèle est rempli avec des tétraèdres.