In security markets, the stock price movements are closely linked to the market information. For example, the subprime mortgage triggered a global financial crisis in 2007. Drops occurred in virtually every stock market in the world. After the Federal Reserve took several steps to address the crisis, the stock markets have been gradually stable. Reaction of the traders to the arrival information results in different patterns of the stock price movements. Thus pattern matching is an important subject in future movement prediction, rule discovery and computer aided diagnosis. In this research, we propose a pattern matching procedure to seize the similar stock price movements of two listed companies during one day. First, the algorithm of searching the longest common subsequence is introduced to sieve out the time intervals where the two listed companies have the same integrated volatility levels and price rise/drop trends. Next we transform the raw price data in the found matching time periods to the Bollinger Band Percent data, then use the power spectrum to extract low frequency components. Adjusted Pearson chi-squared tests are performed to analyze the similarity of the price movement patterns in these periods. We perform the study by simulation investigation first, then apply the procedure to empirical analysis of high frequency transaction data of NYSE.

String-to-String Correction is the process of transforming some mutable string M into an exact copy of some other string (the target string T), using a shortest sequence of well-defined edit operations. The formal STRING-TO-STRING CORRECTION problem asks for the optimal solution using just two operations: symbol deletion, and swap of adjacent symbols. String correction problems using only swaps and deletions are computationally interesting; in his paper On the Complexity of the Extended String-to-String Correction Problem (1975), Robert Wagner proved that the String-to-String Correction problem under swap and deletion operations only is NP-complete for unbounded alphabets. In this thesis, we present the first careful examination of the binary-alphabet case, which we call Binary String-to-String Correction (BSSC). We present several special cases of BSSC for which an optimal solution can be found in polynomial time; in particular, the case where T and M have an equal number of occurrences of a given symbol has a polynomial-time solution. As well, we demonstrate and prove several properties of BSSC, some of which do not necessarily hold in the case of String-to-String Correction. For instance: that the order of operations is irrelevant; that symbols in the mutable string, if swapped, will only ever swap in one direction; that the length of the Longest Common Subsequence (LCS) of the two strings is monotone nondecreasing during the execution of an optimal solution; and that there exists no correlation between the effect of a swap or delete operation on LCS, and the optimality of that operation. About a dozen other results that are applicable to Binary String-to-String Correction will also be presented. / Graduate / 0984 / 0715 / tspreen@gmail.com

