Mémoire numérisé par la Direction des bibliothèques de l'Université de Montréal.

L'objectif général de cette thèse est d'étudier les notions d'aléatoire et d'information algorithmiques - jusqu'ici restreints aux espaces symboliques - sur des espaces plus généraux, précisément les espaces métriques calculables, et d'appliquer ces notions à la théorie des systèmes dynamiques. Les principaux apports sont : (1) le développement d'un cadre robuste pour l'étude d'objets mathématiques (mesures de probabilité, systèmes dynamiques et leurs modèles symboliques) d'un point de vue algorithmique, notamment l'introduction et l'étude détaillée des treillis d'énumération effective; (2) l'extension de l'aléatoire algorithmique aux espaces métriques calculables, améliorant ainsi l'extension menée par Gacs qui imposait une condition supplémentaire à l'espace, et l'étude de quelques notions des probabilités classiques du point de vue de l'aléatoire; (3) un apport à la théorie des systèmes dynamiques, établissant des relations entre l'aléatoire algorithmique et l'aléatoire dynamique. Nous étudions notamment deux notions de complexité algorithmique des orbites, l'une K1 utilisant la mesure, l'autre K2 inspirée du point de vue topologique. Nous montrons que la complexité K1 des orbites partant des points aléatoires est l'entropie du système au sens de la mesure, que la borne supérieure des complexités K2 des orbites est l'entropie topologique, et que K1 et K2 coïncident pour les points aléatoires. Ce travail enrichit les résultats de Brudno et White.

La génomique comparative étudie les similarités et/ou les dissimilarités entre génomes et permet d'établir des relations entre les espèces afin notamment de construire des phylogénies. Elle permet également de mettre en évidence des régions conservées au sein des génomes et de trouver ainsi des ensembles de gènes impliqués dans des processus biologiques conservés au cours de l'évolution. Dans ce mémoire, nous nous intéressons au calcul de mesures entre deux génomes en présence de gènes dupliqués, et plus particulièrement aux mesures à base de points de cassure, d'adjacences, d'intervalles communs et d'intervalles conservés. Suivant une démarche informatique, nous proposons tout d'abord une étude avancée de la complexité algorithmique des problèmes rencontrés, en prouvant notamment pour la plupart d'entre eux soit leur NP-Complétude soit leur APX-Difficulté. Par la suite, nous exposons plusieurs méthodes de calcul de mesures entre deux génomes, à savoir (i) une approche exacte basée sur une transformation en un problème de contraintes à variables booléennes, (ii) une heuristique et (iii) une méthode hybride qui s'appuie sur la méthode exacte et l'heuristique proposées. Par une étude sur un jeu de données réel, nous montrons les qualités respectives de ces méthodes. Enfin, nous proposons un protocole de calcul des intervalles communs et mettons en évidence, par son utilisation et par un outil de visualisation, l'aspect fonctionnel de certains intervalles communs.

Cette thèse est une étude de la géométrie de l'interaction dans le facteur hyperfini (GdI5), introduite par Jean-Yves Girard, et de ses liens avec les constructions plus anciennes. Nous commençons par montrer comment obtenir des adjonctions purement géométriques comme une identité entre des ensembles de cycles apparaissant entre des graphes. Il est alors possible, en choisis- sant une fonction qui mesure les cycles, d'obtenir une adjonction numérique. Nous montrons ensuite comment construire, sur la base d'une adjonction numérique, une géométrie de l'interaction pour la logique linéaire multiplicative additive où les preuves sont interprétées par des graphes. Nous expliquons également comment cette construction permet de définir une sémantique dénotationnelle de MALL, et une notion de vérité. Nous étudions finalement une généralisation de ce cadre utilisant des outils de théorie de la mesure afin d'interpréter les exponentielles et le second ordre. Les constructions sur les graphes étant paramétrées par une fonction de mesure des cycles, nous entreprenons ensuite l'étude de deux cas particuliers. Le premier s'avère être une version combinatoire de la GdI5, et nous obtenons donc une interprétation géométrique de l'orthogonalité basée sur le déterminant de Fuglede-Kadison. Le second cas particulier est une version combinatoire des constructions plus anciennes de la géométrie de l'interaction, où l'orthogonalité est basée sur la nilpotence. Ceci permet donc de comprendre le lien entre les différentes versions de la géométrie de l'interaction, et d'en déduire que les deux adjonctions -- qui semblent à première vue si différentes -- sont des conséquences d'une même identité géométrique. Nous étudions ensuite la notion de vérité subjective. Nous commençons par considérer une version légè- rement modifiée de la GdI5 avec une notion de vérité dépendant du choix d'une sous-algèbre maximale commutative (masa). Nous montrons qu'il existe une correspondance entre la classification des masas introduite par Dixmier (regulière, semi-régulière, singulière) et les fragments de la logique linéaire que l'on peut interpréter dans cette géométrie de l'interaction. Nous étudions alors la vérité subjective de la GdI5, qui dépends du choix d'une représentation du facteur hyperfini de type II1, à la lumière de ce résultat. Finalement, nous détaillerons une proposition de Girard pour étudier les classes de complexité et dé- taillons la caractérisation obtenue par ce dernier de la classe de complexité co-NL, en montrant comment coder un problème complet pour cette classe à l'aide d'opérateurs.

