Cette thèse se situe dans le domaine de la combinatoire algébrique et porte sur la construction de plusieurs structures combinatoires et algébriques sur différentes espèces d'arbres. Après avoir défini un analogue du monoïde plaxique dont les classes d'équivalence sont indexées par les couples d'arbres binaires jumeaux, nous proposons un analogue de la correspondance de Robinson-Schensted dans ce contexte. À partir de ce monoïde, nous construisons une sous-algèbre de Hopf de l'algèbre de Hopf des fonctions quasi-symétriques libres dont les bases sont indexées par les couples d'arbres binaires jumeaux. Ensuite, nous proposons un foncteur combinatoire de la catégorie des monoïdes vers la catégorie des opérades ensemblistes. En utilisant ce foncteur, nous construisons plusieurs opérades qui mettent en jeu divers objets combinatoires. Par le biais d'une construction qui à une opérade associe une algèbre de Hopf non commutative, nous obtenons à partir de l'une des opérades obtenue par notre construction, une algèbre de Hopf basée sur les forêts ordonnées d'arbres plans enracinés. Nous proposons une réalisation polynomiale de cette dernière. Finalement, nous établissons certaines propriétés vérifiées par les arbres binaires équilibrés dans le treillis de Tamari. Nous montrons que l'ensemble des arbres binaires équilibrés y est clos par intervalle et que les intervalles d'arbres binaires équilibrés ont la forme d'hypercubes. Dans l'objectif de dénombrer ces intervalles, nous introduisons une nouvelle sorte de grammaires d'arbres, les grammaires synchrones. Celles-ci permettent d'obtenir une équation fonctionnelle de point fixe pour la série génératrice des arbres qu'elles engendrent / This thesis comes within the scope of algebraic combinatorics and deals with the construction of several combinatorial and algebraic structures on different tree species. After defining an analogue of the plactic monoid whose equivalence classes are indexed by pairs of twin binary trees, we propose in this context an analogue of the Robinson-Schensted correspondence. From this monoid, we construct a Hopf subalgebra of the Hopf algebra of free quasi-symmetric functions whose bases are indexed by pairs of twin binary trees.Then, we propose a combinatorial functor from the category of monoids to the category of set-operads. Using this functor, we construct several operads that involve various combinatorial objects. Through a construction that brings a noncommutative Hopf algebra from an operad, we obtain from one of the operads obtained by our construction, a Hopf algebra based on ordered forests of planar rooted trees. We propose a polynomial realization of the latter.Finally, we establish some properties satisfied by balanced binary trees in the Tamari lattice. We show that the set of balanced binary trees is closed by interval and that the intervals of balanced binary trees have the shape of hypercubes. To enumerate these intervals, we introduce a new kind of tree grammars, namely the synchronous grammars. They allow to obtain a fixed-point functional equation for the generating series of the generated trees

Dans cette thèse, différents problèmes de la combinatoire des mots et de géométrie discrète sont considérés. Nous étudions d'abord l'occurrence des palindromes dans les codages de rotations, une famille de mots incluant entre autres les mots sturmiens et les suites de Rote. En particulier, nous démontrons que ces mots sont pleins, c'est-à-dire qu'ils réalisent la complexité palindromique maximale. Ensuite, nous étudions une nouvelle famille de mots, appelés mots pseudostandards généralisés, qui sont générés à l'aide d'un opérateur appelé clôture pseudopalindromique itérée. Nous présentons entre autres une généralisation d'une formule décrite par Justin qui permet de générer de façon linéaire et optimale un mot pseudostandard généralisé. L'objet central, le f-palindrome ou pseudopalindrome est un indicateur des symétries présentes dans les objets géométriques. Dans les derniers chapitres, nous nous concentrons davantage sur des problèmes de nature géométrique. Plus précisément, nous don-nons la solution à deux conjectures de Provençal concernant les pavages par translation, en exploitant la présence de palindromes et de périodicité locale dans les mots de contour. À la fin de plusieurs chapitres, différents problèmes ouverts et conjectures sont brièvement présentés. / In this thesis, we explore different problems at the intersection of combinatorics on words and discrete geometry. First, we study the occurrences of palindromes in codings of rotations, a family of words including the famous Sturmian words and Rote sequences. In particular, we show that these words are full, i.e. they realize the maximal palindromic complexity. Next, we consider a new family of words called generalized pseudostandard words, which are generated by an operator called iterated pseudopalindromic closure. We present a generalization of a formula described by Justin which allows one to generate in linear (thus optimal) time a generalized pseudostandard word. The central object, the f-palindrome or pseudopalindrome, is an indicator of the symmetries in geometric objects. In the last chapters, we focus on geometric problems. More precisely, we solve two conjectures of Provençal about tilings by translation, by exploiting the presence of palindromes and local periodicity in boundary words. At the end of many chapters, different open problems and conjectures are briefly presented.

