This thesis focuses on the use of extremal techniques in analyzing problems that historically have been associated with other areas of discrete mathematics. We establish new techniques for analyzing combinatorial problems with two different types of nonlinear orders, and then use them to solve important previously-open problems in mathematics. In addition, we use entropy techniques to establish a variety of bounds in the theory of sumsets. In the second chapter, we examine a problem of Furedi and Hajnal regarding forbidden patterns in (0,1)-matrices. We introduce a new technique that gives an asymptotically tight bound on the number of 1-entries that a (0,1)-matrix can contain while avoiding a fixed permutation matrix. We use this result to solve the Stanley-Wilf conjecture, a well-studied open problem in enumerative combinatorics. We then generalize the technique to give results on d-dimensional matrices. In the third chapter, we examine a problem of Pinchasi and Radoicic on cyclically order sets. To do so, we prove an upper bound on the sizes of such sets, given that their orders have the intersection reverse property. We then use this to give an upper bound on the number of edges that a graph can have, assuming that the graph can be drawn so that no cycle of length four has intersecting edges. This improves the previously best known bound and (up to a log-factor) matches the best known lower bound. This result implies improved bounds on a number of well-studied problems in geometric combinatorics, most notably the complexity of pseudo-circle arrangements. In the final chapter, we use entropy techniques to establish new bounds in the theory of sumsets. We show that such sets behave fractionally submultiplicatively, which in turn provides new Plunecke-type inequalities of the form first introduced by Gyarmati, Matolcsi, and Ruzsa.

Submitted by Luciana Ferreira (lucgeral@gmail.com) on 2015-10-26T09:48:39Z No. of bitstreams: 2 Dissertação - Caio Soares de Araújo - 2014.pdf: 1793471 bytes, checksum: 4a336fd03b4e7f3964731aed0679439b (MD5) license_rdf: 23148 bytes, checksum: 9da0b6dfac957114c6a7714714b86306 (MD5) / Approved for entry into archive by Luciana Ferreira (lucgeral@gmail.com) on 2015-10-26T09:53:07Z (GMT) No. of bitstreams: 2 Dissertação - Caio Soares de Araújo - 2014.pdf: 1793471 bytes, checksum: 4a336fd03b4e7f3964731aed0679439b (MD5) license_rdf: 23148 bytes, checksum: 9da0b6dfac957114c6a7714714b86306 (MD5) / Made available in DSpace on 2015-10-26T09:53:07Z (GMT). No. of bitstreams: 2 Dissertação - Caio Soares de Araújo - 2014.pdf: 1793471 bytes, checksum: 4a336fd03b4e7f3964731aed0679439b (MD5) license_rdf: 23148 bytes, checksum: 9da0b6dfac957114c6a7714714b86306 (MD5) Previous issue date: 2014-10-30 / In this work are presented and evaluated sequencing rules and heuristic methods for production scheduling in permutation flow shop systems with setup times independent of the sequence of execution of tasks. The release dates of the tasks were also considered, seeking simulate a reality closer to a production environment in an organization where tasks usually arrive dynamically and not simultaneously. In the first part of this study, were defined and implemented computationally eight rules (R1, R2, R3, R4, R5, R6, R7 and R8), based on recognized rules SPT (Shortest Processing Time) and LPT (Longest Processing Time), adapted to this problem. The second stage of this study consisted of the creation of four heuristics (H1, H2, H3 and H4), based on the best rules, and comparative analysis of the performance of all the methods proposed solution, similar to the assessment rules priority, including the results of the optimal solution obtained by the method of complete enumeration. After computational implementation, the H1, H2 and H3 heuristics performed well, with satisfactory results near optimal solution. / Neste estudo são apresentadas e avaliadas regras de sequenciamento e métodos heurísticos para programação da produção em sistemas flow shop permutacional com tempos de setup independentes da sequência de execução das tarefas. Foram consideradas também as datas de liberação das tarefas, para simular uma realidade mais próxima de um ambiente de produção numa organização em que as tarefas geralmente chegam de forma dinâmica e não simultaneamente. Na primeira parte deste trabalho, foram definidas e implementadas computacionalmente oito regras (R1, R2, R3, R4, R5, R6, R7 e R8), fundamentadas nas reconhecidas regras SPT (Shortest Processing Time) e LPT (Longest Processing Time), adaptadas a este problema. A segunda etapa deste estudo constituiu-se da criação de quatro heurísticas (H1, H2, H3 e H4), baseadas nas melhores regras, e análise comparativa do desempenho de todos os métodos de solução propostos, nos moldes da avaliação feita para as Regras de Prioridade, incluindo os resultados da solução ótima obtida por meio do método de enumeração completa. Após a implementação computacional, as heurísticas H1, H2 e H3 apresentaram um desempenho eficiente, com resultados satisfatórios próximos a solução ótima.

