Dissertationen zum Thema „Combinatorial exploration“

Tom Johnson is an American musician and composer living in Paris who regularly composes pieces based on combinatorial designs. He recently posed the following question: is there a way to construct five Room squares of side seven such that each of the thirty-five possible fill patterns is used exactly once? In this thesis we study his question and several related questions concerning the possible fill patterns in sets of Room squares of side 7 and 11. The second problem addressed in this thesis is a conjecture by Marco Buratti, a combinatorialist from the Universitia di Perusia, Italy. He conjectured that given p a prime and a multiset S containing p - 1 non-zero elements from Zp, there exists a Hamiltonian path in Kp where the multiset of edge lengths is S. Part of the motivation behind studying this particular problem is the possible application to constructing cyclic combinatorial designs. In this thesis we completely solve the case where S contains at most two distinct values.

At the intersection of algebraic geometry, number theory, and combinatorics, an interesting problem is counting points on an algebraic curve over a finite field. When specialized to the case of elliptic curves, this question leads to a surprising connection with a particular family of graphs. In this document, we present some of the underlying theory and then summarize recent results concerning the aforementioned relationship between elliptic curves and graphs. A few results are additionally further elucidated by theory that was omitted in their original presentation.

La chimie combinatoire dynamique a été récemment introduite comme une approche nouvelle et attractive pour générer et cribler un grand nombre de bibliothèques de composés en une seule étape. Basé sur l'interconnexion réversible entre les composés de la bibliothèque, le processus d'auto-ajustement donne accès à la sélection et à l'amplification du meilleur inhibiteur en présence d'une cible. Au cours de cette thèse, nous avons choisi deux cibles biologiques qui nous ont permis d'explorer l'approche de la chimie combinatoire dynamique. La réversibilité du système a été rendue possible en utilisant l'échange de disulfures ou la formation réversible d'acyl hydrazones. Premièrement, une bibliothèque dynamique d'inhibiteurs d'acétylcholinestérase a été générée grâce à l'échange de disulfures. Nous avons observé la réversibilité du système à l'aide de la spectroscopie de RMN. A partir d'un mélange initial de 5 homodisulfures en présence d'un agent réducteur, une bibliothèque contenant 15 composantes a été obtenue. Les composantes de cette bibliothèque ont été mises en évidence par SM-ES et par EC. Deuxièmement, une bibliothèque combinatoire dynamique d'inhibiteurs d'acétylcholinesterase a été générée en se basant sur la formation réversible d'acyl-hydrazones. Le processus pré-équilibré a été utilisé pour obtentir d'une bibliothèque dynamique composée de 66 espèces possibles, à partir de 13 unités de bases. Nous avons ensuite identifié l'inhibiteur très puissant (IC50 et Ki de l'ordre de nM), en utilisant la méthode de la déconvolution dynamique. Finalement, le processus pré-équilibré combiné à la technique de la déconvolution dynamique a été employé pour identifier les inhibiteurs de la HPr kinase/phosphatase. Ainsi, nous avons pu préparer une bibliothèque dynamique constituée de 440 composés possibles, en une seule étape, à partir de 21 unités de bases. Le ligand hétérocyclique bis-cationique s'est révélé un inhibiteur relativement puissant (IC50 de l'ordre de mM)
Dynamic combinatorial chemistry (DCC) has recently been introduced as a new and attractive approach for generating and screening large numbers of library compounds in one step. Based upon the reversible interconnection between library components, the self-adjusting process give access to selection and amplification of the best binder in the presence of a target. In this thesis, two biological targets were chosen to explore the DCC approach. The reversibility of the system was achieved using disulfide interchange or reversible acyl hydrazone formation. Firstly, a dynamic library of acetylcholinesterase inhibitors was generated through disulfide exchange. The reversibility of the system was observed by NMR spectroscopy. Upon scrambling 5 initial homodisulfides in the presence of a reducing agent, a 15-compound library was produced. The library components were analyzed by ESI-MS and CE. Secondly, a dynamic combinatorial library of acetylcholinesterase inhibitors was further generated through reversible acyl hydrazone formation. The pre-equilibrated process was applied to produce a dynamic library composed of 66 possible species, from a set of 13 initial aldehyde and hydrazide building blocks. Using a technique called dynamic deconvolution, a highly potent inhibitor was identified with IC50 in the nanomolar range. Finally, the pre-equilibrated process combined with the dynamic deconvolution technique was further studied to identify HPr kinase/phosphatase inhibitors. From a set of 21 initial aldehyde and hydrazide builiding blocks, a dynamic library of 440 possible compounds was formed in one operation. A bis-cationic heterocyclic ligand was identified as a relatively potent inhibitor, displaying an IC50 in the micromolar range

Thesis (M.S.) -- University of Maryland, College Park, 2004.
Thesis research directed by: Dept. of Materials Science and Engineering. Title from t.p. of PDF. Includes bibliographical references. Published by UMI Dissertation Services, Ann Arbor, Mich. Also available in paper.

Thesis (Ph.D)--Aerospace Engineering, Georgia Institute of Technology, 2009.
Committee Chair: Dr. Dimitri N. Mavris; Committee Member: Dr. Brian J. German; Committee Member: Dr. Daniel P. Schrage; Committee Member: Dr. Frederic Villeneuve; Committee Member: Dr. Michelle R. Kirby; Committee Member: Ms. Antje Lembcke. Part of the SMARTech Electronic Thesis and Dissertation Collection.

In the building automation domain, there are gaps among various tasks related to design engineering. As a result created system designs must be adapted to the given requirements on system functionality, which is related to increased costs and engineering effort than planned. For this reason standards are prepared to enable a coordination among these tasks by providing guidelines and unified artifacts for the design. Moreover, a huge variety of prefabricated devices offered from different manufacturers on the market for building automation that realize building automation functions by preprogrammed software components. Current methods for design creation do not consider this variety and design solution is limited to product lines of a few manufacturers and expertise of system integrators. Correspondingly, this results in design solutions of a limited quality. Thus, a great optimization potential of the quality of design solutions and coordination of tasks related to design engineering arises. For given design requirements, the existence of a high number of devices that realize required functions leads to a combinatorial explosion of design alternatives at different price and quality levels. Finding optimal design alternatives is a hard problem to which a new solution method is proposed based on heuristical approaches. By integrating problem specific knowledge into algorithms based on heuristics, a promisingly high optimization performance is achieved. Further, optimization algorithms are conceived to consider a set of flexibly defined quality criteria specified by users and achieve system design solutions of high quality. In order to realize this idea, optimization algorithms are proposed in this thesis based on goal-oriented operations that achieve a balanced convergence and exploration behavior for a search in the design space applied in different strategies. Further, a component model is proposed that enables a seamless integration of design engineering tasks according to the related standards and application of optimization algorithms.