FARIAS, Pablo Mayckon Silva. O problema de ordenação de rodadas e problemas de otimização associados. 2013. 127 f. Tese (Doutorado em ciência da computação)- Universidade Federal do Ceará, Fortaleza-CE, 2013. / Submitted by Elineudson Ribeiro (elineudsonr@gmail.com) on 2016-07-20T12:44:36Z No. of bitstreams: 1 2013_tese_pmsfarias.pdf: 1600516 bytes, checksum: afaccc349ce6f2d065494cd2601913c0 (MD5) / Approved for entry into archive by Rocilda Sales (rocilda@ufc.br) on 2016-07-25T12:05:15Z (GMT) No. of bitstreams: 1 2013_tese_pmsfarias.pdf: 1600516 bytes, checksum: afaccc349ce6f2d065494cd2601913c0 (MD5) / Made available in DSpace on 2016-07-25T12:05:15Z (GMT). No. of bitstreams: 1 2013_tese_pmsfarias.pdf: 1600516 bytes, checksum: afaccc349ce6f2d065494cd2601913c0 (MD5) Previous issue date: 2013 / This thesis is composed of three well-delineated parts. In the first part, we introduce the round sorting problem (RSP), which models the minimization of the usage of buffer for the temporary storage of packets to be forwarded in TDMA communications of wireless mesh networks. We present a complete foundation for the definition of the RSP, and show that the problem is NP-hard for two theoretical models of radio interference known in the literature. A mixed integer programming formulation is also presented for a purely combinatorial and applicationindependent generalization of the RSP, the SMSP problem. In the second part of the work, we deal with problems about queries on insertions into sequences of numbers. Our main result in this part of the thesis is to show how, after a preprocessing step which runs in linear time on a sequence A of arbitrary real numbers, it is possible to compute in constant time the greatest sum of a (circular or not) contiguous subsequence of the sequence which results from the insertion of a given real number x into a given position p of A. In the third part of the thesis, we use the query algorithms from the second part to obtain an efficient implementation of the GRASP metaheuristic applied to the SMSP problem. An experimental analysis of this implementation is described, in which the values of the solutions returned by the metaheuristic are compared with those of the solutions obtained through the mixed integer formulation, in the case of small instances, and with the available lower bound, in the case of larger instances. / Esta tese é composta de três partes bem-delineadas. Na primeira parte, nós introduzimos o "problema de ordenação de rodadas" (POR), que modela a minimização do uso de memória ("buffer") para o armazenamento temporário de pacotes a serem repassados em comunicações TDMA de redes de rádio em malha. Nós apresentamos uma fundamentação completa para a definição do POR, e mostramos que o problema é NP-difícil para dois modelos teóricos de interferência de rádio conhecidos na literatura. Uma formulação de programação inteira mista é também apresentada para uma generalização puramente combinatória e independente de aplicação do POR, o problema SMSP. Na segunda parte do trabalho, nós abordamos problemas de consulta sobre inserções em sequências de números. O nosso principal resultado nesta parte da tese é mostrar como, após um passo de pré-processamento que executa em tempo linear sobre uma sequência "A" de números reais quaisquer, é possível computar em tempo constante a maior soma de uma subsequência contígua (circular ou não) da sequência que resulta da inserção de dado um número real "x" numa dada posição "p" de "A". Na terceira parte da tese, nós utilizamos os algoritmos de consulta da segunda parte para obter uma implementação eficiente da meta-heurística GRASP aplicada ao problema SMSP. Uma análise experimental dessa implementação é descrita, onde os valores das soluções retornadas pela meta-heurística são comparados com os das soluções obtidas pela formulação inteira mista, no caso de instâncias pequenas, e com o limite inferior disponível, no caso de instâncias maiores.

The Pentecostal and Neo-Pentecostal movements propose a subsequent to salvation Spirit baptism. This baptism is viewed as an experience in which the Spirit either confers or awakens gifts within the life of the believer. The thesis ofthis paper is that Spirit baptism occurs at conversion. Spirit filling on the other hand is one of many metaphors to describe the work of the eschatological Spirit subsequent to salvation. This distinguishing of Spirit baptism and Spirit filling is different to the Pentecostal and Neo-Pentecostal idea that Spirit baptism and Spirit filling are synonymous experiences that occur at some point subsequent to salvation. / Christian Spirituality, Church History and Missiology / Th. M. (Systematic Theology)

Consider a set B of blue points and a set R of red points in the plane such that R ∪ B is in general position. A graph drawn in the plane whose edges are straight-line segments is called a geometric graph. We investigate the problem of drawing non-crossing properly colored geometric graphs on the point set R ∪ B. We show that if ||B| − |R|| ≤ 1 and a subset of R forms the vertices of a convex polygon separating the points of B, lying inside the polygon, from the rest of the points of R, lying outside the polygon, then there exists a non-crossing properly colored geometric path on R∪B covering all points of R ∪ B. If R∪B lies on a circle, the size of the longest non-crossing geometric path is related to the size of the largest separated matching; a separated matching is a non-crossing properly colored geometric matching where all edges can be crossed by a line. A discrepancy of R ∪ B is the maximal difference between cardinalities of color classes of intervals on the circle. When the discrepancy of R ∪ B is at most 2, we show that there is a separated matching covering asymptotically 4 5 of points of R ∪ B. During this proof we use a connection between separated matchings and the longest common subsequences between two binary sequences where the symbols correspond to the colors of the points.

No description available.

No description available.

