Orientador: José Plínio de Oliveira Santos / Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Matemática Estatística e Computação Científica / Made available in DSpace on 2018-08-22T15:43:28Z (GMT). No. of bitstreams: 1 Rodrigues_ChristianeBuffo_M.pdf: 948322 bytes, checksum: be5636b0d15a131df52736cd4f4782d0 (MD5) Previous issue date: 2013 / Resumo: Este trabalho trata da aplicação do Método Simbólico na resolução de problemas de Combinatória. A vantagem desta técnica é o cálculo direto de uma expressão fechada para a Função Geradora F(z) do problema escrito como uma Série de Potências. Consequentemente garantimos a facilidade na enumeração da sequência que queremos a partir do coeficiente de zn de F(z). O desenvolvimento de nosso estudo foi feito aplicando-se o método a dois tipos de Classes: Rotuladas e não Rotuladas, apontando as diferenças básicas entre elas através de exemplos e resultados teóricos. Ao final, concluímos que a enumeração independe do tipo de modelagem feita para o problema / Abstract: This work deals with the application of the Symbolic Method in the solutions of combinatorial problems. The advantage of this technique is the direct calculus for the exact expression of the Generating Function F(z) of the problem, written as a Power Series. Consequently, we ensure the enumeration of the desired sequence, from the coefficient of zn of F(z). Our study was developed by applying the method in two types of Classes: Labeled and unlabelled, pointing the basic differences between them through examples and theoretical results. Finally, we concluded that the enumeration does not depend of the type of the model chosen for the problem / Mestrado / Matematica Aplicada / Mestra em Matemática Aplicada

Depuis quelques années, les réseaux de communication déployés au sein d’aéronefs sont toujours plus vastes et plus complexes. Ces bus numériques multiplexent différents flux de données afin de limiter les câbles, mais cela induit des retards sur les transmissions. Les travaux présentés ici portent sur une approche statistique de l’évaluation des performances du pire temps de traversée d’un réseau embarqué de type AFDX. Il s’agit de définir une nouvelle approche visant à associer à un calcul pire cas, une distribution des temps de transmission des messages, en vue notamment de permettre d’apprécier le pessimisme du calcul pire cas. Les méthodes décrites sont applicables dans le cadre plus général d’un ensemble de tâches. Nous proposons trois contributions dans ces travaux. Tout d’abord, une méthode originaled’évaluation de la distribution de la durée de traversée d’un commutateur AFDX qui s’appuie sur une énumération symbolique des scénarios d’ordonnancement dans la file d’attente. Puis, un algorithme efficace de calcul des délais subis par des messages/tâches périodiques lorsque les déphasages initiaux sont connus. Les délais calculés sont exacts ainsi que la distribution de probabilité. Enfin, le calcul de la distribution des délais subis par des messages/tâches dans un cadregénéral, à l’aide d’une méthode statistique de type Monte Carlo. Des décalages initiaux sont tirés aléatoirement et permettent de nourrir l’algorithme précédent. / Since a few years, communication networks deployed in aircrafts are ever larger and ever more complex. These digital buses multiplex different data streams in order to save cabling, but this causes delays on transmissions.The work presented here is based on a statistical evaluation of the worst case transit time of an embedded network of the AFDX type. It consists in associating a worst case computation with a complete distribution of the transit times in order, among other things, to appreciatethe pessimism of worst case approaches. The methods are also applicable to a set of realtime tasks. This work contributes three major results. First, an original method to evaluate the distribution of the transit time through an AFDX switch, based on the symbolic enumeration of the scheduling scenarios in the waiting queues of the switch. Second, an effective algorithm to compute the delays encountered by periodic messages/ tasks when initial offsets are known. Delays thus computed are exact and so is the delays distribution. Third, the computation of the delays distribution encountered by messages/tasks in a general case using a Monte Carlo based statistical method. Initial offsets are randomised and feed the preceding algorithm.