Functional genetics is the study of the genes present in a genome of an organism, the complex interplay of all genes and their environment being the primary focus of study. The motivation for such studies is the premise that gene expression patterns in a cell are characteristic of its current state. The availability of the entire genome for many organisms now allows scientists unparalleled opportunities to characterize, classify, and manipulate genes or gene networks involved in metabolism, cellular differentiation, development, and disease. System-wide studies of biological systems have been made possible by the advent of high-throughput and large-scale tools such as microarrays which are capable of measuring the mRNA levels of all genes in a genome. Tools and methods for the integration, visualization, and modeling of the large-scale data obtained in typical systems biology experiments are indispensable. Our work focuses on a method that integrates gene expression values obtained from microarray experiments with biological functional information related to the genes measured in order to make global comparisons of multiple experiments. In our method, the integrated data is represented as a lattice and, using appropriate measures, a reference experiment can be compared to samples from a database of similar experiments, and a ranking of similarity is returned. In this work, support for the validity of our method is demonstrated both theoretically and empirically: a mathematical description of the lattice structure with respect to the integrated information is developed and the method is applied to data sets of both simulated and reported microarray experiments. A fast algorithm for constructing the lattice representation is also developed.
Ph. D.

Dans le cadre de l’aide à l’analyse de dialogues, un corpus de dialogues peut être représenté par un ensemble de tableaux d’annotations encodant les différents énoncés des dialogues. Afin d’identifier des schémas dialogiques mis en oeuvre fréquemment, nous définissons une méthodologie en deux étapes : extraction de motifs récurrents, puis partitionnement de ces motifs en classes homogènes constituant ces régularités. Deux méthodes sont développées afin de réaliser l’extraction de motifs récurrents : LPCADC et SABRE. La première est une adaptation d’un algorithme de programmation dynamique tandis que la seconde est issue d’une modélisation formelle du problème d’extraction d’alignements locaux dans un couple de tableaux d’annotations.Le partitionnement de motifs récurrents est réalisé par diverses heuristiques de la littérature ainsi que deux formulations originales du problème de K-partitionnement sous la forme de programmes linéaires en nombres entiers. Lors d’une étude polyèdrale, nous caractérisons des facettes d’un polyèdre associé à ces formulations (notamment les inégalités de 2-partitions, les inégalités 2-chorded cycles et les inégalités de clique généralisées). Ces résultats théoriques permettent la mise en place d’un algorithme de plans coupants résolvant efficacement le problème.Nous développons le logiciel d’aide à la décision VIESA, mettant en oeuvre ces différentes méthodes et permettant leur évaluation au cours de deux expérimentations réalisées par un expert psychologue. Des régularités correspondant à des stratégies dialogiques que des extractions manuelles n’avaient pas permis d’obtenir sont ainsi identifiées
In the context of dialogue analysis, a corpus of dialogues can be represented as a set of arrays of annotations encoding the dialogue utterances. In order to identify the frequently used dialogue schemes, we design a two-step methodology in which recurrent patterns are first extracted and then partitioned into homogenous classes constituting the regularities. Two methods are developed to extract recurrent patterns: LPCA-DC and SABRE. The former is an adaptation of a dynamic programming algorithm whereas the latter is obtained from a formal modeling of the extraction of local alignment problem in annotations arrays.The partitioning of recurrent patterns is realised using various heuristics from the literature as well as two original formulations of the K-partitioning problem in the form of mixed integer linear programs. Throughout a polyhedral study of a polyhedron associated to these formulations, facets are characterized (in particular: 2-chorded cycle inequalities, 2-partition inequalities and general clique inequalities). These theoretical results allow the establishment of an efficient cutting plane algorithm.We developed a decision support software called VIESA which implements these different methods and allows their evaluation during two experiments realised by a psychologist. Thus, regularities corresponding to dialogical strategies that previous manual extractions failed to identify are obtained

Cette thèse présente le résultat de recherches sur deux thèmes combinatoires distincts: le calcul effectif des matrices de Cartan en théorie des représentations des monoïdes et l'exploration des propriétés des éléments minimaux dans les arrangements de Shi des groupes de Coxeter. Bien que disparates, ces deux domaines de recherche partagent l'utilisation de méthodes combinatoires et d'exploration informatique, soit en tant que fin en soi pour le premier domaine, soit comme aide à la recherche pour le second. Dans la première partie de la thèse, nous développons des méthodes pour le calcul effectif des tables de caractères et des matrices de Cartan dans la théorie des représentations des monoïdes. À cette fin, nous présentons un algorithme basé sur nos résultats pour le calcul efficace des points fixes sous une action similaire à une conjugaison, dans le but de mettre en œuvre la formule de [Thiéry '12] pour la matrice de Cartan. Après une introduction largement auto-contenue aux notions nécessaires, nous présentons nos résultats sur le comptage des points fixes, ainsi qu'une nouvelle formule pour la table de caractères des monoïdes finis. Nous évaluons les performances des algorithmes résultants en termes de temps d'exécution et d'utilisation mémoire. Nous observons qu'ils sont plus efficaces par plusieurs ordres de grandeur que les algorithmes non spécialisés pour les monoïdes. Nous espérons que l'implémentation (publique) résultant de ces travaux contribuera à la communauté des représentations des monoïdes en permettant des calculs auparavant difficiles. La deuxième partie de la thèse se concentre sur les propriétés des éléments minimaux dans les arrangements de Shi. Les arrangements de Shi ont été introduits dans [Shi '87] et sont l'objet de la Conjecture 2 dans [Dyer, Hohlweg '14]. Initialement motivés par cette conjecture, après une introduction aux notions nécessaires, nous présentons deux résultats. Premièrement, une démonstration directe dans le cas des groupes de rang 3. Deuxièmement, dans le cas particulier des groupes de Weyl, nous donnons une description des éléments minimaux des régions de Shi en étendant une bijection issue de [Athanasiadis, Linusson '99] et [Armstrong, Reiner, Rhoades '15] entre les fonctions de parking et les régions de Shi permettant d'effectuer le calcul pratique des éléments minimaux. Comme application, à partir des propriétés de ce calcul, nous donnons une démonstration de la conjecture pour les groupes de Weyl indépendante de leur classification. Ces résultats révèlent une interaction intrigante entre les partitions non-croisées et non-embrassées dans le cas des groupes de Weyl classiques
This thesis presents an investigation into two distinct combinatorial subjects: the effective computation of Cartan matrices in monoid representation theory and the exploration of properties of minimal elements in Shi arrangements of Coxeter groups. Although disparate, both of these research focuses share a commonality in the utilization of combinatorial methods and computer exploration either as an end in itself for the former or as a help to research for the latter. In the first part of the dissertation, we develop methods for the effective computation of character tables and Cartan matrices in monoid representation theory. To this end, we present an algorithm based on our results for the efficient computations of fixed points under a conjugacy-like action, with the goal to implement Thiéry's formula for the Cartan matrix from [Thiéry '12]. After a largely self-contained introduction to the necessary background, we present our results for fixed-point counting, as well as a new formula for the character table of finite monoids. We evaluate the performance of the resulting algorithms in terms of execution time and memory usage and find that they are more efficient than algorithms not specialized for monoids by orders of magnitude. We hope that the resulting (public) implementation will contribute to the monoid representation community by allowing previously impractical computations. The second part of the thesis focuses on the properties of minimal elements in Shi arrangements. The Shi arrangements were introduced in [Shi '87] and are the object of Conjecture 2 from [Dyer, Hohlweg '14]. Originally motivated by this conjecture, we present two results. Firstly, a direct proof in the case of rank 3 groups. Secondly, in the special case of Weyl groups, we give a description of the minimal elements of the Shi regions by extending a bijection from [Athanasiadis, Linusson '99] and [Armstrong, Reiner, Rhoades '15] between parking functions and Shi regions. This allows for the effective computation of the minimal elements. From the properties of this computation, we provide a type-free proof of the conjecture in Weyl groups as an application. These results reveal an intriguing interplay between the non-nesting and non-crossing worlds in the case of classical Weyl groups

