|
|
Rabin-Miller test and the choice of a basis
Franců, Martin ; Simon, Petr (advisor) ; Čunát, Vladimír (referee)
This thesis is dedicated to various choices of basis in Rabin-Miller test. Short overview of similar methods is shown and some properties of structure of the set of strong liars are proved in theoretical part. Selected innovative choices of basis are tested on the set of odd composite numbers in range of 100 and 200 000 000 and the results are compared to results of tests with usual choices of bases. Hypothesis about possible improvement of test through using basis of special form with regard to tested number is proposed. Program used for compu- tations of these results is included. The program allows user to compare results of tests with various ways of choosing basis. The second part of the thesis contains documentation of the program.
|
|
|
Datové struktury pro různá rozdělení dat
Čunát, Vladimír ; Koubek, Václav (advisor) ; Mareš, Martin (referee)
In this thesis we study the predecessor problem, which consists of maintaining a dynamic ordered set of keys. After a survey of the most important published results, we provide a detailed description and analysis of a randomized variant of van Emde Boas tree structure. The variant achieves asymptotically optimal space usage, but the (log logN) time bounds are no longer worst-case but expected amortized. The best published expected amortized time bound that is achieved on the (s ; s1-d)-smooth class of distributions is equal to O(log log n). We combine the known techniques into a new structure that achieves the same time bound on a wider class of input distributions. Moreover, the new structure can utilize the optimal amortized structure proposed by Beame and Fich, which ensures that the amortized time complexity is also bound by the optimal p(log n/log log n).
|
|
|
Rabin-Miller test and the choice of a basis
Franců, Martin ; Simon, Petr (advisor) ; Čunát, Vladimír (referee)
This thesis is dedicated to various choices of basis in Rabin-Miller test. Short overview of similar methods is shown and some properties of structure of the set of strong liars are proved in theoretical part. Selected innovative choices of basis are tested on the set of odd composite numbers in range of 100 and 200 000 000 and the results are compared to results of tests with usual choices of bases. Hypothesis about possible improvement of test through using basis of special form with regard to tested number is proposed. Program used for compu- tations of these results is included. The program allows user to compare results of tests with various ways of choosing basis. The second part of the thesis contains documentation of the program.
|
|
|
Datové struktury pro různá rozdělení dat
Čunát, Vladimír ; Koubek, Václav (advisor) ; Mareš, Martin (referee)
In this thesis we study the predecessor problem, which consists of maintaining a dynamic ordered set of keys. After a survey of the most important published results, we provide a detailed description and analysis of a randomized variant of van Emde Boas tree structure. The variant achieves asymptotically optimal space usage, but the (log logN) time bounds are no longer worst-case but expected amortized. The best published expected amortized time bound that is achieved on the (s ; s1-d)-smooth class of distributions is equal to O(log log n). We combine the known techniques into a new structure that achieves the same time bound on a wider class of input distributions. Moreover, the new structure can utilize the optimal amortized structure proposed by Beame and Fich, which ensures that the amortized time complexity is also bound by the optimal p(log n/log log n).
|
|
|
Contemporary Methods in Fractal Image Compression
Čunát, Vladimír ; Senft, Martin (referee) ; Dvořák, Tomáš (advisor)
In the present work we study fractal image compression. We discuss basic techniques, published improvements, and a few proposed enhancements of the current methods including their implementation. A framework for fractal compression is introduced. It is designed in order to be able to replace individual parts of the encoding process by di erent algorithms, simplifying comparison of their combinations. Presented enhancements are evaluated on a set of testing images. With proposed penalisation method decompressed images reach higher qualities. The differential coding combined with reordering of range-blocks decreases the amount of needed space approximately by 5%. On the other hand the prediction implemented by KD-trees isn't as accurate in comparison to a paper using another data structure.
|
guest ::
