Generating trees for permutations avoiding generalized patterns

We construct generating trees with with one, two, and three labels for some classes of permutations avoiding generalized patterns of length 3 and 4. These trees are built by adding at each level an entry to the right end of the permutation, which allows us to incorporate the adjacency condition about some entries in an occurrence of a generalized pattern. We use these trees to find functional equations for the generating functions enumerating these classes of permutations with respect to different parameters. In several cases we solve them using the kernel method and some ideas of Bousquet-Mélou [2]. We obtain refinements of known enumerative results and find new ones.

A note on quadrics through an algebraic curve

In this note we describe the intersection of all quadric hypersur- faces containing a given linearly normal smooth projective curve of genus n and degree 2n + 1

Une nouvelle approche computationnelle pour la découverte des sites de fixation de facteurs de transcription à l’ADN, adaptée aux données de ChIP-chip et de ChIP-séquençage

Les facteurs de transcription sont des protéines spécialisées qui jouent un rôle important dans différents processus biologiques tel que la différenciation, le cycle cellulaire et la tumorigenèse. Ils régulent la transcription des gènes en se fixant sur des séquences d’ADN spécifiques (éléments cis-régulateurs). L’identification de ces éléments est une étape cruciale dans la compréhension des réseaux de régulation des gènes. Avec l’avènement des technologies de séquençage à haut débit, l’identification de tout les éléments fonctionnels dans les génomes, incluant gènes et éléments cis-régulateurs a connu une avancée considérable. Alors qu’on est arrivé à estimer le nombre de gènes chez différentes espèces, l’information sur les éléments qui contrôlent et orchestrent la régulation de ces gènes est encore mal définie. Grace aux techniques de ChIP-chip et de ChIP-séquençage il est possible d’identifier toutes les régions du génome qui sont liées par un facteur de transcription d’intérêt. Plusieurs approches computationnelles ont été développées pour prédire les sites fixés par les facteurs de transcription. Ces approches sont classées en deux catégories principales: les algorithmes énumératifs et probabilistes. Toutefois, plusieurs études ont montré que ces approches génèrent des taux élevés de faux négatifs et de faux positifs ce qui rend difficile l’interprétation des résultats et par conséquent leur validation expérimentale. Dans cette thèse, nous avons ciblé deux objectifs. Le premier objectif a été de développer une nouvelle approche pour la découverte des sites de fixation des facteurs de transcription à l’ADN (SAMD-ChIP) adaptée aux données de ChIP-chip et de ChIP-séquençage. Notre approche implémente un algorithme hybride qui combine les deux stratégies énumérative et probabiliste, afin d’exploiter les performances de chacune d’entre elles. Notre approche a montré ses performances, comparée aux outils de découvertes de motifs existants sur des jeux de données simulées et des jeux de données de ChIP-chip et de ChIP-séquençage. SAMD-ChIP présente aussi l’avantage d’exploiter les propriétés de distributions des sites liés par les facteurs de transcription autour du centre des régions liées afin de limiter la prédiction aux motifs qui sont enrichis dans une fenêtre de longueur fixe autour du centre de ces régions. Les facteurs de transcription agissent rarement seuls. Ils forment souvent des complexes pour interagir avec l’ADN pour réguler leurs gènes cibles. Ces interactions impliquent des facteurs de transcription dont les sites de fixation à l’ADN sont localisés proches les uns des autres ou bien médier par des boucles de chromatine. Notre deuxième objectif a été d’exploiter la proximité spatiale des sites liés par les facteurs de transcription dans les régions de ChIP-chip et de ChIP-séquençage pour développer une approche pour la prédiction des motifs composites (motifs composés par deux sites et séparés par un espacement de taille fixe). Nous avons testé ce module pour prédire la co-localisation entre les deux demi-sites ERE qui forment le site ERE, lié par le récepteur des œstrogènes ERα. Ce module a été incorporé à notre outil de découverte de motifs SAMD-ChIP.

Théorie du langage et esthétique totalisante dans l’œuvre poétique de Christophe Tarkos