Depuis quelques années, l'algorithme fait son entrée dans l'enseignement secondaire en France et à l'étranger. L'enseignement de ce concept fortement lié aux mathématiques et à la preuve soulève de nombreuses questions didactiques. Cette thèse propose une analyse épistémologique du concept afin de permettre l'étude de sa transposition didactique et la construction de situations didactiques. Dans un premier temps, nous présentons une analyse épistémologique détaillée du concept en mettant en avant ses aspects fondamentaux. Cela permet de proposer un modèle de conceptions (au sens de ckc) pour l'algorithme du point de vue du savoir savant et tenant compte l'ensemble des formes que peut prendre l'algorithme. Ces résultats, validés expérimentalement par les analyses d'entretiens avec des chercheurs, permettent de mener une étude de la transposition en jeu dans l'enseignement secondaire français (lycée). Au travers de l'étude des instructions officielles, de manuels scolaires et de ressources en ligne, nous mettons en évidence une transposition partielle du concept principalement orientée vers la programmation et l'usage de l'algorithme comme un outil. Enfin, la dernière partie propose une caractérisation de problèmes fondamentaux pour l'algorithme et des perspectives pour la construction et l'étude de situations didactiques en algorithmique. / For few years, the notion of an algorithm has been introduced in secondary school curricula in France and abroad. Teaching this concept, strongly linked with mathematics and proof raises many didactic questions. This thesis proposes an epistemological analysis of the concept of an algorithm in order to allow the study of its transposition and the building of didactic situations. First, we introduce a detailed epistemological analysis of the concept, highlighting its fundamental aspects. It allows us to propose a model of conceptions (in the meaning of ckc) for algorithm viewed from the academical knowledge and taking into account the different forms an algorithm can take. Those results, experimentally validated by the analysis of interviews of researchers, permit to study the didactic transposition involved in the French secondary school (lycée). Through the study of the official curricula and some textbooks and online resources, we emphasize a partial transposition of the concept, mainly tool-oriented and based on programming. Finally, the last part proposes a characterization of fundamental problems for algorithm and perspectives for designing an studying didactic situations in algorithmics.