Sequentielle Daten sind meist zeitlich geordnete (un)endliche Datenströme von Events über einem multi-dimensionalen Eventschema. Systeme über sequentiellen Daten nutzen Anfragen, um Zusammenhänge von besonderem Interesse in sequentiellen Daten zu beschreiben. Basierend auf historischen Daten müssen solche Anfragen zunächst definiert werden. Diese komplexe Aufgabe wird zumeist nicht automatisiert gelöst. In dieser Dissertation behandeln wir multi-dimensionale Teilfolge-Anfragen mit Platzhaltern und beschränkten Lücken als Anfragesprache für sequentielle Daten. Anfragen bestehen aus einer Zeichenkette s über einem Alphabet aus Symbolen und Variablen, einem globalen Fenster w und einem Tupel c aus lokalen Lückenbeschränkungen. Eine Anfrage passt zu einer Folge t über der Menge an Symbolen, falls die in s vorkommenden Variablen so durch einzelne Symbole ersetzt werden können, dass die daraus resultierende Zeichenkette s' als Teilfolge in t vorkommt. Die Gesamtlänge des Vorkommens darf dabei nicht mehr als w Events umfassen und die Distanz zwischen konsekutiven Positionen der Teilfolge muss c entsprechen. Wir untersuchen, wie zu einer Menge von Folgen S eine Anfrage gefunden werden kann, die S bestmöglich beschreibt (Suchproblem). Wir geben einen Algorithmus an, der dieses Problem löst, und analysieren dessen Komplexität. Zu entscheiden, ob eine Anfrage zu einer Folge passt (Matchingproblem), dominiert die Laufzeit des Algorithmus. Wir führen disjunktive multi-dimensionale Teilfolge-Anfragen mit Platzhaltern und beschränkten Lücken, sowie multi-dimensionale Teilfolge-Anfragen mit Platzhaltern und verallgemeinerten beschränkten Lücken als Erweiterungen ein, und passen den oben genannter Algorithmus an, um das Suchproblem für diese Anfragemodelle zu lösen. Die theoretischen Ergebnisse werden durch die Beschreibung der prototypischen Implementierung der genannten Algorithmen und der experimentellen Evaluation basierend auf synthetischen und realen Datensätzen ergänzt. / Sequence data are (usually temporally) ordered finite or infinite streams over events that are instances of a multi-dimensional schema. Systems which deal with sequence data usually use queries to detect situations of interest. However, finding such queries from historical sequence data is notoriously hard and is often assumed to be a non-automated task. In this dissertation, we propose multi-dimensional subsequence queries with wildcards and gap-size constraints (mswg-queries) as an expressive query model for sequence data. These queries consist of a query string s over an alphabet of variables and types, as well as a global window size w and a tuple c of local gap-size constraints. A query matches a trace t, i.e., a sequence of events, if the variables in s can be replaced by single types in such a way that the resulting string s' occurs as a subsequence in t that spans an area of at most w events, and the distance between consecutive positions in the subsequence conforms with c. We study the task of discovering an mswg-query that describes best a given sample, i.e. a finite set of traces. For that, we provide an algorithm solving this problem, and investigate its complexity. Our analysis identifies the subroutine for solving the matching problem (i.e., deciding whether a given query q matches in a given trace t) as the only potential bottleneck. We propose extensions of mswg-queries for the one-dimensional setting, namely, subsequence queries with generalised gap-size constraints (swgg-queries) and disjunctive subsequence queries (dswg-queries), and discuss how the aforementioned algorithm can be adapted to compute swgg- and dswg-queries that describes best a sample. The formal results are complemented by a description of our prototypical implementation of query discovery and an experimental evaluation based on both, synthetic and real-world data.

The goal of this work is to design a generally useful versioning system for the administration of different types of electronics documents, to design in detail and to implement the client part of this system (based on the client-server model). The implementation is built on .NET platform. This text also describes general approaches to versioning in different systems and shows a survey over the principles of the existing versioning systems with respect to the interaction with user.