Dans le cadre de l'étude des ensembles de pavages, nous nous sommes concentrés sur le cas des pavages de zonotopes (figures d'un espace formées de toutes les combinaisons linéaires d'un ensemble de vecteurs donnés). Après avoir défini un graphe dual d'un pavage de zonotope planaire (par l'utilisation de la relation d'adjacence liant les tuiles), nous avons montré la relation biunivoque qui lie les deux classes d'objets. Nous avons alors étudié comment l'opération de flip (qui est un réarrangement local de tuiles) peut s'exprimer sur le dual, permettant par la suite de construire l'ensemble des pavages du zonotope associé. Cette méthode ne pouvant que très difficilement s'adapter aux cas de dimensions supérieures (zonotopes non planaires), nous avons alors mis au point une méthode de décomposition permettant d'étudier un pavage en nous focalisant sur les propriétés de pavages plus petits. Ce type de méthode nous a permis de démontrer des résultats forts de reconstruction et de structure dans le cas de pavages de dimension 2. De plus, ceci nous a permis de démontrer des résultats de connexité dans certains cas particuliers de dimensions supérieures. Le choix des pavages de zonotopes étend naturellement certains pavages étudiés classiquement (tels que les pavages de dominos sur une grille carrée ou de losanges sur une grille triangulaire). En effet, ils ne peuvent être définis sur une grille, et sont définis en toute dimension.

Dans cette thèse nous traitons des mots interdits minimaux, qui sont les plus petits mots qui n'apparaissent pas comme facteur d'un mot donné, et de leurs applications. Dans la première partie de la thèse nous exposons les propriétés des mots interdits minimaux, et nous considérons quelques cas particuliers, comme celui d'un mot fini, d'un ensemble fini de mots finis, et d'un langage factoriel régulier. Nous présentons aussi les procédures pour le calcul des objets considérés. Ensuite, nous généralisons les mots interdits minimaux au cas de l'existence d'une période, qui détermine les positions des occurrences des facteurs modulo un entier fixé. Ceux-ci sont appelés mots interdits minimaux périodiques. Nous étudions leurs propriétés principales et avec des algorithmes de test de ces propriétés. Dans la deuxième partie de la thèse nous montrons deux applications des mots interdits minimaux. La première est reliée aux systèmes contraints. Nous donnons une construction en temps polynomial de l'ensemble des séquences qui satisfont la contrainte définie par une liste finie de blocs interdits, avec un ensemble spécifié de positions de bit sans contrainte. Nous donnons aussi une construction en temps linéaire d'une présentation à états finis d'un système contraint défini par une liste périodique de blocs interdits. La deuxième application est relative à un problème de biologie : la reconstruction d'une séquence génomique à partir d'un ensemble de ses fragments. Nous donnons une formalisation théorique de ce problème qui le rend résoluble en temps linéaire en utilisant les mots interdits minimaux. Nous prouvons aussi que notre algorithme résout un cas particulier du "problème de la plus petite sur-séquence" (Shortest Superstring Problem).

Cette thèse explore les nombreux changements nés de la Révolution Numérique à travers l'esthétique. Elle aborde les questions essentielles en trois étapes: le discours, la création et la réception. La première partie rassemble les courants et les mots-clefs qui reflètent le discours principal dans son actualité et son historique. Une étude comparative analyse les approches esthétiques typiques. Que l'on étudie les nouveaux médias, l'art visuel, l'art numérique, le « computer art », l'art de l'information ou l'art du code: on cherche tous à définir les nouvelles qualités spécifiques du médium numérique. La deuxième partie se concentre sur les arts sonores et les drames audio en particulier, mais aborde également la musique assistée par ordinateur. L'attention portée au genre du Hörspiel permet de démontrer comment espace et temps évoluent dans le détail. La mise en place d'une hypothèse de travail portant sur les Sonarios - installations sonores spatiales à interactivité scénique - permet de comparer directement 1'« ancien» genre du Hörspiel au « nouveau» genre des Sonarios, en se fondant sur trois études de cas et un état des lieux de l'art. En outre, elle propose un modèle d'interactivité quantitatif et qualitatif. La troisième partie présente les courants prédominants en philosophie. Elle construit un modèle herméneutique à l'aide de l'ontologie, en commençant par la virtualisation et l'actualisation. Abordant philosophiquement des catégories esthétiques, elle affine ce modèle en y incorporant les découvertes de la deuxième partie. Un modèle graphique de signes algorithmiques, développé en sémiotique et en phénoménologie, est alors intégré au domaine de l'esthétique. / This dissertation explores the numerous changes arising from the Digital Revolution through aesthetics. It takes on the essential issues in three steps, tackling discourse, creation and reception. The first part assembles trends and keywords that reflect the main discourse, covering both the present and the past. A comparative study analyzes typical aesthetic approaches: whether considering new media art, virtual art, digital art, computer art, information art or code art, it becomes apparent that almost ail approaches seek the specific new qualities of the digital medium. The second part concentrates on sound arts and on audio dramas in particular, but also tackles computer music. The focus on the genre Hörspiel allows demonstration of how space and time change in detail. The setting up of a working hypothesis of Sonarios, defining interactive scenic spatial sound installations, allows the direct comparison of the 'old' genre Hörspiel and the 'new' genre Sonario on the basis of three case studies and a consideration of the state of the art. It, moreover, suggests a qualitative and quantitative model of interactivity. The third part introduces the prominent research sectors of philosophy. Step by step, it constructs a hermeneutic model with the aid of ontology, starting with the processes of virtualization and actualization. Selected philosophical approaches on important aesthetic categories are presented in order to refine and discuss the model, together with an analysis of findings from the second part. A graphical model of algorithmic signs, developed in the context of semiotics and phenomenology, allows the analysis to be embedded in the context of aesthetics.