Les gènes sont les parties du génome qui codent pour les protéines. Les gènes d’une ou plusieurs espèces peuvent être regroupés en "familles", en fonction de leur similarité de séquence. Cependant, pour connaître les relations fonctionnelles entre ces copies de gènes, la similarité de séquence ne suffit pas. Pour cela, il est important d’étudier l’évolution d’une famille par duplications et pertes afin de pouvoir distinguer entre gènes orthologues, des copies ayant évolué par spéciation et susceptibles d’avoir conservé une fonction commune, et gènes paralogues, des copies ayant évolué par duplication qui ont probablement développé des nouvelles fonctions. Étant donnée une famille de gènes présents dans n espèces différentes, un arbre de gènes (obtenu par une méthode phylogénétique classique), et un arbre phylogénétique pour les n espèces, la "réconciliation" est l’approche la plus courante permettant d’inférer une histoire d’évolution de cette famille par duplications, spéciations et pertes. Le degré de confiance accordé à l’histoire inférée est directement relié au degré de confiance accordé à l’arbre de gènes lui-même. Il est donc important de disposer d’une méthode préliminaire de correction d’arbres de gènes. Ce travail introduit une méthodologie permettant de "corriger" un arbre de gènes : supprimer le minimum de feuilles "mal placées" afin d’obtenir un arbre dont les sommets de duplications (inférés par la réconciliation) sont tous des sommets de "duplications apparentes" et obtenir ainsi un arbre de gènes en "accord" avec la phylogénie des espèces. J’introduis un algorithme exact pour des arbres d’une certaine classe, et une heuristique pour le cas général. / Genes are segments of genomes that code for proteins. Genes of one or more species can be grouped into gene families based on their sequence similarity. In order to determine functional relationships among these multiple gene copies of a family, sequence homology is insufficient as no direct information on the evolution of the gene family by duplication, speciation and loss can be inferred directly from a family of homologous genes. And it is precisely this information that allows us to distinguish between orthologous gene copies, that have evolved by speciation and are more likely to preserve the same function and paralogous gene copies that have evolved by duplication and usually acquire new functions. For a given gene family contained within n species, a gene tree (inferred by typical phylogenetic methods) and a phylogenetic tree of the considered species, reconciliation between the gene tree and the species tree is the most commonly used approach to infer a duplication, speciation and loss history for the gene family. The main criticism towards reconciliation methods is that the inferred duplication and loss history for a gene family is strongly dependent on the gene tree considered for this family. Indeed, just a few misplaced leaves in the gene tree can lead to a completely different history, possibly with significantly more duplications and losses. It is therefore important to have a preliminary method for "correcting” the gene tree, i.e. removing potentially misplaced branches. N. El-Mabrouk and C. Chauve introduced "non-apparent duplications" as nodes that are likely to result from the misplacement of one leaf in the gene tree. Simply put, such a node indicates that one or more triplets contradict the phylogeny given by the species tree. In this work, the problem of eliminating non-apparent duplications from a given gene tree by a minimum number of leaf removals is considered. Depending on the disposition of this type of nodes in the gene tree, the algorithm introduced leads to an O(nlogn) performance and an optimal solution in a best case scenario . The general case however is solved using an heuristic method.

