A singularly perturbed reaction diffusion problem is considered. The small diffusion coefficient generically leads to solutions with boundary layers. The problem is discretized by a vertex-centered finite volume method. The anisotropy of the solution is reflected by using \emph{anisotropic meshes} which can improve the accuracy of the discretization considerably. The main focus is on \emph{a posteriori} error estimation. A residual type error estimator is proposed and rigorously analysed. It is shown to be robust with respect to the small perturbation parameter. The estimator is also robust with respect to the mesh anisotropy as long as the anisotropic mesh sufficiently reflects the anisotropy of the solution (which is almost always the case for sensible discretizations). Altogether, reliable and efficient \emph{a posteriori} error estimation is achieved for the finite volume method on anisotropic meshes.

This thesis consists of two parts. In part I, a group of combinatorial problems pertaining to strings, boolean matrices and graphs is studied. For given two strings x and y, their edit distance is the minimum number of character insertions, deletions and substitutions required to convert x into y. In this thesis we provide an algorithm that computes a constant approximation of edit distance in truly sub-quadratic time. Based on the provided ideas, we construct a separate sub- quadratic time algorithm that can find an occurrence of a pattern P in a given text T while allowing a few edit errors. Afterwards we study the boolean matrix multiplication (BMM) problem where given two boolean matrices, the aim is to find their product over boolean semi-ring. For this problem, we present two combinatorial models and show in these models BMM requires Ω(n3 /2O( √ log n) ) and Ω(n7/3 /2O( √ log n) ) work respectively. Furthermore, we also give a construction of a sparse sub-graph that preserves the distance between a designated source and any other vertex as long as the total weight increment of all the edges is bounded by some constant. In part II, we study the efficient construction of quasi-Gray codes. We give a construction of space optimal quasi-Gray codes over odd sized alphabets with read complexity 4...

No description available.

<p>For a prime p>2 and a smooth proper p-adic formal scheme X over O_K where K is a p-adic field of absolute ramification degree e, we study a series of conditions (Cr_s), s>=0 that partially control the G_K-action on the image of the associated Breuil-Kisin prismatic cohomology RΓ_Δ(X/S) inside the A_inf-prismatic cohomology RΓ_Δ(X_Ainf/A_inf). The condition (Cr₀) is a criterion for a Breuil-Kisin-Fargues G_K-module to induce a crystalline representation used by Gee and Liu, and thus leads to a proof of crystallinity of Hⁱ_et(X_CK, Q_p) that avoids the crystalline comparison. The higher conditions (Cr_s) are used in an adaptation of a ramification bounds strategy of Caruso and Liu. As a result, we establish ramification bounds for the mod p representations Hⁱ_et(X_CK, Z/pZ) for arbitrary e and i, which extend or improve existing bounds in various situations.</p>

A graph G is domination bicritical if the removal of any pair of vertices decreases the domination number. Properties of bicritical graphs are studied. We show that a connected bicritical graph has domination number at least 3, minimum degree at least 3, and edge-connectivity at least 2. Ways of constructing a bicritical graph from smaller bicritical graphs are presented.

Dans cette thèse on s’intéresse à un modèle de faute Byzantins Mobiles. Jusqu’à présent, seulement le problème du Consensus a été résolu en présente de faute Byzantines Mobiles et plusieurs variations de ce modèle de faute ont été proposé. Pour chacun de ces modelés ont été prouvées les bornes inferieures du nombre de processus correct nécessaire et des solutions asymptotiquement optimales ont été proposées. Notre première contribution porte sur les registres repartis dans ce modèle. Les registres repartis sont l’abstraction à la base du stockage reparti. Ces résultats préconisent donc notre deuxième contribution principale, un modèle de faute Byzantine Mobile généralisé. Notre troisième contribution est un ensemble de preuves de nécessité et d’impossibilité pour les registres repartis dans ces modèles. En particulier on prouve qu’il n’est pas possible d’implémenter la spécification plus faible des registres dans un système asynchrone. Par contre, pour les systèmes synchrones, on prouve des bornes inferieures et propose des protocoles asymptotiquement optimaux pour le registrer régulier. Pour conclure, notre dernière contribution porte sur le problème d’accord approximé, une forme affaiblie du consensus. On résout ce problème dans le modèle basé sur ronde, le même du consensus. En outre, il est intéressant de noter qua dans le modèle statique, la borne inferieure sur le nombre de répliques est la même pour le consensus et pour le problème d’accord approximé. Le même invariant s’applique avec les fautes byzantine mobiles. De plus, on accompagne ces bornes inferieures avec une solution asymptotiquement optimale pour le problème d’accord approximé. / In this thesis we consider a model where Byzantine failures are not fixed, we consider the so called Mobile Byzantine failures. So far, only Consensus problem has been solved in presence of Mobile Byzantine failures and interestingly different variations of this failure model have been proposed. For each of them have been proved lower bounds on the number of required processes and have been proposed tight solutions. Our first contribution concerns distributed Registers in such strong model. Distributed Registers are the basic abstraction for Distributed Storages. This advocates our second and main contribution, a general Mobile Byzantine Failure Model. Our main focus is about Distributed Registers, so our third contribution comes, we prove necessities and impossibilities in those models. In particular we prove that is it not possible to solve the weakest register specification in an asynchronous system. On the other side we prove lower bounds for the synchronous system, with respect to the proposed hierarchy models, and tight protocols to solve the Regular Register problem. To conclude, our last contribution is about the Approximate Agreement problem, a weaker form of Consensus. We solve such problem in the same round-based models as Consensus so far. The interesting result is the following, in presence of static Byzantine failures, lower bounds on the number of correct replicas does not change between consensus and approximate agreement. The same invariant still holds in presence of Mobile Byzantine failure. Moreover, along with lower bounds we propose a tight solution to solve approximate agreement.

