|
|
Binary equality words
Hadravová, Jana ; Holub, Štěpán (advisor) ; Stanovský, David (referee)
Binary equality language is a set consisting of all solutions of equation g(w) = h(w), where g, h are arbitrary binary morphisms. Recently, it has been prooved that equality set for each pair of morphisms g, h is generated by at most two words. Structure of binary equality language has been already known in the case that at least one of morphisms g, h is periodic or if their equality set is generated exactly by two words. The main objective of the paper was to find a structure of solutions for morphisms whose equality set is generated by one word. The problem in general case remains unsolved but special result for solutions consisting of just one block for marked morphisms was discovered. Using methods established in this paper (covering by the same pattern to find n-multiple p-overflows and working with the cyclic pair (e, f, z)) it is believed that some more results can be achieved in the near future.
|
|
| |
|
| |
|
|
Searching collisions in hash functions
Joščák, Daniel ; Tůma, Jiří (advisor) ; Holub, Štěpán (referee)
The main interest of this paper is finding collisions in the hash function MD5. We present our new algorithm based on Wangs et al. methods of finding collisions in MD5. While writing this thesis Stevens and Klima published their fast algorithms for finding collisions. We give a description of these algorithms and the calculation of computianal complexity of all three algorithms.
|
|
| |
|
| |
|
| |
|
|
Kódování a efektivita LDPC kódů
Kozlík, Andrew ; Drápal, Aleš (advisor) ; Holub, Štěpán (referee)
Low-density parity-check (LDPC) codes are linear error correcting codes which are capable of performing near channel capacity. Furthermore, they admit efficient decoding algorithms that provide near optimum performance. Their main disadvantage is that most LDPC codes have relatively complex encoders. In this thesis, we begin by giving a detailed discussion of the sum-product decoding algorithm, we then study the performance of LDPC codes on the binary erasure channel under sum-product decoding to obtain criteria for the design of codes that allow reliable transmission at rates arbitrarily close to channel capacity. Using these criteria we show how such codes are designed. We then present experimental results and compare them with theoretical predictions. Finally, we provide an overview of several approaches to solving the complex encoder problem.
|
|
|
Quantum search algorithm
Mejdrech, Lukáš ; Barto, Libor (advisor) ; Holub, Štěpán (referee)
In this work we study Grover's algorithm for quantum computers. This algorithm promises to search in an unstructured database in time comparable with a square root of the number of objects. A description of basic quantum computer principles is followed by the original Grover's formulation and a proof of the algorithm, as well as a later geometrical description of the algorithm. We also mention their suitability for educational purposes. We also include a description of the Grover's algorithm in a programming language, which makes it possible to simulate a quantum computing on classical computers.
|
|
| |
guest ::