Data processing for Big Data plays a vital role for decision-makers in organizations and government, enhances the user experience, and provides quality results in prediction analysis. However, many modern data processing solutions make a significant investment in hardware and maintenance costs, such as Hadoop and Spark, often neglecting the well established and widely used relational database management systems (RDBMS's). In this dissertation, we study three fundamental graph problems in RDBMS. The first problem we tackle is computing shortest paths (SP) from a source to a target in large network graphs. We explore SQL based solutions and leverage the intelligent scheduling that a RDBMS performs when executing set-at-a-time expansions of graph vertices, which is in contrast to vertex-at-a-time expansions in classical SP algorithms. Our algorithms perform orders of magnitude faster than baselines and outperform counterparts in native graph databases. Second, we studied the PageRank problem which is vital in Google Search and social network analysis to determine how to sort search results and identify important nodes in a graph. PageRank is an iterative algorithm which imposes challenges when implementing it over large graphs. We study computing PageRank using RDBMS for very large graphs using a consumer-grade machine and compare the results to a dedicated graph database. We show that our RDBMS solution is able to process graphs of more than a billion edges in few minutes, whereas native graph databases fail to handle graphs of much smaller sizes. Last, we present a carefully engineered RDBMS solution to the problem of triangle enumeration for very large graphs. We show that RDBMS's are suitable tools for enumerating billions of triangles in billion-scale networks on a consumer grade machine. Also, we compare our RDBMS solution's performance to a native graph database and show that our RDBMS solution outperforms by orders of magnitude. / Graduate

MSc (Mathematics) / Department of Mathematics and Applied Mathematics / See the attached abstract below

No description available.

The classification of finite semigroups is difficult even for small orders because of their large number. Most finite semigroups are nilpotent of nilpotency rank 3. Formulae for their number up to isomorphism, and up to isomorphism and anti-isomorphism of any order are the main results in the theoretical part of this thesis. Further studies concern the classification of nilpotent semigroups by rank, leading to a full classification for large ranks. In the computational part, a method to find and enumerate multiplication tables of semigroups and subclasses is presented. The approach combines the advantages of computer algebra and constraint satisfaction, to allow for an efficient and fast search. The problem of avoiding isomorphic and anti-isomorphic semigroups is dealt with by supporting standard methods from constraint satisfaction with structural knowledge about the semigroups under consideration. The approach is adapted to various problems, and realised using the computer algebra system GAP and the constraint solver Minion. New results include the numbers of semigroups of order 9, and of monoids and bands of order 10. Up to isomorphism and anti-isomorphism there are 52,989,400,714,478 semigroups with 9 elements, 52,991,253,973,742 monoids with 10 elements, and 7,033,090 bands with 10 elements. That constraint satisfaction can also be utilised for the analysis of algebraic objects is demonstrated by determining the automorphism groups of all semigroups with 9 elements. A classification of the semigroups of orders 1 to 8 is made available as a data library in form of the GAP package Smallsemi. Beyond the semigroups themselves a large amount of precomputed properties is contained in the library. The package as well as the code used to obtain the enumeration results are available on the attached DVD.

For a number of unsolved problems in graph theory such as the cycle double cover conjecture, Fulkerson's conjecture and Tutte's 5-flow conjecture it is sufficient to prove them for a family of graphs called snarks. Named after the mysterious creature in Lewis Carroll's poem, a \emph{snark} is a cyclically 4-edge connected 3-regular graph of girth at least 5 which cannot be properly edge coloured using three colours. Snarks and problems for which an edge minimal counterexample must be a snark are the central topics of this thesis.   The first part of this thesis is intended as a short introduction to the area. The second part is an introduction to the appended papers and the third part consists of the four papers presented in a chronological order. In Paper I we study the strong cycle double cover conjecture and stable cycles for small snarks. We prove that if a bridgeless cubic graph $G$ has a cycle of length at least $|V(G)|-9$ then it also has a cycle double cover. Furthermore we show that there exist cyclically 5-edge connected snarks with stable cycles and that there exists an infinite family of snarks with stable cycles of length 24. In Paper II we present a new algorithm for generating all non-isomorphic snarks with a given number of vertices. We generate all snarks on 36 vertices and less and study these with respect to various properties. We find that a number of conjectures on cycle covers and colourings holds for all graphs of these orders. Furthermore we present counterexamples to no less than eight published conjectures on cycle coverings, cycle decompositions and the general structure of regular graphs.     In Paper III we show that Jaeger's Petersen colouring conjecture holds for three infinite families of snarks and that a minimum counterexample to this conjecture cannot contain a certain subdivision of $K_{3,3}$ as a subgraph. Furthermore, it is shown that one infinite family of snarks have strong Petersen colourings while another does not have any such colourings. Two simple constructions for snarks with arbitrary high oddness and resistance is given in Paper IV. It is observed that some snarks obtained from this construction have the property that they require at least five perfect matchings to cover the edges. This disproves a suggested strengthening of Fulkerson's conjecture.

Nous proposons tout d'abord une étude de plusieurs problèmes de l'algorithmique distribuée. Nous fournissons un modèle formel appliqué aux réseaux de diffusion anonymes. Dans ce modèle, nous caractérisons les graphes dans lesquels il est possible de résoudre l'énumération et l'élection. Cette caractérisation se base sur la notion d'homomorphisme de graphes. Nous proposons deux algorithmes dont la complexité est polynomiale et qui améliorent les complexités exponentielles connues jusqu'à présent. Dans un second temps, nous étudions le problème du calcul de l'état global et nous introduisons la notion de weak snapshot. Nous montrons qu'il existe des solutions pour ce problème dans les réseaux anonymes. Nous présentons plusieurs résultats concernant le calcul de l'état global en liaison avec des applications telles que le calcul de points de reprise, la détection de la terminaison ou encore le calcul d'une cartographie du réseau. Dans un cadre plus pratique, nous présentons la conception, le développement et l'implémentation des algorithmes proposés pour le calcul de l'état global au sein du logiciel de simulation et de visualisation ViSiDiA. / In this thesis, we first present a study of several problems in the field of distributed algorithms. We provide a formal model that relies on anonymous networks. In this model, we characterize graphs in which it is possible to solve enumeration and leader election problems. This characterization is based on graph homomorphism. We introduce two algorithms with polynomial complexities that improve existing works with exponential complexities. On the other hand, we study the snapshot problem and we introduce the notion of weak snapshot. We show that there exist solutions for this problem in the context of anonymous networks. We present several results about distributed snapshots that deal with checkpoint and rollback recovery, termination detection or the cartography computation of a network. In a practical aspect, we present the conception, the development process and the implementation of these distributed snapshot algorithms within the simulation and visualization software ViSiDiA.

Název práce: Obecná enumerace číselných rozklad· Autor: Jaroslav Hančl Katedra: Katedra aplikované matematiky Vedoucí diplomové práce: doc. RNDr. Martin Klazar, Dr., KAM MFF UK Abstrakt: Předložená diplomová práce se zabývá asymptotikami počítacích funkcí ideál· číselných rozklad·. Jejím hlavním cílem je zjistit největší možný asympto- tický r·st počítací funkce rozkladového ideálu, která je nekonečněkrát rovna nule. Autor se na základě znalosti asymptotik vybraných rozkladových ideál· snaží po- mocí kombinatorických a základních analytických metod odvodit odhady hledané asymptotiky. Výsledkem je za prvé slabší horní odhad, za druhé poměrně silný dolní odhad a za třetí, pro speciální třídu rozkladových ideál· je nalezen největší asymptotický r·st. Klíčová slova: íselné rozklady, asymptotika rozklad·, rozkladové ideály, počítací funkce, kombinatorická enumerace. 1

In low-resource contexts, household-level point-of-use water treatment (POUWT) techniques are the final, and sometimes only, barrier against waterborne illnesses, and in these and other water-related applications, health risks can be quantified using one of two methods. Firstly, Escherichia coli (or other indicator organism) counts can be used to monitor water and determine adherence to a health-based limit (i.e. compliance monitoring). Secondly, E. coli can be used to conduct a quantitative microbial risk assessment (QMRA), indicating the level of protection conferred by a given POUWT device by spiking test water with E. coli to ascertain a reduction efficacy relative to that target organism, a process referred to as challenge testing, which is typically carried out in a laboratory context. Although both methods are well established, both have scope for improvement for effective field application in low-resource contexts. Regarding compliance monitoring, I assessed the performance of a new low-cost field kit for E. coli enumeration, which was designed by others. I also assessed the feasibility of re-using some disposable materials, in terms of sterility and mechanical wear. The use of the new low-cost field kit was successful during the fieldwork campaign; however, re-using disposable materials introduced a relatively high occurrence of false positive results during E. coli enumeration. Use of the new low-cost field kit can reduce financial barriers, thus enabling greater water quality testing coverage. Regarding challenge testing, the aim of this study was to adapt current protocols to assess the household performance (as opposed to laboratory performance) of POUWT techniques. I developed a conceptual framework to conduct Field Challenge Tests (FCT’s) on POUWT techniques, using a probiotic health supplement containing E. coli as the challenge organism. I successfully carried out a FCT in Malawi with limited resources, verifying FCT viability. Applications of such FCT’s include quality control practices for manufactured devices, guiding QMRA and recommendations by public health organizations regarding POU device selection, and assessing the impact of user training programmes regarding POUWT techniques. / Graduate