• Refine Query
  • Source
  • Publication year
  • to
  • Language
  • 8
  • 2
  • 1
  • Tagged with
  • 15
  • 15
  • 5
  • 4
  • 4
  • 4
  • 3
  • 3
  • 3
  • 3
  • 3
  • 3
  • 3
  • 3
  • 2
  • About
  • The Global ETD Search service is a free service for researchers to find electronic theses and dissertations. This service is provided by the Networked Digital Library of Theses and Dissertations.
    Our metadata is collected from universities around the world. If you manage a university/consortium/country archive and want to be added, details can be found on the NDLTD website.
1

Dénombrement des polyominos F-convexes sur le réseau triangulaire et bijection entre polyominos F-convexes hexagonaux et triangulaires

Lachapelle, Luc January 2008 (has links) (PDF)
Les polyominos sur les réseaux carré et hexagonal ayant des propriétés de convexité ont été largement étudiés, et leurs classes de symétrie ont été dénombrées (par leurs séries génératrices selon divers paramètres: l'aire, le périmètre, la largeur, la hauteur, etc.). Les polyominos pouvant être considérés comme des objets dans l'espace, on les dénombre à translations, à rotations et à réflexions près. Un résultat classique de la théorie des groupes, le lemme de Burnside nous aidera à ce niveau. On s'intéresse donc au dénombrement des classes de polyominos convexes ayant des propriétés de symétries. Dans ce mémoire on s'intéresse aux polyominos sur le réseau triangulaire. Quelques travaux ont été faits sur ce réseau, notamment sur les polyominos parallélogrammes, les polyominos dirigés et les animaux. Ce mémoire porte entre autres sur le dénombrement des classes de symétrie des polyominos F-convexes (convexité forte) sur le réseau triangulaire. On présente aussi quelques résultats concernant les polyominos HV-convexes (l'équivalent des polyominos EG-convexes sur le réseau hexagonal, soit une convexité selon un axe horizontal et un axe vertical). Les formes de convexité vont êtres définies dans l'introduction. On introduira aussi une classe particulière de polyominos, soit les polyominos filiformes. Le premier chapitre porte sur le dénombrement des polyominos triangulaires F-convexes. On utilisera pour cela les méthodes de Fouad Hassani et de Mireille Bousquet-Mélou, qui ont fait leurs preuves sur le réseau hexagonal. On obtient ainsi des formes closes remarquables pour leurs séries génératrices selon plusieurs paramètres, dont la largeur, l'aire et le périmètre. Le deuxième chapitre porte sur les polyominos HV-convexes, dont on donne les équations fonctionnelles. Le troisième chapitre dénombre des polyominos convexes triangulaires particuliers, comme les polyominos partages, les polyominos tas et les polyominos parallélogrammes. Le quatrième chapitre dénombre les classes de symétries des polyominos F-convexes, soit leurs orbites. On fait aussi un rappel de quelques résultats de la théorie des groupes et de leur action, notamment sur les groupes diédraux D6 des isométries de l'hexagone et D2, sous-groupe de D4 des isométries du carré. En se basant sur la dualité des graphes plans, on présente dans le cinquième chapitre une bijection entre les polyominos C-convexes du réseau hexagonal et des structures "polyominomiales" sur le réseau triangulaire. Ces structures généralisent les polyominos triangulaires en admettant des parties filiformes tout en satisfaisant les conditions de C-convexité. De plus, nous donnons des formules simples de passage pour ce qui est des paramètres largeur, aire et périmètre selon cette bijection. On en déduit, par restriction, une bijection entre les polyominos F-convexes des réseaux hexagonal et triangulaire. Notons que tous les calculs sur les séries génératrices ont été faits sur le logiciel Maple. ______________________________________________________________________________ MOTS-CLÉS DE L’AUTEUR : Polyomino(s), Polyomino(s) convexe(s), Réseau triangulaire, Dénombrement.
2

Structures arborescentes et développements moléculaires

Ducharme, Martin January 2009 (has links) (PDF)
Le présent travail porte sur la classification de structures arborescentes selon leurs symétries. Plus précisément, il fait l'objet de celle des arbres plans, des 2-arbres k-gonaux exterplanaires, des 2-arbres k-gonaux sans sommets de degré 4 et des 2-arbres polygonaux exterplanaires. Ceci est fait en déterminant le développement moléculaire de ceux-ci vus comme espèces de structures. Le développement moléculaire des arbres plans est obtenu à l'aide du théorème de dissymétrie des arbres R-enrichis (voir Bergeron, Labelle et Leroux, 1994) et par l'utilisation d'une formule d'addition pour Ck(B) où B est une espèce et Ck est l'espèce des cycles orientés de longueur k. Cette formule se trouve dans (Ducharme, 2005). En généralisant cette formule au cas où B est pondérée, nous obtenons le développement moléculaire des arbres plans pondérés par la distribution des degrés de leurs sommets. En ce qui a trait aux 2-arbres k-gonaux exterplanaires, une telle classification pour k = 3 a été faite dans (Labelle, Lamathe et Leroux, 2003; Lamathe 2003) et pour k = 4,5 dans (Ducharme, 2005) en utilisant des formules d'addition d'espèces auxiliaires exprimant des espèces pointées qui, à l'aide d'un théorème de dissymétrie, peuvent exprimer les espèces des 2-arbres k-gonaux exterplanaires. Le seul résultat manquant dans (Ducharme, 2005), pour obtenir le développement moléculaire des 2-arbres k-gonaux exterplanaires, est celui des 2-arbres k-gonaux exterplanaires pointés en un polygone. Celui-ci est obtenu par l'énumération de classes diédrales de mots dont les lettres représentent chacune un type d'isomorphie de 2-arbres k-gonaux exterplanaires pointés en une arête orientée. C'est aussi par l'énumération de classes diédrales que nous obtenons une nouvelle formule d'addition de Pn donnant le développement moléculaire de Pn(B) en fonction de celui des puissances de l'espèce B où Pn est l'espèce des polygones de taille n (cycles non orientés de longueur n). Les espèces apparaissant dans cette formule sont de la forme Pbic 2i (N, M, L) ou Cj(K) où K, L, M et N sont des espèces moléculaires, i|k, j|k et Pbic 2i (X, Y, Z) est une espèce moléculaire de polygones bicolorés. Nous donnons également une condition pour déterminer si Pbic 2i (N₁, M₁, L₁) et Pbic 2j (N₂, M₂, L₂) sont isomorphes dans le cas où N₁, M₁, L₁, N₂, M₂ et L₂ sont des espèces asymétriques. Comme le développement moléculaire des différentes espèces pointées de 2-arbres k-gonaux exterplanaires ne font appel qu'à des espèces asymétriques et aux espèces Ci et Pbic 2i(X, Y, Z) dans lesquelles on a substitué des espèces asymétriques, on peut facilement regrouper les termes semblables pour obtenir le développement moléculaire des 2-arbres k-gonaux exterplanaires. Les coefficients de ce développement moléculaire sont exprimés en fonction de ceux des puissances entières de l'espèce des 2-arbres k-gonaux exterplanaires pointés en une arête orientée. Ces derniers coefficients sont obtenus par inversion de Lagrange. Pour le cas des 2-arbres k-gonaux sans sommets de degré 4, nous faisons une distinction entre les types dont le groupe d'isomorphismes d'ordre 2 est généré par une rotation non trivial et ceux dont le groupe est généré par une réfexion. Ceux-ci sont isomorphes à NE₂ (M) mais seront respectivement associés à l'espèce NC₂ (M) et à l'espèce Pbic 2 (N, M, 1). En plus, seules certaines classes diédrales de mots, dont les lettres représentent chacune un type d'isomorphie de 2-arbres k-gonaux sans sommets de degré 4 pointés en une arête externe orientée dont les sommets sont de degré 2, représentent un type de 2-arbres k-gonaux sans sommets de degré 4. Les coefficients du développement moléculaire des 2-arbres k-gonaux sans sommets de degré 4 sont ensuite exprimés en fonction des coefficients de celui de puissances d'espèces asymétriques obtenus encore par inversion de Lagrange. Le cas des 2-arbres polygonaux exterplanaires est très similaire au cas des 2-arbres k-gonaux exterplanaires où k est pair. L'étiquetage est effectué aux sommets plutôt qu'aux polygones, ce qui occasionne des changements mineurs aux définitions des classes diédrales à énumérer. Les espèces moléculaires de leur développement moléculaire peuvent encore être décrites à l'aide d'espèces asymétriques et de Ci et Pbic 2j (X, Y, Z) où i et j sont des entiers. ______________________________________________________________________________ MOTS-CLÉS DE L’AUTEUR : Arboresence, 2-arbres, Exterplanaire, Moléculaire, Développement.
3

Aspects combinatoires des polynômes de MacDonald

Rodríguez, Adolfo January 2008 (has links) (PDF)
La théorie sur les polynômes de Macdonald a fait l'objet d'une quantité importante de recherches au cours des dernières années. Définis originellement par Macdonald comme une généralisation de quelques-unes des bases les plus importantes de l'anneau des fonctions symétriques, ces polynômes ont des applications dans des domaines tels que la théorie des représentations des groupes quantiques et physique des particules. Ce travail présente quelques-uns des résultats combinatoires les plus importants entourant ces polynômes, en mettant particulièrement l'accent sur la formule combinatoire prouvée récemment par Haglund, Haiman et Loehr pour les polynômes de Macdonald. ______________________________________________________________________________ MOTS-CLÉS DE L’AUTEUR : Polynômes de Macdonald, Fonctions symétriques, Combinatoire algébrique, Combinatoire énumérative, Théorie des représentations, Géométrie algébrique.
4

Analyse des ressources mises à contribution par enseignant et chercheur dans l'élaboration de scénarios d'enseignement en dénombrement visant le développement de la modélisation en secondaire I

Barry, Souleymane January 2009 (has links) (PDF)
La combinatoire élémentaire ou le dénombrement évoque pour beaucoup d'élèves de nombreuses expériences négatives, lorsqu'elle est un objet explicite d'enseignement, l'accent étant souvent mis dans cet enseignement sur le recours à des formules de dénombrement que les élèves ne peuvent rattacher à des modèles de situations (Grenier et Payan, 1998). Dans cette recherche nous sommes intéressé à explorer des voies et moyens permettant d'associer des expériences plus positives à la résolution de problèmes combinatoires, et ce dès les premières années du secondaire. Un tel pari apparaît d'autant plus pertinent que plusieurs études soulignent d'une part non seulement des caractéristiques intéressantes des problèmes combinatoires, soit le fait qu'ils n'exigent presque aucun prérequis notionnel de la part des élèves (Kapur, 1970) et qu'ils sont très peu mathématisés (Grenier et Payan, 1998). Elles soulignent également les accomplissements des élèves qui sont capables, lorsque les situations qu'on leur propose sont bien choisies, de développer des heuristiques puissantes, d'inventer des méthodes de justification ou de validation (Maher, Martino et Alston, 1993; Powell et Maher, 2002). Les problèmes combinatoires apparaissent ainsi intéressants à travailler à différents niveaux d'enseignement et se prêtent au développement de plusieurs processus mathématiques tels la mathématisation, la preuve, le raisonnement inductif (Kapur, 1970; Dubois, 1984; Batanero, Godino et Navarro-Pelayo, 1994; Sriraman et English, 2004). C'est à l'un de ces processus, la modélisation que nous nous sommes plus particulièrement attardé, rejoignant en cela d'autres chercheurs comme Grenier et Payan (1998), mais aussi le nouveau programme de mathématiques du premier cycle du secondaire de l'école québécoise (MELS, 2003) dans lequel la modélisation est associée à la compétence à résoudre des situations-problèmes. Dans la perspective théorique particulière que nous retenons sur la modélisation, celle d'une « modélisation émergente » (Gravemeijer, 2007), l'accent est mis sur l'activité informelle des élèves à qui il faut donner l'opportunité de créer des « modèles spontanés » et par la suite de les revisiter, les raffiner et au besoin de les généraliser (Gravemeijer, 1999). L'élaboration d'une approche d'enseignement mettant l'accent sur l'exploitation de problèmes de dénombrement et le développement du processus de modélisation exige toutefois que le chercheur se donne également une perspective particulière pour aborder la conceptualisation de ces scénarios d'enseignement. Plusieurs recherches ont contribué à développer des situations et séquences sur l'exploration de la combinatoire. Dans ce cas, les séquences ont pour l'essentiel été élaborées par les chercheurs, à partir d'analyses didactiques préalables, et ce, pour les apprentissages potentiels qu'elles favorisent chez les élèves (Glaymann et Varga, 1975; Fischbein et Gazit, 1988; Batanero, Godino et Navarro-Pelayo, 1994). Bien sûr, dans le cas de ces différents travaux portant sur la combinatoire et son exploitation, des expérimentations ont été réalisées en classe auprès d'élèves, et des enseignants ont souvent été impliqués dans l'implantation de ces situations. Toutefois, le rôle qu'y jouent ces enseignants demeure limité à ces expérimentations. Leurs visions quant à la manière dont un tel sujet peut se développer et fonctionner en pratique, leurs connaissances, leur savoir d'expérience n'est pas vraiment pris en compte dans la conceptualisation des situations élaborées, qui demeurent donc ici sous l'entière responsabilité des chercheurs. La perspective adoptée par les chercheurs dans ce cas, vis-à-vis de l'enseignant, s'inscrit dans le courant plus global de la recherche en didactique des mathématiques au plan international dans les années 1990 (Hoyles, 1992; Ponte, 1994; Jaworski, sous presse). Cette prise en compte de l'enseignant, de la complexité du travail auquel il fait face dans la pratique, des connaissances qu'il construit -en pratique, est en effet un phénomène relativement récent (Jaworski, sous presse). C'est dans cette dernière perspective que se place notre travail. Pour construire des situations fécondes sur le plan des apprentissages des élèves, mais aussi viables dans les pratiques des enseignants, tenant compte des contraintes et de la complexité de leur pratique, il nous apparaît en effet nécessaire de prendre en compte le point de vue des enseignants, leur savoir d'expérience, leurs connaissances dans la construction même de scénarios visant le développement du processus de modélisation. Nous avons cherché à documenter, de l'intérieur d'une démarche conjointe d'élaboration d'un tel scénario, les apports respectifs du chercheur et de l'enseignant sous l'angle: des problèmes de dénombrement élaborés; du processus de modélisation développé par les élèves en lien avec ces problèmes et leur exploitation; de l'enseignement visant le développement de ce processus. Une recherche collaborative a été menée à cette fin, impliquant le chercheur et un enseignant de mathématique au secondaire qui ont eu à élaborer et expérimenter dans deux classes de secondaire 1 d'une école de la région de Montréal deux scénarios, un premier en novembre 2006 et un second en mai 2007. La démarche de recherche a pris la forme de rencontres réflexives d'élaboration des scénarios et de retour sur les scénarios expérimentés (le dialogue initié lors de ces rencontres se poursuivant sous une forme virtuelle). Le matériau engrangé puis analysé est donc constitué principalement des verbatims des rencontres réflexives de construction des scénarios et de retour sur les scénarios (bilans et récits d'expérimentation). Une analyse par théorisation ancrée (Glaser et Strauss, 1967) nous a permis de dégager de multiples ressources mobilisées par l'enseignant et le chercheur, nous édifiant ainsi sur leur éclairage respectif sur : les problèmes de dénombrement en jeu, le processus de modélisation par les élèves et l'enseignement visant le développement de ce processus. Ces ressources sont de deux sortes: des ressources interprétatives, c'est-à-dire permettant de donner un sens, de proposer une certaine lecture des aspects abordés dans ce travail conjoint d'élaboration de scénarios, et des ressources d'action, c'est-à-dire des ressources prenant la forme de suggestions de manières de faire, de propositions d'aménagement ou d'animation. Ces ressources, interprétatives et d'action, puisent aux cadres de référence du chercheur et de l'enseignant, mais elles montrent une certaine sensibilité théorique et une capacité d'interprétation. Selon le cas, la lecture interprétative de l'enseignant confirme, réfute, nuance ou étend celle du chercheur qui, au demeurant, témoigne d'une certaine sensibilité pratique, sensibilités théorique et pratique n'étant en définitive l'apanage ni de l'un ni de l'autre. Notre étude permet donc d'élargir la notion de ressources interprétatives telle que l'envisage la sociologie de l'expérience qui la définit surtout en termes de ressources argumentatives et critiques permettant aux acteurs de prendre position par rapport aux élaborations, théories proposées par les chercheurs (Dubet, 1994). Dans une telle perspective, le croisement est vu de façon dichotomique, en termes uniquement des accords et des désaccords entre les acteurs et les chercheurs. Entre les deux, l'accord et la réfutation, avons-nous montré, il y a l'espace d'une nuance, d'une extension. Enfin, dans l'optique du développement du processus de modélisation en début secondaire, l'analyse nous a permis de mettre en évidence des caractéristiques que l'on gagnerait à retrouver dans des problèmes combinatoires, d'identifier des routines d'appui et d'échanges à installer puis à maintenir dans la classe et ce pour installer une culture de modélisation (Tanner et Jones, 1994). Ce travail sur la modélisation s'inscrlt dans une pragmatique de la résolution de problèmes questionnant à la fois la prépondérance dans l'enseignement des problèmes d'application et la recherche à tout prix de l'efficacité chez les élèves. ______________________________________________________________________________ MOTS-CLÉS DE L’AUTEUR : Ressources, Interprétation, Action, Développement, Modélisation.
5

Combinatoire des configurations de boucles compactes

Duchon, Philippe 20 November 2008 (has links) (PDF)
On s'intéresse dans ce mémoire à la riche combinatoire des configurations de boucles compacte (ou FPL, ou matrices à signes alternants, ou orientations eulériennes d'une grille). Sont en particulier abordées les questions d'énumération et les liens avec l'énumération de partitions planes, les conjectures à la Razumov et Stroganov, et la génération aléatoire exactement uniforme de configurations satisfaisant des conditions arbitraires de symétrie.
6

Physique statistique des surfaces aléatoires et combinatoire bijective des cartes planaires

Bouttier, Jérémie 10 June 2005 (has links) (PDF)
Les cartes sont des objets combinatoires apparaissant en physique comme discrétisation naturelle des surfaces aléatoires employées pour la gravité quantique bidimensionnelle ou la théorie des cordes, ainsi que dans les modèles de matrices. Après rappel de ces relations, nous établissons des correspondances entre diverses classes de cartes et d'arbres, autres objets combinatoires de structure simple. Un premier intérêt mathématique de ces constructions est de donner des preuves bijectives, élémentaires et rigoureuses, de plusieurs résultats d'énumération de cartes. Par ailleurs, nous accédons ainsi à une information fine sur la géométrie intrinsèque des cartes, conduisant à des résultats analytiques exacts grâce à une propriété inattendue d'intégrabilité. Nous abordons enfin la question de l'existence d'une limite continue universelle.
7

Combinatoire des espaces coinvariants trivariés du groupe symétrique

Préville-Ratelle, Louis-François 09 1900 (has links) (PDF)
Ce travail traite principalement de l'énumération d'extensions de structures combinatoires classiques appelées chemins de Dyck et fonctions de stationnement. Ces structures, très étudiées en raison de leur rôle fondamental dans de multiples contextes combinatoires, sont aussi étroitement liées à la théorie de la représentation, à la théorie des fonctions symétriques et à la géométrie algébrique, entre autres. En particulier, elles sont liées à l'étude combinatoire des espaces coinvariants diagonaux DRk,n, introduits par Garsia et Haiman, qui sont des représentations du groupe symétrique Gn sur des espaces de polynômes en k jeux de n variables. Dans le cas bivarié, il a été conjecturé que les séries de Hilbert des espaces coinvariants diagonaux « augmentés » DRm2,n et de leur sous-représentation signe DRm2,nɛ sont respectivement égales à une somme de statistiques sur les fonctions de m-stationnement et sur les chemins de m-Dyck. Il existe également une conjecture plus générale pour la série de Frobenius de ces espaces qui s'appelle la conjecture « shuffle » (Haglund et al., 2005). Dans le cas trivarié, Haiman a conjecturé en 1994 les dimensions suivantes : dim(DR3,nɛ) = 2/n(n+1) (4n+1 n-1) et dim(DR3,n) = 2n (n+1)n-2. D'autre part, en 2006, Chapoton a démontré que les intervalles dans le treillis de Tamari sont comptés par 2/n(n+1) (4n+1 n-1). Motivé par ses travaux sur le cas trivarié et par les deux conjectures précédentes, Bergeron a introduit le treillis de m-Tamari et étendu certaines questions concernant les chemins de m-Dyck et les fonctions de m-stationnement pour rendre compte du cas trivarié. Il a conjecturé que : dim(DRm3,nɛ) = m+1/n(mn+1) ((m+1)2n+m n-1), que : dim(DRm3,n) = (m+1)n(mn+1)n-2, et que ces deux cardinalités comptent respectivement les intervalles et les intervalles de stationnement du treillis de m-Tamari. Dans cette thèse, nous démontrons une généralisation commune de ces deux conjectures énumératives que nous avons énoncée avec Bergeron. Plus précisément, avec Mireille Bousquet-Mélou et Guillaume Chapuy, nous avons démontré que la série de Frobenius d'une certaine représentation combinatoire sur les intervalles de stationnement du treillis de m-Tamari est donnée par : Ʃ λ=(λ1,…,λl)˫n (mn+1)l-2 II 1≤i≤l ((m+1)λi λi) Pλ/Zλ. Cette démonstration équivaut à résoudre un nouveau type d'équations différentielles à variable catalytique. Toujours avec Bergeron, nous avons conjecturé que le produit tensoriel de cette représentation combinatoire et de la représentation signe ɛ est isomorphe à DRm3,n. Nous avons également formulé une généralisation de la conjecture « shuffle » en proposant une formule combinatoire explicite pour la série de Frobenius graduée de DRm3,n. Ceci renforce notre hypothèse que l'étude des intervalles du treillis de m-Tamari est bel et bien en lien avec l'étude des espaces DRm3,n. ______________________________________________________________________________ MOTS-CLÉS DE L’AUTEUR : combinatoire algébrique, combinatoire énumérative, représentations du groupe symétrique, fonctions génératrices, statistiques.
8

Chemins et animaux : applications de la théorie des empilements de pièces

Bacher, Axel 28 October 2011 (has links)
Le but de cette thèse est d'établir des résultats énumératifs sur certaines classes de chemins et d'animaux. Ces résultats sont obtenus en appliquant la théorie des empilements de pièces développée par Viennot. Nous étudions les excursions discrètes (ou chemins de Dyck généralisés) de hauteur bornée; nous obtenons des résultats énumératifs qui interprètent combinatoirement et étendent des résultats de Banderier, Flajolet et Bousquet-Mélou. Nous décrivons et énumérons plusieurs classes de chemins auto-évitants, dits chemins faiblement dirigés. Ces chemins sont plus nombreux que les chemins prudents qui forment la classe naturelle la plus grande jusqu'alors. Nous calculons le périmètre de site moyen des animaux dirigés, prouvant des conjectures de Conway et Le Borgne. Enfin, nous obtenons des résultats nouveaux sur l'énumération des animaux de Klarner et les animaux multi-dirigés de Bousquet-Mélou et Rechnitzer. / The goal of this thesis is to prove enumerative results on some classes of lattice walks and animals. These results are applications of the theory of heaps of pieces developed by Viennot. We study discrete excursions (or generalized Dyck paths) with bounded height; we obtain enumerative results that give a combinatorial interpretation and extend results by Banderier, Flajolet and Bousquet-Mélou. We describe and enumerate several classes of self-avoiding walks called weakly directed walks. These classes are larger than the class of prudent walks, the largest natural class enumerated so far. We compute the average site perimeter of directed animals, proving conjectures by Conway and Le Borgne. Finally, we obtain new results on the enumeration of Klarner animals and multi-directed animals defined by Bousquet-Mélou and Rechnitzer.
9

Modélisation de séquences génomiques structurées, génération aléatoire et applications

Ponty, Yann 29 November 2006 (has links) (PDF)
La mise en évidence des mécanismes de sélection agissant sur les données génomiques structurées (ARN, Protéines, ADN...) nécessite l'élaboration de modèles de séquences. Une fois un tel modèle élaboré, il est possible, au prix d'une analyse mathématique parfois complexe ou par le biais de la<br />génération aléatoire, d'évaluer la significativité d'un phénomène observé. Tout d'abord, nous nous intéressons aux propriétés des grammaires pondérées, un formalisme particulièrement adapté à la modélisation de la structure des ARN, dérivant des algorithmes de génération aléatoire efficaces implémentés au sein du prototype GenRGenS. Nous abordons le calcul automatique des pondérations réalisant des valeurs observées pour les paramètres du modèle, ainsi qu'une implémentation basée sur une approche optimisation. Dans un second temps, nous abordons la modélisation de la structure secondaire d'ARN. Après quelques rappels de biologie moléculaire, nous proposons plusieurs modèles basés sur des grammaires pondérées permettant la génération de structures d'ARN réalistes. L'utilisation d'un algorithme d'optimisation permet le calculer des pondérations correspondant à certaines familles d'ARN. Nous proposons enfin un algorithme d'extraction de structure secondaire maximale dans une structure générale, qui permet de profiter des données récentes issues de la cristallographie. Le dernier chapitre de cette thèse s'intéresse à l'analyse d'un algorithme de recherche de similarité heuristique, dont la sensibilité s'avère étroitement liée à la probabilité de présence d'un motif au sein de marches aléatoires particulières, les chemins culminants. Ces marches restent positives, et atteignent une altitude maximale en leur dernier pas. Nous proposons un algorithme récursif de génération aléatoire pour ces chemins. En combinant des techniques issues de la combinatoire énumérative, l'analyse asymptotique et la théorie des langages, nous dérivons des algorithmes de génération aléatoire par rejet linéaires dans de nombreux cas.
10

Combinatoire du polynôme de Tutte et des cartes planaires / Combinatorics of the Tutte polynomial and planar maps

Courtiel, Julien 03 October 2014 (has links)
Cette thèse porte sur le polynôme de Tutte, étudié selon différents points de vue. Dans une première partie, nous nous intéressons à l’énumération des cartes planaires munies d’une forêt couvrante, ici appelées cartes forestières, avec un poids z par face et un poids u par composante non racine de la forêt. De manière équivalente, nous comptons selon le nombre de faces les cartes planaires C pondérées par TC(u + 1; 1), où TC désigne le polynôme de Tutte de C. Nous commençons par une caractérisation purement combinatoire de la série génératrice correspondante, notée F(z; u). Nous en déduisons que F(z; u) est différentiellement algébrique en z, c’est-à-dire que F satisfait une équation différentielle polynomiale selon z. Enfin, pour u ≥ -1, nous étudions le comportement asymptotique du n-ième coefficient de F(z; u). Nous observons une transition de phase en 0, avec notamment un régime très atypique en n-3 ln-2(n) pour u ϵ [-1; 0[, témoignant d’une nouvelle classe d’universalité pour les cartes planaires. Dans une seconde partie, nous proposons un cadre unificateur pour les différentes notions d’activités utilisées dans la littérature pour décrire le polynôme de Tutte.La nouvelle notion d’activité ainsi définie est appelée Δ-activité. Elle regroupe toutes les notions d’activité déjà connues et présente de belles propriétés, comme celle de Crapo qui définit une partition (adaptée à l’activité) du treillis des sous-graphes couvrants en intervalles. Nous conjecturons en dernier lieu que toute activité qui décrit le polynôme de Tutte et qui satisfait la propriété susmentionnée de Crapo peut être définie en termes de Δ-activités. / This thesis deals with the Tutte polynomial, studied from different points of view. In the first part, we address the enumeration of planar maps equipped with a spanning forest, here called forested maps, with a weight z per face and a weight u per non-root component of the forest. Equivalently, we count (with respect to the number of faces) the planar maps C weighted by TC(u + 1; 1), where TC is the Tutte polynomial of C.We begin by a purely combinatorial characterization of the corresponding generating function, denoted by F(z; u). We deduce from this that F(z; u) is differentially algebraic in z, that is, satisfies a polynomial differential equation in z. Finally, for u ≥ -1, we study the asymptotic behaviour of the nth coefficient of F(z; u).We observe a phase transition at 0, with a very unusual regime in n-3 ln-2(n) for u ϵ [-1; 0[, which testifiesa new universality class for planar maps. In the second part, we propose a framework unifying the notions of activity used in the literature to describe the Tutte polynomial. The new notion of activity thereby defined is called Δ-activity. It gathers all the notions of activities that were already known and has nice properties, as Crapo’s property that defines a partition of the lattice of the spanning subgraphs into intervals with respect to the activity. Lastly we conjecture that every activity that describes the Tutte polynomial and that satisfies Crapo’s property can be defined in terms of Δ-activity.

Page generated in 0.4757 seconds