Esta dissertação estuda o problema da programação de operações em sistemas job shop de manufatura onde itens com estruturas de materiais são produzidos a partir de componentes fabricados e montados. Tais sistemas são denominados assembly shops. O caso geral do problema de programação de operações em sistemas job shop, no qual não existem restrições quanto ao número de operações a serem programadas nem quanto ao número de máquinas a serem alocadas, é considerado, até o presente momento, intratável do ponto de vista computacional devido à explosão combinatória inerente ao processo de programação, independente da escolha do critério de desempenho. Isto significa dizer que não existe nenhum método eficiente de programação que resolva globalmente instâncias de porte real do problema dentro de um tempo computacional considerado satisfatório. Devido a este fato, nas últimas três décadas, diversos métodos aproximados e heurísticos foram propostos e avaliados para o problema. Nesta pesquisa, é proposto e avaliado um novo método heurístico de programação. Fundamentado na pressuposição de que a melhoria na sincronização de operações de montagem em sistemas assembly shop leva ao melhor atendimento de datas de entrega de pedidos, o método implementa duas abordagens de programação: uma abordagem backward que satisfaz completamente as datas de entrega e outra forward que satisfaz completamente a restrição de capacidade de máquina. Ambas trabalham iterativamente dentro de dois modelos de simulação do sistema de produção um determinístico e outro probabilístico na busca pela melhoria da sincronização das operações e no atendimento das datas de entrega. Os resultados experimentais demonstraram que o desempenho do novo método foi em média melhor que os dos métodos não iterativos (regras) avaliados e tão bom quanto o desempenho do melhor método não iterativo (regra) testado. / This dissertation studies the problem of scheduling operations in manufacturing job shop environments where items with bill of materials are made of many fabricated and assembled components. Such systems are known as assembly shops. The general job shop scheduling problem, which no restrictions exist neither for the number of operations to be scheduled nor for the number of machines to be allocated, is considered at the present date intractable from the computational point of view, whatever the performance criterion used, due to the combinatorial explosion inherent to the scheduling process. It means that there is not an efficient computational method that solves globally real size instances of the problem within a satisfactory period of time. Due to this fact, in the last three decades several approximated and heuristic methods were created and evaluated for the problem. This research proposes and evaluate a new heuristic method which is based on the assumption that the improvement in operations synchronization at the assembly stations brings forth better achievement of due dates. The method implements two scheduling approaches: a backward approach satisfying due date completely and a forward approach satisfying capacity restriction completely. The two approaches work iteratively within two different simulation models of the production system one deterministic e other probabilistic in searching for operations synchronization improvement and due date achievement. The experimental results have shown the new method was better than the single-pass methods (rules) on average and as good as the better single-pass method (rule) tested.

O problema de corte consiste no corte de objetos maiores para produção de peças menores, de modo que uma certa função objetivo seja otimizada, por exemplo, a perda seja minimizada. O problema de empacotamento pode também ser visto como um problema de corte, onde as peças menores são arranjadas dentro dos objetos. Uma abordagem em grafo E/OU para a resolução de problemas de corte e empacotamento foi proposta inicialmente por Morabito (1989) para problemas de corte bidimensionais e, mais tarde, estendida para problemas tridimensionais (Morabito, 1992). Nesta abordagem foi utilizada uma técnica de busca híbrida, onde se combinou a busca em profundidade primeiro com limite de profundidade e a busca hill-climbing, utilizando-se heurísticas baseadas nos limitantes superiores e inferiores. Experiências computacionais mostraram a viabilidade de uso na prática desta abordagem. Mais tarde, Arenales (1993) generalizou esta a abordagem em grafo E/OU mostrando como diferentes problemas de corte poderiam ser resolvidos, independentemente da dimensão, formas dos objetos e itens, baseado em simples hipóteses, sem realizar, entretanto, estudos computacionais. O presente trabalho tem por objetivo estender a abordagem em grafo E/OU para tratar outros casos não analisados pelos trabalhos anteriores, tais como situações envolvendo diferentes processos de corte, bem como a implementação computacional de métodos baseados na abordagem em grafo E/OU, mostrando, assim, a versatilidade da abordagem para tratar diversas situações práticas de problemas de corte e sua viabilidade computacional. / The cutting problem consists of cutting larger objects in order to produce smaller pieces, in such a way as to optimizing a given objective function, for example, minimizing the waste. The packing problem can also be seen as a cutting problem, where the position that each smaller piece is arranged inside of the objects can be seen as the place it was cut from. An AND/OR-graph approach to solve cutting and packing problems was initially proposed by Morabito (1989) for two-dimensional cutting problem and, later, extended to threedimensional problems (Morabito, 1992). That approach uses a hybrid search, which combines depth-first search under depth bound and hill-climbing strategy. Heuristics were devised based on upper and lower bounds. Computational experiences demonstrated its practical feasibility. The AND/OR-graph approach was later generalized by Arenales (1993) based on simple hypothesis. He showed that different cutting problems Gould be solved using the AND/ORgraph approach, independently of the dimension and shapes. The main objective of this thesis is the practical extension of the AND/OR-graph approach to handle other cases not considered by previous works. It was considered different cutting processes, as well as the analysis of computational implementation, showing how can it be adapted to many classes of practical cutting and packing problems.

