Made available in DSpace on 2016-04-28T14:16:18Z (GMT). No. of bitstreams: 1 Danilo Gustavo Bispo.pdf: 2512902 bytes, checksum: 2261f415993066c8892733480af9c1c9 (MD5) Previous issue date: 2013-04-15 / In this paper I present initially in order to contextualize the influences involved in the emergence of the theory of Alan Turing computability on a history of some issues that mobilized mathematicians in the early twentieth century. In chapter 1, an overview will be exposed to the emergence of ideology Formalist designed by mathematician David Hilbert in the early twentieth century. The aim was to base the formalism elementary mathematics from the method and axiomatic theories eliminating contradictions and paradoxes. Although Hilbert has not obtained full success in your program, it will be demonstrated how their ideas influenced the development of the theory of computation Turing. The theory proposes that Turing is a decision procedure, a method that analyzes any arbitrary formula of logic and determines whether it is likely or not. Turing proves that there can be no general decision. For that will be used as a primary source document On Computable Numbers, with an application to the Entscheidungsproblem. In Chapter 2, you will see the main sections of the document Turing exploring some of its concepts. The project will be completed with a critique of this classic text in the history of mathematics based on historiographical proposals presented in the first chapter / Neste texto apresento inicialmente com o intuito de contextualizar as influências envolvidas no surgimento da teoria de Alan Turing sobre computabilidade um histórico de algum problemas que mobilizaram os matemáticos no início do século XX. No capítulo 1, será exposto um panorama do surgimento da ideologia formalista concebida pelo matemático David Hilbert no início do século XX. O objetivo do formalismo era de fundamentar a matemática elementar a partir do método e axiomático, eliminando das teorias suas contradições e paradoxos. Embora Hilbert não tenha obtido pleno êxito em seu programa, será demonstrado como suas concepções influenciaram o desenvolvimento da teoria da computação de Turing. A teoria que Turing propõe é um procedimento de decisão, um método que analisa qualquer fórmula arbitrária da lógica e determina se ela é provável ou não. Turing prova que nenhuma decisão geral pode existir. Para tanto será utilizado como fonte primária o documento On computable numbers, with an application to the Entscheidungsproblem. No capítulo 2, será apresentado as principais seções do documento de Turing explorando alguns de seus conceitos. O projeto será finalizado com uma crítica a este texto clássico da história da matemática com base nas propostas historiográficas apresentadas no primeiro capítulo

In formal language theory, studying shortest strings in languages, and variations thereof, can be useful since these strings can serve as small witnesses for properties of the languages, and can also provide bounds for other problems involving languages. For example, the length of the shortest string accepted by a regular language provides a lower bound on the state complexity of the language. In Chapter 1, we introduce some relevant concepts and notation used in automata and language theory, and we show some basic results concerning the connection between the length of the shortest string and the nondeterministic state complexity of a regular language. Chapter 2 examines the effect of the intersection operation on the length of the shortest string in regular languages. A tight worst-case bound is given for the length of the shortest string in the intersection of two regular languages, and loose bounds are given for two variations on the problem. Chapter 3 discusses languages that are defined over a free group instead of a free monoid. We study the length of the shortest string in a regular language that becomes the empty string in the free group, and a variety of bounds are given for different cases. Chapter 4 mentions open problems and some interesting observations that were made while studying two of the problems: finding good bounds on the length of the shortest squarefree string accepted by a deterministic finite automaton, and finding an efficient way to check if a finite set of finite words generates the free monoid. Some of the results in this thesis have appeared in work that the author has participated in \cite{AngPigRamSha,AngShallit}.

We investigate the geometric phase (GP) acquired by the states of a spin-1/2 nucleus which is subject to a static magnetic field. This nucleus as the carrier system of GP, is taken as coupled to a dissipative environment, so that it evolves non-unitarily. We study the effects of different characteristics of different environments on GP as nucleus evolves in time. We showed that magnetic field strength is the primary physical parameter that determines the stability of GP / its stability decreases as the magnetic field strength increases. (By decrease in stability what we mean is the increase in the time rate of change of GP.) We showed that this decrease can be very rapid, and so it could be impossible to make use of it as a quantum logic gate in quantum information theory (QIT). To see if these behaviors differ in different environments, we analyze the same system for a fixed temperature environment which is under the influence of an electromagnetic field in a squeezed state. We find that the general dependence of GP on magnetic field does not change, but this time the effects are smoother. Namely, increase in magnetic field decreases the stability of GP also for in this environment / but this decrease is slower in comparison with the former case, and furthermore it occurs gradually. As a second problem we examine the entanglement of two atoms, which can be used as a two-qubit system in QIT. The entanglement is induced by an external quantum system. Both two-level atoms are coupled to a third two-level system by dipole-dipole interaction. The two atoms are assumed to be in ordinary vacuum and the third system is taken as influenced by a certain environment. We examined different types of environments. We show that the steady-state bipartite entanglement can be achieved in case the environment is a strongly fluctuating, that is a squeezed-vacuum, while it is not possible for a thermalized environment.

