Orientador: Arnaldo Vieira Moura / Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Computação / Made available in DSpace on 2018-08-25T06:09:05Z (GMT). No. of bitstreams: 1 Grilo_AlexBredariol_M.pdf: 1279418 bytes, checksum: 80f0b105ffcfb57f6e43c530b32cb7a9 (MD5) Previous issue date: 2014 / Resumo: A Computação Quântica é um tópico relativamente recente e pouco conhecido, principalmente no meio da Computação. Seu estudo surgiu na tentativa de físicos simularem sistemas regidos pela Mecânica Quântica por computadores clássicos, o que se conjecturou inviável. Portanto, um novo modelo computacional que utiliza a estrutura quântica da matéria para computar foi teorizado para suprir estas deficiências. Este trabalho tem como objetivo principal estudar as influências da Computação Quântica na Teoria da Computação. Para atingir tal objetivo, primeiramente são expostos os conhecimentos básicos da Mecânica Quântica através de uma linguagem voltada para Teóricos de Computação sem conhecimento prévio na área, de forma a remover a barreira inicial sobre o tema. Em seguida, serão apresentadas inovações na área da Teoria de Computação oriundas da Computação Quântica. Começaremos com os principais Algoritmos Quânticos desenvolvidos até hoje, que foram os primeiros passos para demonstrar a possível superioridade computacional do novo modelo. Dentre estes algoritmos, apresentaremos o famoso Algoritmo de Shor, que fatora números em tempo polinomial. Adicionalmente, neste trabalho foram estudados tópicos mais avançados e atuais em Computabilidade e Complexidade Quânticas. Sobre Autômatos Quânticos, foram estudados aspectos de um modelo que mistura estados clássicos e quânticos, focando na comparação do poder computacional em relação aos Autômatos Finitos Clássicos. Do ponto de vista de Classes de Complexidade, será abordada a questão se em linguagens da classe QMA, o análogo quântico da classe NP, consegue-se atingir probabilidade de erro nulo na aceitação de instâncias positivas / Abstract: Quantum Computing is a relatively new area and it is not well known, mainly among Computer Scientists. It has emerged while physicists tried to simulate Quantum Systems with classical computers efficiently, which has been conjectured impossible. Then, a new computational model that uses the quantum structure of matter to perform computations has been theorized in order to perform these operations. We intend in this work to study the influences of Quantum Computing in Theoretical Computer Science. In order to achieve this goal, we start by presenting the basics of Quantum Computing to Theoretical Computer Science readers with no previous knowledge in this area, removing any initial barriers for a clean understanding of the topic. We will then follow by showing innovations in Theoretical Computer Science introduced by Quantum Computation. We start by showing the main Quantum Algorithms, that exemplify advantages of the new computational model. Among these algorithms, we will present the Shor Algorithm that factors numbers in polynomial time. We follow with more advanced topics in Quantum Computability and Complexity. We study Quantum Finite Automata Models that work with quantum and classical states, focusing on comparing their computational power with Deterministic Finite Automata. In Complexity Theory, we study the question if for languages in QMA, the quantum analogue of NP, zero probability error can be achieved in yes-instances / Mestrado / Ciência da Computação / Mestre em Ciência da Computação