Made available in DSpace on 2016-04-27T16:57:36Z (GMT). No. of bitstreams: 1 Carlos Alberto de Miranda Pinheiro.pdf: 3726604 bytes, checksum: 7f0acb671f10ca6a3f9af822c2232603 (MD5) Previous issue date: 2015-03-17 / This paper presents the development of a research, which proposed to investigate the knowledge of Combinatorial Analysis studied in the Brazilian schools during 1895 and 2009. This research articulates inside a project called Educação Estatística e Educação Financeira na Escola Básica (Statistical Education and Financial Education in Basic School), linked to the research group PEA-MAT. We analysed some didactic aspects and mathematicians present in seven textbooks used in Brazilian schools during that time, we also had a bibliographical and documental study in presuppositions of content analysis. We wanted to answer the following investigation question:what characteristics of knowledge insertion of Combinatorial Analysis are identified in textbooks during 1895 and 2009? The first phase of content analysis consisted in collecting and studying texts that would inform us what textbooks presented the knowledge of Combinatorial Analysis and some aspects of historical moments of these books, since the foundation of the Pedro II School. With this, we identified that the program of 1895 was the one with more insertion of textbooks and new school contents, before the main educational reforms occurred in the first decades of the XX century. We also tried to identify on the website of the Programa Nacional do Livro Didático (PNLD-Ensino Médio) (National Program of Textbooks-High School) the Mathematic book more used in Belémdo Pará schools, in the first phase of the program, 2004-2009. The second phase of content analysis was the material exploration. In this phase we analysed based on the Anthropological Theory of Didactic, specifically about the praxeological organizations not only mathematical but also didactic, together with the notion of didactic models proposed by Josep Gáscon. Among the results observed, we highlight that while in the first books the focus was only on presentation of formulas deduction, some years later, the task of calculating the values from those formulas was introduced, modifying the approach from theoretical to technical or classic. We can also observe the change in the techniques to calculate the Arrange and the Permutation in the book produced based on the Movement of Modern Mathematics and in a more recent book, approved by the PNLD-Ensino Médio. The tasks and the techniques related to the calculation of numbers of simple combinations will not undergo transformations as time goes by. That is, the praxeological organization identified in the block task/technique/technology/theory changed from a theoretical to a technical approach during the whole period studied / Este trabalho apresenta o desenvolvimento de uma pesquisa que se propôs a investigar os saberes da Análise Combinatória estudada nas escolas brasileiras, no período entre 1895 e 2009. Esta pesquisa articula-se no interior do projeto Educação Estatística e Educação Financeira na Escola Básica , vinculado ao grupo de pesquisa PEA-MAT. Analisamos alguns aspectos didáticos e matemáticos presentes em sete livros didáticos que circularam nas escolas brasileiras, no período em questão, realizando um estudo bibliográfico e documental fundamentado em pressupostos da análise de conteúdo. Buscamos responder à seguinte questão de investigação: que características de inserção dos saberes da Análise Combinatória nos livros didáticos podem ser identificadas no período 1895-2009? A primeira fase da análise de conteúdo consistiu em reunir e estudar textos que nos informassem quais livros escolares apresentavam os saberes da Análise Combinatória e alguns aspectos do momento histórico desses livros, desde a fundação do Colégio Pedro II. Com isso, identificamos que o programa de 1895 foi o que teve a maior inserção de livros didáticos e de novos conteúdos escolares, antes das principais reformas educacionais ocorridas nas primeiras décadas do século XX. Também procuramos identificar no site do Programa Nacional do Livro Didático (PNLD-Ensino Médio) o livro de Matemática mais utilizado nas escolas de Belém do Pará, na primeira fase de implantação desse programa, 2004-2009. A segunda fase da análise de conteúdo foi a exploração do material. Nesta fase foi realizada uma análise à luz da Teoria Antropológica do Didático, especificamente sobre as organizações praxeológica tanto matemáticas como didáticas, juntamente com a noção de modelos didáticos, proposta por JosepGáscon. Entre os resultados observados, destacamos que, enquanto nos primeiros livros o enfoque era apenas a apresentação da dedução das fórmulas, ao longo do tempo foi inserida a tarefa de calcular os valores a partir dessas fórmulas, passando, assim, de uma abordagem puramente teoricista para uma abordagem tecnicista ou clássica. Observa-se, também, uma mudança nas técnicas para calcular o Arranjo e a Permutação no livro produzido à luz das ideias do Movimento de Matemática Moderna e no livro mais recente, aprovado no PNLD-Ensino Médio. As tarefas e as técnicas, relativas ao cálculo do número de combinações simples, não sofreram transformações, ao longo do tempo. Ou seja, a organização praxeológica identificada no bloco tarefa/técnica/tecnologia/teoria passou de uma abordagem teoricista para uma abordagem tecnicista ou clássica ao longo de todo o período estudado