In formal language theory, studying shortest strings in languages, and variations thereof, can be useful since these strings can serve as small witnesses for properties of the languages, and can also provide bounds for other problems involving languages. For example, the length of the shortest string accepted by a regular language provides a lower bound on the state complexity of the language. In Chapter 1, we introduce some relevant concepts and notation used in automata and language theory, and we show some basic results concerning the connection between the length of the shortest string and the nondeterministic state complexity of a regular language. Chapter 2 examines the effect of the intersection operation on the length of the shortest string in regular languages. A tight worst-case bound is given for the length of the shortest string in the intersection of two regular languages, and loose bounds are given for two variations on the problem. Chapter 3 discusses languages that are defined over a free group instead of a free monoid. We study the length of the shortest string in a regular language that becomes the empty string in the free group, and a variety of bounds are given for different cases. Chapter 4 mentions open problems and some interesting observations that were made while studying two of the problems: finding good bounds on the length of the shortest squarefree string accepted by a deterministic finite automaton, and finding an efficient way to check if a finite set of finite words generates the free monoid. Some of the results in this thesis have appeared in work that the author has participated in \cite{AngPigRamSha,AngShallit}.

Orientador: Orlando Lee / Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Computação / Made available in DSpace on 2018-08-22T15:27:35Z (GMT). No. of bitstreams: 1 Curi_RafaelLima_M.pdf: 1469554 bytes, checksum: 8367cf52c9256338ee2963b9a9cdf41d (MD5) Previous issue date: 2013 / Resumo: Neste trabalho estudamos Jogos de Roteamento. Esta subclasse de jogos e uma das mais estudadas na literatura e permite modelar de forma relativamente simples vários cenários realistas. Por exemplo, tráfego de veículos em rodovias, transporte de mercadorias, redes de telefonia, redes de computadores como a Internet, etc. Analisamos as principais variantes de jogos de roteamento, destacando suas diferenças. Comparamos jogos atômicos versus jogos não-atômicos, jogos com fluxo divisível versus jogos com fluxo indivisível, jogos com demanda uniforme versus jogos com demanda genérica e jogos com redes específicas versus jogos com redes genéricas. Focamos nosso estudo na existência, unicidade e quantificação da ineficiência de equilíbrios que emergem do comportamento independente e egoísta dos jogadores. Estudamos o equilíbrio de Wardrop para jogos não-atômicos e o equilíbrio de Nash para jogos atômicos. Na literatura, notamos que a existência e unicidade de um equilíbrio dependem basicamente de três fatores: pressupostos nas funções que definem os custos dos segmentos de uma rota, tipo dos jogadores (atômicos ou não-atômicos, com demandas iguais ou diferentes) e topologia da rede. Apresentamos também os principais resultados de ineficiência obtidos para as métricas Preço da Anarquia (PoA) e Limite de Bicritério. Nos resultados que vimos, observamos que jogos não-atômicos possuem um PoA menor que o de jogos atômicos, jogos com fluxo divisível possuem um PoA menor que o de jogos com fluxo indivisível e jogos com demanda uniforme um PoA menor que o de jogos com demanda genérica / Abstract: In this work, we study Routing Games. This subclass of games is one of the most studied in the literature and allows us to model several realistic scenarios, in a relatively simple way. For instance, road traffic, freight transportation, telephone networks, computer networks like the Internet, etc. We analyze the main variants of routing games, emphasizing their differences. We compare atomic games versus nonatomic games, unsplittable flow games versus splittable flow games, unweighted games versus weighted games and specific network games versus generic network games. We focus our study on the existence, uniqueness and quantification of the inefficiency of equilibria that emerge from the independent and selfish behavior of the players. We study the Wardrop equilibrium for nonatomic games and the Nash equilibrium for atomic games. In the literature, we note that the existence and uniqueness of an equilibrium depends basically on three factors: assumptions on the functions that define the costs of the segments of a route, type of the players (atomic or nonatomic, with equal or different demands), and network topology. We present the main results of inefficiency obtained for the metrics Price of Anarchy (PoA) and Bicriteria Limit. In the results we have considered, we noticed that nonatomic games have lower PoA than the atomic ones, splittable flow games have lower PoA than the unsplittable flow ones, and unweighted games have lower PoA than the weighted ones / Mestrado / Ciência da Computação / Mestre em Ciência da Computação