Nous introduisons d'abord la classe des graphes $k$-dégénérés qui est souvent utilisée pour modéliser des grands graphes épars issus du monde réel. Nous proposons de nouveaux algorithmes d'énumération pour ces graphes. En particulier, nous construisons un algorithme énumérant tous les cycles simples de tailles fixés dans ces graphes, en temps optimal.Nous proposons aussi un algorithme dont la complexité dépend de la taille de la solution pour le problème d'énumération des cliques maximales de ces graphes. Dans un second temps nous considérons les graphes en tant que systèmes distribués et nous nous intéressons à des questions liées à la notion de couplage lorsqu’aucune supposition n’est faite sur l'état initial du système, qui peut donc être correct ou incorrect. Dans ce cadre nous proposons un algorithme retournant une deux tiers approximation du couplage maximum.Nous proposons aussi un algorithme retournant un couplage maximal quand les communications sont restreintes de telle manière à simuler le paradigme du passage de message. Le troisième objet d'étude n'est pas directement lié à l'algorithmique de graphe, bien que quelques techniques classiques de ce domaine soient utilisées pour obtenir certains de nos résultats.Nous introduisons et étudions certaines familles de polytopes, appelées Zonotopes Primitifs, qui peuvent être décrits comme la somme de Minkowski de vecteurs primitifs. Nous prouvons certaines propriétés combinatoires de ces polytopes et illustrons la connexion avec le plus grand diamètre possible de l'enveloppe convexe de points à coordonnées entières à valeurs dans$[k]$, en dimension $d$. Dans un second temps,nous étudions des paramètres de petites instances de Zonotopes Primitifs, tels que leur nombre de sommets, entre autres. / We start by studying the class of $k$-degenerate graphs which are often used to model sparse real-world graphs. We focus one numeration questions for these graphs. That is,we try and provide algorithms which must output, without duplication, all the occurrences of some input subgraph. We investigate the questions of finding all cycles of some givensize and all maximal cliques in the graph. Ourtwo contributions are a worst-case output sizeoptimal algorithm for fixed-size cycleenumeration and an output sensitive algorithmfor maximal clique enumeration for this restricted class of graphs. In a second part weconsider graphs in a distributed manner. Weinvestigate questions related to finding matchings of the network, when no assumptionis made on the initial state of the system. Thesealgorithms are often referred to as selfstabilizing.Our two main contributions are analgorithm returning an approximation of themaximum matching and a new algorithm formaximal matching when communication simulates message passing. Finally, weintroduce and investigate some special families of polytopes, namely primitive zonotopes,which can be described as the Minkowski sumof short primitive vectors. We highlight connections with the largest possible diameter ofthe convex hull of a set of points in dimension d whose coordinates are integers between 0 and k.Our main contributions are new lower bounds for this diameter question as well as descriptions of small instances of these objects.

. / In this PhD, we present some algorithms and complexity results for two general problems that arise in the analysis of a metabolic network: the search for elementary modes of a network and the search for minimal precursors sets. Elementary modes is a common tool in the study of the cellular characteristic of a metabolic network. An elementary mode can be seen as a minimal set of reactions that can work in steady state independently of the rest of the network. It has therefore served as a mathematical model for the possible metabolic pathways of a cell. Their computation is not trivial and poses computational challenges. We show that some problems, like checking consistency of a network, finding one elementary mode or checking that a set of reactions constitutes a cut are easy problems, giving polynomial algorithms based on LP formulations. We also prove the hardness of central problems like finding a minimum size elementary mode, finding an elementary mode containing two given reactions, counting the number of elementary modes or finding a minimum reaction cut. On the enumeration problem, we show that enumerating all reactions containing one given reaction cannot be done in polynomial total time unless P=NP. This result provides some idea about the complexity of enumerating all the elementary modes. The search for precursor sets is motivated by discovering which external metabolites are sufficient to allow the production of a given set of target metabolites. In contrast with previous proposals, we present a new approach which is the first to formally consider the use of cycles in the way to produce the target. We present a polynomial algorithm to decide whether a set is a precursor set of a given target. We also show that, given a target set, finding a minimal precursor set is easy but finding a precursor set of minimum size is NP-hard. We further show that finding a solution with minimum size internal supply is NP-hard. We give a simple characterisation of precursors sets by the existence of hyperpaths between the solutions and the target. If we consider the enumeration of all the minimal precursor sets of a given target, we find that this problem cannot be solved in polynomial total time unless P=NP. Despite this result, we present two algorithms that have good performance for medium-size networks