Orientador: Reginaldo Palazzo Junior / Dissertação (mestrado) - Universidade Estadual de Campinas, Faculdade de Engenharia Eletrica e de Computação / Made available in DSpace on 2018-08-12T13:34:06Z (GMT). No. of bitstreams: 1 Albuquerque_JulioCesarHolandade_M.pdf: 1364323 bytes, checksum: 01181adde228aa4d914d7edabdde4aca (MD5) Previous issue date: 2008 / Resumo: A proposta deste trabalho é apresentar uma abordagem aos processos genéticos e moleculares, utilizando a teoria de comunicações e codificação na modelagem do dogma central da biologia molecular. A partir desta modelagem associamos o código genético a um modulador de um sistema de comunicação. Mais especificamente, tal procedimento consiste em construir uma constelação de sinais a partir dos subgrupos de S3 e S4 baseado no código genético. Considerando este método algébrico de construção de sinais, propomos duas possíveis constelações de sinais para o código genético. A representação do código genético em constelações de sinais correlacionadas deu origem à idéia de "constelação de sinais concatenadas", idéia inovadora na teoria de comunicação e codificação. As constelações de sinais concatenadas possui a propriedade de correção de erros, consistindo de novos conceitos úteis para utilização na teoria da comunicação e codificação. Por outro lado, estas representações do código genético não são únicas pois, até o presente momento, desconhecemos uma álgebra que descreva o código genético juntamente com as suas partições geradas pelos aminoácidos. / Abstract: The purpose of this work is to present an approach to the genetic and molecular processes by use of the communication and coding theory in modelling the central dogma of the molecular biology. From this modelling we associate the genetic code to a modulator in the communication system. More specifically, such a procedure consists is in the construction of a signal constellation by use of the S3 and S4 permutation subgroups based on the code genetic. By considering this algebraic method of signal design, we propose two possible signal constellations to the genetic code. The representation of the genetic code as correlated signal constellations provides the idea idea of "concatenated signal constellation", an innovative idea in communication and coding theory. The concatenated signal constellations have the property of error-correction, a new concept being introduced. On the other hand, these representations of the genetic code are not unique for currently, we do not know an algebraic structure capable of describing the genetic code together with the partitioning generated by the amino acids. / Mestrado / Telecomunicações e Telemática / Mestre em Engenharia Elétrica

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-25T10:24:33Z (GMT). No. of bitstreams: 1 FeresJunior_Jorge_M.pdf: 656533 bytes, checksum: f89557654d48cebb7328f9f5ebbc8d0f (MD5) Previous issue date: 2014 / Resumo: Nesta dissertação estudamos permutações que evitam determinados padrões. Mais especificamente, nosso foco é a contagem de tais permutações. Dentre as várias formas de descrever uma permutação, adotamos a ''representação posicional em linha'', apresentando um tratamento sistemático nesta área de padrão proibido, estudando operações, simetrias, estruturas, transformações, e principalmente, técnicas de contagem para este fim / Abstract: In this dissertation, we study permutations avoiding certain patterns. More specifically, our focus is on counting such permutations. Among the many ways to describe a permutation, we adopted the "positional representation in line" presenting a systematic treatment of this area of forbidden pattern, studying operations, symmetries, structures, transformations, and especially counting techniques for this purpose / Mestrado / Matematica Aplicada / Mestre em Matemática Aplicada

The concept of Parallel Vector (scratch pad) Memories (PVM) was introduced as one solution for Parallel Computing in DSP, which can provides parallel memory addressing efficiently with minimum latency. The parallel programming more efficient by using the parallel addressing generator for parallel vector memory (PVM) proposed in this thesis. However, without hiding complexities by cache, the cost of programming is high. To minimize the programming cost, automatic parallel memory address generation is needed to hide the complexities of memory access. This thesis investigates methods for implementing conflict-free vector addressing algorithms on a parallel hardware structure. In particular, match vector addressing requirements extracted from the behaviour model to a prepared parallel memory addressing template, in order to supply data in parallel from the main memory to the on-chip vector memory. According to the template and usage of the main and on-chip parallel vector memory, models for data pre-allocation and permutation in scratch pad memories of ASIP can be decided and configured. By exposing the parallel memory access of source code, the memory access flow graph (MFG) will be generated. Then MFG will be used combined with hardware information to match templates in the template library. When it is matched with one template, suited permutation equation will be gained, and the permutation table that include target addresses for data pre-allocation and permutation is created. Thus it is possible to automatically generate memory address for parallel memory accesses. A tool for achieving the goal mentioned above is created, Permutator, which is implemented in C++ combined with XML. Memory access coding template is selected, as a result that permutation formulas are specified. And then PVM address table could be generated to make the data pre-allocation, so that efficient parallel memory access is possible. The result shows that the memory access complexities is hiden by using Permutator, so that the programming cost is reduced.It works well in the context that each algorithm with its related hardware information is corresponding to a template case, so that extra memory cost is eliminated.