Submitted by Jean Medeiros (jeanletras@uepb.edu.br) on 2016-12-09T12:17:44Z No. of bitstreams: 1 PDF - Adriano Alves de Silveira.pdf: 5754090 bytes, checksum: 3f1ff5d850c2e62808aa80d8184050a0 (MD5)
Approved for entry into archive by Secta BC (secta.csu.bc@uepb.edu.br) on 2017-02-02T18:18:37Z (GMT) No. of bitstreams: 1 PDF - Adriano Alves de Silveira.pdf: 5754090 bytes, checksum: 3f1ff5d850c2e62808aa80d8184050a0 (MD5)
Made available in DSpace on 2017-02-02T18:18:37Z (GMT). No. of bitstreams: 1 PDF - Adriano Alves de Silveira.pdf: 5754090 bytes, checksum: 3f1ff5d850c2e62808aa80d8184050a0 (MD5) Previous issue date: 2016-10-06
Coordenação de Aperfeiçoamento de Pessoal de Nível Superior - CAPES
This research analyses how an approach in the classroom via Problem Solving, Exploration and Posing can potentialize the teaching and learning of Combinatorial Analysis. A literature review was performed aiming to understand the contributions of other researchers on the researched theme, so that it could be possible to realize what is possible to deepen and add for the scientific community, regarding the teaching and learning process of the Combinatorial Analysis. Besides this, an interview with mathematics teachers was performed, aiming to know their ideas on teaching and learning of Combinatory Analysis and, afterwards, scrutinize until where they could help to plan a sequence of activities. The research was conducted according to a qualitative approach, aiming to search meanings, interpreting and comprehend the information obtained. The modality of research can be characterized as teacher research; according to which the professor is the researcher of his or her own classroom (LANKSHEAR AND KNOBEL, 2008). The teaching and learning Methodology chosen to work in the classroom was the one of the problem solving, exploration and posing, developed with a sequence of activities in a group of the 2nd year of Secondary School of a public school in the city of Alagoinha-PB, Brazil. During the intervention, this researcher acted as a researcher teacher, working in the classroom as a regent teacher, giving a utonomy to the students on the construction of the essential ideas of the Combinatory Analysis, in such a way that the author acted as a mediator and instigator. Data were collected during the lessons through observation and records of the materials used by the students, as well as sound recording. Twenty-one meetings were performed, totaling 25 lessons, each lesson lasting, at most, 45 minutes. The classroom was organized in groups of three students and, in some cases, in pairs, in order to carry out a cooperative and collaborative work, where it was considered important, in this process, the mutual respect among them, respecting the ideas arisen on the search of the problem solution. The results of the research highlighted that through the Mathematics teaching and learning approach via Problem Solving, Exploration and Posing it was possible to monitor the growth of the students, who created their own ideas to solve the problems, and, consequently, found multiple strategies for solution of them; posteriorly, justify their solutions, participating effectively of the construction of their knowledge. Besides this, the students engaged in activities of mathematical exploration, which enabled the comprehension of the essential ideas of Combinatorial Analysis, as well as assuming the role of investigators in the classroom, generalizing, formulating new problems and, afterwards, solving them. From which it follows that such methodology allows learning with more comprehension, strengthening the student to solve problems of Combinatorial Analysis with focus not only on the search of the problem solution, but also on the process of the solution and being able to go far beyond, like the performance of a work of problem posing and exploration.
A presente pesquisa analisa como uma abordagem em sala de aula via Resolução, Exploração e Proposição de problemas pode contribuir/potencializar com o ensino-aprendizagem de Análise Combinatória. Foi realizada uma revisão de literatura com o intuito de compreender as contribuições de outros pesquisadores acerca do tema pesquisado, para que se pudesse perceber o que é possível aprofundar e acrescentar para a comunidade científica, no que diz respeito ao processo de ensino-aprendizagem da Análise Combinatória. Além disso, foi realizada uma entrevista com professores de Matemática, com o intuito de conhecer as suas ideias acerca do ensino-aprendizagem de Combinatória e, posteriormente, perscrutar até que ponto elas poderiam colaborar a planejar uma sequência de atividades. A pesquisa foi empreendida segundo uma abordagem qualitativa, visando buscar significados, interpretar e compreender as informações obtidas. A modalidade de pesquisa pode ser caracterizada como pedagógica, segundo a qual o professor é o pesquisador de sua própria sala de aula (LANKSHEAR E KNOBEL, 2008). A Metodologia de ensino-aprendizagem escolhida para trabalhar em sala de aula foi a de resolução, exploração e proposição de problemas, desenvolvida com uma sequência de atividades em uma turma do 2ª ano do Ensino Médio de uma escola pública na cidade de Alagoinha-PB. Durante a intervenção, o presente pesquisador agiu como professor-pesquisador, trabalhando em sala de aula como professor regente, dando autonomia aos alunos na construção das ideias essenciais de Combinatória, de modo que o autor agiu como mediador e incentivador. Os dados foram levantados durante as aulas através das observações e registros dos materiais utilizados pelos alunos, bem como de gravação sonora. Foram realizados 21 encontros, totalizando 25 aulas, cada aula com duração de, no máximo, 45 minutos. A sala foi organizada em grupos de três alunos e, em alguns casos, em duplas, com o intuito de se realizar um trabalho cooperativo e colaborativo, onde se considerou importante, nesse processo, o respeito mútuo entre eles, respeitando as ideias levantadas na busca da solução dos problemas. Os resultados da pesquisa evidenciaram que através da abordagem via Resolução, Exploração e Proposição de problemas foi possível acompanhar o crescimento dos alunos, que criaram suas próprias ideias para resolver os problemas, e, consequentemente, encontraram múltiplas estratégias de resolução deles; posteriormente, justificam suas soluções, participando efetivamente da construção do seu conhecimento. Além disso, os alunos engajaram-se em atividades de exploração matemática que lhes possibilitaram a apreensão de ideias essenciais de Análise Combinatória, como também assumiram o papel de investigadores em sala de aula, fazendo generalizações, formulando novos problemas e, em seguida, os resolvendo. De onde se conclui que tal metodologia permitiu um aprendizado com mais compreensão, potencializando o aluno para resolver problemas de Análise Combinatória com foco não apenas na busca da solução do problema, mas no processo da resolução e podendo ir muito além, como a realização de um trabalho de proposição e exploração de problemas.