L’imagerie moléculaire est aujourd’hui un outil non-invasif essentiel pour le diagnostic de nombreuses pathologies. Les traceurs technétiés sont actuellement les plus répandus car le 99mTc est facilement disponible, abordable et présente des caractéristiques idéales pour l’imagerie. Néanmoins, le développement de traceurs efficaces nécessite un long et coûteux processus d’optimisation souvent empirique. Dans ce contexte, nous avons entrepris le développement d’une plateforme technétiée conçue pour présenter au sein de sa structure de nombreux sites potentiels de fonctionnalisation et compatible avec une approche combinatoire.Dans un premier temps, un ensemble de 12 ligands N3X (X = N, O, S) a été préparé. Chacun d’entre eux présente dans sa structure un motif triazole introduit par chimie-click et intervenant dans la complexation du métal par un de ses atomes d’azote. Nous avons ensuite évalué l’aptitude de ces ligands à chélater le cœur oxotechnétium dans des conditions douces (5 min, température ambiante) compatible avec une utilisation en milieu hospitalier. Le complexe TriaS-99mTc a été formé quantitativement et sa stabilité en plasma murin a été étudiée. Il s’est révélé stable à plus de 90% dans le plasma murin après 6h d’incubation. L’étude in vivo de ce complexe a par la suite révélé une élimination efficace du milieu circulant par la voie urinaire avec une dégradation minoritaire.A titre d’illustration, nous avons ensuite engagé la structure TriaS dans deux approches distinctes pour le développement de traceurs de la néoangiogenèse tumorale en ciblant l’intégrine αvβ3. D’une part, dans le cadre d’une approche intégrée, plusieurs complexes fonctionnalisés, mimes de RGD, ont été obtenus. Dans chaque cas, l’adjonction de groupements fonctionnels n’a pas affecté l’efficacité de la chélation. En outre la stabilité en plasma est maintenue à un niveau très correct. D’autre part, nous avons développé une approche bifonctionnelle dans laquelle le motif c(RGDfK) joue le rôle de molécule ciblante. Dans ce cas, un motif variable (ici un PEG) peut être introduit par chimie combinatoire pour moduler la solubilité, la biodistribution, et l’excrétion des traceurs. / Molecular imaging is an essential non-invasive tool usable for diagnosis and characterisation of many diseases. Technetium-based tracers are the most popular ones due to disponibility, cost and radiochemical properties of 99mTc. Nevertheless, effective tracers development requires a long, expensive, and mainly empirical optimisation process. This context prompted us tu carry on the development of a new technetium structure which exhibits lots of potential functionalisation spots compatible with a combinatorial approach. We synthesised 12 N3X (X = N, O, S) different ligands. Each of them includes a triazole moiety, (formed via a click-chemistry reaction), which is involved in the metal complexation that implies one of its nitrogen atoms. Then we evaluated their ability to readily form oxotechnetium complexes in conditions that are compatible with medical use in hospital. One complex was formed in quantitative yields and its stability in mice plasma was investigated. A complex called TriaS-99mTc, stable to more than 90% after 6h incubation, was selected. In vivo study of TriaS-99mTc revealed an efficient blood clearance via the urinary excretion pathway with very low degradation. As an application, we used this structure for the development of tracers that target integrin αvβ3, a known biomarker of tumor neoangiogenesis. First, we synthesised functionnalised TriaS-based integrated complexes. Fonctionnal modification of TriaS by addition of side chains and substituents did not affect its ability to chelate oxotechnetium quantitatively. In addition, its stability in mice plasma was satisfactory. We also developped a bifonctionnal approach using c(RGDfK) peptide as the targeting biomolecule. In this way, a variable moiety (herein a PEG moiety) can be inserted in the structure through click-chemistry in order to modulate tracers solubility, biodistribution and excretion.

