This paper develops a potential reduction algorithm for solving a linear-programming problem directly from a "warm start" initial point that is neither feasible nor optimal. The algorithm is of an "interior point" variety that seeks to reduce a single potential function which simultaneously coerces feasibility improvement (Phase I) and objective value improvement (Phase II). The key feature of the algorithm is the ability to specify beforehand the desired balance between infeasibility and nonoptimality in the following sense. Given a prespecified balancing parameter /3 > 0, the algorithm maintains the following Phase I - Phase II "/3-balancing constraint" throughout: (cTx- Z*) < /3TX, where cTx is the objective function, z* is the (unknown) optimal objective value of the linear program, and Tx measures the infeasibility of the current iterate x. This balancing constraint can be used to either emphasize rapid attainment of feasibility (set large) at the possible expense of good objective function values or to emphasize rapid attainment of good objective values (set /3 small) at the possible expense of a lower infeasibility gap. The algorithm exhibits the following advantageous features: (i) the iterate solutions monotonically decrease the infeasibility measure, (ii) the iterate solutions satisy the /3-balancing constraint, (iii) the iterate solutions achieve constant improvement in both Phase I and Phase II in O(n) iterations, (iv) there is always a possibility of finite termination of the Phase I problem, and (v) the algorithm is amenable to acceleration via linesearch of the potential function.

Shared objects are a key component in today's large distributed systems. Linearizability is a popular consistency condition for such shared objects which gives the illusion of sequential execution of operations. The time bound of an operation is the worst-case time complexity from the operation invocation to its response. Some time bounds have been proved for certain operations on linearizable shared objects in partially synchronous systems but there are some gaps between time upper bound and lower bound for each operation. In this work, the goal is to narrow or eliminate the gaps and find optimally fast implementations. To reach this goal, we prove larger lower bounds and show smaller upper bounds (compared to 2d for all operations in previous folklore implementations) by proposing an implementation for a shared object with an arbitrary data type in distributed systems of n processes in which every message delay is bounded within [d-u, d] and the maximum skew between processes' clocks is epsilon. Considering any operation for which there exist two instances such that individually, each instance is legal but in sequence they are not, we prove a lower bound of d + min{epsilon, u, d/3}, improving from d, and show this bound is tight when epsilon < d/3 and epsilon < u. Considering any operation for which there exist k instances such that each instance separately is legal and any sequence of them is legal, but the state of the object is different after different sequences, we prove a lower bound of (1-1/k)u, improving from u/2, and show this bound is tight when k = n. A pure mutator only modifies the object but does not return anything about the object. A pure accessor does not modify the object. For a pure mutator OP1 and a pure accessor OP2, if given a set of instances of OP1, the state of the object reflects the order in which the instances occur and an instance of OP2 can detect whether an instance of OP1 occurs, we prove the sum of the time bound for OP1 and OP2 is at least d + min{epsilon, u, d/3}, improving from d. The upper bound is d + 2*epsilon from our implementation.

Context. Almost all of the modern computers today have a CPU withmultiple cores, providing extra computational power. In the new ageof big data, parallel execution is essential to improve the performanceto an acceptable level. With parallelisation comes new challenges thatneeds to be considered. Objectives. In this work, parallel algorithms are compared and analysedin relation to their sequential counterparts, using the Java platform.Through this, find the potential speedup for multithreading andwhat factors affects the performance. In addition, provide source codefor multithreaded algorithms with proven time complexities. Methods. A literature study was conducted to gain knowledge anddeeper understanding into the aspects of sorting algorithms and thearea of parallel computing. An experiment followed of implementing aset of algorithms from which data could be gather through benchmarkingand testing. The data gathered was studied and analysed with itscorresponding source code to prove the validity of parallelisation. Results. Multithreading does improve performance, with two threadsin average providing a speedup of up to 2x and four threads up to3x. However, the potential speedup is bound to the available physicalthreads of the CPU and dependent of balancing the workload. Conclusions. The importance of workload balancing and using thecorrect number of threads in relation to the problem to be solved,needs to be carefully considered in order to utilize the extra resourcesavailable to its full potential.

