Une coloration propre d'un graphe est une fonction qui attribue une couleur à chaque sommet du graphe avec la restriction que 2 sommets voisins ont des couleurs distinctes. Les colorations propres permettent de modéliser des problèmes d'ordonnancement, d'allocation de fréquences ou de registres. Le problème de trouver une coloration propre d'un graphe qui minimise le nombre de couleurs est un problème NP-difficile très connu. Dans cette thèse, nous étudions le nombre de Grundy et le nombre b-chromatique des graphes, deux paramètres qui permettent d'évaluer quelques heuristiques pour le problème de la coloration propre. Nous commençons par dresser un état de l'art des résultats sur ces deux paramètres. Puis, nous montrons que déterminer le nombre de Grundy est NP-difficile sur les graphes bipartis ou cordaux mais polynomial sur le graphes sans P5 bipartis. Ensuite, nous montrons que déterminer le nombre b-chromatique est NP-difficile pour un graphe cordal et distance-héréditaire, et nous donnons des algorithmes polynomiaux pour certaines sous-classes de graphes blocs, complémentaires des graphes bipartis et P4-sparses. Nous considérons également la complexité à paramètre fixé de déterminer le nombre de Grundy (resp. nombre b-chromatique) et en particulier, nous montrons que décider si le nombre de Grundy (ou le nombre b-chromatique) d'un graphe G est au moins |V(G)| - k admet un algorithme FPT lorsque k est le paramètre. Enfin, nous considérons la complexité de nombreux problèmes liés à la comparaison du nombre de Grundy et nombre b-chromatique avec divers autres paramètres d'un graphe.

Cette thèse s'est attachée à répondre à trois problématiques principales. La première est une enquête historiographique sur le bocage, l'habitat et le parcellaire médiéval et les paysages vendéens afin d'identifier les impasses et les voies de rénovation possibles des discours scientifiques. La seconde est une analyse archéogéographique des formes planimétriques (la voirie, le parcellaire, l'habitat en réseau), à plusieurs échelles d'espace et de temps, contenues dans une fenêtre de 800 km² dans le sud de la Vendée (85). Il s'est agit de comprendre leur organisation, leur mise en place et leur transmission sur une échelle de temps long et selon le paradigme de la dynamique et de la complexité des processus. Enfin, le dernier axe de recherche a consisté en une réflexion sur les liens entre les différentes connaissances sur le parcellaire, la voirie, le peuplement depuis la Protohistoire jusqu'à nos jours afin de proposer une piste de renouvellement du récit géohistorique traditionnel.

Cette thèse se situe à l'interface de trois grands domaines : la combinatoire des mots, la théorie des automates et la théorie des nombres. Plus précisément, nous montrons comment des outils provenant de la combinatoire des mots et de la théorie des automates interviennent dans l'étude de problèmes arithmétiques concernant les séries formelles à coefficients dans un corps fini.Le point de départ de cette thèse est un célèbre théorème de Christol qui caractérise les séries de Laurent algébriques sur le corps F_q(T), l'entier q désignant une puissance d'un nombre premier p, en termes d'automates finis et dont l'énoncé est : " Une série de Laurent à coefficients dans le corps fini F_q est algébrique si et seulement si la suite de ses coefficients est engendrée par un p-automate fini ". Ce résultat, qui révèle dans un certain sens la simplicité de ces séries de Laurent, a donné naissance à des travaux importants parmi lesquels de nombreuses applications et généralisations.L'objet principal de cette thèse est, dans un premier temps, d'exploiter la simplicité de séries de Laurent algébriques à coefficients dans un corps fini afin d'obtenir des résultats diophantiens, puis d'essayer d'étendre cette étude à des fonctions transcendantes arithmétiquement intéressantes. Nous nous concentrons tout d'abord sur une classe de séries de Laurent algébriques particulières qui généralisent la fameuse cubique de Baum et Sweet. Le résultat principal obtenu pour ces dernières est une description explicite de leur développement en fraction continue, généralisant ainsi certains travaux de Mills et Robbins. Rappelons que le développement en fraction continue permet généralement d'obtenir des informations très précises sur l'approximation rationnelle ; les meilleures approximations étant obtenues directement à partir de la suite des quotients partiels. Malheureusement, il est souvent très difficile d'obtenir le développement en fraction continue d'une série de Laurent algébrique, que celle-ci soit donné par une équation algébrique ou par son développement en série de Laurent. La deuxième étude que nous présentons dans cette thèse fournit une information diophantienne à priori moins précise que la description du développement en fraction continue, mais qui a le mérite de concerner toutes les séries de Laurent algébriques (à coefficients dans un corps fini). L'idée principale est d'utiliser l'automaticité de la suite des coefficients de ces séries de Laurent afin d'obtenir une borne générale pour leur exposant d'irrationalité. Malgré la généralité de ce résultat, la borne obtenue n'est pas toujours satisfaisante. Dans certains cas, elle peut s'avérer plus mauvaise que celle provenant de l'inégalité de Mahler. Cependant, dans de nombreuses situations, il est possible d'utiliser notre approche pour fournir, au mieux, la valeur exacte de l'exposant d'irrationalité, sinon des encadrements très précis de ce dernier.Dans un dernier travail nous nous plaçons dans un cadre plus général que celui des séries de Laurent algébriques, à savoir celui des séries de Laurent dont la suite des coefficients a une " basse complexité ". Nous montrons que cet ensemble englobe quelques fonctions remarquables, comme les séries algébriques et l'inverse de l'analogue du nombre \pi dans le module de Carlitz. Il possède, par ailleurs, des propriétés de stabilité intéressantes : entre autres, il s'agit d'un espace vectoriel sur le corps des fractions rationnelles à coefficients dans un corps fini (ce qui, d'un point de vue arithmétique, fournit un critère d'indépendance linéaire), il est de plus laissé invariant par diverses opérations classiques comme le produit de Hadamard