Nesta dissertação estudamos --- do ponto de vista algorítmico --- o seguinte problema, conhecido como problema da partição conexa balanceada. Dado um grafo conexo G com pesos atribuídos a seus vértices, e um inteiro q >= 2, encontrar uma partição dos vértices de G em q classes, de forma que cada classe da partição induza um grafo conexo e que, ao considerar as somas dos pesos dos vértices de cada classe, a menor das somas seja o maior possível. Em outras palavras, o objetivo é encontrar q classes cujos pesos sejam tão balanceados quanto possível. Sabe-se que este problema é NP-difícil. Mencionamos alguns resultados sobre complexidade computacional e algoritmos que são conhecidos para este problema. Apresentamos algumas heurísticas que desenvolvemos, todas elas baseadas no uso do algoritmo polinomial para árvores, devido a Perl e Schach, que apresentamos com detalhe. Implementamos quatro heurísticas e um algoritmo de 3/4-aproximação conhecido para o caso q=2. Exibimos os resultados obtidos com os vários testes computacionais conduzidos com instâncias aleatórias, com grafos de diferentes pesos e densidades. Os resultados computacionais indicam que o desempenho dessas heurísticas --- todas elas polinomiais --- é bem satisfatório. No caso especial em que q=2, observamos que a heurística mais onerosa sistematicamente produziu soluções melhores ou iguais às do algoritmo de aproximação / In this dissertation we study algorithmic aspects of the following problem, known as the balanced connected partition. Given a connected graph G with weights defined on its vertices, and an integer q >= 2, find a partition of the vertices of G into q classes such that each class induces a connected graph, and furthermore, when we consider the sum of the weights of the vertices in each class, the smallest sum is as large as possible. In other words, the q classes must have weights that are as balanced as possible. This problem is known to be NP-hard. We mention some computational complexity and algorithmic results that are known for this problem. We present some heuristics that we designed, all of them based on the use of the polynomial algorithm for trees, due to Perl and Schach, which we show in detail. We implemented four heuristics and a 3/4-approximation algorithm that is known for q=2. We run tests on many random instances, of graphs with different weights and densities. The computational results indicate that the performance of these heuristics --- all of polynomial time complexity --- are very satisfactory. For q=2, we observed that the most expensive heuristic produced solutions with values which are systematically better or equal to those produced by the approximation algorithm.