We present a formally specified event specification language (Solicitor). Solicitor is suitable for real-time systems, since it results in resource-predictable and efficient event monitors. In event monitoring, event expressions defined in an event specification language control the monitoring by matching incoming streams of event occurrences against the event expressions. When an event expression has a complete set of matching event occurrences, the event type that this expression defines has occurred. Each event expression is specified by combining contributing event types with event operators such as sequence, conjunction, disjunction; contributing event types may be primitive, representing happenings of interest in a system, or composite, specified by event expressions. The formal specification of Solicitor is based on a formal schema that separates two important aspects of an event expression; these aspects are event operators and event contexts. The event operators aspect addresses the relative constraints between contributing event occurrences, whereas the event contexts aspect addresses the selection of event occurrences from an event stream with respect to event occurrences that are used or invalidated during event monitoring. The formal schema also contains an abstract model of event monitoring. Given this formal specification, we present realization issues of, a time complexity study of, as well as a proof of limited resource requirements of event monitoring. We propose an architecture for resource-predictable and efficient event monitoring. In particular, this architecture meets the requirements of realtime systems by defining how event monitoring and tasks are associated. A declarative way of specifying this association is proposed within our architecture. Moreover, an efficient memory management scheme for event composition is presented. This scheme meets the requirements of event monitoring in distributed systems. This architecture has been validated by implementing an executable component prototype that is part of the DeeDS prototype. The results of the time complexity study are validated by experiments. Our experiments corroborate the theory in terms of complexity classes of event composition in different event contexts. However, the experimental platform is not representative of operational real-time systems and, thus, the constants derived from our experiments cannot be used for such systems.

Network analysis in GIS is often related to finding solutions to transportation problems. In a GIS the real world is represented by either one of two spatial models, vector-based, or raster-based. Prefering raster or vector GIS is more a question of choice than of accuracy. A raster-based GIS model shows a better fit, when the problem is concerned with finding a path across terrain which does not have predefined paths. The approach of this study is to translate the scenario into a &lsquo / least-cost path&rsquo / graph with an associated cost function on the raster-based GIS layer. Sometimes, computation of shortest paths between different locations on a raster-based GIS has to be done in real-time. Therefore, knowing which shortest path algorithm runs fastest on real networks is needed. In order to meet this requirement, Dijsktra&rsquo / s algorithm with priority queue implementation is selected, because it reduces the time complexity of Dijsktra&rsquo / s algorithm from O(V2 log V) to O(E log V ). The run-time results of Dijsktra&rsquo / s algorithm, Dijsktra&rsquo / s algorithm with priority queue implementation and ArcMap Spatial Analyst Tool are compared for a number of raster GIS layers which have different number of nodes. Dijsktra&rsquo / s algorithm with priority queue implementation and Spatial Analyst tool of ArcMap show a linear relationship between node numbers and time, whereas Dijsktra&rsquo / s algorithm represents a quadratic relationship. Hence, when the number of nodes and edges in graph is increased, the run-time performance of the Dijsktra&rsquo / s algorithm decreases rapidly.

Made available in DSpace on 2014-06-12T15:53:49Z (GMT). No. of bitstreams: 2 arquivo1931_1.pdf: 3171518 bytes, checksum: 18e05da39f750dea38eaa754f1aa4735 (MD5) license.txt: 1748 bytes, checksum: 8a4605be74aa9ea9d79846c1fba20a33 (MD5) Previous issue date: 2009 / Atualmente, com o aumento do poder computacional e os estudos em usabilidade, sistemas de tempo real e foto-realismo, os requisitos de qualquer sistema de computador são mais complexos e sofisticados. Sistemas de Realidade Aumentada não são exceção em sua tentativa de resolver problemas da vida real do usuário com um nível reduzido de risco, tempo gasto ou complexidade de aprendizado. Tais sistemas podem ser classificados como baseados em marcadores ou livres de marcadores. O papel essencial da realidade aumentada sem marcadores é evitar o uso desnecessário e indesejável de marcadores nas aplicações. Para atender à demanda por tecnologias de realidade aumentada robustas e não-intrusivas, esta dissertação propõe uma cadeia de execução para o desenvolvimento de aplicações de realidade aumentada sem marcadores, especialmente baseadas na técnica de recuperação da estrutura a partir do movimento em tempo real