Cette thèse prend pour objet le nouage entre l’autoréflexivité et la mise en forme esthétique dans la poésie de Christophe Tarkos, produite dans les années 1990. Elle met en lumière les rapports entre l’élaboration d’une théorie du langage au sein de cette œuvre poétique et ses visées esthétiques totalisantes. Il s’agit d’identifier les principes générateurs de la théorie et de fournir une analyse de ses fondements qui s’ancrent dans la crise de la représentation moderne commençant dans la deuxième moitié du dix-neuvième siècle. Les motifs de la crise revisités par Tarkos inscrivent sa poésie dans une historicité, et notre thèse tente d’interpréter cette actualisation dans une œuvre qui donne forme au monde et à la mémoire individuelle. L’hypothèse qui chapeaute notre étude est que la théorie du langage favorise l’intelligibilité de l’œuvre totalisante en lui offrant un support réflexif. Notre thèse, qui privilégie une méthode fondée sur l’analyse des textes, se divise en trois parties. La première propose une recension de la réception critique de l’œuvre, dont nous retraçons les grandes lignes d’interprétation, de Christian Prigent à Jean-Michel Espitallier. Tout en plaçant Tarkos dans le champ poétique français, cette étape nous permet de positionner notre recherche par rapport à certains lieux communs de la critique. La deuxième partie vise à étudier la théorie du langage de Tarkos à partir de ses manifestes principaux (Le Signe =, Manifeste chou, Ma langue est poétique et La poésie est une intelligence) qui révèlent plusieurs principes, pouvoirs et limites de la langue et de la poésie. Afin de montrer la spécificité du concept de la « pâte-mot » de Tarkos, nous l’étudions dans un dialogue avec la figure de la « pâte » langagière chez la poète française Danielle Collobert. La troisième partie propose une étude de la volonté et de l’esthétique totalisantes dans l’œuvre de Tarkos, qui cherche à donner forme au réel. En effet, la poésie répond à l’excès du réel par diverses stratégies. Tout en voulant représenter son caractère débordant par une énonciation logorrhéique ou en usant de procédés comme celui de la répétition, elle cherche à le maîtriser dans des formes textuelles stables comme des fragments de prose « carrés » (Carrés, Caisses), dans des listes énumératives (Anachronisme) ou dans des réseaux d’images. La volonté totalisante chez Tarkos semble également prendre origine dans un sentiment d’urgence qui concerne, en dernière instance, une bataille contre la finitude.

Efficient tree construction for the multicast problem

A new heuristic for the Steiner Minimal Tree problem is presented here. The method described is based on the detection of particular sets of nodes in networks, the “Hot Spot” sets, which are used to obtain better approximations of the optimal solutions. An algorithm is also proposed which is capable of improving the solutions obtained by classical heuristics, by means of a stirring process of the nodes in solution trees. Classical heuristics and an enumerative method are used CIS comparison terms in the experimental analysis which demonstrates the goodness of the heuristic discussed in this paper.

Efficient tree construction for the multicast problem

A new heuristic for the Steiner minimal tree problem is presented. The method described is based on the detection of particular sets of nodes in networks, the “hot spot” sets, which are used to obtain better approximations of the optimal solutions. An algorithm is also proposed which is capable of improving the solutions obtained by classical heuristics, by means of a stirring process of the nodes in solution trees. Classical heuristics and an enumerative method are used as comparison terms in the experimental analysis which demonstrates the capability of the heuristic discussed

Uma nova heurística para o problema de minimização de trocas de ferramentas

O problema de minimização de troca de ferramentas (MTSP) busca uma sequência de processamento de um conjunto de tarefas, de modo a minimizar o número de trocas de ferramentas requeridas. Este trabalho apresenta uma nova heurística para o MTSP, capaz de produzir bons limitantes superiores para um algoritmo enumerativo. Esta heurística possui duas fases: uma fase construtiva que é baseada em um grafo em que os vértices correspondem a ferramentas e existe um arco k = (i, j) que liga os vértices i e j se e somente se as ferramentas i e j são necessárias para a execução de alguma tarefa k; e uma fase de refinamento baseada na meta-heurística Busca Local Iterativa. Resultados computacionais mostram que a heurística proposta tem um bom desempenho para os problemas testados, contribuindo para uma redução significativa no número de nós gerados de um algoritmo enumerativo.

Eduard Study (1862-1930) - ein mathematischer Mephistopheles im geometrischen Gärtchen