L'alignement de macromolécules biologiques comme les protéines, l'ADN ou encore l'ARN est une problématique biologique et bio-informatique qui a pour but de révéler une partie des mystères du fonctionnement des cellules, constituants des êtres vivants. Les ARN non-codant sont des macromolécules intervenant dans le métabolisme de tout être vivant et les deux problématiques majeurs les concernant sont: la prédiction de leur structure pour mieux comprendre leur fonctionnement et leur détection dans des bases de données ou des génomes. L'une des approches: l'alignement structure-séquence d'ARN, répond à ces deux problématiques. Le problème d'alignement structure-séquence consiste à aligner une structure connue d'un premier ARN avec la séquence d'un deuxième ARN.La structure est représentée sous la forme d'un graphe ou de façon équivalente sous la forme d'une séquence arc-annotées et la séquence représente la suite des nucléotides de l'ARN.Pour résoudre ce problème, nous cherchons à optimiser l'alignement selon une fonction de coût. C'est donc un problème d'optimisation, qui malheureusement se révèle NP-Difficile.En conséquence différents travaux définissent des classes d'instances réduites pour lesquelles ils proposent des algorithmes spécifiques mais à complexités polynomiales.Les travaux de ma thèse unifient et la généralisent les approches précédentes par la construction d'un algorithme à complexité paramétrée non spécifique à une classe d'instances. En utilisant cet algorithme, il est possible de résoudre le problème d'alignement structure-séquence pour toutes les instances possibles, et aussi efficacement que les précédentes approches sur leur domaine de résolution respectif. Cet algorithme utilise une technique empruntée à la théorie des graphes: la décomposition arborescente, c'est-à-dire qu'il transforme la structure donnée en une décomposition arborescente et c'est ensuite cette décomposition qui est alignée avec la séquence donnée. L'alignement entre une décomposition arborescente et une séquence se fait par programmation dynamique.Sa mise en place a nécessité une reformulation du problème ainsi qu'une modification importante de l'utilisation classique de la programmation dynamique pour les décompositions arborescentes. Au final, cela conduit à un algorithme paramétré dont le paramètre est entièrement lié à la décomposition arborescente. La construction des décompositions arborescentes pour lesquelles l'alignement s'effectuera plus le efficacement possible est malheureusement un problème lui aussi NP-Difficile. Néanmoins, nous avons créé une heuristique de construction de décompositions adaptée aux structures d'ARN.Nous avons alors défini des nouvelles classes de structures pour lesquelles notre algorithme (décomposition et alignement) possède une faible complexité. Ces classes incluent notamment toutes les autres classes précédemment définies et la complexité de notre algorithme est au moins aussi faible que celles des algorithmes spécifiques sur leurs classes de structures respectives. Ces classes de structures représentent la majorité des structures connues et contiennent de nombreux éléments importants jusqu'alors non pris en compte (tel que les motifs tertiaires d'ARN). Le problème de l'alignement structure-séquence tente de répondre aux problématiques de prédictions de structures et de recherche d'ARN. Néanmoins, la qualité des résultats obtenus par sa résolution dépendent de la fonction de coût utilisée. Durant ma thèse j'ai commencé la mise place de la construction par apprentissage d'une nouvelle fonction de coût, adaptée aux nouvelles classes de structures que nous avons défini. Enfin de par la nature de l'algorithme, le travail réalisé permet des améliorations non négligeables, en terme de qualité des résultats et de rapidité de calcul comme la recherche de solution sous-optimales ou l'utilisation de l'algorithme au sein d'heuristiques dérivées d'heuristiques classiques. / The alignment of biological macromolecules such as proteins, DNA or RNA is a biological and bio-informatics problematic which aims to reveal some of the mysteries of how cells works. The non-coding RNA are involved in the metabolism of all living beings. The two major issues concerning them are: the prediction of their structure to better understand their function and their detection in databases or genomes. One approach, the structure-sequence alignment of RNA, addresses these two issues. The work done during my thesis provides some constructive elements on this problem and led me to call the graph algorithmic for its resolution. The alignment problem is to align a structure of a first RNA with the sequence of a second RNA. The structure on the first RNA is represented as a graph or equivalently as an arc-annotated sequence and the sequence represents the nucleotide sequence of the second RNA.To solve this problem, we aim to compute a minimal cost alignment, according to a given cost function. So, this is an optimization problem, which turns out to be NP-hard.Accordingly, different works define several reduced structure classes for which they propose specific algorithms but with polynomial complexity. The work of my thesis unifies and generalizes previous approaches by the construction of a unique (not class specific) parameterized algorithm. Using this algorithm, it is possible to solve the problem of structure-sequence alignment for all possible instances, and as effectively as previous approaches in their respective field of resolution.This algorithm uses a technique from graph theory: the tree decomposition, that is to say, it transforms the given structure into a tree-decomposition and the decomposition is then aligned with the sequence. The alignment between a tree-decomposition and a sequence is done by dynamic programming. Its implementation requires a reformulation of the problem as well as a substantial modifications to the conventional use of dynamic programming for tree decompositions. This leads to an algorithm whose parameter is entirely related to the tree-decomposition.The construction of tree decompositions for which the alignment is the most effective is unfortunately a NP-Hard problem. Nevertheless, we have developed a heuristic construction of decompositions adapted to RNA structures. We then defined new structure classes which extend existing ones without degrading the complexity of the alignment but which can represent the majority of known structures containing many important elements that had not be taken into account previously (such as RNA tertiary motifs).The sequence-structure alignment problem attempts to answer the problem of prediction of structures and RNA research. However, the quality of the results obtained by its resolution depends on the cost function. During my PhD I started to define new cost functions adapted to the new structure classes by a machine learning approach. Finally, the work allows significant improvements in terms of quality of results and computation. For example the approach directly allows the search for sub-optimal solutions or its use within heuristics derived from traditional heuristic methods.

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. / The recent French schools reform (2009) was accompanied by a change in mathematics curriculum. With respect to the “classe de seconde” (9th-10th Grade in US High School), two subjects question us: first, the new positioning of algebra, now part of the functional domain, giving it a primary role of tool, and on the other hand, the introduction of algorithmic concepts.Through the value of combining these two subjects, this thesis proposes a didactic study of the resumption of elementary algebra in “classe de seconde”, and especially of the objects orbiting around equation concept, objects of which we search to refine the meaning, through the detour of algorithmics. Positioned within the anthropological theory of the didactic by Chevallard, we study the conditions and constraints of this resumption. Through a didactic engineering implementation in collaboration with three high school teachers, we show how the resumption of basic algebra concepts through algorithmics induced for students a gesture of generalization, while achieving some materialization of algebraic objects, manipulating them in a computer program. For teachers, this engineering induces a questioning of their praxeology teaching algebra, generated by non-routine tasks of equations categorization and modeling. Finally, we highlight the challenge of integrating algorithmics domain within mathematics discipline and the need for teachers to be trained, to ensure the viability of this teaching.