Submitted by Luciana Ferreira (lucgeral@gmail.com) on 2017-01-19T10:20:09Z No. of bitstreams: 2 Dissertação - Diego de Souza Avendano - 2016.pdf: 2770544 bytes, checksum: 621a0eef262e3cc91e4fab9e3a64f74a (MD5) license_rdf: 0 bytes, checksum: d41d8cd98f00b204e9800998ecf8427e (MD5) / Approved for entry into archive by Luciana Ferreira (lucgeral@gmail.com) on 2017-01-19T10:21:18Z (GMT) No. of bitstreams: 2 Dissertação - Diego de Souza Avendano - 2016.pdf: 2770544 bytes, checksum: 621a0eef262e3cc91e4fab9e3a64f74a (MD5) license_rdf: 0 bytes, checksum: d41d8cd98f00b204e9800998ecf8427e (MD5) / Made available in DSpace on 2017-01-19T10:21:18Z (GMT). No. of bitstreams: 2 Dissertação - Diego de Souza Avendano - 2016.pdf: 2770544 bytes, checksum: 621a0eef262e3cc91e4fab9e3a64f74a (MD5) license_rdf: 0 bytes, checksum: d41d8cd98f00b204e9800998ecf8427e (MD5) Previous issue date: 2016-11-21 / Coordenação de Aperfeiçoamento de Pessoal de Nível Superior - CAPES / The aim of this dissertation is outline the course by which the concept of rule "arises" in Wittgenstein's thought. I shall consider that the origin of the approach to the concept of "rule" lies in the rapid development of the author's thinking between 1929-1934. His immediate problem was to remedy the glaring error, presented by Ramsey, on the Tractarian remarks about the logical necessity. In order to correct this error, Wittgenstein introduces two major innovations with which he believes that can solve the problem and still preserve the rigid tractarian demarcation between logical truth and empirical truth. First, he will replace the combinatorial model underlying the natural language that prevailed in the Tractatus by a conception which he describes as a system of propositions (Satzsysteme), in which language would be considered as a complex system of autonomous propositional calculi. This change make possible preserves the thesis that all necessity is a logical necessity, however, it will be necessary to abandon the referential conception of meaning and the logical independence of elementary propositions. Thus, our proposal in this dissertation is to establish all aspects of the Tractarian philosophy that precede and sustain the proposal of language as correspondence, emphasizing that the abandonment shall result in changes such as: 1) a word has its meaning only in the context of its propositional system; 2) the meaning of any word is the totality of the rules governing its use in this system; 3) The meaning of a proposition is the method of its verification. Finally, in order to understand the context of these changes, it seems to be the case, that in one hand, we need to establish the essence and general form of the proposition in the Tractatus, and thereby elucidate some aspects of what are the essential traits of language and the world; On the other, to establish the limits and the scope of analysis, so we can understand its mutation outlined in accordance with the new criterion of sense – the rules – since what counts as the object of analysis will not be determined by a general form, but displayed by a “possible calculus”. / Em minha dissertação buscarei esboçar o percurso pelo qual o conceito de regra “surge” no pensamento de Wittgenstein. Irei considerar que a origem da abordagem do conceito de “regra” encontra-se no rápido desenvolvimento do pensamento do autor entre 1929 – 1934. Nesta época, seu problema imediato era remediar o erro das considerações Tractarianas acerca da necessidade lógica apresentado por Ramsey. Para corrigir este erro, Wittgenstein introduz duas inovações com as quais ele acredita poder resolver o problema e, ainda, preservar a rígida demarcação tractariana entre verdade lógica e verdade empírica. Primeiro, ele irá substituir o modelo único de cálculo subjacente à linguagem natural que imperava no Tractatus por uma concepção que ele descrever como sistema de proposições (Satzsysteme), no qual a linguagem seria vista como um complexo emaranhado de sistemas proposicionais autônomos, cada qual constituindo um espaço lógico distinto. Desta maneira, ele preserva a tese de que toda necessidade é uma necessidade lógica, contudo, será preciso abandonar a concepção referencial de significado e a independência lógica das proposições elementares. Assim, nossa proposta nesta dissertação é estabelecer todos os aspectos da filosofia do Tractatus que antecedem e fundamentam a proposta da linguagem enquanto correspondência, enfatizando que o abandono desta última resulta em mudanças como: 1) uma palavra só tem significado no contexto do seu sistema proposicional; 2) o significado de uma palavra qualquer é a totalidade das regras que governam seu uso neste sistema; 3) o sentido de uma proposição é o método de sua verificação. Por fim, para que possamos compreender o contexto dessas mudanças, parece ser o caso de, por um lado, estabelecer a essência e a forma geral da proposição no Tractatus e, com isso, elucidar alguns aspectos do que, segundo o autor, são traços essências da linguagem e do mundo; por outro, estabelecer os limites do âmbito da análise, para que possamos compreender a sua mutação esboçada em conformidade com o novo critério do sentido, as regras, pois o que conta como objeto de análise será menos determinado por uma forma geral e mais exibido por um “cálculo” possível.

