L'etude et la comprehension de phenomenes naturels qu'il<br />semble difficile de predire, tels les<br />tremblements de terre et les raz de maree intriguent depuis quelques<br />temps un certain nombre de physiciens. En effet, il semble que les<br />modeles classiques bases sur des fonctions d'etat continues<br />peuvent difficilement expliquer les phenomenes observes.<br /><br />En 1987, Bak, Tang et Wiesenfeld introduisent un modele base<br /> sur un automate particulier dont l'etude experimentale montre<br /> des caracteristiques proches de celles observees pour des<br /> tremblements de terre. Cet automate est appele automate du tas de sable.<br /><br /> En 1990, Dhar, Ruelle, Sen et<br />Verma etudient les proprietes mathematiques<br />de l'automate du tas de sable. Cet article jette les bases d'une théorie algebrique et combinatoire des<br />etats critiques du systeme en montrant que ceux-ci forment un<br />groupe abelien fini.<br /><br />Cette these porte essentiellement sur l'etude de ce groupe d'un<br />point de vue algorithmique, combinatoire et algebrique. Nous<br />etudions dans un premier temps la complexite de l'operateur de<br />groupe. Puis nous etudions le groupe sur quelques familles de<br />graphes connues avant de montrer que le groupe d'un graphe planaire<br />est isomorphe au groupe de chacun de ses duaux geometriques.<br /><br />Nous montrons comment associer à un groupe abelien fini un<br />idéal de polynomes et dans le cas du groupe du Tas de Sable, nous<br />donnerons une caracterisation de l'operateur de groupe en terme de<br />reduction de polynome.

Cette thèse traite de phénomènes de seuils et de modèles d'urnes, en adoptant le point de vue de la combinatoire analytique. On traite ici trois problèmes qui illustrent cette approche: la transition de phase du problème k-sat, les modèles d'urnes triangulaires de Polya-Eggenberger et le modèle de duel de Ok Corral. La transition de phase du problème k-sat se manifeste par le fait la densité d'une formule caractérise de manière presque sûre sa satisfaisabilité. Nos travaux visent à mettre en évidence une partie de ce phénomène et se relient à un modèle d'urne à jets. Le modèle d'urne de Polya-Eggenberger utilise une urne contenant des boules de diverses couleurs, soumises à des règles de pioches et de substitutions. En utilisant une technique de Flajolet-Gabarro-Pekari, nous déterminons la distribution limite de la composition des modèles dits triangulaires. Le modèle de duel de Ok Corral intervient dans une problématique plus générale de Lanchester de gestion des conflits, selon laquelle on cherche à prédire l'issue de duels entre plusieurs forces armées, en environnement aléatoire. Nous utilisons un lien pré-établi entre ce modèle et une urne de type Polya-Eggenberger pour donner de nouvelles expressions des probabilités du modèle et raffiner les résultats récents de Kingman.

L'objet de cette thèse est l'étude des liens existant entre la combinatoire de l'écriture d'un nombre réel en base entière ou sous la forme d'une fraction continue et le caractère algébrique ou transcendant de ce nombre réel (une conjecture de Borel prévoit que tout irrationnel algébrique est un nombre absolument normal: ses écritures en bases entières ont la même propriété que celle d'une suite aléatoire de chiffres).

Ce travail porte sur les séries à coefficients entiers positifs, sur les séries N-rationnelles et est centré autour de deux types de questions : le problème de la hauteur d'étoile et l'étude des propriétés des distributions de longueurs des codes. On étudie le problème de la hauteur d'étoile de séries rationnelles particulières : les séries N-rationnelles en une variable. On caractérise de différentes façons les séries N-rationnelles qui sont de hauteur d'étoile 1, et on donne un critère permettant de décider de la hauteur d'étoile d'une classe importante de séries N-rationnelles en une variable. L'étude de la hauteur d'étoile des séries N-rationnelles en une variable repose sur l'utilisation des propriétés de leurs représentations par des matrices. On établit, en particulier, à partir d'un résultat d'Handelman, une caractérisation du rayon spectral d'une matrice compagnon irréductible à coefficients entiers positifs. On étudie, ensuite, les distributions de longueurs des codes circulaires et des codes préfixes. On prouve trois nouveaux résultats concernant les codes circulaires. On généralise, dans plusieurs directions, la caractérisation des distributions de longueurs des codes circulaires établie dans le cas d'un alphabet fini par Schützenberger. D'une part, on remplace l'alphabet fini par un alphabet quelconque dont les éléments ont des poids, ce qui permet d'étendre le résultat à deux distributions de longueurs. D'autre part, on restreint les conditions, ce qui permet d'établir la décidabilité dans le cas d'une distribution finie. On donne une nouvelle formulation de cette caractérisation. Ce résultat, établi par des méthodes combinatoires, met en évidence la décidabilité dans le cas d'une distribution finie. On établit une condition nécessaire et suffisante pour qu'une suite d'entiers positifs soit la distribution de longueur d'un code circulaire maximal sur un alphabet fini. Enfin, on met en évidence les liens entre les séries génératrices des codes préfixes rationnels et une classe de séries N-rationnelles : les DOL-séries. On donne une condition suffisante pour qu'une suite N-rationnelle soit la distribution de longueurs d'un code rationnel préfixe maximal sur un alphabet à k lettres.

Ces travaux s'inscrivent dans le cadre général de la théorie des automates, de la combinatoire des mots, de la combinatoire énumérative et de l'algorithmique. Ils ont en commun de traiter des automates et des langages réguliers, de problèmes d'énumération et de présenter des résultats constructifs, souvent explicitement sous forme d'algorithmes. Les domaines dont sont issus les problèmes abordés sont assez variés. Ce texte est compose de trois parties consacrées aux codes préfixes, à certaines séquences lexicographiques et à l'énumération d'automates.

