Thesis (Ph. D.)--University of Texas at Austin, 2004. / Supervisors: James W. Fredrickson and Gautam Ahuja. Vita. Includes bibliographical references.

Thesis (M.S.)--State University of New York at Binghamton, Thomas J. Watson School of Engineering and Applied Science, Department of Computer Science, 2009. / Includes bibliographical references.

Thesis (Ph.D.) - Carleton University, 2007. / Includes bibliographical references (p. 115-129). Also available in electronic format on the Internet.

Thesis (Ph. D.)--University of Washington, 2007. / Vita. Includes bibliographical references (p. 132-136).

of doctoral thesis "Computational Homotopy Theory": We consider several basic problems of algebraic topology, with connections to combinatorial and geometric questions, from the point of view of compu- tational complexity. The extension problem asks, given topological spaces X, Y , a subspace A ⊆ X, and a (continuous) map f : A → Y , whether f can be extended to a map X → Y . For computational purposes, we assume that A, X, Y are represented as finite simplicial complexes and f as a simplicial map. We study the problem under the assumption that, for some d ≥ 1, Y is d- connected, otherwise the problem is undecidable by uncomputability of the fundamental group; We prove that, this problem is still undecidable for dim X = 2d + 2. On the other hand, for every fixed dim X ≤ 2d + 1, we obtain an algorithm that solves the extension problem in polynomial time. We obtain analogous complexity results for the problem of determining the set of homotopy classes of maps X → Y . We also consider the computation of the homotopy groups πk(Y ), k ≥ 2, for a 1-connected Y . Their computability was established by Brown in 1957; we show that πk(Y ) can be computed in polynomial time for every fixed k ≥ 2. On the other hand, we prove that computing πk(Y ) is #P-hard if k is a part of input. It is a strengthening of...

A standard problem in the field of computational finance is that of pricing derivative securities. This is often accomplished by estimating an expected value of a functional of a stochastic process, defined by a stochastic differential equation (SDE). In such a setting the random sampling algorithm Monte Carlo (MC) is useful, where paths of the process are sampled. However, MC in its standard form (SMC) is inherently slow. Additionally, if the analytical solution to the underlying SDE is not available, a numerical approximation of the process is necessary, adding another layer of computational complexity to the SMC algorithm. Thus, the computational cost of achieving a certain level of accuracy of the estimation using SMC may be relatively high. In this thesis we introduce and review the theory of the SMC method, with and without the need of numerical approximation for path simulation. Two numerical methods for path approximation are introduced: the Euler–Maruyama method and Milstein's method. Moreover, we also introduce and review the theory of a relatively new (2008) MC method – the multilevel Monte Carlo (MLMC) method – which is only applicable when paths are approximated. This method boldly claims that it can – under certain conditions – eradicate the additional complexity stemming from the approximation of paths. With this in mind, we wish to see whether this claim holds when pricing a European call option, where the underlying stock process is modelled by geometric Brownian motion. We also want to compare the performance of MLMC in this scenario to that of SMC, with and without path approximation. Two numerical experiments are performed. The first to determine the optimal implementation of MLMC, a static or adaptive approach. The second to illustrate the difference in performance of adaptive MLMC and SMC – depending on the used numerical method and whether the analytical solution is available. The results show that SMC is inferior to adaptive MLMC if numerical approximation of paths is needed, and that adaptive MLMC seems to meet the complexity of SMC with an analytical solution. However, while the complexity of adaptive MLMC is impressive, it cannot quite compensate for the additional cost of approximating paths, ending up roughly ten times slower than SMC with an analytical solution.