Cette thèse concerne les valeurs du caractère irréductible (renormalisé) comme fonction de la partition indexant la représentation (et non de la permutation sur laquelle on calcule le caractère). Avec une bonne renormalisation, les caractères s’écrivent comme des polynômes en fonction des coordonnées des diagrammes multirectangulaires d’une part et en fonction des cumulants libres d’autre part ( ce sont des observables du diagramme apparaissant naturellement dans des problèmes d’asymptotique). Nous avons donné des interprétations combinatoires des coefficients de ces différentes expressions. Celles-ci peuvent s’exprimer en termes de cartes, dont le genre est lié au comportement asymptotique du terme correspondant. Ce type d’expression permet d’une part de bien comprendre le comportement asymptotique : nous avons ainsi amélioré les bornes connues sur les caractères ainsi que le domaine de validité d’équivalents classique. D’autre part, la combinatoire apparaissant dans ces questions est riche et a pu être utilisée dans l’étude d’identité sur des fractions rationnelles / The main object of this thesis is the (normalized) irreducible character values of the symmetric group, seen as a function of the partition indexing the representation (and not of the permutation on which we compute the character value). With a good rescaling, the characters can be written as polynomials in so-called Stanley coordinates or in terms of free cumulants (the latter are observables of the diagram, which appear naturally in the asymptotics study of character values). We give a combinatorial interpretation for the coefficients of these two expressions. More precisely, the summans are indexed by maps, whose genus is linked with their asymptotic behaviour. This kind of expression is very useful to obtain asymptotic results : for example, one has given upper bounds on character values and enlarged the domain of validity of some known equivalents. Moreover, the combinatorics involved in these questions is interesting and has been applied to identities on rational functions

Title: Tests of independence for multivariate data Author: Bc. Michal Kudlík Department: Department of Probability and Mathematical Statistics Supervisor: Ing. Marek Omelka, PhD., Department of Probability and Mathema- tical Statistics Abstract: This thesis is an overview of tests of independence for multidimensi- onal data. The report includes tests on independence of categorical and conti- nuous random variables, tests assuming normal distribution of data, asymptotic nonparametric tests and permutation tests with application of the Monte Carlo method. This thesis shows the suitability of tests with properly chosen real data and checks significance level and compares the strength of the selected tests by simulation study while using appropriate statistical software. Based on the simu- lation study the thesis discusses an appropriateness of the use of different tests for different situations. Keywords: independence, permutation and asymptotic tests of independence, Monte Carlo method, simulation study 1

M.Sc. / In this thesis we study some of the propertie of a clas called automatic structures. Automatic structures are structures that can be encoded (in some defined way) into a set of regular languages. This encoding allows one to prove many interesting properties about automatic structures, including decidabilty results.

This thesis demonstrates an alternative, concise but informative, method for representing group elements, which will prove particularly useful for the sporadic groups. It explains the theory behind symmetric presentations, and describes the algorithm for working with elements represented in this manner.

De nouvelles réglementations imposent désormais aux compagnies aériennes d'établir une stratégie de gestion des risques pour réduire encore davantage le nombre d'accidents. Les données des enregistreurs de vol, très peu exploitées à ce jour, doivent être analysées de façon systématique pour identifier, mesurer et suivre l'évolution des risques. L'objectif de cette thèse est de proposer un ensemble d'outils méthodologiques pour répondre à la problématique de l'analyse des données de vol. Les travaux présentés dans ce manuscrit s'articulent autour de deux thèmes statistiques : la sélection de variables en apprentissage supervisé d'une part et l'analyse des données fonctionnelles d'autre part. Nous utilisons l'algorithme des forêts aléatoires car il intègre des mesures d'importance pouvant être employées dans des procédures de sélection de variables. Dans un premier temps, la mesure d'importance par permutation est étudiée dans le cas où les variables sont corrélées. Nous étendons ensuite ce critère pour des groupes de variables et proposons une nouvelle procédure de sélection de variables fonctionnelles. Ces méthodes sont appliquées aux risques d'atterrissage long et d'atterrissage dur, deux questions importantes pour les compagnies aériennes. Nous présentons enfin l'intégration des méthodes proposées dans le produit FlightScanner développé par Safety Line. Cette solution innovante dans le transport aérien permet à la fois le monitoring des risques et le suivi des facteurs qui les influencent. / New recommendations require airlines to establish a safety management strategy to keep reducing the number of accidents. The flight data recorders have to be systematically analysed in order to identify, measure and monitor the risk evolution. The aim of this thesis is to propose methodological tools to answer the issue of flight data analysis. Our work revolves around two statistical topics: variable selection in supervised learning and functional data analysis. The random forests are used as they implement importance measures which can be embedded in selection procedures. First, we study the permutation importance measure when the variables are correlated. This criterion is extended for groups of variables and a new selection algorithm for functional variables is introduced. These methods are applied to the risks of long landing and hard landing which are two important questions for airlines. Finally, we present the integration of the proposed methods in the software FlightScanner implemented by Safety Line. This new solution in the air transport helps safety managers to monitor the risks and identify the contributed factors.