Este trabalho introduz o conceito de cortes k e cortes kl sobre um circuito mapeado, em uma representação netlist. Esta nova abordagem é derivada do conceito de cortes k e cortes kl sobre AIGs (and inverter graphs), respeitando as diferenças entre essas duas formas de representar um circuito. As principais diferenças são: (1) o número de entradas em um nodo do grafo, e (2) a presença de inversores e buffers de forma explícita no circuito mapeado. Um algoritmo para enumerar cortes k e cortes kl é proposto e implementado. A principal motivação de usar cortes kl sobre circuitos mapeados é para realizar otimizações locais na síntese lógica de circuitos digitais. A principal contribuição deste trabalho é uma abordagem nova de remapeamento iterativo, utilizando cortes kl, reduzindo a área do circuito e respeitando as restrições de temporização do circuito. O uso de portas lógicas complexas pode potencialmente reduzir a área total de um circuito, mas elas precisam ser escolhidas corretamente de forma a manter as restrições de temporização do circuito. Ferramentas comerciais de síntese lógica trabalham melhor com portas lógicas simples e não são capazes de explorar eventuais vantagens em utilizar portas lógicas complexas. A abordagem proposta de remapeamento iterativo utilizando cortes kl é capaz de explorar uma quantidade maior de portas lógicas com funções lógicas diferentes, reduzindo a área do circuito, e mantendo as restrições de temporização intactas ao fazer uma checagem STA (análise temporal estática). Resultados experimentais mostram uma redução de até 38% de área na parte combinacional de circuitos para um subconjunto de benchmarks IWLS 2005, quando comparados aos resultados de ferramentas comerciais de síntese lógica. Outra contribuição deste trabalho é um novo modelo de rendimento (yield) para fabricação de circuitos integrados (IC) digitais, considerando problemas de resolução da etapa de litografia como uma fonte de diminuição do yield. O uso de leiautes regulares pode melhorar bastante a resolução da etapa de litografia, mas existe um aumento de área significativo ao se introduzir a regularidade. Esta é a primeira abordagem que considera o compromisso (trade off) de portas lógicas com diferentes níveis de regularidade e diferentes áreas durante a síntese lógica, de forma a melhorar o yield do projeto. A ferramenta desenvolvida de remapeamento tecnológico utilizando cortes kl foi modificada de forma a utilizar esse modelo de yield como função custo, de forma a aumentar o número de boas amostras (dies) por lâmina de silício (wafer), com resultados promissores. / This work introduces the concept of k-cuts and kl-cuts on top of a mapped circuit in a netlist representation. Such new approach is derived from the concept of k-cuts and klcuts on top of AIGs (and inverter graphs), respecting the differences between these two circuit representations. The main differences are: (1) the number of allowed inputs for a logic node, and (2) the presence of explicit inverters and buffers in the netlist. Algorithms for enumerating k-cuts and kl-cuts on top of a mapped circuit are proposed and implemented. The main motivation to use kl-cuts on top mapped circuits is to perform local optimization in digital circuit logic synthesis. The main contribution of this work is a novel iterative remapping approach using klcuts, reducing area while keeping the timing constraints attained. The use of complex gates can potentially reduce the circuit area, but they have to be chosen wisely to preserve timing constraints. Logic synthesis commercial design tools work better with simple cells and are not capable of taking full advantage of complex cells. The proposed iterative remapping approach can exploit a larger amount of logic gates, reducing circuit area, and respecting global timing constraints by performing an STA (static timing analysis) check. Experimental results show that this approach is able to reduce up to 38% in area of the combinational portion of circuits for a subset of IWLS 2005 benchmarks, when compared to results obtained from logic synthesis commercial tools. Another contribution of this work is a novel yield model for digital integrated circuits (IC) manufacturing, considering lithography printability problems as a source of yield loss. The use of regular layouts can improve the lithography, but it results in a significant area overhead by introducing regularity. This is the first approach that considers the tradeoff of cells with different level of regularity and different area overhead during the logic synthesis, in order to improve overall design yield. The technology remapping tool based on kl-cuts developed was modified in order to use such yield model as cost function, improving the number of good dies per wafer, with promising interesting results.