<p>As more and more datasets with self-exciting properties become available, the demand for robust models that capture contagion across events is also getting stronger. Hawkes processes stand out given their ability to capture a wide range of contagion and self-excitation patterns, including the transmission of infectious disease, earthquake aftershock distributions, near-repeat crime patterns, and overdose clusters. The Hawkes process is flexible in modeling these various applications through parametric and non-parametric kernels that model event dependencies in space, time and on networks.</p> <p>In this thesis, we develop new frameworks that integrate Hawkes Process models with multi-armed bandit algorithms, high dimensional marks, and high-dimensional auxiliary data to solve problems in search and rescue, forecasting infectious disease, and early detection of overdose spikes.</p> <p>In Chapter 3, we develop a method applications to the crisis of increasing overdose mortality over the last decade.  We first encode the molecular substructures found in a drug overdose toxicology report. We then cluster these overdose encodings into different overdose categories and model these categories with spatio-temporal multivariate Hawkes processes. Our results demonstrate that the proposed methodology can improve estimation of the magnitude of an overdose spike based on the substances found in an initial overdose. </p> <p>In Chapter 4, we build a framework for multi-armed bandit problems arising in event detection where the underlying process is self-exciting. We derive the expected number of events for Hawkes processes given a parametric model for the intensity and then analyze the regret bound of a Hawkes process UCB-normal algorithm. By introducing the Hawkes Processes modeling into the upper confidence bound construction, our models can detect more events of interest under the multi-armed bandit problem setting. We apply the Hawkes bandit model to spatio-temporal data on crime events and earthquake aftershocks. We show that the model can quickly learn to detect hotspot regions, when events are unobserved, while striking a balance between exploitation and exploration. </p> <p>In Chapter 5, we present a new spatio-temporal framework for integrating Hawkes processes with multi-armed bandit algorithms. Compared to the methods proposed in Chapter 4, the upper confidence bound is constructed through Bayesian estimation of a spatial Hawkes process to balance the trade-off between exploiting and exploring geographic regions. The model is validated through simulated datasets and real-world datasets such as flooding events and improvised explosive devices (IEDs) attack records. The experimental results show that our model outperforms baseline spatial MAB algorithms through rewards and ranking metrics.</p> <p>In Chapter 6, we demonstrate that the Hawkes process is a powerful tool to model the infectious disease transmission. We develop models using Hawkes processes with spatial-temporal covariates to forecast COVID-19 transmission at the county level. In the proposed framework, we show how to estimate the dynamic reproduction number of the virus within an EM algorithm through a regression on Google mobility indices. We also include demographic covariates as spatial information to enhance the accuracy. Such an approach is tested on both short-term and long-term forecasting tasks. The results show that the Hawkes process outperforms several benchmark models published in a public forecast repository. The model also provides insights on important covariates and mobility that impact COVID-19 transmission in the U.S.</p> <p>Finally, in chapter 7, we discuss implications of the research and future research directions.</p>

[pt] Nesse trabalho, propomos o problema AdInvest, que modela o processo decisiório de alocação de investimento em marketing digital do ponto de vista do anunciante. Para o problema proposto, definimos um algoritmo chamado balGreedy, e provamos suas garantias para instâncias determísticas e estocásticas do AdInvest. Os teoremas provados garantem ao nosso algoritmo resultados de pior caso relativamente próximos ao OPT, em diversos tipos de instâncias levantadas ao decorrer do trabalho. Em especial, focamos nas instâncias que modelam o efeito de saturação das audiências, que se faz presente na dinâmica de anúncios online. Como mostrado nos experimentos computacionais, o algoritmo balGreedy se mostrou consistentemente eficiente em comparação com as políticas alternativas adotadas, tanto nas instâncias que foram geradas por simulação, quanto em instâncias reais obtidas a partir de dados de um anunciante do Facebook Ads. / [en] In this work, we propose the problem AdInvest, which models the decision-making process for allocating investment in digital marketing from the advertiser perspective. For the proposed problem, we define an algorithm called balGreedy, and we prove its guarantees in deterministic and stochastic instances of the AdInvest. The proven theorems assure to our algorithm worst-case results relatively close to OPT, in several types of instances raised during the work. In particular, we focus on the instances that model the audience saturation effect, which is present in the dynamics of online advertisements. As shown in the computational experiments, the balGreedy algorithm had been consistently efficient compared to the alternative policies adopted, both in the instances generated by simulation and in real instances built from the data of a certain Facebook Ads advertiser.

No description available.

Imagine your local creamery administers a survey asking their patrons to choose their five favorite ice cream flavors. Any data collected by this survey would be an example of partially ranked data, as the set of all possible flavors is only ranked into subsets of the chosen flavors and the non-chosen flavors. If the creamery asks you to help analyze this data, what approaches could you take? One approach is to use the natural symmetries of the underlying data space to decompose any data set into smaller parts that can be more easily understood. In this work, I describe how to use permutation representations of the symmetric group to create and study efficient algorithms that yield such decompositions.

We study the properties of a number of algorithms proposed to explore the computational space generated by a very simple and general idea: the notion of a mathematical definition and a number of suggested formal interpretations ofthis idea. Theories of partial inductive definitions (PID) constitute a class of logics based on the notion of an inductive definition. Formal systems based on this notion can be used to generalize Horn-logic and naturally allow and suggest extensions which differ in interesting ways from generalizations based on first order predicate calculus. E.g. the notion of completion generated by a calculus of PID and the resulting notion of negation is completely natural and does not require externally motivated procedures such as "negation as failure". For this reason, computational issues arising in these calculi deserve closer inspection. This work discuss a number of finitary theories of PID and analyzethe algorithmic and semantical issues that arise in each of them. There has been significant work on implementing logic programming languages in this setting and we briefly present the programming language and knowledge modelling tool GCLA II in which many of the computational prob-lems discussed arise naturally in practice. / <p>Also published as SICS Dissertation no. SICS-D-19</p>