La géométrie algorithmique a pour but de concevoir et d'analyser des algorithmes pour résoudre des problèmes géométriques. C'est un domaine récent de l'informatique théorique, qui s'est très rapidement développé depuis son apparition dans la thèse de M. I. Shamos en 1978. La randomisation permet d'éviter le recours à des structures compliquées, et s'avère très efficace, tant du point de vue de la complexité théorique, que des résultats pratiques. Nous nous sommes intéressés plus particulièrement à la conception d'algorithmes dynamiques : en pratique, il est fréquent que l'acquisition des données d'un problème soit progressive. Il n'est évidemment pas question de recalculer le résultat à chaque nouvelle donnée, d'où la nécéssité d'utiliser des schémas (semi-)dynamiques. Nous introduisons une structure très générale, le graphe d'influence, qui permet de construire de nombreuses structures géométriques : diagrammes de Voronoï, arrangements de segments... Nous étudions les algorithmes, à la fois du point de vue de la complexité théorique, de leur mise en oeuvre pratique et de l'efficacité des programmes.

Les séquences de jeux sont une méthodologie établie pour structurer les preuves cryptographiques. De telles preuves peuvent être formalisées rigoureusement en regardant les jeux comme des programmes probabilistes et en utilisant des méthodes de vérification de programmes. Cette thèse décrit CertiCrypt, un outil permettant la construction et vérification automatique de preuves basées sur les jeux. CertiCrypt est implémenté dans l'assistant à la preuve Coq, et repose sur de nombreux domaines, en particulier les probabilités, la complexité, l'algèbre, et la sémantique des langages de programmation. CertiCrypt fournit des outils certifiés pour raisonner sur l'équivalence de programmes probabilistes, en particulier une logique de Hoare relationnelle, une théorie équationnelle pour l'équivalence observationnelle, une bibliothèque de transformations de programme, et des techniques propres aux preuves cryptographiques, permettant de raisonner sur les évènements. Nous validons l'outil en formalisant les preuves de sécurité de plusieurs exemples emblématiques, notamment le schéma de chiffrement OAEP et le schéma de signature FDH.

Sont présentés les différents travaux que j'ai pu effectuer: dans le domaine des automates cellulaires et de leur programmation, puis les travaux portant sur les fonctions Booléennes et leur complexité.

