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)

Modern database systems use a query optimizer to identify the most efficient strategy, called “query execution plan”, to execute declarative SQL queries. The role of the query optimizer is especially critical for the complex decision-support queries featured in current data warehousing and data mining applications. Given an SQL query template that is parametrized on the selectivities of the participating base relations and a choice of query optimizer, a plan diagram is a color-coded pictorial enumeration of the execution plan choices of the optimizer over the query parameter space. Complementary to the plan-diagrams are cost and cardinality diagrams which graphically plot the estimated execution costs and cardinalities respectively, over the query parameter space. These diagrams are collectively known as optimizer diagrams. Optimizer diagrams have proved to be a powerful tool for the analysis and redesign of modern optimizers, and are gaining interest in diverse industrial and academic institutions. However, their utility is adversely impacted by the impractically large computational overheads incurred when standard brute-force approaches are used for producing fine-grained diagrams on high-dimensional query templates. In this thesis, we investigate strategies for efficiently producing close approximations to complex optimizer diagrams. Our techniques are customized for different classes of optimizers, ranging from the generic Class I optimizers that provide only the optimal plan for a query, to Class II optimizers that also support costing of sub-optimal plans and Class III optimizers which offer enumerated rank-ordered lists of plans in addition to both the former features. For approximating plan diagrams for Class I optimizers, we first present database oblivious techniques based on classical random sampling in conjunction with nearest neighbor (NN) inference scheme. Next we propose grid sampling algorithms which consider database specific knowledge such as(a) the structural differences between the operator trees of plans on the grid locations and (b) parametric query optimization principle. These algorithms become more efficient when modified to exploit the sub-optimal plan costing feature available with Class II optimizers. The final algorithm developed for Class III optimizers assume plan cost monotonicity and utilize the rank-ordered lists of plans to efficiently generate completely accurate optimizer diagrams. Subsequently, we provide a relaxed variant, which trades quality of approximation, for reduction in diagram generation overhead. Our proposed algorithms are capable of terminating according to user given error bound for plan diagram approximation. For approximating cost diagrams, our strategy is based on linear least square regression performed on a mathematical model of plan cost behavior over the parameter space, in conjunction with interpolation techniques. Game theoretic and linear programming approaches have been employed to further reduce the error in cost approximation. For approximating cardinality diagrams, we propose a novel parametrized mathematical model as a function of selectivities for characterizing query cardinality behavior. The complete cardinality model is constructed by clustering the data points according to their cardinality values and subsequently fitting the model through linear least square regression technique separately for each cluster. For non-sampled data points the cardinality values are estimated by first determining the cluster they belong to and then interpolating the cardinality value according to the suitable model. Extensive experimentation with a representative set of TPC-H and TPC-DS-based query templates on industrial-strength optimizers indicates that our techniques are capable of delivering 90% accurate optimizer diagrams while incurring no more than 20% of the computational overheads of the exhaustive approach. Infact, for full-featured optimizers, we can guarantee zero error optimizer diagrams which usually require less than 10% overheads. Our results exhibit that (a) the approximation is materially faithful to the features of the exact optimizer diagram, with the errors thinly spread across the picture and Largely confined to the plan transition boundaries and (b) the cost increase at the non-sampled point due to assignment of sub-optimal plan is also limited. These approximation techniques have been implemented in the publicly available Picasso optimizer visualizer tool. We have also modified PostgreSQL’s optimizer to incorporate costing of sub-optimal plans and enumerating rank-ordered lists of plans. In addition to these, we have designed estimators for predicting the time overhead involved in approximating optimizer diagrams with regard to user given error bounds. In summary, this thesis demonstrates that accurate approximations to exact optimizer diagrams can indeed be obtained cheaply and consistently, with typical overheads being an order of magnitude lower than the brute-force approach. We hope that our results will encourage database vendors to incorporate the foreign-plan-costing and plan-rank-list features in their optimizer APIs.