Nous avons tous l'intuition qu'un travail peut être réalisé en beaucoup moins de temps s'il est réparti entre plusieurs personnes ou sur plusieurs machines. Cette notion se nomme le parallélisme qui peut se définir comme l'état de ce qui se développe dans la même direction ou en même temps. C'est naturellement que la notion de parallélisme a été appliquée aux ordinateurs. De ce fait, il a été possible de répondre aux besoins de puissance nécessaire à la réalisation de projets gourmands en temps de calculs et en taille mémoire. Le parallélisme combiné à une algorithmique performante permet de gagner du temps afin de répondre au mieux à d'importants besoins. Il rompt avec l'approche classique qui consiste à gagner de la vitesse en effectuant plus rapidement chaque opération, approche bornée par les lois de la physique. La notion de parallélisme a donc grandement contribué à la multiplication des modèles informatiques. <br /><br />Nous nous intéresserons au modèle systolique et au modèle parallèle à gros grains baptisé (Coarse Grained Multicomputers). Le modèle CGM a été proposé par F. Dehne et al. et il possède des propriétés qui le rendent très intéressant d'un point de vue pratique. Il est parfaitement adapté à la modélisation des architectures existantes pour lesquelles le nombre de processeurs peut être de plusieurs milliers et la taille des données peut atteindre plusieurs milliards d'octets. Un algorithme développé pour ce modèle est constitué de calculs locaux utilisant, si possible, des algorithmes séquentiels optimaux et de rondes de communication dont le nombre doit être indépendant de la taille des données à traiter. Le modèle CGM est donc très intéressant d'un point de vue économique. En effet, ce modèle est indépendant des architectures réelles et permet de réutiliser des algorithmes séquentiels efficaces, ce qui le rend très portable. <br /><br />Dans cette thèse nous nous intéressons à des problèmes d'algorithmique du texte. Ces problèmes peuvent améliorer la compression de données ou bien être utilisés en bio-informatique. Ainsi, nous proposons des solutions CGM aux problèmes de recherche de la plus longue sous-suite croissante, de la plus longue sous-suite commune à deux mots, du plus long suffixe répété en chaque caractère d'un mot et de répétitions. Pour cela, nous sommes partis de solutions systoliques existantes que nous avons adaptées au modèle CGM. Le but de ce travail est en fait double. D'une part, nous proposons pour la première fois des solutions CGM à ces quatre problèmes. D'autre part, nous montrons comment des solutions systoliques peuvent être dérivées en algorithmes CGM. En effet, de nombreux problèmes ont été étudiés sur des architectures systoliques, c'est à dire des machines dédiées, non réutilisables pour d'autres problèmes. Le modèle CGM quant à lui permet de travailler avec des machines peu coûteuses et réutilisables à souhaits. De plus, l'expérience acquise au cours de ces travaux nous permet d'avoir une bonne idée des solutions systoliques adaptables au modèle CGM. Ceci pourrait permettre de consolider le pont existant entre modèles à grains fins et modèles à gros grains. <br /><br />Nous finissons cette thèse par une discussion sur l'équilibrage de charge des solutions proposées et sur la prédictivité de l'adaptation d'autres solutions systoliques au modèle CGM.

Nous nous intéressons dans cette thèse à des problèmes d'optimisation liés au domaine des réseaux. Ces problèmes sont d'une part des problèmes d'optimisation ``classiques'' dans lesquels nous cherchons à pallier la NP-difficulté d'un problème en proposant des algorithmes approchés, le plus souvent avec garantie de performance. D'autre part, nous avons considéré des problèmes dans lesquels les utisateurs du réseau sont indépendants et individualistes. Chaque utilisateur souhaite alors optimiser sa propre fonction objectif, qui peut être très différente de la fonction objectif globale que, en tant que concepteurs d'un protocole, nous souhaitons optimiser. Nous nous plaçons alors dans le cadre de la théorie des jeux algorithmique et cherchons à optimiser cette fonction objectif globale en prenant en compte des contraintes supplémentaires dues au fait que les utilisateurs se comportent de façon individualiste. Les problémes que nous avons considérés sont des problémes d'ordonnancement et de routage.

No description available.

Thèse numérisée par la Direction des bibliothèques de l'Université de Montréal.

Les problèmes de découpe et de placement sont des problèmes combinatoires. Ils sont classes dans la catégorie des problèmes NP-Complets et admettent de nombreuses applications en industrie, en systèmes multiprocesseurs. Nous proposons dans cette thèse, plusieurs méthodes de résolution exactes et approchées, séquentielles et parallèles du problème de découpe et de placement à deux dimensions.