Les propriétés physiques macroscopiques des matériaux granulaires découlent directement de leurs micro-structures. L'étude de tels matériaux nécessite la segmentation de leur structures 3D à partir d'images acquises par CT-scans. Cependant, ces images sont parfois difficiles à analyser, car de nombreux défauts et artefactes de reconstruction peuvent apparaître. Obtenir des structures 3D proches des données réelles nécessite un filtrage adapté, qui ne peut être obtenu que par une analyse approfondie du matériaux.Un filtrage adapté améliore la perception de chacun des grains et la structure 3D peut être alors obtenue par segmentation. La complexité de ces structures rend la tâche difficile : les grains qui la représentent prennent des formes irrégulières, allongées et pas nécessairement convexes. Ces grains sont généralement fortement agglomérés et difficiles à séparer. De plus, des phénomènes de fracturation sont fréquemment observés. Les grains sont éclatés en petits fragments pouvant s'éloigner de la position d'origine du grain.Dans le cadre de cette thèse, une chaîne complète de segmentation est présentée. Les données brutes d'acquisition sont tout d'abord filtrés et pré-traités pour en extraire un certain nombre de mesures statistiques , telles que le nombre de phase, le nombre de grains de chaque phase, la distribution des tailles de grains et l'identification spectral de chaque phase. Une première segmentation grossière est effectuée en utilisant la transformation de ligne de partage des eaux. Une hiérarchie des contours obtenus permet d'éliminer la sur-segmentation. Enfin, une méthode permettant d'évaluer la similitude entre deux bords adjacents est présenté, et nous permettera de réassembler les grains fragmentés, dont les fragments ont été dispersés.Les acquitions par CT-scan sont conséquentes et leur étude nécessite une utilisation efficace des architectures récentes de calcul. Le choix de la chaîne de traitement est basé sur l'étude de l'état de l'art et son application aux données 3D, avec comme objectif d'équilibrer les coûts de traitement et la qualité de la segmentation. Une nouvelle méthode de segmentation nous permet d'atteindre de meilleurs performances en améliorant également la qualité des résultats. Enfin, deux nouveaux algorithmes sont proposés pour la détection de composantes connexes et la transformation de ligne de partage des eaux. / The physical properties of granular materials on a macroscopic scale derive from their microstructures. The segmentation of CT-images of this type of material is the first step towards simulation and modeling but it is not a trivial task. However, the quality of those images is often affected by the presence of noise and reconstruction artefacts. Obtaining 3D structures that fit the reality requires an adapted filter, which can only be obtained by a complete analysis of the material.This adapted filter enhances each grain and the full structure of the material is obtained by segmentation. However, non-spherical, elongated or non-convex objects fail to be separated with classical methods. Moreover, grains are commonly fragmented due to external conditions. Grains are ground into multiple fragments of different shape and volume; those fragments drift from one another in the binder phase.In this thesis, a complete process chain is proposed to segment complex structures that can be acquired by CT-scan. The raw data is first filtered and processed, and statistical features are extracted such as the number of phases, the number of grains of each phase, the size distribution and spectral identification of the phases. A primary segmentation is performed to identify every connection between touching grains and is based on the watershed transform. A hierarchy is built on the obtained contours to eliminate over-segmentation. Reconstruction of grains from fragments is achieved using affinities that match the local thickness and the regularity of the interface.Typical CT-images are voluminous, and the study of granular materials requires efficient use of modern computing architectures. Studying the state-of-the-art and its application to 3D data has oriented our choice has allowed us to balance the quality of segmentation and the computing cost. A novel segmentation method allows for higher performances while improving the quality of the result. Finally, two new algorithms are proposed for the labeling of connected components and for the watershed transformation.