Orientador: Rosangela Ballini / Tese (doutorado) - Universidade Estadual de Campinas, Instituto de Economia / Made available in DSpace on 2018-08-19T16:56:59Z (GMT). No. of bitstreams: 1 Aggio_GustavodeOliveira_D.pdf: 2849218 bytes, checksum: 6c073c3959c91ca84f78c51c5873c6aa (MD5) Previous issue date: 2011 / Resumo: Nesta tese buscamos compreender aspectos das dinâmicas dos fenômenos da aceitabilidade da moeda, da estrutura de taxas de juros e do processo inflacionário utilizando a abordagem dos sistemas dinâmicos complexos. Nossa justificativa é que o comportamento dos agentes econômicos ocorre de forma descentralizada e, ao menos em parte, delimitado por uma estrutura funcional que, por sua vez, também é sujeita a variação ao longo do tempo. Portanto, nossa abordagem deve considerar um fenômeno em processo e sujeito a não-linearidades. A tese está dividida em cinco capítulos. No primeiro nós expomos conceitos gerais sobre sistemas dinâmicos complexos, auto-organização, modelos baseados em agentes e lógica fuzzy e conjuntos probabilísticos. Explicitamos, assim, as características que atribuímos aos fenômenos estudados e o método empregado para análise. No segundo capítulo nós oferecemos uma teoria em processo para a emergência da aceitabilidade generalizada de uma moeda, assim como dois modelos para a demonstração das possibilidades deste processo. No terceiro capítulo nós observamos estudos sobre a dinâmica da estrutura das taxas de juros e sugerimos uma explicação para a diferença empiricamente observada entre a dinâmica das taxas de juros de curto e longo prazo. No quarto capítulo nós realizamos um estudo sobre a volatilidade e a persistência na série de variações percentuais do Índice de Preços ao Consumidor dos Estados Unidos. No capítulo final nós comparamos a abordagem do processo inflacionário da chamada nova síntese neoclássica com um modelo de dinâmica de preços fora do equilíbrio / Abstract: In this thesis we aim to understand aspects of the dynamics of the phenomena of the acceptability of the money, of the structure of interest rates and of the inflationary process using the approach of complex dynamic systems. Our explanation is that the behavior of the economic occurs in a decentralized manner, and at least partially delimited by a functional structure which, in turn, is also subject to variation over time. Therefore, our approach should consider a phenomenon in the process and subject to the nonlinearities. The thesis is divided into five chapters. At first chapter we expose the general concepts about complex dynamic systems, self-organization, agent-based models and fuzzy logic and probabilistic sets. Made explicit, so the characteristics we attribute to the phenomena studied and the analysis method. In the second chapter we offer a theory in process for the emergence of generalized acceptance of money, as well as two models for demonstrating the possibilities of this process. In the third chapter we observe dynamics studies of the structure of interest rates and suggest an explanation for the empirically observed differences between the dynamics of interest rates for short and long term. In the fourth chapter we perform a study on the volatility and persistence in the series of percentage changes in the Consumer Price Index of the United States. In the final chapter we compare the approach of the inflationary process of the so-called new neoclassical synthesis with a model of price dynamics out of balance / Doutorado / Teoria Economica / Doutor em Ciências Econômicas

[pt] Os códigos de prefixo têm importância fundamental na comprenssão e transmissão de dados. Estes códigos também apresentam relações com problemas de busca. Neste tese, apresentamos novos resultados estruturais e algorítimos sobre a classe dos códigos de prefixo. Explicamos teoricamente as boas taxas de compressão observadas para alguns métodos utilizados na prática. Propomos também algoritmos eficientes para construção de códigos de prefixo ótimos e variantes. Os principais resultados aqui descritos são os seguintes: - um novo algoritmo paralelo para construção de códigos de prefixos ótimos: - uma cota superior para a perda de compressão introduzida pela restrição de comprimento nos códigos de prefixo: - uma cota superior para a perda de compressão introduzida pela restrição de comprimento nos códigos de prefixo alfabéticos: - um algoritmo aproximativo e linear para construção de códigos de prefixo com restrição de comprimento: - um algoritmo aproximativo com complexidade 0(n log n) para construção de códigos de prefixo alfabéticos com restrição de comprimento: - uma nova versão de algoritmo WARM-UP com complexidade fortemente polinomial: - um algoritmo linear para reconhecer códigos de prefixo ótimos com restrição de comprimento: - uma prova afirmativa da conjectura de Vitter sobre o desempenho dos códigos de Huffmann dinâmicos construídos pelo algoritmo FGK (Faller, Gallanger e Knuth) / [en] The prefix codes play an important role in data compression and data communication. These codes also present relation with search problems. In this thesis, we present new structural and algorithmic results concerning the prefix code class. We theoretically explain results related to the high compression rates of some methods that have been used for pratical purposes. We also propose efficient algorthims for constructing optimal prefix codes and some variants. The major results are listed below: -a new parallel algorithm for constructing optimal prefix codes: -a sharp upper bound for the compression loss introduced due usage of length restricted prefix codes: -an upper bound for the compression loss introduced due the usage of length restricted alphabetic prefix codes: -an 0(n log n) time approximative algorithm for constructing lenght restricted prefix code: -a 0(n log n) time approximative algorithm for constructing lenght restricted alphabetic prefix code: -a strongly polinomial version for the WARM-UP algorithm: -a linear time algorithm for recognizing optimal length restricted prefix codes: -a proof for Vitter´s conjecture about the perfomance of the Dynamic Huffman Codes constructed by FGK (Faller, Gallager and Knuth) algorithm.

