doc. Ing. Štěpán Starosta, Ph.D.

Infinite words generated by morphisms include fixed points of morphisms and words stemming from S-adic systems [1] and L-systems [2]. The objective of the thesis is the research of combinatorial properties of these structures, for instance, their factor/palindromic/abelian complexity and properties that are preserved in the case of the generating morphisms being recognizable. The thesis may furthermore focus on design of effecient algorithms or/and formalization in the generic prove assistant Isabelle/HOL [3].

• [1] Berthé, V., Delecroix, V.: Beyond substitutive dynamical systems: S-adic expansions, RIMS Lecture note ‘Kokyuroku Bessatu’ B46, pp. 81–123 (2014)
• [2] Rozenberg, G. Salomaa, A.: The Book of L, Springer Berlin Heidelberg, 1986
• [3] https://isabelle.in.tum.de/

Special cases of languages generated by morphism comprise, for instnance, language of fixed points of morphisms, languages of S-adic words [1], and factorial languages of L-systems [2]. The goal of the work is to investigate and describe combinatorial properties of such languages. Namely, their factor/palindromic/abelian complexity; properties preserved when the morphism is recognizable or circular. A possible option for the topic is focus on design of relevant effective algorithms and/or formalization in the proof assistant Isabelle/HOL [3-5].

Literatura:

• [1] Berthé, V., Delecroix, V.: Beyond substitutive dynamical systems: S-adic expansions, RIMS Lecture note ‘Kokyuroku Bessatu’ B46, pp. 81–123 (2014)

• [2] Rozenberg, G. Salomaa, A.: The Book of L, Springer Berlin Heidelberg, 1986

• [3] https://isabelle.in.tum.de/

• [4] Holub, Š., & Starosta, Š. (2021). Formalization of Basic Combinatorics on Words. In L. Cohen & C. Kaliszyk (Eds.), 12th International Conference on Interactive Theorem Proving (ITP 2021) (Vol. 193, pp. 22:1–22:17). Schloss Dagstuhl – Leibniz-Zentrum für Informatik. https://doi.org/10.4230/LIPIcs.ITP.2021.22

• [5] Klouda, K., Starosta, Š. (2024). The number of primitive words of unbounded exponent in the language of an HD0L-system is finite. Journal of Combinatorial Theory, Series A, 206, 105904. https://doi.org/10.1016/j.jcta.2024.105904

doc. Ing. Štěpán Starosta, Ph.D.

Mgr. Petr Matyáš

Department of Software Engineering

doc. Ing. Štěpán Starosta, Ph.D.

doc. Ing. Lubomíra Dvořáková, Ph.D.

Department of Theoretical Computer Science

For a given finite group G consisting of morphisms and antimorphisms, we study finite words with language closed under the group G. We introduce related notions and definitions focusing on G-richness and its related notion of G-palindromic defect. We discuss and consider several algorithms and data structures for the implementation of a non-naive algorithm for G-defect computation. We implement and test our the proposed solution. Tests confirm the correctness of our solution. We believe that our implemented algorithm will become a part of the SageMath in the near future.

Thesis on DSpace

doc. Ing. Štěpán Starosta, Ph.D.

Ing. Josef Gattermayer, Ph.D.

Department of Computer Systems

The subject of this thesis is an insight into blockchain technology as a reliable computing distributed platform. A short introduction to cryptography used in existing blockchains is provided, as well as architecture, principle and potential security problems. It describes the concept of smart contracts. The output of this thesis is the analysis and model of application of these new technologies in the institution of the Faculty of Information Technology during the election to the academic senate.

Thesis on DSpace

doc. Ing. Štěpán Starosta, Ph.D.

Mgr. Jakub Růžička

Department of Computer Systems

Survey part of this thesis is chiefly focused on the security of electronic voting systems and it also describes specific cases of use of these systems in practice. Constructive part of the thesis follows up on theoretical (research) part and it observes electronic voting system named Baletka, which is being developed in the Faculty of Information Technology CTU in Prague and it ought to serve as a realization of electronic voting for Scientific Council FIT CTU. Another part of this thesis is a security analysis of a crucial component of the system (web application implemented in Ruby on Rails framework). All the other subjects of investigation that did not lead to exploited vulnerabilities are also mentioned. In these investigations the principles and functionalities of attacks are elucidated. At the end, the vulnerabilities found are remedied.

Thesis on DSpace

doc. Ing. Štěpán Starosta, Ph.D.

Ing. Marek Skotnica

Department of Software Engineering

This bachelor thesis deals with analyzing processes in Science and Research at the Faculty of Information Technology in Prague. The introduction explains the basics of process analysis, describes approaches to information gathering, process modeling and summary of process optimization techniques. After obtaining sufficient information by examining the organization's documents and analytical interviews, standardized models of the processes under investigation are created. Process optimization is performed over these models, using heuristic methods, the output of which is theoretical optimization. The stage of implementation seeks concrete implementation options for theoretical solutions. As proof of the idea of these solutions, a proof of concept of two implementation options has been developed to automate a particular action that has been performed manually. Thanks to the created models, it is possible to link this work to other interested parties. The work is supplemented by materials for analyst interviews, notes of meetings and commented parts of heuristic methods.

Thesis on DSpace

doc. Ing. Štěpán Starosta, Ph.D.

prof. Dr. Ing. Petr Kroha, CSc.

Department of Software Engineering

