Browsing by Subject "complexity"

Now showing 1 - 8 of 8

Access status: Restricted ,
Optymalne rozwiązywanie problemów początkowych z informacją zaburzoną
(Data obrony: 2017-06-14) Witek, Alicja
Wydział Matematyki Stosowanej
Access status: Open Access ,
Polynomials on the space of ω-ultradifferentiable functions
(2007) Grasela, Katarzyna
The space of polynomials on the space $D_{\omega}$ of $\omega$-ultradifferentiable functions is represented as the direct sum of completions of symmetric tensor powers of $D^{\prime}_{\omega}$.
Access status: Open Access ,
Randomized and quantum algorithms for solving initial-value problems in ordinary differential equations of order k
(2008) Goćwin, Maciej; Szczęsny, Marek
The complexity of initial-value problems is well studied for systems of equations of first order. In this paper, we study the $\varepsilon$-complexity for initial-value problems for scalar equations of higher order. We consider two models of computation, the randomized model and the quantum model. We construct almost optimal algorithms adjusted to scalar equations of higher order, without passing to systems of first order equations. The analysis of these algorithms allows us to establish upper complexity bounds. We also show (almost) matching lower complexity bounds. The $\varepsilon$-complexity in the randomized and quantum setting depends on the regularity of the right-hand side function, but is independent of the order of equation. Comparing the obtained bounds with results known in the deterministic case, we see that randomized algorithms give us a speed-up by $1/2$, and quantum algorithms by $1$ in the exponent. Hence, the speed-up does not depend on the order of equation, and is the same as for the systems of equations of first order. We also include results of some numerical experiments which confirm theoretical results.
Access status: Open Access ,
The complexity of open k-monopolies in graphs for negative k
(Wydawnictwa AGH, 2019) Peterin, Iztok
Let $G$ be a graph with vertex set $V(G)$, $\delta(G)$ minimum degree of $G$ and $k\in\left\{1-\left\lceil\frac{\delta(G)}{2}\right\rceil,\ldots ,\left\lfloor \frac{\delta(G)}{2}\right\rfloor\right\}$. Given a nonempty set $M\subseteq V(G)$) a vertex $v$ of $G$ is said to be $k$-controlled by $M$ if $\delta_{M}(v) \geq \frac{\delta_{V(G)}(v)}{2}+k$ where $\delta_{M}(v)$ represents the number of neighbors of $v$ in $M$. The set $M$ is alled an open $k$-monopoly for $G$ if it $k$-controls every vertex $v$ of $G$. In this short note we prove that the problem of computing the minimum cardinality of an open k-monopoly in a graph for a negative integer $k$ is NP-complete even restricted to chordal graphs.
Access status: Open Access ,
The use of integral information in the solution of a two-point boundary value problem
(2007) Drwięga, Tomasz
We study the worst-case ε-complexity of a two-point boundary value problem $u^{\prime\prime}(x)=f(x)u(x)$, $x \in [0,T]$, $u(0)=c$, $u^{\prime}(T)=0$, where $c,T \in \mathbb{R}$ ($c \neq 0$, $T \gt 0$) and $f$ is a nonnegative function with $r$ ($r\geq 0$) continuous bounded derivatives. We prove an upper bound on the complexity for linear information showing that a speed-up by two orders of magnitude can be obtained compared to standard information. We define an algorithm based on integral information and analyze its error, which provides an upper bound on the $\varepsilon$-complexity.
Access status: Restricted ,
Złożoność całkowania funkcji z osobliwościami
(Data obrony: 2015-10-22) Strzembosz-Pieńkowski, Wojciech
Wydział Matematyki Stosowanej
Access status: Restricted ,
Złożoność dwupunktowych problemów brzegowych w modelu deterministycznym, zrandomizowanym i kwantowym
(Data obrony: 2017-06-14) Góralczyk, Maksymilian
Wydział Matematyki Stosowanej
Access status: Open Access ,
Złożoność obliczeniowa całkowania stochastycznego w sensie Itô
(Data obrony: 2011-11-30) Przybyłowicz, Paweł
Wydział Matematyki Stosowanej
In the thesis we study the computational complexity of the stochastic Itô integration. We first investigate the optimal approximation of Itô integrals when linear information about the Wiener process B, consisting of certain Riemann integrals of its trajectories, is available. We show upper and lower bounds on the complexity which, in some cases, turn out to be optimal. Obtained results indicates that algorithms which use integral information are more efficient than algorithms which use only discrete values of the Wiener process B. In the second part of the thesis we deal with the numerical approximation of stochastic Itô integrals of regular and singular deterministic functions $f:[0,T]->R$. In the regular case we show that the nonadaptive Ito-Taylor algorithm is optimal. In the singular case we show that any nonadaptive algorithm cannot efficiently handle such a problem, even in the case of a single singularity. Hence, in the case of a single singularity, we construct an adaptive Itô-Taylor algorithm which has the optimal error known from the regular case. Next, we consider the case of multiple singularities and we show that even adaptive algorithms cannot preserve the optimal rate of convergence known from the regular case. We show that also in the asymptotic setting nonadaptive algorithms cannot preserve the optimal error known from the regular case.