Submitted by Gilvan Passos (gilvan.dspassos@gmail.com) on 2018-11-02T17:23:45Z No. of bitstreams: 3 GilvanTCC.pdf: 392056 bytes, checksum: c92e4c9757ada7893dc6f62a78267aa6 (MD5) IMG_20181102_131441.jpg: 1218636 bytes, checksum: 36aa8c31ec2aca115870ea2c2a9e278c (MD5) IMG_20181102_131427.jpg: 1672384 bytes, checksum: ef52fc665bf97e6c37ae0b3c0202ac2c (MD5) / Approved for entry into archive by PPGM Matemática (ppgmufam@gmail.com) on 2018-11-08T18:51:06Z (GMT) No. of bitstreams: 3 GilvanTCC.pdf: 392056 bytes, checksum: c92e4c9757ada7893dc6f62a78267aa6 (MD5) IMG_20181102_131441.jpg: 1218636 bytes, checksum: 36aa8c31ec2aca115870ea2c2a9e278c (MD5) IMG_20181102_131427.jpg: 1672384 bytes, checksum: ef52fc665bf97e6c37ae0b3c0202ac2c (MD5) / Rejected by Divisão de Documentação/BC Biblioteca Central (ddbc@ufam.edu.br), reason: A Dissertação inserida está sem Ficha Catalográfica. Instruções no link http://biblioteca.ufam.edu.br/servicos/elaboracao-de-ficha-catalografica Dúvidas? ddbc@ufam.edu.br on 2018-11-09T13:58:53Z (GMT) / Submitted by Gilvan Passos (gilvan.dspassos@gmail.com) on 2018-11-09T20:14:38Z No. of bitstreams: 4 GilvanTCC.pdf: 392056 bytes, checksum: c92e4c9757ada7893dc6f62a78267aa6 (MD5) IMG_20181102_131441.jpg: 1218636 bytes, checksum: 36aa8c31ec2aca115870ea2c2a9e278c (MD5) IMG_20181102_131427.jpg: 1672384 bytes, checksum: ef52fc665bf97e6c37ae0b3c0202ac2c (MD5) fichacatalografica.pdf: 5598 bytes, checksum: 78c21bd3648cbde20ad062f8314ad74d (MD5) / Approved for entry into archive by PPGM Matemática (ppgmufam@gmail.com) on 2018-11-13T14:28:28Z (GMT) No. of bitstreams: 4 GilvanTCC.pdf: 392056 bytes, checksum: c92e4c9757ada7893dc6f62a78267aa6 (MD5) IMG_20181102_131441.jpg: 1218636 bytes, checksum: 36aa8c31ec2aca115870ea2c2a9e278c (MD5) IMG_20181102_131427.jpg: 1672384 bytes, checksum: ef52fc665bf97e6c37ae0b3c0202ac2c (MD5) fichacatalografica.pdf: 5598 bytes, checksum: 78c21bd3648cbde20ad062f8314ad74d (MD5) / Approved for entry into archive by Divisão de Documentação/BC Biblioteca Central (ddbc@ufam.edu.br) on 2018-11-13T18:08:41Z (GMT) No. of bitstreams: 4 GilvanTCC.pdf: 392056 bytes, checksum: c92e4c9757ada7893dc6f62a78267aa6 (MD5) IMG_20181102_131441.jpg: 1218636 bytes, checksum: 36aa8c31ec2aca115870ea2c2a9e278c (MD5) IMG_20181102_131427.jpg: 1672384 bytes, checksum: ef52fc665bf97e6c37ae0b3c0202ac2c (MD5) fichacatalografica.pdf: 5598 bytes, checksum: 78c21bd3648cbde20ad062f8314ad74d (MD5) / Made available in DSpace on 2018-11-13T18:08:41Z (GMT). No. of bitstreams: 4 GilvanTCC.pdf: 392056 bytes, checksum: c92e4c9757ada7893dc6f62a78267aa6 (MD5) IMG_20181102_131441.jpg: 1218636 bytes, checksum: 36aa8c31ec2aca115870ea2c2a9e278c (MD5) IMG_20181102_131427.jpg: 1672384 bytes, checksum: ef52fc665bf97e6c37ae0b3c0202ac2c (MD5) fichacatalografica.pdf: 5598 bytes, checksum: 78c21bd3648cbde20ad062f8314ad74d (MD5) Previous issue date: 2018-03-28 / This work aims to study combinatorial analysis, which is an important branch of mathematics which is not usually subtly treated and through many years was teached as the mechanical memorization, leaving aside the learning process, self-learning and logical construction. It is important to emphasize the application of combinatorial analysis in set theory and probabilities theory that are often present in problem solving. It is necessary to present to our students the potential and beauty of the logical construction of ideas of combinatorial analysis, not excluding formulas applications, that can be used when the concepts and structure is well assimilated. We present counting methods beyond those used in basic education such as repetition chaotic permutations combinations, inclusion and exclusion principles, Kaplansky and Dirichlet lemmas, but we also highlight basic methods such as simple arrangements, simple combinations, and simple permutations. Beyond that, we present a generalization of the factorial numbers through the Gamma function besides olympics problems resolutions. / Este trabalho tem por objetivo estudar Análise Combinatória, que é um importante ramo da matemática que normalmente não é tratado com sutileza e transmitida ao longo dos anos através de memorização mecânica deixando o processo aprendizagem, auto-aprendizagem e construção lógica de lado. É importante enfatizar a aplicação da Análise Combinatória nas teorias dos conjuntos e teoria das probabilidades que muitas vezes se fazem presentes nas resoluções de problemas. Se faz necessário apresentar para nossos alunos o potencial e a beleza da construção lógica de ideias que a Análise Combinatória proporciona não excluindo as aplicações de fórmulas mas que elas possam ser usadas quando os conceitos e a estrutura forem bem assimiladas. Apresentamos métodos de contagem além dos usados no ensino básico como permutações caóticas combinações com repetição, princípio da inclusão e exclusão, lemas de Kaplansky e de Dirichlet mas também destacamos os métodos básicos como arranjos simples, combinações simples e permutações simples. Além disso, para apresentamos uma generalização dos números fatoriais definida pela função Gama e resoluções de problemas de olimpíadas.

