O objetivo principal deste trabalho é apresentar uma exposição detalhada do Teorema de Poincaré-Andronov-Hopf para uma família de transformações do plano. Apresentaremos também uma aplicação a um sistema dinâmico que modela a evolução do preço e excesso de demanda em um mercado constituído por uma única mercadoria. / The main purpose of this work is to present a detailed exposition of the Poincaré-Andronov-Hopf Theorem for a family of transformations in the plane. We also present an application to a dynamical system modelling the evolution of the price and the excess demand in a single asset market.

Sejam X um espaço topológico não necessariamente compacto e T:X->X uma aplicação contínua. Se f:X->R é contínua, daremos condições sobre f que garantam a existência de medidas maximizantes caracterizadas em termos de seu suporte. / Let X be a topological space not necessarily compact, and T:X->X a continuous map. If f:X->R is a continuous function, we seek conditions on f in order to guarantee existence of maximizing measures that are characterized in terms of its support.

O objetivo principal deste trabalho é apresentar uma exposição detalhada do Teorema de Poincaré-Andronov-Hopf para uma família de transformações do plano. Apresentaremos também uma aplicação a um sistema dinâmico que modela a evolução do preço e excesso de demanda em um mercado constituído por uma única mercadoria. / The main purpose of this work is to present a detailed exposition of the Poincaré-Andronov-Hopf Theorem for a family of transformations in the plane. We also present an application to a dynamical system modelling the evolution of the price and the excess demand in a single asset market.

The problem of resource allocation and management in the context of multiple crises occurring in an urban environment is challenging. In this thesis, the problem is formulated using game theory and a solution is developed based on the Nash equilibrium to optimize the allocation of resources to the different crisis events in a fair manner considering several constraints such as the availability of resources, the criticality of the events, the amount of resources requested etc. The proposed approach is targeted at managing small to medium level crisis events occurring simultaneously within a specific pre-defined perimeter with the resource allocation centers being located within the same fixed region. The objective is to maximize the utilization of the emergency response units while minimizing the response times. In the proposed model, players represent the crisis events and the strategies correspond to possible allocations. The choice of strategies by each player impacts the decisions of the other players. The Nash equilibrium condition will correspond to the set of strategies chosen by all the players such that the resource allocation optimal for a given player also corresponds to the optimal allocations of the other players. The implementation of the Nash equilibrium condition is based on the Hansen's combinatorial theorem based approximation algorithm. The proposed solution has been implemented using C++ and experimental results are presented for various test cases. Further, metrics are developed for establishing the quality and fairness of the obtained results.

Recent research has shown that it is often preferable to encode real-world problems as propositional satisfiability (SAT) problems and then solve using a general purpose SAT solver. However, much of the valuable information and structure of these realistic problems is flattened out and hidden inside the corresponding Conjunctive Normal Form (CNF) encodings of the SAT domain. Recently, systematic SAT solvers have been progressively improved and are now able to solve many highly structured practical problems containing millions of clauses. In contrast, state-of-the-art Stochastic Local Search (SLS) solvers still have difficulty in solving structured problems, apparently because they are unable to exploit hidden structure as well as the systematic solvers. In this thesis, we study and evaluate different ways to effectively recognise, model and efficiently exploit useful structures hidden in realistic problems. A summary of the main contributions is as follows: 1. We first investigate an off-line processing phase that applies resolution-based pre-processors to input formulas before running SLS solvers on these problems. We report an extensive empirical examination of the impact of SAT pre-processing on the performance of contemporary SLS techniques. It emerges that while all the solvers examined do indeed benefit from pre-processing, the effects of different pre-processors are far from uniform across solvers and across problems. Our results suggest that SLS solvers need to be equipped with multiple pre-processors if they are ever to match the performance of systematic solvers on highly structured problems. [Part of this study was published at the AAAI-05 conference]. 2. We then look at potential approaches to bridging the gap between SAT and constraint satisfaction problem (CSP) formalisms. One approach has been to develop a many-valued SAT formalism (MV-SAT) as an intermediate paradigm between SAT and CSP, and then to translate existing highly efficient SAT solvers to the MV-SAT domain. In this study, we follow a different route, developing SAT solvers that can automatically recognise CSP structure hidden in SAT encodings. This allows us to look more closely at how constraint weighting can be implemented in the SAT and CSP domains. Our experimental results show that a SAT-based mechanism to handle weights, together with a CSP-based method to instantiate variables, is superior to other combinations of SAT and CSP-based approaches. In addition, SLS solvers based on this many-valued weighting approach outperform other existing approaches to handle many-valued CSP structures. [Part of this study was published at the AAAI-05 conference]. 3. Finally, we propose and evaluate six different schemes to encode temporal reasoning problems, in particular the Interval Algebra (IA) networks, into SAT CNF formulas. We then empirically examine the performance of local search as well as systematic solvers on the new temporal SAT representations, in comparison with solvers that operate on native IA representations. Our empirical results show that zChaff (a state-of-the-art complete SAT solver) together with the best IA-to-SAT encoding scheme, can solve temporal problems significantly faster than existing IA solvers working on the equivalent native IA networks. [Part of this study was published at the CP-05 workshop].