<p> We study an alignment model for coding DNA sequences recently proposed by J. Hein in [4] that takes into account both DNA and protein information, and attempts to minimize the total amount of evolution at both DNA and protein levels[4,5,6]. Although there are two quadratic algorithms (i.e. Hua-Jiang algorithm[8] and PLH algorithm[9]) for Hein's model if the gap penalty function is affine, both of them are impractical because of the large constant factor embedded in the quadratic time complexity function. We therefore consider a mild simplification named Context-free Codon Alignment and present a much more efficient algorithm for the simplified model. The algorithms have been implemented and tested on both real and simulated sequences, and it is found that they produce almost identical alignments in most cases. Furthermore, we extend our model and design a heuristic algorithm to handle frame-shift errors and overlapping frames.</p> / Thesis / Master of Science (MSc)

This thesis consists of six papers. In Paper I, we give an algorithm for merging sorted lists of monomials and together with a projection technique, we obtain a new complexity bound for the Buchberger-Möller algorithm and the FGLM algorithm. In Paper II, we discuss four different constructions of vector space bases associated to vanishing ideals of points. We show how to compute normal forms with respect to these bases and give complexity bounds. As an application we drastically improve the computational algebra approach to the reverse engineering of gene regulatory networks. In Paper III, we introduce the concept of multiplication matrices for ideals of projective dimension zero. We discuss various applications and, in particular, we give a new algorithm to compute the variety of an ideal of projective dimension zero. In Paper IV, we consider a subset of projective space over a finite field and give a geometric description of the minimal degree of a non-vanishing form with respect to this subset. We also give bounds on the minimal degree in terms of the cardinality of the subset. In Paper V, we study an associative version of an algorithm constructed to compute the Hilbert series for graded Lie algebras. In the commutative case we use Gotzmann's persistence theorem to show that the algorithm terminates in finite time. In Paper VI, we connect the commutative version of the algorithm in Paper V with the Buchberger algorithm. / At the time of doctoral defence, the following papers were unpublished and had a status as follows: Paper 3: Manuscript. Paper 4: Manuscript. Paper 5: Manuscript. Paper 6: Manuscript

In this paper, an algorithm that calculates the direction of the wind from the directions of sailors during fleet races is proposed. The algorithm is based on a 1-D spatial convolution and it is named Convolution Based Direction Filtering (CBDF). The CBDF-algorithm is used in the TracTrac race client that broadcasts sailboat races in real-time. The fact that the proposed algorithm is polynomial makes it suitable, to be used as a real-time application inside TracTrac, even for large fleets. More concretely, we show that the time complexity of the CBDF-algorithm is O(n2), in the worst-case, where n &gt; 0 is the number of boats in competition. It is also shown that in more realistic sailing scenarios, the CBDF-algorithm is in fact a linear algorithm.

<p>The effects of open system evolution on single particle interferometry, quantum computation, and the adiabatic approximation are investigated.</p><p>Single particle interferometry: Three concepts concerning completely positive maps (CPMs) and trace preserving CPMs (channels), named subspace preserving (SP) CPMs, subspace local channels, and gluing of CPMs, are introduced. SP channels preserve probability weights on given orthogonal sum decompositions of the Hilbert space of a quantum system. Subspace locality determines what channels act locally with respect to such decompositions. Gluings are the possible total channels obtainable if two evolution devices, characterized by channels, act jointly on a superposition of a particle in their inputs. It is shown that gluings are not uniquely determined by the two channels. We determine all possible interference patterns in single particle interferometry for given channels acting in the interferometer paths. It is shown that the standard interferometric setup cannot distinguish all gluings, but a generalized setup can.</p><p>Quantum computing: The robustness of local and global adiabatic quantum search subject to decoherence in the instantaneous eigenbasis of the search Hamiltonian, is examined. In both the global and local search case the asymptotic time-complexity of the ideal closed case is preserved, as long as the Hamiltonian dynamics is present. In the case of pure decoherence, where the environment monitors the search Hamiltonian, it is shown that the local adiabatic quantum search performs as the classical search with scaling N, and that the global search scales like N^3/2 , where N is the list length. We consider success probabilities p<1 and prove bounds on the run-time with the same scaling as in the conditions for the p → 1 limit.</p><p>Adiabatic evolution: We generalize the adiabatic approximation to the case of open quantum systems in the joint limit of slow change and weak open system disturbances. </p>