|
|
Distinguishing pairs of words using finite automata
Bilan, Daria ; Koucký, Michal (advisor) ; Šámal, Robert (referee)
This work considers a fundamental open problem in informatics - distin- guishing two words by a deterministic finite automaton with the smallest pos- sible number of states. We review the existing research, where proven lower and upper bounds in terms of words' lengths differ exponentially. Next, we empirically try two approaches not studied previously: analysis of discerning sets and application of randomly generated automata. We show that the first approach does not help improve the bounds for the main problem, while the random automata could be successful for randomly taken word pairs but not for all of them. A combination of a randomly generated automaton with the best performing already known, though, may decrease an average number of states by several orders of magnitude. We propose several topics for further investigation based on the obtained experimental results. 1
|
|
|
Major obstetric complications in women with inherited thrombophilia in comparison to the control group of women
Pechrová, Viktorie ; Koucký, Michal (advisor) ; Čábela, Radek (referee)
Leiden mutation and mutation of the gen for prothrombin are classified as hereditary thrombophilia affecting external cascade's hemocoagulation factors. The higher incidence is in the Europoid. We marked those disorders not only as risk factors for thromboembolism but as risk factors for obstetrics complications as well. This bachelor thesis completes theoretical knowledge of Leiden mutation and mutation of the gen for prothrombin. Afterward, the thesis is focused on obstetrics complications that are associated with those thrombophilias. The analytical part of the thesis is devoted to the association of the mentioned mutations and the higher risk of recurrent pregnancy loss. Meaning that women who carry the such mutation are more likely to have the anamnesis of 2 or more miscarriages compared to women without thrombophilia. First, the hypothesis was set that the women with thrombophilia are going to have more frequent recurrent pregnancy loss compared to the control group without thrombophilia. To verify the hypothesis a retrospective check of the databases was made. The databases were from The Institute of Medical Biochemistry and Laboratory Diagnostics of the General University Hospital and of the First Faculty of Medicine of Charles University, where the group with thrombophilia was taken. The...
|
|
|
Complexity of dynamic data structures
Král, Karel ; Koucký, Michal (advisor) ; Drucker, Andrew (referee) ; Ishai, Yuval (referee)
Sorting is one of the fundamental problems in computer science. In this thesis we present three individual results. Asymptotically optimal sorting networks have been created by Ajtai et al. [1983]. But Asharov et al. [2021] have observed that boolean circuits based on sorting networks are not optimal for sorting short integers. We present a construction of even smaller boolean circuits for sorting short integers. Lower bounds for offline Oblivious RAM have been connected to lower bounds for sorting circuits by Boyle and Naor [2016]. Larsen and Nielsen [2018] have shown a lower bound for online Oblivious RAM. We provide a lower bound for online Oblivious RAM in a more general model. Finally we provide an algorithm with expected running time O(n log log(n)) for sort- ing integers on random access machine with word length between log(n) and log(n) cubed. This algorithm does not match the expected running time of the algorithm of Han and Thorup [2002], but our algorithm is much easier to implement and analyse. 1
|
|
|
Limits of Data Structures, Communication, and Cards
Dvořák, Pavel ; Koucký, Michal (advisor) ; Hansen, Kristoffer Arnsfelt (referee) ; Chakrabarti, Amit (referee)
Limits of Data Structures, Communication, and Cards - Abstract In this thesis, we study several aspects of computational complexity. One of the main topics is the complexity of data structures, which are algorithms for efficient storing data supporting efficient queries to the data. In the case of dynamic data structures, they also allow modification of the data before querying. A long-standing open problem in this area is to prove an unconditional polynomial lower bound of the trade-off between the update time and the query time of an adaptive dynamic data structure computing some explicit function. We provide an unconditional polynomial lower bound for a restricted class of semi-adaptive dynamic data structures computing functions of large corruption bound, that generalizes the result by Ko and Weinstein [FOCS '20] who provided such a lower bound for data structures computing the Disjointness function. Further, we provide conditional lower bounds for certain static data structures computing permutation inversion, and polynomial evaluation and inversion. These lower bounds beat the best-known unconditional lower bounds for the problems of interest. Further, we study the communication complexity of the elimination problem, which is a prob- lem closely related to the direct sum. In the elimination problem, Alice...
|
|
|
Nursing care for a woman with pre-eclampsia, perinatological results in relation to creatinine levels in maternal blood
Šmejkalová, Tereza ; Koucký, Michal (advisor) ; Čábela, Radek (referee)
Pre-eclampsia (PE) is a serious multi-organ disease complicating pregnancy. It occurs in 2-8% of pregnancies worldwide and approximately 50,000 women die from its consequences each year. This bachelor's thesis summarizes the theoretical knowledge of PE, - specifically the etiopathogenesis, classification and symptoms of the disease, treatment management, likely complications and other aspects that are important in nursing care. The practical part of the thesis deals with the use of serum creatinine (S-creatinine) levels to determine the severity of the patient's condition and the likely consequences for the foetus. The main objective of the thesis was to find a correlation between maternal S-creatinine levels prior to delivery and perinatal outcomes. The sub-objective was to monitor serum urea (S-urea) levels in relation to the length of pregnancy. Our hypothesis was that as the mother's antepartum S-creatinine level increases, the length of gestation shortens, newborn birth weight decreases, postpartum adaptation worsens, and the length of maternal hospitalization increases. To perform the research, we retrospectively collected data from pregnant women with a PE diagnosis who gave birth at the Department of Obstetrics and Gynaecology of the First Faculty of Medicine of Charles University and of...
|
|
|
DPLL algorithm and propositional proofs
Hrnčiar, Maroš ; Krajíček, Jan (advisor) ; Koucký, Michal (referee)
Proof complexity is an interesting mathematical part connecting logic and complexity theory. It investigates which proof systems are needed for effective theorem proving. The aim of this paper is to present a relation between propositional proof systems and SAT algorithms. We will see that a run of an algorithm on the unrealizable formula can be seen as a propositional proof of its unsatisfiability, so the algorithm practically defines whole proof system. The thesis is mainly recommended for readers interested in proof complexity, but it can also independently illustrate a resolution principle and perhaps show some less common view of SAT assuming reader's basic knowledge of propositional logic, graph theory and complexity.
|
|
| |
|
|
The Online Labeling Problem
Bulánek, Jan ; Koucký, Michal (advisor) ; Brodal, Gerth (referee) ; Iacono, John (referee)
A sorted array is a fundamental algorithmic concept. Its on-line variant gives rise to the online labeling problem. In the online labeling problem we are given an array of size m and a stream of n integers from the universe {1, ..., r} coming in an arbitrary order. Our task is to maintain all received items in the array in sorted order. The inserted items do not have to be stored consecutively in the array. Since the final order of the items is not known until we see all the items, moves of already inserted items are allowed but should be minimized. We present two algorithms which together provide an optimal solution for almost all values of m as a function of n. We provide tight lower bounds for almost all ranges of m. We introduce a notion of the limited universe and prove lower bounds also in that setting. Some of our lower bounds also apply to randomized algorithms. Powered by TCPDF (www.tcpdf.org)
|
|
|
Functional Data Stuctures and Algorithms
Straka, Milan ; Dvořák, Zdeněk (advisor) ; Koucký, Michal (referee) ; Brodal, Gerth (referee)
Title: Functional Data Structures and Algorithms Author: Milan Straka Institute: Computer Science Institute of Charles University Supervisor of the doctoral thesis: doc. Mgr. Zdeněk Dvořák, Ph.D, Computer Science Institute of Charles University Abstract: Functional programming is a well established programming paradigm and is becoming increasingly popular, even in industrial and commercial appli- cations. Data structures used in functional languages are principally persistent, that is, they preserve previous versions of themselves when modified. The goal of this work is to broaden the theory of persistent data structures and devise efficient implementations of data structures to be used in functional languages. Arrays are without any question the most frequently used data structure. Despite being conceptually very simple, no persistent array with constant time access operation exists. We describe a simplified implementation of a fully per- sistent array with asymptotically optimal amortized complexity Θ(log log n) and especially a nearly optimal worst-case implementation. Additionally, we show how to effectively perform a garbage collection on a persistent array. The most efficient data structures are not necessarily based on asymptotically best structures. On that account, we also focus on data structure...
|
|
|
Communication complexity
Wagner, Vojtěch ; Krajíček, Jan (advisor) ; Koucký, Michal (referee)
Title: Communication Complexity Author: Vojtěch Wagner Department: Department of Algebra Supervisor: prof. RNDr. Jan Krajíček, DrSc. Abstract: This work deals with communication complexity, which considers mo- del of two (or more) parties, each holding its own binary input (let's say x and y). Each of players has information only about his own input. Their common goal is to compute value of some function f(x, y) of these inputs. Communicati- on complexity measures amount of information communicated between players in order to compute f(x, y). This work especially concerns two main models - deterministic, in which all decision made by players is deterministic and they compute the right value in all cases and probabilistic model which allows ran- domized fashion and the goal of the players is to compute the right value with high enough probability. We present some basic concepts and methods to lower bound communication complexity of functions, all ilustrated on some examples of basic functions. In the end we present some complex and practically relevant examples, on which presented methods are demonstrated. Keywords: communication complexity, deterministic communication model, ran- domized model, lower bounds on communication complexity. 1
|
guest ::
RSS feed.