Thesis (Ph. D.)--University of Missouri-Columbia, 2008.
The entire dissertation/thesis text is included in the research.pdf file; the official abstract appears in the short.pdf file (which also appears in the research.pdf); a non-technical general description, or public abstract, appears in the public.pdf file. Title from title screen of research.pdf file (viewed on June 8, 2009) Vita. Includes bibliographical references.

Une carte combinatoire est un modèle topologique qui permet de représenter les subdivisions de l'espace en cellules et les relations d'adjacences et d'incidences entre ces cellules en n dimensions. Cette structure de données est de plus en plus utilisée en traitement d'images, mais elle manque encore d'outils pour les analyser. Notre but est de définir de nouveaux outils pour les cartes combinatoires nD. Nous nous intéressons plus particulièrement à l'extraction de sous-cartes fréquentes dans une base de cartes. Nous proposons deux signatures qui sont également des formes canoniques de cartes combinatoires. Ces signatures ont chacune leurs avantages et leurs inconvénients. La première permet de décider de l'isomorphisme entre deux cartes en temps linéaire, en contrepartie le coût de stockage en mémoire est quadratique en la taille de la carte. La seconde signature a un coût de stockage en mémoire linéaire en la taille de la carte, cependant le temps de calcul de l'isomorphisme est quadratique. Elles sont utilisables à la fois pour des cartes connexes, non connexes, valuées ou non valuées. Ces signatures permettent de représenter une base de cartes combinatoires et de rechercher un élément de manière efficace. De plus, le temps de recherche ne dépend pas du nombre de cartes présent dans la base. Ensuite, nous formalisons le problème de recherche de sous-cartes fréquentes dans une base de cartes combinatoires nD. Nous implémentons deux algorithmes pour résoudre ce problème. Le premier algorithme extrait les sous-cartes fréquentes par une approche en largeur tandis que le second utilise une approche en profondeur. Nous comparons les performances de ces deux algorithmes sur des bases de cartes synthétiques. Enfin, nous proposons d'utiliser les motifs fréquents dans une application de classification d'images. Chaque image est décrite par une carte qui est transformée en un vecteur représentant le nombre d'occurrences des motifs fréquents. À partir de ces vecteurs, nous utilisons des techniques classiques de classification définies sur les espaces vectoriels. Nous proposons des expérimentations en classification supervisée et non supervisée sur deux bases d'images.

En biologie des systèmes, l'analyse des voies métaboliques est une méthode essentielle pour étudier le métabolisme et améliorer la compréhension du fonctionnement des systèmes vivants. Deux concepts clés sont l'analyse des modes élémentaires de flux (EFMs), qui permet de décrire les réseaux métaboliques en termes de voies minimales, et les Minimal Cut Sets (MCSs), représentant les coupures minimales de flux du réseau en termes de réactions. Dans le cadre de cette thèse, nous avons développé une méthode de programmation logique pour le calcul des modes élémentaires de flux: aspefm. L'outil est une méthode de raisonnement automatique à base de Answer Set Programming (ASP), étendue par des contraintes linéaires. Cette approche permet de récupérer des voies lorsque les méthodes classiques ne le peuvent pas, d'interroger directement le réseau et d'éviter l'explosion en mémoire. La méthode peut prendre en compte des contraintes biologiques importantes de tous types, ce que nous avons illustré sur un réseau central d'Escherichia coli. Elle est aussi applicable aux réseaux à l'échelle du génome, et calcule plus aisément des solutions de large taille que les méthodes à base de programmation linéaire. Notre méthode a été appliquée, à la bactérie pathogène Pseudomonas aeruginosa (PA) qui est présente dans 80% des plaies chroniques. PA utilise des stratégies écologiques différentes de celles des bactéries modèles comme E. coli. Elle est retrouvée généralement dans les plaies chroniques avec une autre bactérie infectieuse, Staphylococcus aureus (SA). Nous supposons que leurs deux métabolismes sont complémentaires, ce qui permet une production de biomasse plus élevée conduisant à des mauvais pronostics pour les patients. L'extension de notre outil aspefm à l'analyse des MCSs sur un modèle de consortium de ces deux bactéries nous a permis de retrouver des métabolites dont l'échange entre les deux bactéries permettrait de compenser des phénotypes prédits létaux, ainsi que d'explorer des cibles thérapeutiques potentielles contre les bactéries. Par ailleurs, dans un autre cadre, nous avons appliqué notre méthode de calcul au métabolisme de la cellule cancéreuse humaine et à la formation du stroma tumoral
In systems biology, metabolic pathways analysis is an essential method to study metabolism and improve the understanding of biological systems. Key concepts include Elementary Flux Modes (EFMs), describing metabolic networks in terms of minimal pathways, and Minimal Cut Sets (MCSs), representing minimal cutting sets of reactions affecting network flux. In the scope of this thesis, we developed a logic programming method for the computation of Elementary Flux Modes: aspefm. The tool is an automatic reasoning method based on Answer Set Programming (ASP), extended by linear constraints. This approach allows one to get minimal pathways when classical methods are unable to, and to directly query the network, helping with memory usage considerations. Important biological constraints of many different kinds can be integrated into the program, which we illustrated on a central metabolic model of Escherichia coli. The method is also applicable to genome-scale metabolic models, showing better performance than linear programming-based methods on enumeration of large-size solutions. The method was applied to the pathogenic bacterium Pseudomonas aeruginosa (PA) found in 80% of chronic wounds. PA uses different ecological strategies than model bacteria. PA is commonly co-isolated from wounds with another opportunistic pathogen, Staphylococcus aureus (SA), and it is hypothesized the metabolisms of the two bacteria are complementary enabling higher biomass production and increasing wound bioburden leading to poor patient outcomes. We extended our tool aspefm to the analysis of MCSs on a consortium model of these two bacteria, permitting us to retrieve exchanged metabolites involved in the recovery of growth after several intervention strategies, and leading to insights about potential therapeutic targets against the two bacteria. Furthermore, in an other context, we applied our computation method to cancer cell metabolism and tumoural stroma formation

