Orientador: Francisco de Assis Magalhães Gomes Neto / Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Matematica, Estatistica e Computação Cientifica / Made available in DSpace on 2018-08-12T16:09:04Z (GMT). No. of bitstreams: 1 Villela_PedroFerraz_M.pdf: 727069 bytes, checksum: d87d64ae49bfc1a53017a463cf10b453 (MD5) Previous issue date: 2008 / Resumo: Neste trabalho, propomos um método exato para a resolução de problemas de programação quadrática que envolvem restrições de cardinalidade. Como aplicação, empregamos o método para a obtenção da fronteira eficiente de um problema (bi-objetivo) de otimização de carteiras de investimento. Nosso algoritmo é baseado no método Branch-and-Bound. A chave de seu sucesso, entretanto, reside no uso do método de Lemke, que é aplicado para a resolução dos subproblemas associados aos nós da árvore gerada pelo Branch-and-Bound. Ao longo do texto, algumas heurísticas também são introduzidas, com o propósito de acelerar a convergência do método. Os resultados computacionais obtidos comprovam que o algoritmo proposto é eficiente. / Abstract: In this work, we propose an exact method for the resolution of quadratic programming problems involving cardinality restrictions. As an application, the algorithm is used to generate the effective Pareto frontier of a (bi-objective) portfolio optimization problem. This algorithm is based on the Branch-and-Bound method. The key to its success, however, resides in the application of Lemke's method to the resolution of the subproblems associated to the nodes of the tree generated by the Branch-and-Bound algorithm. Throughout the text, some heuristics are also introduced as a way to accelerate the performance of the method. The computational results acquired show that the proposed algorithm is efficient. / Mestrado / Otimização / Mestre em Matemática Aplicada

Submitted by Kamila Costa (kamilavasconceloscosta@gmail.com) on 2015-08-27T12:52:40Z No. of bitstreams: 2 Dissertação - Rogério J de M Júnior.pdf: 1412276 bytes, checksum: 362c58043c52c9e05db80b80055fe0f2 (MD5) Ficha.pdf: 6202 bytes, checksum: 7bc34b7b59769c34edf90b86a7983117 (MD5) / Approved for entry into archive by Divisão de Documentação/BC Biblioteca Central (ddbc@ufam.edu.br) on 2015-08-28T20:05:14Z (GMT) No. of bitstreams: 2 Dissertação - Rogério J de M Júnior.pdf: 1412276 bytes, checksum: 362c58043c52c9e05db80b80055fe0f2 (MD5) Ficha.pdf: 6202 bytes, checksum: 7bc34b7b59769c34edf90b86a7983117 (MD5) / Approved for entry into archive by Divisão de Documentação/BC Biblioteca Central (ddbc@ufam.edu.br) on 2015-08-28T20:24:20Z (GMT) No. of bitstreams: 2 Dissertação - Rogério J de M Júnior.pdf: 1412276 bytes, checksum: 362c58043c52c9e05db80b80055fe0f2 (MD5) Ficha.pdf: 6202 bytes, checksum: 7bc34b7b59769c34edf90b86a7983117 (MD5) / Made available in DSpace on 2015-08-28T20:24:20Z (GMT). No. of bitstreams: 2 Dissertação - Rogério J de M Júnior.pdf: 1412276 bytes, checksum: 362c58043c52c9e05db80b80055fe0f2 (MD5) Ficha.pdf: 6202 bytes, checksum: 7bc34b7b59769c34edf90b86a7983117 (MD5) Previous issue date: 2015-05-15 / CAPES - Coordenação de Aperfeiçoamento de Pessoal de Nível Superior / In this dissertation we discuss briefly some issues quickly treated during the undergraduate course such as countable and uncountable sets, cardinality and other related subjects. We will present a brief historical review of the facts that gave rise to these problems, as well as people who have developed knowledge on these issues. The purpose of this report is succinctly present a direction to the Basic Education teachers for their classes, giving the opportunity to teachers to have more confidence when working with numerical sets and functions on these sets. It will also be used as a motivational element to the theoretical approach, or this associated with the problems that gave rise to such issues, both for teachers, and for students and scholars interested, because these are curious and intriguing subjects for those which enjoy studying mathematics of such subjects that are, of some kind, advanced or abstract. Among others, we can assign the comparison of cardinality of infinite sets, demonstrating that sets of racional numbers and the algebraic numbers are countable, and the real numbers and the transcendental numbers are uncountable, and besides, we show the cardinality of other interesting sets that are of great value to research in modern mathematics. Thus we think we are contributing to the improvement of teachers and students of Basic Education. / Neste trabalho abordaremos alguns assuntos tratados brevemente durante o curso de graduação tais como enumerabilidade e não enumerabilidade de conjuntos, cardinalidade e outros assuntos correlatos. Apresentaremos um pequeno aparato histórico que deram origem a esses problemas, assim como as pessoas que lançaram conhecimento sobre tais temas. O objetivo é apresentar sucintamente aos professores do ensino básico suporte para as aulas, dando a oportunidade do professor ter mais segurança quando trabalhar com conjuntos numéricos. Também servirá como elemento motivacional tanto para professores como para os alunos interessados, pois trata de assuntos curiosos e atiçadores para quem gosta de estudar matemática, como comparar a cardinalidade de conjuntos infinitos, a infinidade de números transcendentes e sua dificuldade de determiná-los e outros assuntos que são de grande riqueza de pesquisa na matemática moderna. Dessa forma pensamos estar contribuindo para o aperfeiçoamento de professores e alunos do ensino básico.