Diese Arbeit befasst sich mit Eduard Study (1862-1930), einem der deutschen Geometer um die Jahrhundertwende, der seine Zeit zum Einen durch seine Kontakte zu Klein, Hilbert, Engel, Lie, Gordan, Halphen, Zeuthen, Einstein, Hausdorff und Weyl geprägt hat, zum Anderen in ihr aber auch für seine beißenden und stilistisch ausgefeilten Kritiken ebenso berühmt wie berüchtigt war. Da sich Study mit einer Vielzahl mathematischer Themen beschäftigt hat, führen wir zunächst in die von ihm bearbeiteten Gebiete der Geometrie des 19. Jahrhunderts ein (analytische und synthetische Geometrie im Sinne von Monge, Poncelet, Plücker und Reye, Invariantentheorie Clebsch-Gordan'scher Prägung, abzählende Geometrie von Chasles und Halphen, die Werke Lie's und Grassmann’s, Liniengeometrie sowie Axiomatik und Grundlagenkrise). In seiner darauf folgenden Biographie finden sich als zentrale Stellen seine Habilitation bei Klein über die Chasles’sche Vermutung, sein Streit mit Zeuthen darüber als eine der Debatten der Mathematischen Annalen (aus der er historisch zwar nicht, mathematisch aber tatsächlich als Gewinner hätte herausgehen müssen, wie wir an der Lösung des Problems durch van der Waerden sehen werden) und seine Auseinandersetzungen als etablierter Bonner Professor mit Engel über Lie, Weyl über Invariantentheorie, zahlreichen philosophischen Richtungen über das Raumproblem, Pasch’s Axiomatik, Hilbert’s Formalismus sowie Brouwer’s und Weyl’s Intuitionismus.

Permutation classes, sorting algorithms, and lattice paths

A permutation is said to avoid a pattern if it does not contain any subsequence which is order-isomorphic to it. Donald Knuth, in the first volume of his celebrated book "The art of Computer Programming", observed that the permutations that can be computed (or, equivalently, sorted) by some particular data structures can be characterized in terms of pattern avoidance. In more recent years, the topic was reopened several times, while often in terms of sortable permutations rather than computable ones. The idea to sort permutations by using one of Knuth’s devices suggests to look for a deterministic procedure that decides, in linear time, if there exists a sequence of operations which is able to convert a given permutation into the identical one. In this thesis we show that, for the stack and the restricted deques, there exists an unique way to implement such a procedure. Moreover, we use these sorting procedures to create new sorting algorithms, and we prove some unexpected commutation properties between these procedures and the base step of bubblesort. We also show that the permutations that can be sorted by a combination of the base steps of bubblesort and its dual can be expressed, once again, in terms of pattern avoidance. In the final chapter we give an alternative proof of some enumerative results, in particular for the classes of permutations that can be sorted by the two restricted deques. It is well-known that the permutations that can be sorted through a restricted deque are counted by the Schrӧder numbers. In the thesis, we show how the deterministic sorting procedures yield a bijection between sortable permutations and Schrӧder paths.

Deriving Deligne-Mumford stacks with perfect obstruction theories

Intersection theory on moduli spaces has lead to immense progress in certain areas of enumerative geometry. For some important areas, most notably counting stable maps and counting stable sheaves, it is important to work with a virtual fundamental class instead of the usual fundamental class of the moduli space. The crucial prerequisite for the existence of such a class is a two-term complex controlling deformations of the moduli space. Kontsevich conjectured in 1994 that there should exist derived version of spaces with this specific property. Another hint at the existence of these spaces comes from derived algebraic geometry. It is expected that for every pair of a space and a complex controlling deformations of the space their exists, under some additional hypothesis, a derived version of the space having the chosen complex as cotangent complex. In this thesis one version of these additional hypothesis is identified. We then show that every space admitting a two-term complex controlling deformations satisfies these hypothesis, and we finally construct the derived spaces.

The AustLit Gateway and Scholarly Bibliography: A Specialist Implementation of the FRBR

This paper discusses how the AustLit: Australian Literature Gateway's interpretation, enhancement, and implementation of the International Federation of Library Associations and Institutions' Functional Requirements for Bibliographic Records (FRBR Final Report 1998) model is meeting the needs of Australian literature scholars for accurate bibliographic representation of the histories of literary texts. It also explores how the AustLit Gateway's underpinning research principles, which are based on the tradition of scholarly enumerative and descriptive bibliography, with enhancements from analytical bibliography and literary biography, have impacted upon our implementation of the FRBR model. The major enhancement or alteration to the model is the use of enhanced manifestations, which allow the full representation of all agents' contributions to be shown in a highly granular format by enabling creation events to be incorporated at all levels of the Work, Expression, and Manifestation nexus.