Este trabalho propõe uma metodologia para enumerar soluções, que indiquem a barra e a compensação de potência reativa necessária para o sistema elétrico sob análise, que atendam aos requisitos avaliados pela função objetivo e as restrições. Nessa alocação de compensação ótima de potência reativa, obtemos as melhores barras e configurações de potências e tecnologias de dispositivos de compensação, minimizando as perdas totais de potência ativa da rede. Em redes fracas com conversores de frequência (por exemplo, para conexão de fontes renováveis, ou interligações utilizando conversores HVDC), esta metodologia proposta busca a melhor relação de curto-circuito trifásico (SCR) no ponto de conexão do conversor de frequência, melhorando a conexão da barra de interesse. O método busca soluções para alocar um único dispositivo de compensação, e soluções alocando simultaneamente dois dispositivos. A metodologia proposta baseia-se na enumeração exaustiva das soluções, e o estudo de caso nos sistemas de 14 e 30 barras do IEEE mostrou a aplicabilidade e funcionalidade da metodologia proposta. / This work proposes a methodology to enumerate solutions, which indicate the bar and the reactive power compensation required for the electrical system under analysis, that meet the requirements evaluated by the objective function and the constraints. In this allocation of optimal compensation of reactive power, we obtain the optimal bars and technologies of compensation devices, minimizing the total losses of active power of the network. In weak networks with frequency converters (e.g. for connection of renewable sources, or interconnections using HVDC converters), the proposed methodology seeks the best threephase short-circuit (SCR) relation at the connection point, improving the connection of the new generation. The method looks for solutions to allocate a single compensation device, and solutions to allocate two devices simultaneously. The proposed methodology is based on the exhaustive enumeration of the solutions. A case study carried out in the IEEE 14 and 30 bus systems shows the applicability and performance of the proposed methodology.