Pruesse et Ruskey ont présenté un algorithme pour la génération de leur code Gray pour les idéaux d'un poset (ensemble partiellement ordonné) où deux idéaux adjacents diffèrent par un ou deux éléments. Leur algorithme fonctionne en temps amorti de O(n) par idéal. Squire a présenté une récurrence pour les idéaux d'un poset qui lui a permis de trouver un algorithme pour générer ces idéaux en temps amorti de O(log n) par idéal, mais pas en code Gray. Nous utilisons la récurrence de Squire pour trouver un code Gray pour les idéaux d'un poset, où deux idéaux adjacents diffèrent par un ou deux éléments. Dans le pire des cas, notre algorithme a la même complexité que celle de l'algorithme de Pruesse et Ruskey et dans les autres cas, sa complexité est meilleure que celle de leur algorithme et se rapproche de celle de l'algorithme de Squire. Squire a donné une condition pour obtenir cette complexité. Nous avons trouvé une condition moins restrictive que la sienne. Cette condition nous a permis d'améliorer la complexité de notre algorithme. ______________________________________________________________________________ MOTS-CLÉS DE L’AUTEUR : Poset, Extension linéaire, Cycle hamiltonien, Code Gray, Algorithme, Complexité.

Nous présentons un ensemble de résultats concernant deux types de problèmes biologiques: (1) la comparaison de structures de molécules d'ARN et (2) le calcul de distances intergénomiques en présence de gènes dupliqués. Dans ce manuscrit, nous déterminons la complexité algorithmique de certains problèmes liés soit à la comparaison de structures de molécules d'ARN (distance d'édition, problème APS, recherche de motifs de 2-intervalles, design d'ARN), soit aux réarrangements génomiques (distances de breakpoints et d'intervalles conservés). \\ L'approche adoptée pour l'ensemble de ces problèmes a été de déterminer, si possible, des algorithmes exacts et rapides répondants aux problèmes posés. Pour tout problème pour lequel cela ne semblait pas possible, nous avons essayé de prouver qu'il ne peut être résolu de fa\ccon rapide. Pour ce faire, nous démontrons que le problème en question est algorithmiquement difficile. Enfin, le cas échéant, nous poursuivons l'étude de ce problème en proposant, essentiellement, trois types de résultats: (1) Approximation, (2) Complexité paramétrée, (3) Heuristique. Nous utilisons, dans ce manuscrit, des notions d'optimisation combinatoire, de mathématique, de théorie des graphes et d'algorithmique.

Cette thèse porte sur des minorants pour des mesures de complexité liées à des sous-classes de la classe P de langages pouvant être décidés en temps polynomial par des machines de Turing. Nous considérons des modèles de calcul non uniformes tels que les programmes sur monoïdes et les programmes de branchement. Notre première contribution est un traitement abstrait de la méthode de Nečiporuk pour prouver des minorants, indépendamment de toute mesure de complexité spécifique. Cette méthode donne toujours les meilleurs minorants connus pour des mesures telles que la taille des programmes de branchements déterministes et non déterministes ou des formules avec des opérateurs booléens binaires arbitraires ; nous donnons une formulation abstraite de la méthode et utilisons ce cadre pour démontrer des limites au meilleur minorant obtenable en utilisant cette méthode pour plusieurs mesures de complexité. Par là, nous confirmons, dans ce cadre légèrement plus général, des résultats de limitation précédemment connus et exhibons de nouveaux résultats de limitation pour des mesures de complexité auxquelles la méthode de Nečiporuk n'avait jamais été appliquée. Notre seconde contribution est une meilleure compréhension de la puissance calculatoire des programmes sur monoïdes issus de petites variétés de monoïdes finis. Les programmes sur monoïdes furent introduits à la fin des années 1980 par Barrington et Thérien pour généraliser la reconnaissance par morphismes et ainsi obtenir une caractérisation en termes de semi-groupes finis de NC^1 et de ses sous-classes. Étant donné une variété V de monoïdes finis, on considère la classe P(V) de langages reconnus par une suite de programmes de longueur polynomiale sur un monoïde de V : lorsque l'on fait varier V parmi toutes les variétés de monoïdes finis, on obtient différentes sous-classes de NC^1, par exemple AC^0, ACC^0 et NC^1 quand V est respectivement la variété de tous les monoïdes apériodiques finis, résolubles finis et finis. Nous introduisons une nouvelle notion de docilité pour les variétés de monoïdes finis, renforçant une notion de Péladeau. L'intérêt principal de cette notion est que quand une variété V de monoïdes finis est docile, nous avons que P(V) contient seulement des langages réguliers qui sont quasi reconnus par morphisme par des monoïdes de V. De nombreuses questions ouvertes à propos de la structure interne de NC^1 seraient réglées en montrant qu'une variété de monoïdes finis appropriée est docile, et, dans cette thèse, nous débutons modestement une étude exhaustive de quelles variétés de monoïdes finis sont dociles. Plus précisément, nous portons notre attention sur deux petites variétés de monoïdes apériodiques finis bien connues : DA et J. D'une part, nous montrons que DA est docile en utilisant des arguments de théorie des semi-groupes finis. Cela nous permet de dériver une caractérisation algébrique exacte de la classe des langages réguliers dans P(DA). D'autre part, nous montrons que J n'est pas docile. Pour faire cela, nous présentons une astuce par laquelle des programmes sur monoïdes de J peuvent reconnaître beaucoup plus de langages réguliers que seulement ceux qui sont quasi reconnus par morphisme par des monoïdes de J. Cela nous amène à conjecturer une caractérisation algébrique exacte de la classe de langages réguliers dans P(J), et nous exposons quelques résultats partiels appuyant cette conjecture. Pour chacune des variétés DA et J, nous exhibons également une hiérarchie basée sur la longueur des programmes à l'intérieur de la classe des langages reconnus par programmes sur monoïdes de la variété, améliorant par là les résultats de Tesson et Thérien sur la propriété de longueur polynomiale pour les monoïdes de ces variétés. / This thesis deals with lower bounds for complexity measures related to subclasses of the class P of languages that can be decided by Turing machines in polynomial time. We consider non-uniform computational models like programs over monoids and branching programs.Our first contribution is an abstract, measure-independent treatment of Nečiporuk's method for proving lower bounds. This method still gives the best lower bounds known on measures such as the size of deterministic and non-deterministic branching programs or formulae{} with arbitrary binary Boolean operators; we give an abstract formulation of the method and use this framework to prove limits on the best lower bounds obtainable using this method for several complexity measures. We thereby confirm previously known limitation results in this slightly more general framework and showcase new limitation results for complexity measures to which Nečiporuk's method had never been applied.Our second contribution is a better understanding of the computational power of programs over monoids taken from small varieties of finite monoids. Programs over monoids were introduced in the late 1980s by Barrington and Thérien as a way to generalise recognition by morphisms so as to obtain a finite-semigroup-theoretic characterisation of NC^1 and its subclasses. Given a variety V of finite monoids, one considers the class P(V) of languages recognised by a sequence of polynomial-length programs over a monoid from V: as V ranges over all varieties of finite monoids, one obtains different subclasses of NC^1, for instance AC^0, ACC^0 and NC^1 when V respectively is the variety of all finite aperiodic, finite solvable and finite monoids. We introduce a new notion of tameness for varieties of finite monoids, strengthening a notion of Péladeau. The main interest of this notion is that when a variety V of finite monoids is tame, we have that P(V) does only contain regular languages that are quasi morphism-recognised by monoids from V. Many open questions about the internal structure of NC^1 would be settled by showing that some appropriate variety of finite monoids is tame, and, in this thesis, we modestly start an exhaustive study of which varieties of finite monoids are tame. More precisely, we focus on two well-known small varieties of finite aperiodic monoids: DA and J. On the one hand, we show that DA is tame using finite-semigroup-theoretic arguments. This allows us to derive an exact algebraic characterisation of the class of regular languages in P(DA). On the other hand, we show that J is not tame. To do this, we present a trick by which programs over monoids from J can recognise much more regular languages than only those that are quasi morphism-recognised by monoids from J. This brings us to conjecture an exact algebraic characterisation of the class of regular languages in P(J), and we lay out some partial results that support this conjecture. For each of the varieties DA and J, we also exhibit a program-length-based hierarchy within the class of languages recognised by programs over monoids from the variety, refining Tesson and Thérien's results on the polynomial-length property for monoids from those varieties.

No description available.

La complexité de la communication a été introduite en 1979 par Andrew Chi-Chi Yao. Elle est depuis devenue l'un des modèles de calcul les plus étudiés. L'objectif de celle-ci est d'étudier des problèmes dont les entrées sont distribuées entre plusieurs joueurs, en quantifiant la communication que ceux-ci doivent échanger. Nous utilisons d'abord la complexité de Kolmogorov, une caractérisation algorithmique de l'aléatoire, pour prouver des bornes inférieures sur la complexité de la communication. Notre méthode constitue une généralisation de la méthode d'incompressibilité. L'avantage de cette approche est de mettre en valeur la nature combinatoire des preuves. Nous étudions ensuite la simulation des distributions de probabilité causales avec de la communication. Ce modèle généralise la complexité de la communication traditionnelle et comprend en particulier les distributions quantiques. Nous montrons pour ce problème des bornes inférieures et supérieures. Dans le cas des fonctions booléennes, la borne inférieure que nous proposons est équivalente aux normes de factorisation, une puissante méthode introduite par Linial et Shraibman en 2006. Enfin, nous étudions la complexité en boîte non-locale. Cette ressource a été introduite par Popescu et Rohrlich pour étudier la non-localité. Le problème est de quantifier le nombre de boîtes nécessaire et suffisant pour calculer une fonction ou simuler une distributions. Nous donnons encore des bornes inférieures et supérieures pour ces problèmes, ainsi que des applications à l'évaluation sécurisée, un problème cryptographique très important.

Les problèmes d'optimisation combinatoires définis sur graphes aléatoires sont au coeur de la théorie de la complexité algorithmique. Ils sont également étroitement liés à une formulation champ moyen, dite approximation de Bethe, de modèles sur réseau de verres de spins et verres structuraux. Cette thèse s'appuie sur ce parallèle pour appliquer à des problèmes d'optimisation une approche issue de la physique statistique des systèmes désordonnés, la méthode de la cavité. Etant donné un ensemble d'entrées (instances) d'un problème d'optimisation, cette méthode permet de déterminer les propriétés des solutions des instances typiques, ainsi que celles des instances atypiques, dont les probabilités sont exponentiellement petites (grandes déviations sur la structure externe). Pour une instance donnée, la méthode de la cavité donne également accès à la thermodynamique des différentes solutions admissibles (grandes déviations sur la structure interne). D'un point de vue physique, de nombreux problèmes algorithmiquement difficiles se révèlent ainsi posséder une phase de type verre. Cette thèse est composée de trois parties destinées à exposer les principes, applications et limitations de la méthode de la cavité. La première partie rappelle, dans la perspective des grandes déviations, les liens entre physique statistique et optimisation combinatoire. La deuxième partie aborde les modèles définis sur graphes aléatoires et, pour différents ensembles de graphes, analyse les propriétés typiques et atypiques de ces modèles. La troisième partie est consacrée aux grandes déviations sur le "désordre interne", constitué par les solutions et quasi-solutions d'une instance donnée. Une attention particulière est dévolue au traitement des phases vitreuses où l'ensemble des solutions est fragmenté en un nombre exponentiel d'amas disjoints (structure dite à un pas de brisure de symétrie des répliques); il est montré comment la méthode de la cavité fournit dans de tels cas une description fine des propriétés géométriques de l'espace des solutions.