Sökning: "Time-Complexity"

Visar resultat 1 - 5 av 40 avhandlingar innehållade ordet Time-Complexity.

1. 1. Functional Program Correctness Through Types

   Författare :Nils Anders Danielsson; Chalmers tekniska högskola; []
   Nyckelord :NATURVETENSKAP; NATURAL SCIENCES; well-typed syntax; normalisation by evaluation; program correctness; total languages; partial languages; lazy evaluation; time complexity; strong invariants; dependent types;

   Sammanfattning : This thesis addresses the problem of avoiding errors in functionalprograms. The thesis has three parts, discussing different aspects ofprogram correctness, with the unifying theme that types are anintegral part of the methods used to establish correctness. LÄS MER

3. 2. Resource-Predictable and Efficient Monitoring of Events

   Författare :Jonas Mellin; Sten F. Andler; Sharma Chakravarthy; Ulf Nilsson; Peter Fritzson; Linköpings universitet; []
   Nyckelord :NATURVETENSKAP; NATURAL SCIENCES; composition; efficiency; event; formalization; monitoring; performance; predictability; real-time systems; time complexity; timeliness; Computer science; Datavetenskap;

   Sammanfattning : 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. LÄS MER

4. 3. Open Quantum Systems : Effects in Interferometry, Quantum Computation, and Adiabatic Evolution

   Författare :Johan Åberg; Erik Sjöqvist; Sten Lunell; Vlatko Vedral; Uppsala universitet; []
   Nyckelord :NATURVETENSKAP; NATURAL SCIENCES; Physics; Open Systems; Completely Positive Maps; Channels; Decoherence; Quantum Information; Quantum Computing; Adiabatic Approximation; Quantum Search; Time-Complexity; Fysik; Physics; Fysik;

   Sammanfattning : The effects of open system evolution on single particle interferometry, quantum computation, and the adiabatic approximation are investigated.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. LÄS MER

5. 4. New Results on Combinatorial Algorithms

   Författare :Anders Dessmark; Data Vetenskap; []
   Nyckelord :NATURVETENSKAP; NATURAL SCIENCES; Sorting; Subgraph isomorphism; Partial k-trees; computer technology; Time complexity; Parallel computation; Data- och systemvetenskap; Convex layers; Systems engineering; Broadcasting;

   Sammanfattning : In this thesis improved upper bounds for several important combinatorial problems are provided. Below is a list of the main results showed in the thesis. The problem of determining whether a k-connected partial k-tree is isomorphic to subgraph of another partial k-tree is shown to be solvable in time O(nk+2). LÄS MER

7. 5. Algorithmic Graph Problems - From Computer Networks to Graph Embeddings

   Författare :Martin Wahlén; Data Vetenskap; []
   Nyckelord :NATURVETENSKAP; NATURAL SCIENCES; Approximation Algorithms; Exact Algorithms; Time Complexity; Broadcasting;

   Sammanfattning : This dissertation is a contribution to the knowledge of the computational complexity of discrete combinatorial problems. 1. The first problem that we consider is to compute the maximum independent set of a box graph, that is, given a set of orthogonal boxes in the plane compute the largest subset such that no boxes in the subset overlap. LÄS MER