This paper explores the link between agriculture investment and agriculture output in Namibia. The existing theory on investment and growth constitutes a basis for empirical work on investment-output nexus. Neither the neoclassical nor the new growth theories on investment have considered the growth effects of investment at sector and industry level and its implication on capital allocation, particularly for developing countries that are resource constrained. The key question addressed in this paper is whether investment in agriculture is associated with agriculture output, both at the sector and sub-sector levels. The paper adopted the ARDL bounds test model constructed with quarterly data for the period 2000 to 2020 and found that investment and agricultural output exhibit a long-run relationship. The coefficient estimates showed that public investment, development bank loans and agriculture export have a positive impact on agricultural output while inflation, lending rates and commercial bank loans have a deleterious effect. The long-run causality tests suggest that there is unidirectional causality between commercial credit expenditure and aggregate agriculture output, as well as a unidirectional causality running from exports to livestock and crop sub-sector output. Based on error correction terms, agriculture output tends to rapidly adjust to short-term disturbances, hence rebound of agriculture output to a long-run growth path can take place with minimum or no delays. This study concludes that the Keynesian hypothesis is valid for Namibia's agriculture and the direction of causality is from investment to agriculture growth. Therefore, the role of government in supporting sustainable development of the agricultural sector cannot be overemphasised.

京都大学 / 0048 / 新制・課程博士 / 博士(情報学) / 甲第19129号 / 情博第575号 / 新制||情||101(附属図書館) / 32080 / 京都大学大学院情報学研究科通信情報システム専攻 / (主査)教授 岩間 一雄, 教授 髙木 直史, 教授 五十嵐 淳 / 学位規則第4条第1項該当 / Doctor of Informatics / Kyoto University / DFAM

京都大学 / 0048 / 新制・課程博士 / 博士(情報学) / 甲第20032号 / 情博第627号 / 新制||情||109(附属図書館) / 33128 / 京都大学大学院情報学研究科通信情報システム専攻 / (主査)教授 原田 博司, 教授 守倉 正博, 教授 梅野 健 / 学位規則第4条第1項該当 / Doctor of Informatics / Kyoto University / DFAM

A large class of practical planning problems that require reasoning about uncertain outcomes, as well as tradeoffs among competing goals, can be modeled as Markov decision processes (MDPs). This model has been studied for over 60 years, and has many applications that range from stochastic inventory control and supply-chain planning, to probabilistic model checking and robotic control. Standard dynamic programming algorithms solve these problems for the entire state space. A more efficient heuristic search approach focuses computation on solving these problems for the relevant part of the state space only, given a start state, and using heuristics to identify irrelevant parts of the state space that can be safely ignored. This dissertation considers the heuristic search approach to this class of problems, and makes three contributions that advance this approach. The first contribution is a novel algorithm for solving MDPs that integrates the standard value iteration algorithm with branch-and-bound search. Called branch-and-bound value iteration, the new algorithm has several advantages over existing algorithms. The second contribution is the integration of recently-developed suboptimality bounds in heuristic search algorithm for MDPs, making it possible for iterative algorithms for solving these planning problems to detect convergence to a bounded-suboptimal solution. The third contribution is the evaluation and analysis of some techniques that are widely-used by state-of-the-art planning algorithms, the identification of some weaknesses of these techniques, and the development of a more efficient implementation of one of these techniques -- a solved-labeling procedure that speeds converge by leveraging a decomposition of the state-space graph of a planning problem into strongly-connected components. The new algorithms and techniques introduced in this dissertation are experimentally evaluated on a range of widely-used planning benchmarks.