L'objet de ce mémoire est l'étude et la construction d'un modèle de surfaces fondé sur la représentation par un atlas de cartes : <br />L'intérêt d'un tel modèle est qu'il permet de travailler localement sur la sur face sans perte de la cohérence globale, et d'autre part d'hériter des notions de géométrie différentielle attachées à cette représentation pour définir une surface régulière, et donc résoudre intrinsèquement les problèmes de continuité ordinairement rencontrés par les représentations paramétriques par morceaux. Nous avons présenté ce modèle dans le cadre des modèles de surfaces d'usage courant en informatique graphique, puis dans le cadre plus théorique de la géométrie différentielle. <br /> Nous avons ensuite proposé la construction d'un tel modèle à partir d'un nuage de points 3D interpolés au préalable par une surface triangulée qui est une variété de dimension 2, connexe et compacte. Cette construction se déroule en trois étapes. Chaque étape rencontre un problème géométrique auquel nous proposons une solution innovante. En particulier, nous avons démontré que le nerf d'un recouvrement bien formé est une triangulation combinatoire. Nous avons également étudié la para métrisation d'une couronne du plan par un C1-difféomorphisme, ainsi que le raccord continu de surfaces par combinaison convexe.

Le domaine des protocoles tolérants aux pannes étudie quelles tâches concurrentes sont résolubles dans différents modèles de calcul avec pannes. Des outils mathématiques basés sur la topologie combinatoire ont été développés depuis les années 1990 pour aborder ces questions. Dans ce cadre, la tâche que l’on veut résoudre, et le protocole auquel on fait appel, sont modélisés par des complexes simpliciaux chromatiques. On définit qu’un protocole résout une tâche lorsqu’il existe une certaine application simpliciale entre ces complexes.Dans cette thèse, on étudie ces méthodes géométriques du point de vue de la sémantique. Le premier objectif est de fonder cette définition abstraite de résolution d’une tâche sur une autre plus concrète, basée sur des entrelacements de traces d’exécution. On examine diverses notions de spécifications pour les objets concurrents, afin de définir un cadre général pour la résolution de tâches par des objets partagés. On montre ensuite comment extraire de ce cadre la définition topologique de résolubilité de tâches.Dans la deuxième partie de la thèse, on prouve que les complexes simpliciaux chromatiques peuvent être utilisés pour évaluer des formules de logique épistémique. Cela permet d’interpréter les preuves topologiques d’impossibilité en fonction de la quantité de connaissances à acquérir pour résoudre une tâche.Enfin, on présente quelques liens préliminaires avec la sémantique dirigée pour les programmes concurrents. On montre comment la subdivision chromatique d’un simplexe peut être retrouvée en considérant des notions combinatoires de chemins dirigés. / The field of fault-tolerant protocols studies which concurrent tasks are solvable in various computational models where processes may crash. To answer these questions, powerful mathematical tools based on combinatorial topology have been developed since the 1990’s. In this approach, the task that we want to solve, and the protocol that we use to solve it, are both modeled using chromatic simplicial complexes. By definition, a protocol solves a task when there exists a particular simplicial map between those complexes.In this thesis we study these geometric methods from the point of view of semantics. Our first goal is to ground this abstract definition of task solvability on a more concrete one, based on interleavings of execution traces. We investigate various notions of specification for concurrent objects, in order to define a general setting for solving concurrent tasks using shared objects. We then show how the topological definition of task solvability can be derived from it.In the second part of the thesis, we show that chromatic simplicial complexes can actually be used to interpret epistemic logic formulas. This allows us to understand the topological proofs of task unsolvability in terms of the amount of knowledge that the processes should acquire in order to solve a task.Finally, we present a few preliminary links with the directed space semantics for concurrent programs. We show how chromatic subdivisions of a simplex can be recovered by considering combinatorial notions of directed paths.

Cette thèse traite principalement des contreparties combinatoires et constructives de certains théorèmes d'optimisation combinatoire qui font appel à des outils de topologie algébrique. Des généralisations des lemmes de Sperner et des formules combinatoires de Ky Fan sont proposées, ainsi que des applications à la coloration des graphes de Kneser et au célèbre problème du partage équitable du collier. Un problème d'ordonnancement lié à ce dernier problème est également abordé. Enfin, le dernier chapitre contient des résultats nouveaux pour les sigma-jeux (jeux de lampes) sur la grille.