Nous abordons trois axes de la combinatoire algébrique et énumérative. Le premier concerne principalement la recherche d'un contre-exemple à la conjecture commutativement équivalente. Proposée dans les années soixante, elle conjecture que les codes non commutativement préfixes ne sont pas inclus dans des codes maximaux finis. La stratégie que nous adoptons est de d'abord trouver des codes non commutativement préfixes puis de chercher des codes maximaux finis susceptibles de les contenir. Nous donnons une caractérisation, raffinant l'inégalité de Kraft-Redheffer, des ensembles commutativement préfixes. Grâce à l’algorithme qui en découle, nous trouvons 70 codes non commutativement préfixes. Certains d'entre eux améliorent la borne inférieure qui était connue pour le problème du ratio de Shor. De plus, 7 de ces codes se projettent dans des factorisations de groupes cycliques, chose dont nous ignorions jusqu'à présent l'existence. Grâce aux raisonnements classiques de la théorie des factorisations des groupes cycliques, nous calculons des bornes inférieures sur les tailles des codes maximaux finis susceptibles de les contenir. Nous introduisons également la notion de "code modulaire baïonnette complet". Elle nous permet notamment d'améliorer certaines de ces bornes inférieures et de trouver les premiers exemples de codes non commutativement préfixes et non inclus dans des codes maximaux finis. Le deuxième axe de recherche porte sur la combinatoire des circuits. Nous dénombrons les circuits selon la nature de leurs générateurs, leurs nombre de générateurs, leurs nombre d’entrées et leurs nombre de sorties. La principale difficulté que nous rencontrons provient de l’ambiguïté de la grammaire qui définie les circuits. Nous présentons une nouvelle grammaire, issue d'une construction combinatoire et algébrique, non ambiguë qui les engendre. Nous en déduisons une bijection entre les circuits et des familles de chemins colorés en trois dimensions. En étudiant la combinatoire de ces chemins, nous obtenons des formules de récurrences, des équations fonctionnelles et des formules closes sur les circuits. Le dernier axe de recherche de cette thèse porte sur la réécriture dans des quotients magmatiques. Nous caractérisons tous les morphismes d'opérades peignes et nous en exhibons une structure de treillis. Nous étudions ensuite les 10 quotients magmatiques où deux arbres de degré 3 sont confondus. Pour 8 d'entre eux, nous en donnons des présentations convergentes, leurs séries de Hilbert et des réalisations combinatoires. Pour les 2 autres ainsi que pour les opérades peignes de degré supérieur à 4, nous conjecturons à partir de plusieurs explorations informatiques qu'ils ne possèdent pas de présentations convergentes
We study three domains of algebraic and enumerative combinatorics. Firstly, we are looking for a counter-example to the commutatively equivalence conjecture. Stated in the Sixties, it conjectures that a not commutatively prefix code is not included in a finite maximal code. First, we find some not commutatively prefix codes and then we search for some finite maximal codes that might contain them. Thanks to a refinement of Kraft's inequality that we have proven, we found mostly by computer exploration 70 not commutatively prefix codes. Some of them improve a lower bound from Shor or embedded in some factorizations of cyclic groups. Thanks to classical studies on factorizations of cyclic groups, we compute some lower bounds for the size of finites maximals codes that might contains them. We introduce the notion of "complete modular bayonet code", in order to compute the first examples of not commutatively prefix codes that are not included in a finite maximal code. Secondly, we present and prove a new construction of prographs. We deduce from it a bijection between prographs and some families of three-dimensional colouredlattice paths. By a classical study of these lattice paths, we obtain recurrence relations satisfied by the prographs and a functional equation satisfied by the generating series of prographs. Finally, we compute some closed formulas for prographs made of only one type of generators. Finally, we conclude this thesis by a study of magmatic quotient. Driven by computer experimentations, we study the 10 quotients of the magmatic operad by one cubic relation by expressing their Hilbert series and providing combinatorial realizations. Moreover, we found all morphisms between comb operads and we exhibit a lattice structure over them

The Aldous order is an ordering of representations of the symmetric group motivated by the Aldous Conjecture, a conjecture about random processes proved in 2009. In general, the Aldous order is very difficult to compute, and the proper relations have yet to be determined even for small cases. However, by restricting the problem down to Young-Jucys-Murphy elements, the problem becomes explicitly combinatorial. This approach has led to many novel insights, whose proofs are simple and elegant. However, there remain many open questions related to the Aldous Order, both in general and for the Young-Jucys-Murphy elements.

Les modèles de Markov d’ordre 2 (HMM2) sont des modèles stochastiques qui ont démontré leur efficacité dans l’exploration de séquences génomiques. Cette thèse explore l’intérêt de modèles de différents types (M1M2, M2M2, M2M0) ainsi que leur couplage à des méthodes combinatoires pour segmenter les génomes bactériens sans connaissances a priori du contenu génétique. Ces approches ont été appliquées à deux modèles bactériens afin d’en valider la robustesse : Streptomyces coelicolor et Streptococcus thermophilus. Ces espèces bactériennes présentent des caractéristiques génomiques très distinctes (composition, taille du génome) en lien avec leur écosystème spécifique : le sol pour les S. coelicolor et le milieu lait pour S. thermophilus
Second-order Hidden Markov Models (HMM2) are stochastic processes with a high efficiency in exploring bacterial genome sequences. Different types of HMM2 (M1M2, M2M2, M2M0) combined to combinatorial methods were developed in a new approach to discriminate genomic regions without a priori knowledge on their genetic content. This approach was applied on two bacterial models in order to validate its achievements: Streptomyces coelicolor and Streptococcus thermophilus. These bacterial species exhibit distinct genomic traits (base composition, global genome size) in relation with their ecological niche: soil for S. coelicolor and dairy products for S. thermophilus. In S. coelicolor, a first HMM2 architecture allowed the detection of short discrete DNA heterogeneities (5-16 nucleotides in size), mostly localized in intergenic regions. The application of the method on a biologically known gene set, the SigR regulon (involved in oxidative stress response), proved the efficiency in identifying bacterial promoters. S. coelicolor shows a complex regulatory network (up to 12% of the genes may be involved in gene regulation) with more than 60 sigma factors, involved in initiation of transcription. A classification method coupled to a searching algorithm (i.e. R’MES) was developed to automatically extract the box1-spacer-box2 composite DNA motifs, structure corresponding to the typical bacterial promoter -35/-10 boxes. Among the 814 DNA motifs described for the whole S. coelicolor genome, those of sigma factors (B, WhiG) could be retrieved from the crude data. We could show that this method could be generalized by applying it successfully in a preliminary attempt to the genome of Bacillus subtilis