To take advantage of the high speed in an optic fiber, one of the basic concept in fiber optic communication is to allow several users to simultaneously transmit data over the channel. One technique that provides multiple access is it fiber optic-code division multiple access (FO-CDMA). In FO-CDMA each user is assigned one or more signature sequences called codewords, which are subsets of a type of optical orthogonal code (OOC). The channel input/output consists of the superposition of several users codewords and at the receiver end an optical correlator extracts the information. In the parallel code constructions, presented in this report, each user j is assigned a subset Cj from a code C. The subsets are disjoint and their union is the whole set C. A new way to map the information bits is to insert up to L zeros before each codeword from Cj and let this represent information aswell. This gives high rates for active users but an investigation is needed to ensure that this does not compromise the systems wanted property of sending information with a small probability of errors for all users. Therefore a simulation environment has been implemented in Matlab. The result from these simulations shows that BER for the L parallel codes is acceptable and not much higher than for the traditional constructions. Because of the higher rate these construction should be preferred but an analysis if a hardware implementation is possible.

Access to and understanding data plays an essential role in the increasingly digital world. Representation and analysis of relations between various data entities, i.e., graph and network structures in the data, is an important problem for various industries. In contrast to simple graphs that focus on edges with two endpoints only, a hypergraph provides a natural method to represent multi-way interactions with an arbitrary number of endpoints for each edge, and it can be a better alternative than a bipartite graph for comparable applications. However, traditional approaches for visually representing hypergraphs are purely static diagrams without support for interaction, which can be difficult to perceive and do not scale well with regard to the number of nodes and edges. They are not adequate for the representation and interactive exploration of large or dense hypergraph data sets found in real-world applications. The ISOVIS (Information and Software Visualisation) research group at Linnaeus University has previously introduced a novel radial visualization approach for undirected hypergraphs called Onion. The Onion tool focuses on solving the issues of edge clutter, overlaps, and edge crossings. However, certain open challenges and suggestions for improvements were identified for the respective implementation, and there is an opportunity to fill a gap in the hypergraph visualization research by building upon the original Onion approach study. In this thesis project, we implement the new version of the Onion approach based on the principles and challenges established previously. The contributions of this work include evidence regarding the effectiveness and efficiency of a hypergraph comparison technique, the usability of edge bundling in the context of hypergraph exploration tasks, and the scalability of the interactive visualization through an entirely new web-based version of the Onion approach. To obtain the respective results, the new implementation is applied for two case studies involving real-world data sets, and further validated through a user study with several participants. The results of this work can be helpful for researchers of network visualization and practitioners in need of approaches for representing and exploring data that can be modeled as hypergraphs.