Dans ce mémoire, nous nous intéressons à l'étude et la résolution de problèmes d'ordonnancement de type flowshop de permutation, en présence de contraintes d'écarts temporels (ou time lags), définies entre les couples d'opérations consécutives au sein des travaux. De telles contraintes généralisent les contraintes de précédence classiques et peuvent modéliser de nombreuses situations réelles. De nouveaux résultats de complexité sont démontrés et viennent compléter des résultats classiques tirés de la littérature. Nous présentons aussi un état de l'art assez détaillé sur les travaux concernant les problèmes d'ordonnancement avec time lags, qui met en évidence le manque d'attention reçu par ces problèmes. Nous développons ensuite un schéma générique de résolution exacte reposant sur une Procédure par Séparation et Evaluation et nous l'utilisons pour résoudre plusieurs problèmes de flowshop de permutation en présence de time lags. L'efficacité de cette approche de résolution est évaluée grâce à des séries d'expériences numériques. Enfin, des extensions permettant de prendre en compte des contraintes supplémentaires sont proposées.

Ce travail de thèse s'inscrit dans le domaine de la recherche de structures dans un graphe. <br />On étudie certaines propriétés algorithmiques et combinatoires pour successivement trois types de colorations : orientée, mixte et décomposition acircuitique. <br />Pour la coloration orientée, on obtient des résultats de NP-complétude pour des classes de graphes très spécifiques ainsi que des résultats d'inapproximabilité. Pour dépasser ces difficultés, nous définissons une notion de coloration mixte et obtenons un résultat d'approximation différentielle ainsi qu'une interprétation du polynôme chromatique mixte qui généralise le résultat de Stanley pour certains graphes mixtes. En relachant la contrainte de classe monochromatique stable, nous étudions finalement la complexité de la décomposition acircuitique, caractérisons une famille de tournoi critique indécomposable et établissons les premières propriétés du polynôme chromatique acircuitique.

A partir d'une réflexion conceptuelle et méthodologique pour un réel couplage des automates cellulaires et des modèles multi-agents, le modèle de simulation VisualSimores a été conçu pour répondre, en partie, aux problématiques de simulation de la mobilité résidentielle en milieu urbain. L'intérêt majeur de cette approche réside dans la mise en exergue, dans une perspective d'aide à la décision en aménagement et urbanisme, des rapports qu'entretiennent entre eux, deux phénomènes séparément observables : la mobilité résidentielle des ménages d'une part et les changements urbains d'autre part. La difficulté de l'exercice apparaît immédiatement : il s'agit de cerner les liens qui, à certains types de ménages font correspondre des catégories de logements et vise versa. Plus largement, il s'agit d'identifier les logiques selon lesquelles les ménages expriment et concrétisent leur choix résidentiels. Dans cette perspective, et en raison de la nature complexe du système urbain, la combinaison d'un modèle d'automates cellulaires contraint par un modèle bayésien du comportement des ménages et le paradigme multi agents se révèle plus appropriée.

Les silhouettes ambiguës, comme celle du lapin/canard (Jastrow, 1899), ont été étudiées selon plusieurs approches. Toutefois, les figures prises en exemples dans la large majorité des études sont généralement les mêmes. Cette redondance des images ambiguës utilisées pousse à croire qu'elles sont peut-être assez rares. Certaines observations anecdotiques suggèrent cependant qu’elles seraient au contraire relativement fréquentes. C'est ce que cherche à déterminer cette expérience. Nous avons utilisé des modèles tridimensionnels d'animaux projetés de façon aléatoire afin d'en extraire les silhouettes dont la complexité périmétrique a ensuite été modifiée par lissage. Treize sujets ont dû indiquer ce qu'ils percevaient dans l'image. Nous démontrons qu’une silhouette est classée en moyenne dans 1.9079 catégories de base. Nous avons également démontré qu’une diminution de la complexité périmétrique rend d’abord une silhouette plus ambiguë pour éventuellement atteindre un sommet (équivalent à environ six fois la complexité périmétrique d’un disque) à la suite duquel l’ambiguïté chute. / Ambiguous silhouettes such as the duck/rabbit (Jastrow, 1899) have been studied by several approaches. However, the figures taken as examples in the vast majority of studies are generally the same. This redundancy of the ambiguous images used in litterature implies they may be quite rare. On the other hand, anecdotal evidence suggests that they might be relatively frequent. This is what this experiment is trying to establish. We used three-dimensional models of animals from a random point of view to extract silhouettes whose perimetric complexity was subsequently modified by smoothing. Thirteen subjects were asked to indicate what they saw in the image. We show that silhouettes are classified on average with 1.9079 based categories. We also established that a decrease in the perimetric complexity initially makes a more ambiguous figure but that this effect eventually reaches a peak (at a perimetric complexity of approximately 6 times that of a disk) after which ambiguity drops.