L'extraction de sous-structures significatives a toujours été un élément clé de l’étude des graphes. Dans le cadre de l'apprentissage automatique, supervisé ou non, ainsi que dans l'analyse théorique des graphes, trouver des décompositions spécifiques et des sous-graphes denses est primordial dans de nombreuses applications comme entre autres la biologie ou les réseaux sociaux.Dans cette thèse, nous cherchons à étudier la dégénérescence de graphe, en partant d'un point de vue théorique, et en nous appuyant sur nos résultats pour trouver les décompositions les plus adaptées aux tâches à accomplir. C'est pourquoi, dans la première partie de la thèse, nous travaillons sur des résultats structurels des graphes à arête-admissibilité bornée, prouvant que de tels graphes peuvent être reconstruits en agrégeant des graphes à degré d’arête quasi-borné. Nous fournissons également des garanties de complexité de calcul pour les différentes décompositions de la dégénérescence, c'est-à-dire si elles sont NP-complètes ou polynomiales, selon la longueur des chemins sur lesquels la dégénérescence donnée est définie.Dans la deuxième partie, nous unifions les cadres de dégénérescence et d'admissibilité en fonction du degré et de la connectivité. Dans ces cadres, nous choisissons les plus expressifs, d'une part, et les plus efficaces en termes de calcul d'autre part, à savoir la dégénérescence 1-arête-connectivité pour expérimenter des tâches de dégénérescence standard, telle que la recherche d’influenceurs.Suite aux résultats précédents qui se sont avérés peu performants, nous revenons à l'utilisation du k-core mais en l’intégrant dans un cadre supervisé, i.e. les noyaux de graphes. Ainsi, en fournissant un cadre général appelé core-kernel, nous utilisons la décomposition k-core comme étape de prétraitement pour le noyau et appliquons ce dernier sur chaque sous-graphe obtenu par la décomposition pour comparaison. Nous sommes en mesure d'obtenir des performances à l’état de l’art sur la classification des graphes au prix d’une légère augmentation du coût de calcul.Enfin, nous concevons un nouveau cadre de dégénérescence de degré s’appliquant simultanément pour les hypergraphes et les graphes biparties, dans la mesure où ces derniers sont les graphes d’incidence des hypergraphes. Cette décomposition est ensuite appliquée directement à des architectures de réseaux de neurones pré-entrainés étant donné qu'elles induisent des graphes biparties et utilisent le core d'appartenance des neurones pour réinitialiser les poids du réseaux. Cette méthode est non seulement plus performant que les techniques d'initialisation de l’état de l’art, mais il est également applicable à toute paire de couches de convolution et linéaires, et donc adaptable à tout type d'architecture
Extracting Meaningful substructures from graphs has always been a key part in graph studies. In machine learning frameworks, supervised or unsupervised, as well as in theoretical graph analysis, finding dense subgraphs and specific decompositions is primordial in many social and biological applications among many others.In this thesis we aim at studying graph degeneracy, starting from a theoretical point of view, and building upon our results to find the most suited decompositions for the tasks at hand.Hence the first part of the thesis we work on structural results in graphs with bounded edge admissibility, proving that such graphs can be reconstructed by aggregating graphs with almost-bounded-edge-degree. We also provide computational complexity guarantees for the different degeneracy decompositions, i.e. if they are NP-complete or polynomial, depending on the length of the paths on which the given degeneracy is defined.In the second part we unify the degeneracy and admissibility frameworks based on degree and connectivity. Within those frameworks we pick the most expressive, on the one hand, and computationally efficient on the other hand, namely the 1-edge-connectivity degeneracy, to experiment on standard degeneracy tasks, such as finding influential spreaders.Following the previous results that proved to perform poorly we go back to using the k-core but plugging it in a supervised framework, i.e. graph kernels. Thus providing a general framework named core-kernel, we use the k-core decomposition as a preprocessing step for the kernel and apply the latter on every subgraph obtained by the decomposition for comparison. We are able to achieve state-of-the-art performance on graph classification for a small computational cost trade-off.Finally we design a novel degree degeneracy framework for hypergraphs and simultaneously on bipartite graphs as they are hypergraphs incidence graph. This decomposition is then applied directly to pretrained neural network architectures as they induce bipartite graphs and use the coreness of the neurons to re-initialize the neural network weights. This framework not only outperforms state-of-the-art initialization techniques but is also applicable to any pair of layers convolutional and linear thus being applicable however needed to any type of architecture

Cette thèse porte sur trois problèmes en combinatoire algébrique effective et algorithmique.Les premières parties proposent une approche alternative aux bases de Gröbner pour le calcul des invariants secondaires des groupes de permutations, par évaluation en des points choisis de manière appropriée. Cette méthode permet de tirer parti des symétries du problème pour confiner les calculs dans un quotient de petite dimension, et ainsi d'obtenir un meilleur contrôle de la complexité algorithmique, en particulier pour les groupes de grande taille. L'étude théorique est illustrée par de nombreux bancs d'essais utilisant une implantation fine des algorithmes. Un prérequis important est la génération efficace de vecteurs d'entiers modulo l'action d'un groupe de permutation, dont l'algorithmique fait l'objet d'une partie préliminaire.La quatrième partie cherche à déterminer, pour un certain quotient naturel d'une algèbre de Hecke affine, quelles spécialisations des paramètres aux racines de l'unité donne un comportement non générique.Finalement, la dernière partie présente une conjecture sur la structure d'une certaine $q$-déformation des polynômes harmoniques diagonaux en plusieurs paquets de variables pour la famille infinie de groupes de réflexions complexes.Tous ces chapitres s'appuient fortement sur l'exploration informatique, et font l'objet de multiples contributions au logiciel Sage
This thesis concerns algorithmic approaches to three challenging problems in computational algebraic combinatorics.The firsts parts propose a Gröbner basis free approach for calculating the secondary invariants of a finite permutation group, proceeding by using evaluation at appropriately chosen points. This approach allows for exploiting the symmetries to confine the calculations into a smaller quotient space, which gives a tighter control on the algorithmic complexity, especially for large groups. The theoretical study is illustrated by extensive benchmarks using a fine implementation of algorithms. An important prerequisite is the generation of integer vectors modulo the action of a permutation group, whose algorithmic constitute a preliminary part of the thesis.The fourth part of this thesis is determining for a certain interesting quotient of an affine Hecke algebra exactly which root-of-unity specialization of its parameter lead to non-generic behavior.Finally, the last part presents a conjecture on the structure of certain q-deformed diagonal harmonics in many sets of variables for the infinite family of complex reflection groups.All chapters proceed widely by computer exploration, and most of established algorithms constitute contributions of the software Sage