In spite of its 150 years history, the problem of classifying all finite-dimensional division algebras over a field k is still unsolved whenever k is not algebraically closed. The present thesis concerns some different aspects of this problem, and the related problems of classifying all composition and absolute valued algebras. A tripartition of the class of all fields is given, based on the dimensions in which division algebras over a field exist. Moreover, all finite-dimensional flexible real division algebras are classified. This class includes in particular all finite-dimensional commutative real division algebras, of which two different classifications, along different lines, are presented. It is shown that every vector product algebra has dimension zero, one, three or seven, and that its isomorphism type is determined by its adherent quadratic form. This yields a new and elementary proof for the corresponding, classical result for unital composition algebras. A rotation in a Euclidean space is an orthogonal map that locally acts as a plane rotation with a fixed angle. All pairs of rotations in finite-dimensional Euclidean spaces are classified up to orthogonal similarity. A description of all composition algebras having an LR-bijective idempotent is given. On the basis of this description, all absolute valued algebras having a one-sided unity or a non-zero central idempotent are classified.

Boolean functions play an important role in the design and analysis of symmetric-key cryptosystems, as well as having applications in other fields such as coding theory. Boolean functions acting on large number of inputs introduces the problem of computing the cryptographic properties. Traditional methods of computing these properties involve transformations which require computation and memory resources exponential in the number of input variables. When the number of inputs is large, Boolean functions are usually defined by the algebraic normal form (ANF) representation. In this thesis, methods for computing the weight and nonlinearity of Boolean functions from the ANF representation are investigated. The relation between the ANF coecients and the weight of a Boolean function was introduced by Carlet and Guillot. This expression allows the weight to be computed in $mathcal{O}(2^p)$ operations for a Boolean function containing p monomials in its ANF. In this work, a more ecient algorithm for computing the weight is proposed, which eliminates the unnecessary calculations in the weight expression. By generalizing the weight expression, a formulation of the distances to the set of linear functions is obtained. Using this formulation, the problem of computing the nonlinearity of a Boolean function from its ANF is reduced to an associated binary integer programming problem. This approach allows the computation of nonlinearity for Boolean functions with high number of input variables and consisting of small number of monomials in a reasonable time.

Boolean functions play an important role in the design and analysis of symmetric-key cryptosystems, as well as having applications in other fields such as coding theory. Boolean functions acting on large number of inputs introduces the problem of computing the cryptographic properties. Traditional methods of computing these properties involve transformations which require computation and memory resources exponential in the number of input variables. When the number of inputs is large, Boolean functions are usually defined by the algebraic normal form (ANF) representation. In this thesis, methods for computing the weight and nonlinearity of Boolean functions from the ANF representation are investigated. The relation between the ANF coefficients and the weight of a Boolean function was introduced by Carlet and Guillot. This expression allows the weight to be computed in $mathcal{O}(2^p)$ operations for a Boolean function containing $p$ monomials in its ANF. In this work, a more efficient algorithm for computing the weight is proposed, which eliminates the unnecessary calculations in the weight expression. By generalizing the weight expression, a formulation of the distances to the set of linear functions is obtained. Using this formulation, the problem of computing the nonlinearity of a Boolean function from its ANF is reduced to an associated binary integer programming problem. This approach allows the computation of nonlinearity for Boolean functions with high number of input variables and consisting of small number of monomials in a reasonable time.

In this work analyses the transition from UML class diagrams to XML schema. The main problems, such as - UML does not include all the features required to describe a XML schema - are explored. Also, the principles of XML schema normalization, resemblances and differences between applying normal forms to XML documents and relational data bases are presented.

The phenotype inference from genotype in RNA viruses maps the viral genome/protein sequences to the molecular functions in order to understand the underlying molecular mechanisms that are responsible for the function changes. The inference is currently done through a laborious experimental process which is arguably inefficient, incomplete, and unreliable. The wealth of RNA virus sequence data in the presence of different phenotypes promotes the rise of computational approaches to aid the inference. Key residue identification and genotype-phenotype mapping function learning are two approaches to identify the critical positions out of hitchhikers and elucidate the relations among them. The existing computational approaches in this area focus on prediction accuracy, yet a number of fundamental problems have not been considered: the scalability of the data, the capability to suggest informative biological experiments, and the interpretability of the inferences. A common scenario of inference done by biologists with mutagenesis experiments usually involves a small number of available sequences, which is very likely to be inadequate for the inference in most setups. Accordingly biologists desire models that are capable of inferring from such limited data, and algorithms that are capable of suggesting new experiments when more data is needed. Another important but always been neglected property of the models is the interpretability of the mapping, since most existing models behave as ’black boxes’. To address these issues, in the thesis I design a supervised combinatorial filtering algorithm that systematically and efficiently infers the correct set of key residue positions from available labeled data. For cases where more data is needed to fully converge to an answer, I introduce an active learning algorithm to help choose the most informative experiment from a set of unlabeled candidate strains or mutagenesis experiments to minimize the expected total laboratory time or financial cost. I also propose Disjunctive Normal Form (DNF) as an appropriate assumption over the hypothesis space to learn interpretable genotype-phenotype functions. The challenges of these approaches are the computational efficiency due to the combinatorial nature of our algorithms. The solution is to explore biological plausible assumptions to constrain the solution space and efficiently find the optimal solutions under the assumptions. The algorithms were validated in two ways: 1) prediction quality in a cross-validation manner, and 2) consistency with the domain experts’ conclusions. The algorithms also suggested new discoveries that have not been discussed yet. I applied these approaches to a variety of RNA virus datasets covering the majority of interesting RNA phenotypes, including drug resistance, Antigenicity shift, Antibody neutralization and so on to demonstrate the prediction power, and suggest new discoveries of Influenza drug resistance and Antigenicity. I also prove the extension of the approaches in the area of severe acute community disease.