abstract: The uncrossing partially ordered set $P_n$ is defined on the set of matchings on $2n$ points on a circle represented with wires. The order relation is $\tau'\leq \tau$ in $P_n$ if and only if $\tau'$ is obtained by resolving a crossing of $\tau$. %This partial order has been studied by Alman-Lian-Tran, Huang-Wen-Xie, Kenyon, and Lam. %The posets $P_n$ emerged from studies of circular planar electrical networks. Circular planar electrical networks are finite weighted undirected graphs embedded into a disk, with boundary vertices and interior vertices. By Curtis-Ingerman-Morrow and de Verdi\`ere-Gitler-Vertigan, the electrical networks can be encoded with response matrices. By Lam the space of response matrices for electrical networks has a cell structure, and this cell structure can be described by the uncrossing partial orders. %Lam proves that the posets can be identified with dual Bruhat order on affine permutations of type $(n,2n)$. Using this identification, Lam proves the poset $\hat{P}_n$, the uncrossing poset $P_n$ with a unique minimum element $\hat{0}$ adjoined, is Eulerian. This thesis consists of two sets of results: (1) flag enumeration in intervals in the uncrossing poset $P_n$ and (2) cyclic sieving phenomenon on the set $P_n$. I identify elements in $P_n$ with affine permutations of type $(0,2n)$. %This identification enables us to explicitly describe the elements in $P_n$ with the elements in $\mathcal{MP}_n$. Using this identification, I adapt a technique in Reading for finding recursions for the cd-indices of intervals in Bruhat order of Coxeter groups to the uncrossing poset $P_n$. As a result, I produce recursions for the cd-indices of intervals in the uncrossing poset $P_n$. I also obtain a recursion for the ab-indices of intervals in the poset $\hat{P}_n$, the poset $P_n$ with a unique minimum $\hat0$ adjoined. %We define an induced subposet $\mathcal{MP}_n$ of the affine permutations under Bruhat order. Reiner-Stanton-White defined the cyclic sieving phenomenon (CSP) associated to a finite cyclic group action on a finite set and a polynomial. Sagan observed the CSP on the set of non-crossing matchings with the $q$-Catalan polynomial. Bowling-Liang presented similar results on the set of $k$-crossing matchings for $1\leq k \leq 3$. In this dissertation, I focus on the set of all matchings on $[2n]:=\{1,2,\dots,2n\}$. I find the number of matchings fixed by $\frac{2\pi}{d}$ rotations for $d|2n$. I then find the polynomial $X_n(q)$ such that the set of matchings together with $X_n(q)$ and the cyclic group of order $2n$ exhibits the CSP. / Dissertation/Thesis / Doctoral Dissertation Mathematics 2018

Este trabalho propõe uma metodologia para enumerar soluções, que indiquem a barra e a compensação de potência reativa necessária para o sistema elétrico sob análise, que atendam aos requisitos avaliados pela função objetivo e as restrições. Nessa alocação de compensação ótima de potência reativa, obtemos as melhores barras e configurações de potências e tecnologias de dispositivos de compensação, minimizando as perdas totais de potência ativa da rede. Em redes fracas com conversores de frequência (por exemplo, para conexão de fontes renováveis, ou interligações utilizando conversores HVDC), esta metodologia proposta busca a melhor relação de curto-circuito trifásico (SCR) no ponto de conexão do conversor de frequência, melhorando a conexão da barra de interesse. O método busca soluções para alocar um único dispositivo de compensação, e soluções alocando simultaneamente dois dispositivos. A metodologia proposta baseia-se na enumeração exaustiva das soluções, e o estudo de caso nos sistemas de 14 e 30 barras do IEEE mostrou a aplicabilidade e funcionalidade da metodologia proposta. / This work proposes a methodology to enumerate solutions, which indicate the bar and the reactive power compensation required for the electrical system under analysis, that meet the requirements evaluated by the objective function and the constraints. In this allocation of optimal compensation of reactive power, we obtain the optimal bars and technologies of compensation devices, minimizing the total losses of active power of the network. In weak networks with frequency converters (e.g. for connection of renewable sources, or interconnections using HVDC converters), the proposed methodology seeks the best threephase short-circuit (SCR) relation at the connection point, improving the connection of the new generation. The method looks for solutions to allocate a single compensation device, and solutions to allocate two devices simultaneously. The proposed methodology is based on the exhaustive enumeration of the solutions. A case study carried out in the IEEE 14 and 30 bus systems shows the applicability and performance of the proposed methodology.

Este trabalho introduz o conceito de cortes k e cortes kl sobre um circuito mapeado, em uma representação netlist. Esta nova abordagem é derivada do conceito de cortes k e cortes kl sobre AIGs (and inverter graphs), respeitando as diferenças entre essas duas formas de representar um circuito. As principais diferenças são: (1) o número de entradas em um nodo do grafo, e (2) a presença de inversores e buffers de forma explícita no circuito mapeado. Um algoritmo para enumerar cortes k e cortes kl é proposto e implementado. A principal motivação de usar cortes kl sobre circuitos mapeados é para realizar otimizações locais na síntese lógica de circuitos digitais. A principal contribuição deste trabalho é uma abordagem nova de remapeamento iterativo, utilizando cortes kl, reduzindo a área do circuito e respeitando as restrições de temporização do circuito. O uso de portas lógicas complexas pode potencialmente reduzir a área total de um circuito, mas elas precisam ser escolhidas corretamente de forma a manter as restrições de temporização do circuito. Ferramentas comerciais de síntese lógica trabalham melhor com portas lógicas simples e não são capazes de explorar eventuais vantagens em utilizar portas lógicas complexas. A abordagem proposta de remapeamento iterativo utilizando cortes kl é capaz de explorar uma quantidade maior de portas lógicas com funções lógicas diferentes, reduzindo a área do circuito, e mantendo as restrições de temporização intactas ao fazer uma checagem STA (análise temporal estática). Resultados experimentais mostram uma redução de até 38% de área na parte combinacional de circuitos para um subconjunto de benchmarks IWLS 2005, quando comparados aos resultados de ferramentas comerciais de síntese lógica. Outra contribuição deste trabalho é um novo modelo de rendimento (yield) para fabricação de circuitos integrados (IC) digitais, considerando problemas de resolução da etapa de litografia como uma fonte de diminuição do yield. O uso de leiautes regulares pode melhorar bastante a resolução da etapa de litografia, mas existe um aumento de área significativo ao se introduzir a regularidade. Esta é a primeira abordagem que considera o compromisso (trade off) de portas lógicas com diferentes níveis de regularidade e diferentes áreas durante a síntese lógica, de forma a melhorar o yield do projeto. A ferramenta desenvolvida de remapeamento tecnológico utilizando cortes kl foi modificada de forma a utilizar esse modelo de yield como função custo, de forma a aumentar o número de boas amostras (dies) por lâmina de silício (wafer), com resultados promissores. / This work introduces the concept of k-cuts and kl-cuts on top of a mapped circuit in a netlist representation. Such new approach is derived from the concept of k-cuts and klcuts on top of AIGs (and inverter graphs), respecting the differences between these two circuit representations. The main differences are: (1) the number of allowed inputs for a logic node, and (2) the presence of explicit inverters and buffers in the netlist. Algorithms for enumerating k-cuts and kl-cuts on top of a mapped circuit are proposed and implemented. The main motivation to use kl-cuts on top mapped circuits is to perform local optimization in digital circuit logic synthesis. The main contribution of this work is a novel iterative remapping approach using klcuts, reducing area while keeping the timing constraints attained. The use of complex gates can potentially reduce the circuit area, but they have to be chosen wisely to preserve timing constraints. Logic synthesis commercial design tools work better with simple cells and are not capable of taking full advantage of complex cells. The proposed iterative remapping approach can exploit a larger amount of logic gates, reducing circuit area, and respecting global timing constraints by performing an STA (static timing analysis) check. Experimental results show that this approach is able to reduce up to 38% in area of the combinational portion of circuits for a subset of IWLS 2005 benchmarks, when compared to results obtained from logic synthesis commercial tools. Another contribution of this work is a novel yield model for digital integrated circuits (IC) manufacturing, considering lithography printability problems as a source of yield loss. The use of regular layouts can improve the lithography, but it results in a significant area overhead by introducing regularity. This is the first approach that considers the tradeoff of cells with different level of regularity and different area overhead during the logic synthesis, in order to improve overall design yield. The technology remapping tool based on kl-cuts developed was modified in order to use such yield model as cost function, improving the number of good dies per wafer, with promising interesting results.

Este trabalho introduz o conceito de cortes k e cortes kl sobre um circuito mapeado, em uma representação netlist. Esta nova abordagem é derivada do conceito de cortes k e cortes kl sobre AIGs (and inverter graphs), respeitando as diferenças entre essas duas formas de representar um circuito. As principais diferenças são: (1) o número de entradas em um nodo do grafo, e (2) a presença de inversores e buffers de forma explícita no circuito mapeado. Um algoritmo para enumerar cortes k e cortes kl é proposto e implementado. A principal motivação de usar cortes kl sobre circuitos mapeados é para realizar otimizações locais na síntese lógica de circuitos digitais. A principal contribuição deste trabalho é uma abordagem nova de remapeamento iterativo, utilizando cortes kl, reduzindo a área do circuito e respeitando as restrições de temporização do circuito. O uso de portas lógicas complexas pode potencialmente reduzir a área total de um circuito, mas elas precisam ser escolhidas corretamente de forma a manter as restrições de temporização do circuito. Ferramentas comerciais de síntese lógica trabalham melhor com portas lógicas simples e não são capazes de explorar eventuais vantagens em utilizar portas lógicas complexas. A abordagem proposta de remapeamento iterativo utilizando cortes kl é capaz de explorar uma quantidade maior de portas lógicas com funções lógicas diferentes, reduzindo a área do circuito, e mantendo as restrições de temporização intactas ao fazer uma checagem STA (análise temporal estática). Resultados experimentais mostram uma redução de até 38% de área na parte combinacional de circuitos para um subconjunto de benchmarks IWLS 2005, quando comparados aos resultados de ferramentas comerciais de síntese lógica. Outra contribuição deste trabalho é um novo modelo de rendimento (yield) para fabricação de circuitos integrados (IC) digitais, considerando problemas de resolução da etapa de litografia como uma fonte de diminuição do yield. O uso de leiautes regulares pode melhorar bastante a resolução da etapa de litografia, mas existe um aumento de área significativo ao se introduzir a regularidade. Esta é a primeira abordagem que considera o compromisso (trade off) de portas lógicas com diferentes níveis de regularidade e diferentes áreas durante a síntese lógica, de forma a melhorar o yield do projeto. A ferramenta desenvolvida de remapeamento tecnológico utilizando cortes kl foi modificada de forma a utilizar esse modelo de yield como função custo, de forma a aumentar o número de boas amostras (dies) por lâmina de silício (wafer), com resultados promissores. / This work introduces the concept of k-cuts and kl-cuts on top of a mapped circuit in a netlist representation. Such new approach is derived from the concept of k-cuts and klcuts on top of AIGs (and inverter graphs), respecting the differences between these two circuit representations. The main differences are: (1) the number of allowed inputs for a logic node, and (2) the presence of explicit inverters and buffers in the netlist. Algorithms for enumerating k-cuts and kl-cuts on top of a mapped circuit are proposed and implemented. The main motivation to use kl-cuts on top mapped circuits is to perform local optimization in digital circuit logic synthesis. The main contribution of this work is a novel iterative remapping approach using klcuts, reducing area while keeping the timing constraints attained. The use of complex gates can potentially reduce the circuit area, but they have to be chosen wisely to preserve timing constraints. Logic synthesis commercial design tools work better with simple cells and are not capable of taking full advantage of complex cells. The proposed iterative remapping approach can exploit a larger amount of logic gates, reducing circuit area, and respecting global timing constraints by performing an STA (static timing analysis) check. Experimental results show that this approach is able to reduce up to 38% in area of the combinational portion of circuits for a subset of IWLS 2005 benchmarks, when compared to results obtained from logic synthesis commercial tools. Another contribution of this work is a novel yield model for digital integrated circuits (IC) manufacturing, considering lithography printability problems as a source of yield loss. The use of regular layouts can improve the lithography, but it results in a significant area overhead by introducing regularity. This is the first approach that considers the tradeoff of cells with different level of regularity and different area overhead during the logic synthesis, in order to improve overall design yield. The technology remapping tool based on kl-cuts developed was modified in order to use such yield model as cost function, improving the number of good dies per wafer, with promising interesting results.

Orientador: Jose Plinio de Oliveira Santos / Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Matematica, Estatistica e Computação Cientifica / Made available in DSpace on 2018-08-05T07:47:09Z (GMT). No. of bitstreams: 1 Bovo_Eduardo_M.pdf: 3427598 bytes, checksum: 757ebc9282f3c010e155c26ec46fb42a (MD5) Previous issue date: 2005 / Resumo: Neste trabalho são desenvolvidos conceitos algébricos, analíticos e combinatórios que culminam no Teorema de Enumeração de Pólya; bem como são fornecidas muitas de suas aplicações em enumeração de padrões (grafos, colorações geométricas, tipos e permutações, etc). Tal teorema clássico, que tem suas bases em Teoria dos Grupos, utiliza fundamentalmente o conceito de funções geradoras, o que permite grande generalidade e computabilidade de resultados. Finalmente são apresentadas algumas generalizações do resultado principal, aplicações destas e também uma importante interpretação probabilística / Abstract: In this dissertation we present algebraic, analytic and combinatorial results that are used to prove Polya's Enumeration Theorem. Applications to counting patterns (graphs, colourings, permutations, etc.) are given. This classical Theorem has its foundations on the theory of groups and uses, mainly, the concept of generating functions which allows great generality and computability of results. At the end some generalizations of the main theorem are given including applications and, aiso, an important probabilistic interpretation / Mestrado / Combinatoria Enumerativa / Mestre em Matemática Aplicada

Orientador: Jose Plinio de Oliveira Santos, Marcio Antonio de Faria Rosa / Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Matematica, Estatistica e Computação Cientifica / Made available in DSpace on 2018-08-08T09:04:51Z (GMT). No. of bitstreams: 1 Silva_Robsonda_M.pdf: 1769033 bytes, checksum: 1d7dfaf76d2a38bd63024d4910459fc3 (MD5) Previous issue date: 2007 / Resumo: Este trabalho está dividido em duas partes. Na primeira, apresentamos as funções simétricas: o espaço vetorial das funções simétricas sobre os números racionais, algumas bases, um produto escalar e as chamadas funções (simétricas) de Schur. Na segunda parte, exibimos algumas das muitas aplicações desta teoria: no estudo dos caracteres das representações do grupo simétrico; nas partições planas; na enumeração de permutações; na enumeração sob a ação de grupos / Abstract: This work is divided in two parts. In the first one, we present the symmetric functions: the symmetric functions vector space over the field of the rational numbers, some bases, an inner product and the so called Schur (symmetric) functions. In the second part, we present some of the many aplications of this theory: in the study of the characters of the symmetric group's representations; in the plane partitions; in permutation enumeration; in the enumeration under group action / Mestrado / Matematica / Mestre em Matemática

O objetivo deste trabalho é usar jogos e tópicos de Teoria dos Grafos como ferramenta para desenvolver a habilidade da enumeração, que está por trás dos cálculos combinatórios ensinados no Ensino Fundamental e Médio. Mais especificamente, neste trabalho são introduzidos os métodos mais comuns de contagem através de situacões-problema e jogos, como o Nim e o Dominó, que podem ser melhor explorados ao serem descritos atráves dos elementos de um grafo. Com essa motivacão são apresentados conceitos básicos da Teoria dos Grafos e tópicos de coloração de grafos, como o número cromático e os polinômios cromáticos. Esses tópicos fornecem exemplos ricos e motivacionais ao processo de ensino e aprendizagem dos raciocínios combinatórios. Por outro lado, os tópicos abordados contém em si a riqueza e a complexidade da Matemática, como é o caso do Teorema das 4 Cores, demonstrado com o uso da enumeração de todos os casos possíveis. Nesse contexto são apresentados os conceitos de coloração de vértices de grafos dando destaque principal para problemas combinatórios que envolvem o número cromático e o polinômio cromático de um grafo. Complementando o trabalho, são propostas atividades para serem desenvolvidas em sala de aula. / The purpose of this work is to use games and topics of Graph Theory as a tool to develop the ability of enumeration, which is behind combinatorial calculations taught in Elementary and High School. More specifically, in this work, the most common methods of counting through problem situations and games, such as Nim and Domino, which can be better explored when described through the elements of a graph. With this motivation are presented basic concepts of the Theory of Graphs and graph coloring topics such as chromatic number and chromatic polynomials. Those topics provide rich and motivational examples to the process of teaching and learning combinatorial reasoning. On the other hand, the topics approach contains in itself the richness and complexity of Mathematics, as is the case with the 4-Color Theorem, demonstrated with the use of the enumeration of all possible cases. In this context are presented concepts of coloring of vertices of graphs giving main highlight to combinatorial problems which involve the chromatic number and the chromatic polynomial of a graph. Complementing the work, activities are proposed to be developed in the classroom.

No description available.