Submitted by Geyciane Santos (geyciane_thamires@hotmail.com) on 2015-06-18T15:59:03Z No. of bitstreams: 1 Dissertação - Bruno Raphael Cardoso Dias.pdf: 2590139 bytes, checksum: cd42989e41c3aa52c2f6debcdfbd565d (MD5) / Approved for entry into archive by Divisão de Documentação/BC Biblioteca Central (ddbc@ufam.edu.br) on 2015-06-18T18:57:13Z (GMT) No. of bitstreams: 1 Dissertação - Bruno Raphael Cardoso Dias.pdf: 2590139 bytes, checksum: cd42989e41c3aa52c2f6debcdfbd565d (MD5) / Approved for entry into archive by Divisão de Documentação/BC Biblioteca Central (ddbc@ufam.edu.br) on 2015-06-18T18:58:47Z (GMT) No. of bitstreams: 1 Dissertação - Bruno Raphael Cardoso Dias.pdf: 2590139 bytes, checksum: cd42989e41c3aa52c2f6debcdfbd565d (MD5) / Made available in DSpace on 2015-06-18T18:58:47Z (GMT). No. of bitstreams: 1 Dissertação - Bruno Raphael Cardoso Dias.pdf: 2590139 bytes, checksum: cd42989e41c3aa52c2f6debcdfbd565d (MD5) Previous issue date: 2014-03-20 / CAPES - Coordenação de Aperfeiçoamento de Pessoal de Nível Superior / The channel allocation problem is addressed, where, as a wireless mobile network with transmission antennas distributed in the region of interest and one or more given track limited frequency discretized broadcast channels, is to promote allocation of such channels by the antennas in such a way to meet the demand for calls optimizing the use of resources, which in this case prioritized to optimize the use of channels allocated in an optimization problem Min-Max distribution channel - the Span -, where the highest allocated channel must be as small as possible. This problem has a increasingly important given the large demand growth and limiting technological resources of communication involved. The approach to the problem is Optimization Combinatorics and related fields. Therefore, a literature study is presented on the topic, focusing on mobile phones and networks based on cognitive radio networks. The From this, it is proposed new theoretical model for the problem representation using special stains on graphs, task scheduling on parallel machines resource constraints and geometry distances with constraint programming, and possible to identify specific characteristics of some application scenarios of the problem general. Based on these models, the developed algorithms are presented and implemented, and approximate methods based on local search with emphasis on meta-heuristic simulated annealing, and exact methods, involving branch-and-cut with IBM / ILOG CPLEX tool and, finally, hybrid methods, prune-branch-and-bound. The computational experiments are presented with a comparative analysis of performance, either using classical literature instances, as set Philadelphia and its variants as well as artificial instances proposals to cover variants discussed, as well as larger involving network 70 to to 150 stations. The results validate the proposed theoretical models and algorithms developed and implemented, since, equal or better results to the literature were obtained with several great solutions proven, beyond theoretical discussion and variants proposals believed to strengthen the understanding of the problem and the related literature / O problema de alocação de canais é abordado, onde, dado uma rede móvel sem fio com antenas de transmissão distribuídas na região de interesse e dada uma ou mais faixa de frequência limitada discretizada em canais de transmissão, consiste em promover uma alocação de tais canais pelas antenas de tal modo a atender as chamadas em demanda otimizando o uso dos recursos, que neste caso priorizou-se a otimização do uso dos canais alocados, em um problema de otimização Min-Max da distribuição dos canais - o span -, onde o maior canal alocado deve ser o menor possível. Tal problema possui uma importância cada vez maior dado o grande crescimento da demanda e a limitação dos recursos tecnológicos de comunicação envolvidos. A abordagem ao problema é de Otimização Combinatória e áreas afins. Sendo assim, é apresentado um estudo da literatura sobre o tema, com enfoque em redes celulares e redes baseadas em rádios cognitivos. A partir disto, propõe-se novos modelos teóricos para representação do problema utilizando colorações especiais em grafos, escalonamento de tarefas em máquinas paralelas com restrições de recursos e geometria de distâncias com programação por restrições, sendo possível identificar características específicas de alguns cenários de aplicação do problema geral. Com base em tais modelos, são apresentados os algoritmos desenvolvidos e implementados, sendo métodos aproximados, baseados em busca local com ênfase na meta-heurística simulated annealing, e métodos exatos, envolvendo branch-and-cut com a ferramenta IBM/ILOG CPLEX e, por fim, métodos híbridos, branch-prune-and-bound. Os experimentos computacionais realizados são apresentados com uma análise comparativa de desempenho, usando tanto instâncias clássicas da literatura, como o conjunto Philadelphia e suas variantes, como também instâncias artificiais propostas para contemplar variantes abordadas, bem como de maior tamanho, envolvendo redes entre 70 a 150 estações. Os resultados obtidos validam os modelos teóricos propostos e os algoritmos desenvolvidos e implementados, uma vez que, resultados iguais ou melhores aos da literatura foram obtidos, com várias soluções ótimas comprovadas,além da discussão teórica e variantes propostas que se acredita robustecer o entendimento do problema e a literatura relacionada.