Les gènes sont les parties du génome qui codent pour les protéines. Les gènes d’une ou plusieurs espèces peuvent être regroupés en "familles", en fonction de leur similarité de séquence. Cependant, pour connaître les relations fonctionnelles entre ces copies de gènes, la similarité de séquence ne suffit pas. Pour cela, il est important d’étudier l’évolution d’une famille par duplications et pertes afin de pouvoir distinguer entre gènes orthologues, des copies ayant évolué par spéciation et susceptibles d’avoir conservé une fonction commune, et gènes paralogues, des copies ayant évolué par duplication qui ont probablement développé des nouvelles fonctions. Étant donnée une famille de gènes présents dans n espèces différentes, un arbre de gènes (obtenu par une méthode phylogénétique classique), et un arbre phylogénétique pour les n espèces, la "réconciliation" est l’approche la plus courante permettant d’inférer une histoire d’évolution de cette famille par duplications, spéciations et pertes. Le degré de confiance accordé à l’histoire inférée est directement relié au degré de confiance accordé à l’arbre de gènes lui-même. Il est donc important de disposer d’une méthode préliminaire de correction d’arbres de gènes. Ce travail introduit une méthodologie permettant de "corriger" un arbre de gènes : supprimer le minimum de feuilles "mal placées" afin d’obtenir un arbre dont les sommets de duplications (inférés par la réconciliation) sont tous des sommets de "duplications apparentes" et obtenir ainsi un arbre de gènes en "accord" avec la phylogénie des espèces. J’introduis un algorithme exact pour des arbres d’une certaine classe, et une heuristique pour le cas général. / Genes are segments of genomes that code for proteins. Genes of one or more species can be grouped into gene families based on their sequence similarity. In order to determine functional relationships among these multiple gene copies of a family, sequence homology is insufficient as no direct information on the evolution of the gene family by duplication, speciation and loss can be inferred directly from a family of homologous genes. And it is precisely this information that allows us to distinguish between orthologous gene copies, that have evolved by speciation and are more likely to preserve the same function and paralogous gene copies that have evolved by duplication and usually acquire new functions. For a given gene family contained within n species, a gene tree (inferred by typical phylogenetic methods) and a phylogenetic tree of the considered species, reconciliation between the gene tree and the species tree is the most commonly used approach to infer a duplication, speciation and loss history for the gene family. The main criticism towards reconciliation methods is that the inferred duplication and loss history for a gene family is strongly dependent on the gene tree considered for this family. Indeed, just a few misplaced leaves in the gene tree can lead to a completely different history, possibly with significantly more duplications and losses. It is therefore important to have a preliminary method for "correcting” the gene tree, i.e. removing potentially misplaced branches. N. El-Mabrouk and C. Chauve introduced "non-apparent duplications" as nodes that are likely to result from the misplacement of one leaf in the gene tree. Simply put, such a node indicates that one or more triplets contradict the phylogeny given by the species tree. In this work, the problem of eliminating non-apparent duplications from a given gene tree by a minimum number of leaf removals is considered. Depending on the disposition of this type of nodes in the gene tree, the algorithm introduced leads to an O(nlogn) performance and an optimal solution in a best case scenario . The general case however is solved using an heuristic method.

The aim of this habilitation is to exhibit my contributions in several area of Bio-Algorithmics. Rather than an exhaustive presentation of my works, I have made the choice of presenting results we obtained with collaborators on a representative subset of the problems I have been involved in since 2005. For ease of readability, I will regroup the results obtained according to the biological problems: i) RNA structures comparison, ii) Genomes comparison and iii) Pattern matching in biological networks and their respective combinatorial objects: i) Arc-annotated sequences, ii) Permutations and Sequences and iii) Graphs. More precisely, The first part will be devoted to the Arc-Annotated Sequences that are used in RNA structure comparison. We will focus on five problems that we investigated: LAPCS, APS, MAPCS, EDIT and ALIGN. In the second part, we will consider the two main research area related to comparative genomics we were involved in: gene clusters detection and (dis)similarity measures computation -- which rely on permutation and string representations. Finally, we will present some results that were obtained mainly during the PhD of Florian Sikora that I co-supervised.