A palindrome is a word which reads the same from the left and from the right. Palindromic defect of word $w$ is the difference between $|w| + 1$ and the amount of pairwise distinct palindromic substrings of $w$. Concepts of palindrome and palindromic defect can be generalized to generalized palindrome, $\Theta$-defect and $G$-defect, where $\Theta$ is an antimorphism, $G$ is a finite group consisting of morphisms and antimorphisms (see \cite{palindromes}). The free open-source mathematics software system SageMath \cite{github_sage} contains a developed library containing numerous algorithms dealing with words. The first goal of the thesis is to present and prove several newly discovered algorithms for computing palindromic defect and its generalizations. As a special case of one of these algorithms, linear time algorithm for computing classical palindromic defect will be shown. The second goal of the thesis is to start adding some of these algorithms into SageMath.

Thesis on DSpace

doc. Ing. Štěpán Starosta, Ph.D.

Ing. Karel Klouda, Ph.D.

Department of Theoretical Computer Science

This thesis deals with non-pushy and circular D0L-systems. We present a summary of the known results on D0L-systems, especially concerning the method to describe all bispecial factors in a fixed point of a morphism. Based on analysis of this methods we design and implement its algorithm in computer algebra system SAGE.

Thesis on DSpace

doc. Ing. Štěpán Starosta, Ph.D.

Ing. Karel Klouda, Ph.D.

Department of Software Engineering

This thesis focuses on creating a mobile application of MARAST which is a tool for learning math on Faculty of Information Technology of the Czech Technical University in Prague. Thesis includes analysis of MARAST's web version and specification of suggested changes needed for enabling data sharing with mobile application. Outcomes of this thesis are a design and implementation of application interface for sharing data and developed functional mobile application MARAST for iOS system.

Thesis on DSpace

doc. Ing. Štěpán Starosta, Ph.D.

Mgr. Jan Starý, Ph.D.

Department of Software Engineering

This work describes present cryptocurrency market. Then it defines attributes of cryptocurrency exchanges relevant to perform triangular arbitrage. On the basis of these attributes selected cryptocurrency exchanges are analysed. The core requirements important for the application are specified. The work also discusses the already existing applications. After that the new application is designed and implemented. The implementation includes downloading data from 3rd party APIs, processing them and displaying potential triangular arbitrage execution opportunities in real-time. Moreover, it allows a user to compare individual cryptocurrency exchanges considering the historical opportunities of triangular arbitrage execution.

Thesis on DSpace

doc. Ing. Štěpán Starosta, Ph.D.

Ing. Josef Vogel, CSc.

Department of Software Engineering

This thesis describes the process of analysis and implementation of the Homework Management system in Jupyter. The main goal of this system is to allow teachers to prepare, distribute and collect homework assignments, which are prepared as Jupyter notebooks. Result of this work is a working prototype of the system that fulfills the requirements. All the steps of analysis, implementation, configuration, and deployment are thoroughly described.

Thesis on DSpace

doc. Ing. Štěpán Starosta, Ph.D.

doc. Ing. Tomáš Vitvar, Ph.D.

Department of Software Engineering

This thesis describes the development of an application that works on the seminar bingo principle. The theoretical part is devoted to the application requirements and the comparison of possible technologies for the implementation of a web application. The practical part deals with software development, including its testing. The result of the implementation enhances seminars and in addition helps with maintaining much needed focus among the participants.

Thesis on DSpace

doc. Ing. Štěpán Starosta, Ph.D.

doc. Ing. Ivan Šimeček, Ph.D.

Department of Software Engineering

This diploma thesis focuses on the selection of appropriate technologies for the creation of interactive graphical visualizations of calculation output and on implementation of model examples designated to support the teaching of mathematical subjects with the use of proposed solution. First part of the thesis is dedicated to the analysis of available rendering systems. Subsequently, a list of model examples suitable for interactive demonstrations during a lecture is assembled. Afterwards the thesis focuses on the selection of a suitable rendering system, on the design and the implementation of a web application containing individual model examples, on the testing of this application and on its trial deployment. The output of this thesis is a finished web application implemented with the use of the Plotly library, which includes defined model examples such as function approximation with the help of Taylor polynomial or visualization of the method of Lagrange multipliers. The application supports easy creation of new visualizations and their integration with the MARAST teaching support system.

Thesis on DSpace

doc. Ing. Štěpán Starosta, Ph.D.

doc. Ing. Jan Janoušek, Ph.D.

Department of Theoretical Computer Science

In this thesis, several algorithms for problems from the mathematical field combinatorics on words are thoroughly explained. The algorithms are also implemented in the free and open-source mathematics software system SageMath with the goal of their eventual integration into the same system. The algorithms include: classifying mortal and bounded letters of a morphism, deciding whether a morphism is injective, finding a simplification of a morphism, finding all infinite repetitions in a D0L system, and finding all factors (up to a certain length) of words of the language of a PD0L system. Furthermore, the problem of deciding whether a morphism of a D0L system is injective on the set of factors of words of the language of the system is discussed. The decidability of this problem is an open question, which is not answered in this thesis, but it is shown why it is nontrivial and where some approaches to solving this problem fail.

Thesis on DSpace

doc. Ing. Štěpán Starosta, Ph.D.

Ing. Jiří Novák, Ph.D.

Department of Software Engineering

In this thesis I am creating a web application for the Department of Zoology and Fisheries at the Faculty of Agrobiology, Food and Natural Resources of the Czech University of Life Sciences in Prague. The application will be used to create and manage online surveys, which will consist of images and questionnaires. Within this work I analyze the requirements for the application and then design, implement and document it according to these requirements. Finally, I will test the implemented application with real users. Multiple ways for users to subjectively rate images will be supported, and the questionnaire will also support different types of questions. The data obtained from the user ratings will then be statistically analysed by the application module, with a particular focus on investigating the correlation between the answers to the questionnaire questions and the subjective ratings of the images.

Thesis on DSpace