Les problèmes d’optimisation combinatoire sont devenus la cible de nombreuses recherches scientifiques pour leur importance dans la résolution de problèmes académiques et de problèmes réels rencontrés dans le domaine de l’ingénierie et dans l’industrie. La résolution de ces problèmes par des méthodes exactes ne peut être envisagée à cause des délais de traitement souvent exorbitants que nécessiteraient ces méthodes pour atteindre la (les) solution(s) optimale(s). Dans cette thèse, nous nous sommes intéressés au contexte algorithmique de résolution des problèmes combinatoires, et au contexte de modélisation de ces problèmes. Au niveau algorithmique, nous avons appréhendé les méthodes hybrides qui excellent par leur capacité à faire coopérer les méthodes exactes et les méthodes approchées afin de produire rapidement des solutions. Au niveau modélisation, nous avons travaillé sur la spécification et la résolution exacte des problématiques complexes de fouille des ensembles de motifs en étudiant tout particulièrement le passage à l’échelle sur des bases de données de grande taille. D'une part, nous avons proposé une première parallélisation de l'algorithme DGVNS, appelée CPDGVNS, qui explore en parallèle les différents clusters fournis par la décomposition arborescente en partageant la meilleure solution trouvée sur un modèle maître-travailleur. Deux autres stratégies, appelées RADGVNS et RSDGVNS, ont été proposées qui améliorent la fréquence d'échange des solutions intermédiaires entre les différents processus. Les expérimentations effectuées sur des problèmes combinatoires difficiles montrent l'adéquation et l'efficacité de nos méthodes parallèles. D'autre part, nous avons proposé une approche hybride combinant à la fois les techniques de programmation linéaire en nombres entiers (PLNE) et la fouille de motifs. Notre approche est complète et tire profit du cadre général de la PLNE (en procurant un haut niveau de flexibilité et d’expressivité) et des heuristiques spécialisées pour l’exploration et l’extraction de données (pour améliorer les temps de calcul). Outre le cadre général de l’extraction des ensembles de motifs, nous avons étudié plus particulièrement deux problèmes : le clustering conceptuel et le problème de tuilage (tiling). Les expérimentations menées ont montré l’apport de notre proposition par rapport aux approches à base de contraintes et aux heuristiques spécialisées
Combinatorial optimization problems have become the target of many scientific researches for their importance in solving academic problems and real problems encountered in the field of engineering and industry. Solving these problems by exact methods is often intractable because of the exorbitant time processing that these methods would require to reach the optimal solution(s). In this thesis, we were interested in the algorithmic context of solving combinatorial problems, and the modeling context of these problems. At the algorithmic level, we have explored the hybrid methods which excel in their ability to cooperate exact methods and approximate methods in order to produce rapidly solutions of best quality. At the modeling level, we worked on the specification and the exact resolution of complex problems in pattern set mining, in particular, by studying scaling issues in large databases. On the one hand, we proposed a first parallelization of the DGVNS algorithm, called CPDGVNS, which explores in parallel the different clusters of the tree decomposition by sharing the best overall solution on a master-worker model. Two other strategies, called RADGVNS and RSDGVNS, have been proposed which improve the frequency of exchanging intermediate solutions between the different processes. Experiments carried out on difficult combinatorial problems show the effectiveness of our parallel methods. On the other hand, we proposed a hybrid approach combining techniques of both Integer Linear Programming (ILP) and pattern mining. Our approach is comprehensive and takes advantage of the general ILP framework (by providing a high level of flexibility and expressiveness) and specialized heuristics for data mining (to improve computing time). In addition to the general framework for the pattern set mining, two problems were studied: conceptual clustering and the tiling problem. The experiments carried out showed the contribution of our proposition in relation to constraint-based approaches and specialized heuristics

Le travail que nous développons dans le cadre de cette thèse s'articule autour des problèmes de recherche de structure de recouvrement de graphes sous contrainte sur le degré des sommets. Comme l'arbre de recouvrement couvre les sommets d'un graphe connexe avec un minimum de liens, il est généralement proposé comme solution à ce type de problèmes. Cependant, pour certaines applications telles que le routage dans les réseaux optiques, les solutions ne sont pas nécessairement des sous-graphes. Nous supposons dans cette thèse que la contrainte sur le degré est due à une capacité limitée instantanée des sommets et que la seule exigence sur le recouvrement est sa connexité. Dans ce cas, la solution peut être différente d'un arbre. Nous reformulons ces problèmes de recouvrement en nous appuyant sur une extension du concept d'arbre appelée hiérarchie de recouvrement. Notre objectif principal est de démontrer son intérêt vis-à-vis de l'arbre en termes de faisabilité et de coût du recouvrement. Nous considérons deux types de contraintes sur le degré : des bornes sur le degré des sommets ou une borne sur le nombre de sommets de branchement et cherchons dans les deux cas un recouvrement de coût minimum. Nous illustrons aussi l'applicabilité des hiérarchies en étudiant un problème prenant davantage en compte la réalité du routage optique. Pour ces différents problèmes NP-difficiles, nous montrons, tant sur le coût des solutions optimales que sur la garantie de performance des solutions approchées, l'intérêt des hiérarchies de recouvrement. Ce constat se voit conforté par des expérimentations sur des graphes aléatoires
The work conducted in this thesis is focused on the minimum spanning problems in graphs under constraints on the vertex degrees. As the spanning tree covers the vertices of a connected graph with a minimum number of links, it is generally proposed as a solution for this kind of problems. However, for some applications such as the routing in optical networks, the solution is not necessarily a sub-graph. In this thesis, we assume that the degree constraints are due to a limited instantaneous capacity of the vertices and that the only pertinent requirement on the spanning structure is its connectivity. In that case, the solution may be different from a tree. We propose the reformulation of this kind of spanning problems. To find the optimal coverage of the vertices, an extension of the tree concept called hierarchy is proposed. Our main purpose is to show its interest regarding the tree in term of feasibility and costs of the coverage. Thus, we take into account two types of degree constraints: either an upper bound on the degree of vertices and an upper bound on the number of branching vertices. We search a minimum cost spanning hierarchy in both cases. Besides, we also illustrate the applicability of hierarchies by studying a problem that takes more into account the reality of the optical routing. For all those NP-hard problems, we show the interest of the spanning hierarchy for both costs of optimal solutions and performance guarantee of approximate solutions. These results are confirmed by several experimentations on random graphs

Les données médicales souffrent de problèmes d'uniformisation ou d'incertitude, ce qui les rend difficilement utilisables directement par des logiciels médicaux, en particulier dans le cas du recrutement pour les essais cliniques. Dans cette thèse, nous proposons une approche permettant de palier la mauvaise qualité de ces données à l'aide de méthodes de classification supervisée. Nous nous intéresserons en particulier à 3 caractéristiques de ces données : asymétrie, incertitude et volumétrie. Nous proposons l'algorithme MOCA-I qui aborde ce problème combinatoire de classification partielle sur données asymétriques sous la forme d'un problème de recherche locale multi-objectif. Après avoir confirmé les apports de la modélisation multi-objectif dans ce contexte, nous calibrons MOCA-I et le comparons aux meilleurs algorithmes de classification de la littérature, sur des jeux de données réels et asymétriques de la littérature. Les ensembles de règles obtenus par MOCA-I sont statistiquement plus performants que ceux de la littérature, et 2 à 6 fois plus compacts. Pour les données ne présentant pas d'asymétrie, nous proposons l'algorithme MOCA, statistiquement équivalent à ceux de la littérature. Nous analysons ensuite l'impact de l'asymétrie sur le comportement de MOCA et MOCA-I, de manière théorique et expérimentale. Puis, nous proposons et évaluons différentes méthodes pour traiter les nombreuses solutions Pareto générées par MOCA-I, afin d'assister l'utilisateur dans le choix de la solution finale et réduire le phénomène de sur-apprentissage. Enfin, nous montrons comment le travail réalisé peut s'intégrer dans une solution logicielle.