Dans cette thèse, nous présentons les relations entre le principe de réflexion MRP introduit par Moore, les propriétés d'arbres généralisées ITP et ISP introduites par Weiß, ainsi que les propriétés square introduites par Jensen et développées par Schimmerling. Le résultat principal de cette thèse est que MRP+MA entraine ITP(λ, ω2) pour tout cardinal λ ≥ ω2. Ce résultat implique par conséquent que les méthodes actuelles pour prouver la consistance de MRP+MA nécessitent au moins l'existence d'un cardinal supercompact. Il s'avère que MRP seul ne suffit pas à démontrer ce résultat, et nous donnons la démonstration que MRP n'entraine pas la propriété d'arbre plus faible, à savoir TP(ω2, ω2). De plus MRP+MA n'entraine pas le principe d'arbre plus fort ISP(ω2, ω2). Enfin nous étudions les relations entre MRP et des versions faibles de square. Nous montrons que MRP implique la négation de square(λ, ω) et MRP+MA implique la négation de square(λ, ω1) pour tout λ ≥ ω2.

Nous présentons différents résultats liés par les outils et les structures qu'ils font intervenir (intégrales itérées, produits de mélange). Dans la première partie, nous considérons le calcul de certaines intégrales de type Selberg et leurs limites lorsque le nombre de variables tend vers l'infini. Dans le cas général, on montre que le résultat s'exprime comme un produit dont le nombre de facteurs ne dépend pas du nombre de variables (sous certaines conditions). Si la puissance du déterminant de Vandermonde vaut 2, il est possible de calculer la limite de ces intégrales lorsque le nombre de variables tend vers l'infini à l'aide d'opérateurs liés à l'interpolation de Newton. Dans la seconde partie, nous étudions les propriétés de dépendance linéaire de familles de fonctions obtenues par intégrales itérées et donnons un critère qui permet d'assurer l'indépendance linéaire d'une famille infinie de fonctions à partir de l'étude des relations entre les fonctions obtenues par intégrales simples. Nous montrons comment construire effectivement les corps de germes de fonctions analytiques nécessaires et en donnons quelques exemples qui permettent d'étendre les résultats connus sur les hyperlogarithmes. Ensuite, nous étudions certaines bases de l'algèbre libre dans le but d'appliquer la factorisation de Schützenberger. Nous rappelons quelques résultats classiques, puis nous intéressons à la famille obtenue à partir des mots de Lyndon. Celle-ci ne permet pas d'écrire la factorisation qui nous intéresse mais nous précisons les caractéristiques de sa famille duale. Enfin, nous donnons un critère relatif à deux familles en dualité assurant que l'on peut écrire cette factorisation.

Cette thèse présente l'ensemble des concepts mathématiques et de Génie Logiciel ayant servi à la réalisation d'un cahier de brouillon interactif pour la théorie des graphes : Cabri-graphes.

Le dual topologique de l'espace des séries en un nombre quelconque, éventuellement infini, de variables non commutatives avec un corps topologique séparé de coefficients, pour la topologie produit, n'est autre que l'espace des polynômes. Il en résulte de façon immédiate que les endomorphismes continus sur les séries sont exactement les matrices infinies mais finies en ligne. Les matrices triangulaires infinies, puisque formant une algèbre de Fréchet, disposent quant à elles d'un calcul intégral et différentiel, que nous développons dans un cadre assez général, et qui permet d'établir une correspondance exponentielle-logarithme de type Lie. Nous déployons ces outils sur l'algèbre de Weyl (à deux générateurs) réalisée fidèlement comme une algèbre d'opérateurs agissant continûment sur l'espace des séries formelles (en une variable). Puis nous démontrons que chaque endomorphisme d'un espace vectoriel de dimension infinie dénombrable peut s'obtenir explicitement sous la forme de la somme d'une famille sommable en des opérateurs plus élémentaires, les opérateurs d'échelle (généralisation de l'algèbre de Weyl), précisant de la sorte le théorème de densité de Jacobson. Par dualité (topologique) un résultat similaire concernant les opérateurs continus sur un espace de combinaisons linéaires infinies tombent presque gratuitement. Par ailleurs nous développons la notion d'algèbre (contractée) large d'un monoïde à zéro (obtenue par complétion de l'algèbre contractée) qui nous permet de calculer de nouvelles formules d'inversion de Möbius ainsi que des séries de Hilbert.

Nous étudions des aspects combinatoires et algorithmiques relatifs aux codes identifiants dans les graphes. Un code identifiant est un ensemble de sommets d'un graphe tel que, d'une part, chaque sommet hors du code a un voisin dans le code et, d'autre part, tous les sommets ont un voisinage distinct à l'intérieur du code. Nous caractérisons tout d'abord les graphes orientés et non-orientés atteignant les bornes supérieures connues pour la taille minimum d'un code identifiant. Nous donnons également de nouveaux majorants et minorants sur ce paramètre pour les graphes de degré maximum donné, les graphes de maille au moins 5, les graphes d'intervalles et les graphes adjoints. Nous étudions ensuite la complexité algorithmique des problèmes de décision et d'optimisation associés à la notion de code identifiant. Nous montrons que ces problèmes restent algorithmiquement difficiles, même quand on les restreint aux graphes bipartis, co-bipartis, split, d'intervalles ou adjoints. Enfin, nous donnons un algorithme PTAS pour les graphes d'intervalles unitaires.