Notre thèse de doctorat s'intéresse à l'enseignement et l'apprentissage de savoirs informatiques chez des débutants en France. Elle vise à comprendre comment des débutants mettent en oeuvre et construisent des savoirs informatiques. Nous avons utilisé une méthodologie qualitative de type ethnographique mobilisant des observations, des questionnaires, des entretiens semi-directifs et des analyses de textes officiels et de manuels. Nous avons aussi précédé par une approche comparative des pratiques des lycéens et des étudiants d'une part, et des enseignants, d'autre part. Les résultats montrent des pratiques contrastées, entretenues par des tensions dans le prescrit. Au lycée, en dehors de la spécialité ISN, où l'informatique est rattachée aux mathématiques, les pratiques semblent influencées par quatre facteurs : la motivation (liée aux représentations), la formation continue des enseignants, la jeunesse dans le métier et l'approche pédagogique utilisée. La pratique est focalisée sur l'approche logique de l'algorithmique avec un travail au papier-crayon : la programmation est limitée, et lorsqu'elle a lieu, c'est plus avec une calculatrice mais aussi rarement avec le langage Algobox. Chez les élèves, l'algorithmique est vue comme un nouveau domaine supplémentaire introduit en mathématiques mais différent des mathématiques et de l'informatique. Les très bons élèves en algorithmique sont en général bons en mathématiques. L'ISN accueille des élèves de tous les profils, mais avec des motivations différentes, allant de la découverte de l'informatique dans un contexte formel au refuge des autres spécialités : leurs pratiques sont contrastées. C'est avec l'ISN qu'ils découvrent l'informatique au travers des formes d'enseignement variées et des problèmes de plus en plus complexes. Les pratiques des enseignants restent influencées par leur formation d'origine, avec un manque de recul chez les non-spécialistes d'informatique. À l'Université, les pratiques des étudiants en programmation sont avancées par rapport à celles des lycéens, une avance liée à la complémentarité des modules qui sont dispensés par des spécialistes. Les programmes informatiques ainsi réalisés sont souvent sophistiqués et incorporent des éléments issus de différentes sources externes. Les notions mathématiques investies par les étudiants sont souvent modestes. Si les lycéens et les étudiants sont tous débutants en informatique, les différences de pratiques entre eux semblent liées aux compétences spécifiques des enseignants. Au-delà de la formation des enseignants, la motivation occupe une place fondamentale pour adhérer à cet enseignement/apprentissage et soutenir des pratiques enseignantes comme chez les apprenants. / Our dissertation focuses on the teaching and learning of computer knowledge to beginners in France. It aims to understand how beginners implement and build computer knowledge. We used a qualitative methodology mobilizing ethnographic observations, questionnaire, semi-structured interviews and the analysis of official instructions and textbooks. We also conducted a comparative study of the practice of both school and university students, on the one hand, and teachers, on the other hand. Results show contrasting situations between secondary schools and university. In high school, algorithmic curricula exist within mathematic education. In this case, practice is influenced by four factors: motivation (related to representation), professional development for teachers, youth in business and pedagogical approach. The practice mainly focuses on a logical approach to algorithmic using work paper and pencil: programming is limited, and when it occurs, it is often with a calculator but rarely with the Algobox language. Among students, algorithms are perceived as a new domain in the mathematics programs, but different from both mathematics and informatics. Very good students in computing are generally good at math. Another elective course, specifically about informatics, has also been recently implemented for grade 12 students. It welcomes students of all profiles, but with different motivations, from the discovery of computers in a formal context to a shelter against other elective courses: their practices are manyfold. Within ISN, they discover computers through various forms of education and problems of increasing complexity. Teacher practice is influenced by their original education, with a lack of experience for non specialists teachers. At the University level, students show more advanced practice. They produce computer programs are often sophisticated and incorporate elements from various external sources. The mathematics knowledge invested by students is often modest. If students in lycée and university are all computer beginners, the differences in practice between them seem linked to the specific skills of teachers. In addition to teacher's training, motivation is fundamental to adhere to this teaching/learning and support practice, both for teachers and students.