Cardinality constrained optimization problems (CCOP) are a new class of optimization problems with many applications. In this thesis, we propose a framework called mathematical programs with disjunctive subspaces constraints (MPDSC), a special case of mathematical programs with disjunctive constraints (MPDC), to investigate CCOP. Our method is different from the relaxed complementarity-type reformulation in the literature. The first contribution of this thesis is that we study various stationarity conditions for MPDSC, and then apply them to CCOP. In particular, we recover disjunctive-type strong (S-) stationarity and Mordukhovich (M-) stationarity for CCOP, and then reveal the relationship between them and those from the relaxed complementarity-type reformulation. The second contribution of this thesis is that we obtain some new results for MPDSC, which do not hold for MPDC in general. We show that many constraint qualifications like the relaxed constant positive linear dependence (RCPLD) coincide with their piecewise versions for MPDSC. Based on such result, we prove that RCPLD implies error bounds for MPDSC. These two results also hold for CCOP. All of these disjunctive-type constraint qualifications for CCOP derived from MPDSC are weaker than those from the relaxed complementarity-type reformulation in some sense. / Graduate

Inom linja ̈r algebra har varje vektorrum ett s ̊a kallat dualrum, vilket är ett vektorrum bestående av alla linjära funktioner från det ursprungliga rummet till sin kropp. Att beräkna dimensionen av ett dualrum tillhörande ett ändlig-dimensionellt vektorrum är relativt enkelt, för oändlig-dimensionella vektorrum är det mer komplicerat. Den sats vi ska diskutera, Erdős–Kaplansky Satsen, ämnar lösa den frågan med påståendet att ett dualrum tillhörande ett oändlig-dimensionellt vektorrum har dimension lika med sin kardinalitet.

We examine the complexity and expressivity of the combination of the Description Logic ALCQI with a terminological formalism based on cardinality restrictions on concepts. This combination can naturally be embedded into C², the two variable fragment of predicate logic with counting quantifiers. We prove that ALCQI has the same complexity as C² but does not reach its expressive power. / An abriged version of this paper has been submitted to CSL'99

Software product line engineering is a common method for designing complex software systems. Feature modeling is the most common approach to specify product lines. A feature model is a feature diagram (a special tree of features) plus some crosscutting constraints. Feature modeling languages are grouped into basic and cardinality-based models. The common understanding of the semantics of feature models is a Boolean semantics. We discuss a major deficiency of this semantics and fix it by applying, in turn, modal logic, the theory of multisets, and formal language theory. In order to adequately represent the semantics of basic models, we propose a Kripke semantics and show that basic feature modeling needs a modal rather than Boolean logic. We propose two multiset based theories for cardinality-based feature diagrams, called flat and hierarchical semantics. We show that the hierarchical semantics of a given cardinality-based diagram captures all information in the diagram. We also charac- terize sets of multisets, which can provide a hierarchical semantics of some diagrams. We provide three different reduction processes going from a cardinality-based diagram to an appropriate regular expression. As for crosscutting constraints, we propose a formal language interpretation of them. We also characterize some existing analysis operations over feature models in terms of operations on the corresponding languages and discuss the relevant decidability problems. / Thesis / Doctor of Philosophy (PhD)

Cardinality estimation is a fundamental task in database query processing and optimization. As shown in recent papers, machine learning (ML)-based approaches may deliver more accurate cardinality estimations than traditional approaches. However, a lot of training queries have to be executed during the model training phase to learn a data-dependent ML model making it very time-consuming. Many of those training or example queries use the same base data, have the same query structure, and only differ in their selective predicates. To speed up the model training phase, our core idea is to determine a predicate-independent pre-aggregation of the base data and to execute the example queries over this pre-aggregated data. Based on this idea, we present a specific aggregate-based training phase for ML-based cardinality estimation approaches in this paper. As we are going to show with different workloads in our evaluation, we are able to achieve an average speedup of 90 with our aggregate-based training phase and thus outperform indexes.

Text in Afrikaans / A study of the philosophical and historical foundations of infinity highlights the problematic development of infinity. Aristotle distinguished between potential and actual infinity, but rejected the latter. Indeed, the interpretation of actual infinity leads to contradictions as seen in the paradoxes of Zeno. It is difficult for a human being to understand actual infinity. Our logical schemes are adapted to finite objects and events. Research shows that students focus primarily on infinity as a dynamic or neverending process. Individuals may have contradictory intuitive thoughts at different times without being aware of cognitive conflict. The intuitive thoughts of students about both the actual (at once) infinite and potential (successive) infinity are very complex. The problematic nature of actual infinity and the contradictory intuitive cognition should be the starting point in the teaching of the concept infinity. / Educational Studies / M.Ed. (Mathematic Education)