碩士
元智大學
工業工程與管理學系
96
The applications of genetic algorithms in solving combinatorial problems are frequently faced with a problem of early convergence and the evolutionary processes are often trapped into a local but not the global optimum. This premature convergence occurs when the population of a genetic algorithm reaches a suboptimal state that the genetic operators can no longer produce offspring with a better performance than their parents. In the literature, plenty of work has been investigated to introduce new methods and operators in order to overcome this essential problem of genetic algorithms. As these methods and the belonging operators are rather problem specific in general. In this research, we take a different approach by observing the progress of the evolutionary process and when the diversity of the population dropping below a threshold level then artificial chromosomes with high diversity will be introduced to increase the average diversity level thus to ensure the process can jump out the local optimum. The proposed method is implemented independently of the problem characteristics and can be applied to improve the global convergence behavior of genetic algorithms. The experimental results using TSP instances show that the proposed approach is very effective in preventing the premature convergence when compared with the earlier approaches.

A thesis submitted to the Faculty of Science, University of the Witwatersrand, Johannesburg, in ful lment of the requirements for the degree of Doctor of Philosophy. Johannesburg, 2017.
In this thesis, various partition functions with respect to `-regular overpartitions, a special partition inequality and partition con gurations are studied. We explore new combinatorial properties of overpartitions which are natural generalizations of integer partitions. Building on recent work, we state general combinatorial identities between standard partition, overpartition and `-regular partition functions. We provide both generating function and bijective proofs. We then establish an in nite set of Ramanujan-type congruences for the `-regular overpartitions. This signi cantly extends the recent work of Shen which focused solely on 3{regular overpartitions and 4{regular overpartitions. We also prove some of the congruences for `-regular overpartition functions combinatorially. We then provide a combinatorial proof of the inequality p(a)p(b) > p(a+b), where p(n) is the partition function and a; b are positive integers satisfying a+b > 9, a > 1 and b > 1. This problem was posed by Bessenrodt and Ono who used the inequality to study a maximal multiplicative property of an extended partition function. Finally, we consider partition con gurations introduced recently by Andrews and Deutsch in connection with the Stanley-Elder theorems. Using a variation of Stanley's original technique, we give a combinatorial proof of the equality of the number of times an integer k appears in all partitions and the number of partition con- gurations of length k. Then we establish new generalizations of the Elder and con guration theorems. We also consider a related result asserting the equality of the number of 2k's in partitions and the number of unrepeated multiples of k, providing a new proof and a generalization.
MT2017

A thesis submitted to the Faculty of Science, University of the Witwatersrand, Johannesburg, in ful lment of the requirements for the degree of Doctor of Philosophy. Johannesburg, 2016.
In this thesis, various partition functions with respect to Rogers-Ramanujan identities and George Andrews' partitions with initial repetitions are studied. Agarwal and Goyal gave a three-way partition theoretic interpretation of the Rogers- Ramanujan identities. We generalise their result and establish certain connections with some work of Connor. Further combinatorial consequences and related partition identities are presented. Furthermore, we re ne one of the theorems of George Andrews on partitions with initial repetitions. In the same pursuit, we construct a non-diagram version of the Keith's bijection that not only proves the theorem, but also provides a clear proof of the re nement. Various directions in the spirit of partitions with initial repetitions are discussed and results enumerated. In one case, an identity of the Euler-Pentagonal type is presented and its analytic proof given.
M T 2016

Cette thèse porte sur l'étude de la complexité de l'exploration de graphes dynamiques par agent mobile. Une entité mobile (appelée agent) se déplaçant dans un graphe dynamique doit traverser/visiter au moins une fois chacun de ses sommets. (Le temps de traversée d'une arête est unitaire.) Ce problème fondamental en algorithmique par agents mobiles a été très étudié dans les graphes statiques depuis l'article originel de Claude Shannon. Concernant les graphes dynamiques, seul le cas des graphes dynamiques périodiques a été étudié. Nous étudions ce problème dans deux familles de graphes dynamiques, les graphes dynamiques périodiquement variables (PV-graphes) et les graphes dynamiques T-intervalle-connexes. Les résultats obtenus dans cette thèse améliorent des résultats existants et donnent des bornes optimales sur le problème étudié. Un PV-graphe est défini par un ensemble de transporteurs suivant infiniment leur route respective le long des stations du réseau. En 2013, Flocchini, Mans et Santoro ont étudié le problème de l'exploration des PV-graphes en considérant que l'agent doit toujours rester sur les transporteurs. Cette thèse montre l'impact de la capacité d'attendre sur les stations. Nous prouvons que l'attente sur les stations permet à l'agent d'atteindre de meilleures complexités en pire cas : le nombre de mouvements est réduit d'un facteur multiplicatif d'au moins $\Theta(p)$, et la complexité en temps passe de $\Theta(kp^2)$ à $\Theta(np)$, où $n$ est le nombre de stations, $k$ le nombre de transporteurs, et $p$ la période maximale ($n\leq kp$ dans tout PV-graphe connexe). Par ailleurs, l'algorithme que nous proposons pour prouver les bornes supérieures permet de réaliser la cartographie du PV-graphe, en plus de l'explorer. Dans la deuxième partie de cette thèse, nous considérons le même problème (l'exploration) dans les graphes dynamiques T-intervalle-connexes. Un graphe dynamique est $T$-intervalle-connexe ($T \geq 1$) si pour chaque fenêtre de $T$ unités de temps, il existe un sous-graphe couvrant connexe stable. Nous considérons dans un premier temps les graphes dynamiques T-intervalle-connexes qui ont un anneau de taille $n$ comme graphe sous-jacent et nous montrons que la complexité en temps en pire cas de leurs exploration est de $2n-T-\Theta(1)$ unités de temps si l'agent connaît la dynamique du graphe, et $n+ \frac{n}{\max\{1,T-1\}} (\delta-1) \pm\Theta(\delta)$ unités de temps sinon, où $\delta$ est le temps maximum entre deux apparitions successives d'une arête. Nous généralisons ensuite ces résultats en considérant une autre famille de graphes sous-jacents, les cactus à $n$ sommets. Un cactus est un graphe connexe dans lequel deux cycles ont au plus un sommet en commun. Nous donnons un algorithme qui permet d'explorer ces graphes dynamiques en au plus $2^{O(\sqrt{log n})} n$ unités de temps, et nous montrons que la borne inférieure de notre algorithme est $2^{\Omega(\sqrt{log n})} n$.