The increasing reliance on oceans, rivers and waterways in a spectrum of human activities have demonstrated the large demand for advanced marine technologies that facilitate multifarious in-water services and tasks. The autonomous underwater vehicle (AUV) is a representative marine technology which has been contributing continuously to many ocean-related fields. An elaborate control system is essential to AUVs. However, AUVs present difficult control system design problems due to their nonlinear dynamics, the unpredictable environment and the poor knowledge about the hydrodynamic coupling of the vehicle degrees of freedom. When designing the motion controller, the practical constraints on the AUV system such as limited perceiving, computing and actuating capabilities should also be respected. The model predictive control (MPC) is an advanced control technology that leverages optimization to calculate the control command. Thanks to the optimization nature, MPC can conveniently handle the complex nonlinearity in system dynamics as well as the state and control constraints. MPC takes the receding horizon control paradigm which gains satisfactory robustness against model uncertainties and external disturbances. Therefore, MPC is an ideal candidate for solving the AUV motion control problems. On the other hand, since the optimization is solved by iterative numerical algorithms, the obtained control signal is an implicit function of the system state, which complicates the characterization of the closed-loop properties. Moreover, the nonlinear system dynamics makes the online optimization nonlinear programming (NLP) problems. The high computational complexity may cause an issue on the real-time control for embedded platforms with limited computing resources. In order to push the advanced MPC technology towards real-world AUV applications, this PhD dissertation is concerned with fundamental AUV motion control problems and attempts to address the aforementioned challenges and provide novel solutions. This dissertation proceeds with Chapter 1 by providing state-of-the-art introductions to related research areas. The mathematical model used for the AUV motion control is elaborated in Chapter 2. In Chapter 3, we consider the AUV navigation and control problem in constrained workspace. A unified receding horizon optimization framework consisting of the dynamic path planning and the nonlinear model predictive control (NMPC) tracking control is developed. Although the NMPC tracking controller well accommodates the practical constraints on the AUV system, it presents a brand new design philosophy compared with the existing control systems that are implemented on real AUVs. Since the existing AUV control systems are reliable controllers, AUV practitioners tend not to fully replace them but to improve the control performance by adding features. By considering this, in Chapter 4, we develop the Lyapunov-based model predictive control (LMPC) scheme which builds on the existing AUV control system and invoke online optimization to improve the control performance. Chapter 5 focuses on the path following (PF) problem. Unlike the trajectory tracking control which equally emphasizes the spatial and temporal control objectives, the PF control often prioritizes the path convergence over the speed assignment. To incorporate this objective prioritization into the controller design, a novel multi-objective model predictive control (MOMPC) scheme is developed. While the MPC technique provides several salient features (e.g., optimality, constraints handling, objective prioritization, robustness, etc.), those features come at a price: a computational bottleneck is formed by the heavy burden of solving online optimizations in real time. To explicitly address this issue, in Chapter 6, the computational complexity of the MPC algorithms is particularly emphasized. Two novel strategies which potentially alleviate the computational burden of the MPC-based AUV tracking control are proposed. In Chapter 7, some conclusive remarks are provided and a few avenues for future research are identified. / Graduate

MinistÃre de l'Enseignement SupÃrieur et de la Recherche / Nesta tese, estudamos vÃrios problemas de teoria dos grafos relativos à coloraÃÃo e convexidade em grafos. A maioria dos resultados contidos aqui sÃo ligados à complexidade computacional destes problemas para classes de grafos particulares. Na primeira, e principal, parte desta tese, discutimos coloraÃÃo de grafos que à uma das Ãreas mais importantes de teoria dos grafos. Primeiro, consideramos trÃs problemas de coloraÃÃo chamados coloraÃÃo gulosa, coloraÃÃo ponderada e coloraÃÃo ponderada imprÃpria. Em seguida, discutimos um problema de decisÃo, chamado boa rotulagem de arestas, cuja definiÃÃo foi motivada pelo problema de atribuiÃÃo de frequÃncias em redes Ãticas. A segunda parte desta tese à dedicada a um parÃmetro de otimizaÃÃo em grafos chamado de nÃmero de fecho (geodÃtico). A definiÃÃo deste parÃmetro à motivada pela extensÃo das noÃÃes de conjuntos e fecho convexos no espaÃo Euclidiano. Por m, apresentamos em anexo outros trabalhos desenvolvidos durante esta tese, um em hipergrafos dirigidos Eulerianos e Hamiltonianos e outro sobre sistemas de armazenamento distribuÃdo. / In this thesis, we study several problems of Graph Theory concerning Graph Coloring and Graph Convexity. Most of the results contained here are related to the computational complexity of these problems for particular graph classes. In the first and main part of this thesis, we deal with Graph Coloring which is one of the most studied areas of Graph Theory. We first consider three graph coloring problems called Greedy Coloring, Weighted Coloring and Weighted Improper Coloring. Then, we deal with a decision problem, called Good Edge-Labeling, whose definition was motivated by the Wavelength Assignment problem in optical networks. The second part of this thesis is devoted to a graph optimization parameter called (geodetic) hull number. The definition of this parameter is motivated by an extension to graphs of the notions of convex sets and convex hulls in the Euclidean space. Finally, we present in the appendix other works developed during this thesis, one about Eulerian and Hamiltonian directed hypergraphs and the other concerning distributed storage systems.

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

The subject of the thesis belongs to the field of operations management. We deal with sequencing problems arising when there are multiple repair operations available to fix a broken man-made system and the true cause of the system failure is uncertain. It is assumed that the system is formally described by a probabilistic model, and it is to be repaired by a sequence of troubleshooting operations designed to identify the cause of the malfunction and fix the system. The challenge is to find a course of repair which has minimal expected cost. We study several variants of the problem proposed in the literature. We analyze computational complexity of those variants, apply integer linear programming to one variant of the problem, and examine the relation to machine scheduling.