|
|
Datové struktury pro setříděné ukládání dat
Bulánek, Jan ; Koucký, Michal (advisor) ; Kráľ, Daniel (referee)
In this work we study two variants of a bucketing game. This game is used for the lower bound proof of time complexity of item insertion into a sorted array, a data structure for the order maintenance problem. We show that these two variants of the bucketing game have the same time complexity up to a constant factor. Then we show that sorted arrays can use cache efficiently for certain operations. Finally, we present one implementation of the order maintenance data structure using the array of size n1+e.
|
|
| |
|
|
Variants of Reed-Solomon codes over other algebraic structures
Končický, Václav ; Koucký, Michal (advisor) ; Mareš, Martin (referee)
Reed-Solomon codes are a well known family of error-correcting codes with many good properties. However, they require a finite field to operate, limiting the alphabet size to a prime power. In this work, we build a weaker algebraic structure which supports alphabet of any integer size and requires only standard addition, multiplication and division to implement. Then we study a family of error-correcting codes based on matrix multiplication over this structure. We also adapt the Reed-Solomon code principle on this code family and study its properties. We prove and verify experimentally that while a random code of this family has high distance, the Reed-Solomon adaptation fails to perform well. 1
|
|
|
Pseudorandom walks and chip firing games
Mittal, Parth ; Koucký, Michal (advisor) ; Dvořák, Zdeněk (referee)
We study two deterministic analogues of random walks. The first is the chip-firing game, a single player game played by moving chips around a directed graph, popularised by Björner and Lovász. We find an efficient simulation of boolean circuits and Turing machines using instances of the chip-firing game - after assigning a fixed strategy to the player. The second is the Propp machine, or the rotor router model, a quasirandom model intro- duced by Priezzhev. We improve results of Kijima et al. and show a bound of O(m) on the discrepancy of this process from a random walk on d-regular graphs with m edges. 1
|
|
|
Constructions of Bounded-depth Superconcentrators
Domes, Tomáš ; Koucký, Michal (advisor) ; Šámal, Robert (referee)
In the thesis, we summarize known results regarding different types of expanders, upper and lower bounds on their sizes, and their explicit constructions. From the expanders, we construct bounded-depth superconcentrators of optimal size for every depth, and we show some explicit bounded-depth superconcentrator constructions from the explicit expanders. Apart from few minor generalizations, we do not bring any new results, but we present several known bounded-depth superconcentrator constructions in one place together with all the tools needed for the constructions. As far as we know, no such survey has existed before.
|
|
|
On search complexity of discrete logarithm
Václavek, Jan ; Hubáček, Pavel (advisor) ; Koucký, Michal (referee)
In this thesis, we study the discrete logarithm problem in the context of TFNP - the complexity class of search problems with a syntactically guaranteed existence of a solution for all instances. Our main results show that suitable variants of the discrete logarithm problem, which we call Index and DLog, are complete for the classes PPP and PWPP, respectively. Additionally, our reductions provide new structural insights into PWPP by establishing two new PWPP-complete problems. First, the problem Dove, a relaxation of the PPP-complete problem Pigeon. Dove is the first PWPP-complete problem not defined in terms of an explicitly shrinking function. Second, the problem Claw, a total search problem capturing the computational complexity of breaking claw-free permuta- tions. In the context of TFNP, the PWPP-completeness of Claw matches the known intrinsic relationship between collision-resistant hash functions and claw-free permuta- tions established in the cryptographic literature. 1
|
|
|
The relationship between selected inflammation markers and markers of the endothelial dysfunction to preterm labor and fetal inflammatory response
Koucký, Michal ; Hájek, Zdeněk (advisor) ; Krofta, Ladislav (referee) ; Živný, Jan (referee)
The doctoral dissertacion is focused on the role of inflammation in the pathogenesis of preterm labor. In the first part, we describe the current view on pathophysiology of preterm labor. In the second part, we evaluated the relationship of specific markers of inflammation and endothelial dysfunction to preterm birth and fetal inflammatory response. The most important findings of our study was that we found decreased levels of MMP-2 and decreased levels of sRAGE in women with preterm labor in comparison with the control group of pregnant women. Similarly, we found decreased levels of MMP-2 in women with subsequent diagnosed fetal inflammatory response. sRAGE is currently ranked among patttern recognition receptors. In the case of sRAGE we followed the results of our pilot project, it can be assumed that the its low level are connected with tissue damage. We confirmed that it can play an important role in the pathogenesis of preterm labor. We assume abnormal regulatory mechanisms of the production of MMP-2. In both cases, however, further studies are required to elucidate the functional significance of our results.
|
|
|
Kolmogorov complexity and Shannon information
Sekerka, Michal ; Koucký, Michal (advisor) ; Šámal, Robert (referee)
There arose two successful formalisations of the quantitative aspect of information over the course of the twentieth century: Shannon information and Kolmogorov complexity. Both afore mentioned definitions are rooted in mostly separate parts of mathematics. Shannon's information came to existence as an application of the elementary theory of probability and statistics. It is defined as a function in probability, with it being a lower bound on binary compression. Kolmogorov complexity, on the other hand, springs from formal logic and theory of computability. Kolmogrov defined it as the length of a minimal algorithmic description of a message. It is a beautiful result that when certain conditions do apply then those two functions behave asymptotically equivalently. My thesis is concerned with formally defining both measures of information, comparing their drawbacks, highlighting their similarities and differences and at last but not least proving their coveted asymptotic relationship. 1
|
|
|
New Bounds for Combinatorial Problems and Quasi-Gray Codes
Das, Debarati ; Koucký, Michal (advisor) ; Vassilevska Williams, Virginia (referee) ; Porat, Ely (referee)
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...
|
|
|
Nursing process in a woman diagnosed with intrauterine growth restriction of the fetus.
Vavrousová, Lucie ; Endlicherová, Jana (advisor) ; Koucký, Michal (referee)
Intrauterine growth retardation represents the great risk for proper development of the fetus. An early diagnosis which is determined by several ultrasound bioemtrics of the fetus in relation to gestational age is very important. It i salso important to distinguish the terms IUGR and SGA. The term SGA denotes the fetus whose weight is bellow the reference limit in relation to gestational age. This limit is usually less than 10th percentile. The term IUGR indicates the pathological proces that affects the growth and development of the fetus. A number of factors are know to lead to intrauterine growth retardation by the mother and the fetus. In theoretical part I will focus on definition, classification, etiology, prevalence, right diagnosis and therapy. Shortly I will mention the management of the IUGR fetus chilbirth. In practical part I will present a case history of a woman with the severe intrauterine growth retardation of the fetus who was admitted to a high-risk pregnancy ward. The pregnancy was terminated by a ceaserean section for pathological flow. Part of the practical part i salso the elaboration of a nursering plan based on the nursering plan according to Gordon. Keywords: nursing proces, midwife, intrauterine growth restriction of the fetus, fetal hypoxia, placental insufficiency
|
guest ::
RSS feed.