With the increasing level of complexity that leaders face today, represented in the accelerating pace of technology advancement and globalization, along with the climate change indicators reaching unprecedented levels, the need for good leadership quality has become more crucial than ever. The Framework for Strategic Sustainable Development provides a systems perspective, a principle-based definition and a way to strategically move towards sustainability, however still there is a need to specify what is required for leaders to lead organizations through this process. The aim of the thesis is to explore how corporate leadership development companies can develop the essential leadership competencies to address the sustainability challenge. The study used the Key Competences in Sustainability Framework as a base to interview six leadership development companies from different areas in the world. The findings revealed that there is an essential need for self-development for leaders to handle complexity, as well as the need from leaders to create the proper conditions for their organizations to utilize the competences from the KCSF. Furthermore the results also showcased the need for standard common definition regarding sustainability.

Ladner’s theorem states that if P ≠ NP, then there are problems in NP that are neither in P nor NP-complete. Csp(Γ) is a class of problems containing many well-studied combinatorial problems in NP. Csp(Γ) problems are of the form: given a set of variables constrained by a set of constraints from the set of allowed constraints Γ, is there an assignment to the variables satisfying all constraints? A famous, and in the light of Ladner’s theorem, surprising conjecture states that there is a complexity dichotomy for Csp(Γ); that is, for any fixed finite Γ, the Csp(Γ) problem is either in P or NP-complete. In this thesis we focus on problems expressible in the Csp(Γ) framework with different computational goals, such as: counting the number of solutions, deciding whether two sets of constraints have the same set of solutions, deciding whether all minimal solutions of a set of constraints satisfies an additional constraint etc. By doing so, we capture a host of problems ranging from fundamental problems in nonmonotonic logics, such as abduction and circumscription, to problems regarding the equivalence of systems of linear equations. For several of these classes of problem, we are able to give complete complexity classifications and rule out the possibility of problems of intermediate complexity. For example, we prove that the inference problem in propositional variable circumscription, parameterized by the set of allowed constraints Γ, is either in P, coNP-complete, or ΠP/2-complete. As a by-product of these classifications, new tractable cases and hardness results for well-studied problems are discovered. The techniques we use to obtain these complexity classifications are to a large extent based on connections between algebraic clone theory and the complexity of Csp(Γ). We are able to extend these powerful algebraic techniques to several of the problems studied in this thesis. Hence, this thesis also contributes to the understanding of when these algebraic techniques are applicable and not.