Esta dissertação trata do problema da k-árvore de custo mínimo (kMST): dados um grafo conexo G, um custo não-negativo c_e para cada aresta e e um número inteiro positivo k, encontrar uma árvore com k vértices que tenha custo mínimo. O kMST é um problema NP-difícil e portanto não se conhece um algoritmo polinomial para resolvê-lo. Nesta dissertação discutimos alguns casos em que é possível resolver o problema em tempo polinomial. Também são estudados algoritmos de aproximação para o kMST. Entre os algoritmos de aproximação estudados, apresentamos a 2-aproximação desenvolvida por Naveen Garg, que atualmente é o algoritmo com melhor fator de aproximação. / This dissertation studies the minimum cost k-tree problem (kMST): given a connected graph G, a nonnegative cost function c_e for each edge e and a positive integer k, find a minimum cost tree with k vertices. The kMST is an NP-hard problem, which implies that it is not known a polynomial algorithm to solve it. In this dissertation we discuss some cases that can be solved in polynomial time. We also study approximation algorithms for the kMST. Among the approximation algorithms we present the 2-approximation developed by Naveen Garg, which is currently the algorithm with the best approximation factor.

Neste trabalho são apresentadas contribuições para a estimação do desempenho elétrico na distribuição de energia elétrica, com implicações nos mais diversos problemas da operação e do planejamento da distribuição. Entende-se por desempenho elétrico, a avaliação dos parâmetros de congestionamento de redes, as perdas e o nível de tensão. A motivação deste trabalho está na agregação dos esforços advindos da campanha de medição compulsória das concessionárias de distribuição e da necessidade do órgão regulador de estabelecer parâmetros de avaliação do desempenho operacional das empresas, como previsto no documento intitulado “Procedimentos da Distribuição” da Aneel. A estimação do desempenho elétrico é formulada segundo um problema de otimização multiobjetivo onde as funções objetivo compõem uma avaliação de probabilidade de ocorrência e uma avaliação de proximidade dos parâmetros elétricos calculados com os valores obtidos por medição. Os valores das cargas são discretizados segundo probabilidades de ocorrência em cada intervalo, de modo que a formulação resulte em um problema de otimização combinatória multiobjetivo de dimensão exponencial. Propõe-se um procedimento de redução de rede, que diminua consideravelmente o espaço de decisões, e um procedimento de expansão de redes para recompô-la. Também são propostas heurísticas específicas para a obtenção de soluções com cargas diversificadas e desequilibradas. Para uma aplicação adequada destas heurísticas, propôs-se e aplicou-se um método evolucionário metaheurístico para composição das soluções factíveis, ordenadas de acordo com o conceito de dominância de Pareto. Para cada fronteira de dominância, ou conjunto de fronteiras, o aplicativo constrói a distribuição probabilística da corrente e fluxo de potência de cada trecho, o nível de tensão em todas as barras e as perdas técnicas totais do circuito. A formulação matemática de otimização é flexível o bastante para a aplicação prática, considerando os diversos estágios de implementação dos atuais sistemas supervisórios. O modelo evolucionário metaheurístico proposto foi aplicado para um caso ilustrativo evidenciando as suas potencialidades e os pontos a serem aprimorados. / This thesis aims at contributing for the estimation of electrical performance in the distribution of electrical energy. Electrical performance is assumed to be the evaluation of network congestion parameters, losses and voltage level. The development of this work was impelled due to distribution utilities compulsory measurement permanent campaigns, and due to the need of the regulatory agency in establishing operational performance standards, as stated in the Distribution Code of Aneel, the Brazilian Energy Regulatory Agency. The electrical performance estimation is formulated according to an optimization problem where the objective functions correspond to an evaluation of occurrence probability, and correspond to a proximity evaluation of calculated parameters with values obtained by measurement as well. Load values are discretized according to ocurrence probabilities within each interval, so that formulation results in a multiobjective combinatorial optimization of exponential dimension. Network reduction procedures to substantially reduce Decision Domain and network expansion procedures to recompose it are proposed. Specific heuristics are also proposed to get solutions with load diversity and unbalanced loads. In order to adequately apply these heuristics, a metaheuristic evolutionary method to build feasible solutions is proposed and applied, and ranked according to Pareto´s concept. For each dominance frontier or group of frontiers, the application builds the probabilistic: current and load flow distribution of for each branch, voltage level for each bar and circuit technical losses. The mathematical formulation of optimization is flexible enough to be effectively applied taking into account different levels of supervisory systems developed in the utilities. The metaheuristic evolutionary model proposed was applied to a representative case with main potentialities and weak points to be improved.