Nous sommes partie d’un constat, celui de la fréquence, de la réitération, et surtout de la persistance, depuis des dizaines d’années, de nombreuses erreurs d’un genre particulier relatives à l’emploi des pronoms personnels du français, produites par les apprenants tunisiens. Nous avons formé le projet de travailler sur les divers obstacles et les différentes sources de difficultés auxquels se heurte l’apprenant tunisien dans l’apprentissage et l’emploi de ce fait linguistique. Les problèmes liés à cet apprentissage et à cet emploi semblent présenter la double particularité d’être d’un côté spécifiques à la nature de ce fait de langue (cette catégorie de morphèmes est très complexe à cause des contraintes morpho – syntaxiques qu’elle présente) et inhérents à ses degrés de convergence et de divergence avec les faits de langue correspondants dans la langue maternelle de l’apprenant, le dialecte tunisien, et dans « sa deuxième première langue », l’arabe classique ; et d’un autre côté, généraux c’est-à-dire liés au contexte dans lequel cette langue est enseigné, contexte où plusieurs paramètres entrent en jeu : problèmes sociolinguistiques et psycholinguistiques. La question du statut du français enseigné en Tunisie est posé, statut qui varie d’un cycle à l’autre, et d’une région à l’autre et qui exige, dans tous les cas, des outils, des méthodes et des pratiques pédagogiques appropriés.La thèse que nous développons dans ce travail repose sur l’idée qu’à l’origine des problèmes constatés dans l’emploi des pronoms personnels, se trouvent ces différents facteurs généraux et spécifiques qui ont toujours agi à la défaveur de l’enseignement-apprentissage de la grammaire en général et qui, malgré la succession des réformes, n’ont jamais été pris en charge. Ainsi, l’échec de l’enseignement-apprentissage des pronoms personnels est essentiellement lié à l’absence de prise en charge des vraies difficultés rencontrées dans ce contexte par les enseignants et les apprenants. / We started from a general remark about the frequency, reiteration and particularly the persistence, since many years, of numerous errors of a particular kind. These errors are relative to the use of personal pronouns of the French language produced by Tunisian learners.We developed the project through working on the diverse obstacles of different sources to which the Tunisian learner is exposed in the learning and use of this linguistic fact. The problems related to this learning and this use seem to be of a double particularity. One the one hand, the problems are specific to the nature of this element in the language (This category of morphemes is very complex because of the morpho-syntactic constraints which it presents) and inherent to its convergence and divergence degrees with the corresponding language facts of the learner’s mother tongue, the Tunisian Arabic dialect, and also with the “first second language”, the Standard Arabic. On the other hand, they are general which means that they are related to the context in which the language is taught. Many parameters, mainly sociolinguistic and psycholinguistic problems, intervene in this context. The issue of the status of the French taught in Tunisia is raised. This status varies from one cycle to another and one region to another and which requires, in all cases, appropriate methods and pedagogical practices. The thesis that we develop in this work is built on the idea that the remarked problems in the use of personal pronouns originate from different general and specific factors that have always acted unfavorably in the learning-teaching of the grammar in general which, despite the subsequent reforms, have never been taken into consideration. Hence, the failure of the learning-teaching of personal pronouns is essentially related to the absence of consideration of the real difficulties involved in this context both to the teachers and the learners.

The subject for this thesis is to find a basis which minimizes the number of bit operations involved in a finite field multiplication. The number of bases of a finite field increases quickly with the extension degree, and it is therefore important to find efficient search algorithms. Only fields of characteristic two are considered. A complexity measure is introduced, in order to compare bases. Different methods and algorithms are tried out, limiting the search in order to explore larger fields. The concept of equivalent bases is introduced. A comparison is also made between the Polynomial, Normal and Triangular Bases, referred to as known bases, as they are commonly used in implementations. Tables of the best found known bases for all fields up to GF(2^24) is presented. A list of the best found bases for all fields up to GF(2^25) is also given.

This collected volume gives a concise account of the most relevant scientific results of the COST Action IS1104 "The EU in the new complex geography of economic systems: models, tools and policy Evaluation", a four-year project supported by COST (European Cooperation in Science and Technology). It is divided into three parts reflecting the different perspectives under which complex spatial economic systems have been studied: (i) the Macro perspective looks at the interactions among international or regional trading partners; (ii) the Meso perspective considers the functioning of (financial, labour) markets as social network structures; and, finally, (iii) the Micro perspective focuses on the strategic choices of single firms and households. This Volume points also at open issues to be addressed in future research.

One of the most important issues in contemporary database application became processing of the large amount of data. Second problem is different characteristic of the data that are processed by the system. Those data are perceived as large continuous streams of elements rather than finite sets of elements. This thesis presents new class of database systems that handles data stream processing, issues and benefits form using these systems in the context of telecommunication systems. / This thesis presents stream databases which are able to process data streams. Moreover advantages and disadvantages of those systems are presented. / przemyslaw.pawluk@pwr.wroc.pl (+48)697-958-666

This is a study of the emotion terms happy and happiness conducted in order to identify the possible grounds in which these notions are perceived by the British English speaking speech community and how people use these terms according to their conceptual frameworks. Basically, it is supposed that the terms happy and happiness are very close in their meanings and they imply more or less the same sense from different angles. This prediction, however, is only partly true. Through this study it is found that there is not as much overlap in the meaning of happy and happiness as one would expect.